8.5 Constrained Optimization

We consider the following problem:

where the feasible set is:

with $\mathcal{E}$ is the set of equality constraints and $\mathcal{I}$ the set of inequality constraints.

8.5.1 Lagrange Multipliers

Let’s have a single constrained $h(\theta)=0$.

We know that the gradient of the loss and the gradient of the constraint are (anti-?)parallel at some point $\theta^*$ minimizing $\mathcal{L}(\theta)$.

• proof

  If we move by $\epsilon$ on the constraint surface we have:

  $$h(\theta+\epsilon) \approx h(\theta)+\epsilon^\top \nabla h(\theta)$$

  As we have $h(\theta+\epsilon)=h(\theta)=0$, we must have $\epsilon \perp \nabla h(\theta)$.

  We seek a point $\theta^*$ on the constrained surface minimizing $\mathcal{L}(\theta)$. $\nabla \mathcal{L}(\theta)$ must also be orthogonal to the constraint surface, otherwise we could decrease the objective by just moving on the surface.

  ---

for some $\lambda\in \mathbb{R}$.

This leads to the objective:

At a stationary point, we have:

This is called a critical point.

If we have $m>1$ constraints, we can add them:

We end up with $D+m$ equations for $D+m$ variables and can use unconstrained optimization methods to solve this system.

Exemple

We minimize $\mathcal{L}(\theta_1,\theta_2)=\theta_1^2+\theta_2^2$, subject to the constraint $\theta_1+\theta_2=1$.

The Lagrangian is:

Therefore we need to solve:

8.5.2 The KKT conditions

We introduce inequality constraints $g(\theta)\leq0$:

However, this is a discontinuous function that is hard to optimize.

Instead, we can consider $\mu\geq0:$

and our optimization problem becomes:

The general Lagrangian becomes:

When $\mathcal{L}$ and $g$ are convex, then all critical points must satisfy the Karush-Kuhn-Tucker (KKT) conditions:

• All constraints are satisfied (feasibility)

  $$g(\theta)\leq 0,h(\theta)=0$$

• The solution is a stationary point:

  $$\nabla \mathcal{L}(\theta^*)+\sum_{i=1}^m \lambda_i \nabla h_i(\theta) + \sum_{j=1}^n \mu_j \nabla g_j(\theta)=0$$

• The penalty for the inequality constraints points in the right direction (dual feasibility):

  $$\mu \geq 0$$

• The Lagrange multiplies pick up any slack in the inequality constraints:

If the $\mathcal{L}$ is convex and the constraints define a convex set, then the KKT conditions are sufficient to ensure global optimality.

8.5.3 Linear Programming

We optimize a linear function subject to linear constraints, represented as:

The feasible set defines a convex polytope: a convex space defined as an intersection of half-spaces.

8.5.3.1 The simplex algorithm

It can be shown that the optima of an LP occur at the vertex of the polytope defining the feasible set.

The simplex algorithm solves LPs by moving from vertex to vertex, seeking the edge that most improve the objective.

8.5.3.2 Applications

Applications range from business to machine learning, in robust linear regression settings. It is also useful for state estimation in graphical models.

8.5.4 Quadratic programming

We optimize a quadratic function:

If $H$ is semi-positive, then this is a convex problem.

Example

Let’s consider:

with $H=2I$ and $c=-(3,1/4)$

Subject to $|\theta_1|+|\theta_2|\leq 1$

We can decompose the above constraint into:

We can write as $A\theta -b \leq 0$, with

This is now in the standard QP form.

We see that the 2 edges of the diamond to the left are inactive because the objective is in the opposite directions.

This means $g_3>0$ and $g_4>0$ and by complementarity $\mu_3^*=\mu_4^*=0$

From the KKT conditions, we know that:

This gives us:

The solution is $\theta=(1, 0)^\top, \mu=(0.625, 0.375,0,0)^\top$

8.5.4.1 Applications

QP programming is used in the lasso method for sparse linear regression, which optimizes:

It can also be used for SVM.