Lagrangian Formulations

Once equipped with a ConstrainedMinimizationProblem, several algorithmic approaches can be adopted for finding an approximation to the solution of the constrained problem.

Recall that we consider constrained minimization problems (CMPs) expressed as:

\[\begin{split}\min_{x \in \Omega} & \,\, f(x) \\ \text{s.t. } & \,\, g(x) \le \mathbf{0} \\ & \,\, h(x) = \mathbf{0}\end{split}\]

Lagrangian Formulation

The Lagrangian problem associated with the CMP above is given by:

\[\min_{x \in \Omega} \max_{\lambda_g \ge 0, \, \lambda_h} \mathcal{L}(x,\lambda) \triangleq f(x) + \lambda_g^{\top} g(x) + \lambda_h^{\top} h(x)\]

The vectors \(\lambda_g\) and \(\lambda_h\) are called the Lagrange multipliers or dual variables associated with the CMP. Observe that \(\mathcal{L}(x,\lambda)\) is a concave function of \(\lambda\) regardless of the convexity properties of \(f, g\) and \(h\).

A pair \((x^*,\lambda^*)\) is called a saddle-point of \(\mathcal{L}(x,\lambda)\) if for all \((x,\lambda)\),

\[\mathcal{L}(x^*,\lambda) \le \mathcal{L}(x^*,\lambda^*) \le \mathcal{L}(x,\lambda^*).\]

This approach can be interpreted as a zero-sum two-player game, where the “primal” player \(x\) aims to minimize \(\mathcal{L}(x,\lambda)\) and the goal of the “dual” player \(\lambda\) is to maximize \(-\mathcal{L}(x,\lambda)\) (or equiv. minimize \(-\mathcal{L}(x,\lambda)\)).

Note that the notion of a saddle-point of the Lagrangian is in fact equivalent to that of a (pure) Nash equilibrium of the zero-sum game. If \((x^*,\lambda^*)\) is a saddle-point of \(\mathcal{L}(x,\lambda)\), then, by definition, neither of the two players can improve their payoffs by unilaterally deviating from \((x^*,\lambda^*)\).

In the context of a convex CMP (convex objectives, constraints and \(\Omega\)), given certain technical conditions (e.g. Slater’s condition (see:math:S 5.2.3 in [Boyd and Vandenberghe, 2004]), or compactness of the domains), the existence of a pure Nash equilibrium is guaranteed [von Neumann, 1928].

Warning

A constrained non-convex problem might have an optimal feasible solution, and yet its Lagrangian might not have a pure Nash equilibrium. See example in Fig 1. of Cotter et al. [2019].

class cooper.lagrangian_formulation.LagrangianFormulation(cmp, ineq_init=None, eq_init=None, aug_lag_coefficient=0.0)

Provides utilities for computing the Lagrangian associated with a ConstrainedMinimizationProblem and for populating the gradients for the primal and dual parameters.

Parameters

• cmp (ConstrainedMinimizationProblem) – ConstrainedMinimizationProblem we aim to solve and which gives rise to the Lagrangian.

• ineq_init (Optional[Tensor]) – Initialization values for the inequality multipliers.

• eq_init (Optional[Tensor]) – Initialization values for the equality multipliers.

• aug_lag_coefficient (float) – Coefficient used for the augmented Lagrangian.

composite_objective(closure, *closure_args, write_state=True, **closure_kwargs)

Computes the Lagrangian based on a new evaluation of the CMPState`.

If no explicit proxy-constraints are provided, we use the given inequality/equality constraints to compute the Lagrangian and to populate the primal and dual gradients.

In case proxy constraints are provided in the CMPState, the non-proxy constraints (potentially non-differentiable) are used for computing the Lagrangian, while the proxy-constraints are used in the backward computation triggered by _populate_gradient() (and thus must be differentiable).

Parameters

• closure – Callable returning a cooper.problem.CMPState

• write_state – If True, the state of the formulation’s cooper.problem.ConstrainedMinimizationProblem attribute is replaced by that returned by the closure argument. This flag can be used (when set to False) to evaluate the Lagrangian, e.g. for logging validation metrics, without overwritting the information stored in the formulation’s cooper.problem.ConstrainedMinimizationProblem.

Proxy-Lagrangian Formulation

class cooper.lagrangian_formulation.ProxyLagrangianFormulation(cmp, ineq_init=None, eq_init=None, aug_lag_coefficient=0.0)

Placeholder class for the proxy-Lagrangian formulation proposed by Cotter et al. [2019].

Todo

Implement Proxy-Lagrangian formulation as described in Cotter et al. [2019]

Base Lagrangian Formulation

class cooper.lagrangian_formulation.BaseLagrangianFormulation(cmp, ineq_init=None, eq_init=None, aug_lag_coefficient=0.0)

Base class for Lagrangian Formulations.

cmp

ConstrainedMinimizationProblem we aim to solve and which gives rise to the Lagrangian.

ineq_multipliers

Trainable cooper.multipliers.DenseMultipliers associated with the inequality constraints.

eq_multipliers

Trainable cooper.multipliers.DenseMultipliers associated with the equality constraints.

create_state(cmp_state)

Initialize dual variables and optimizers given list of equality and inequality defects. cooper.multipliers.DenseMultiplier

Parameters

• eq_defect – Defects for equality constraints

• ineq_defect – Defects for inequality constraints.

property dual_parameters: List[Tensor]

Returns a list gathering all dual parameters

Return type

List[Tensor]

property is_state_created

Returns True if any Lagrange multipliers have been initialized.

state()

Collects all dual variables and returns a tuple containing their torch.Tensor values. Note that the values are a different type from the cooper.multipliers.DenseMultiplier objects.

Return type

Tuple[Optional[Tensor]]

weighted_violation(cmp_state, constraint_type)

Computes the dot product between the current multipliers and the constraint violations of type constraint_type. If proxy-constraints are provided in the CMPState, the non-proxy (usually non-differentiable) constraints are used for computing the dot product, while the “proxy-constraint” dot products are stored under self.state_update.

Parameters

• cmp_state (CMPState) – current CMPState

• constraint_type (str) – type of constrained to be used

Return type

Tensor