Goal: Make use of the Lagrangian and other methods to accomodate constraints.

Formalism

In matrix form, this translates to:

Notes:

• $A, b, C, d$ are provided as inputs of fmincon and include the lower/upper bounds.
• Non-linear constraints need a special Matlab function returning $g$ and $h$.

Existence of a minimizer: Feasible set $\mathcal{D}$ is non-empty and bounded and $f, g_{i}, h_{i}$ differentiable $\Rightarrow \exists$ a minimizer

Lagrangian

Equality constraints: existence and optimality

Definition (Lagrangian function): $\mathcal{L}(x, \lambda) = f(x) - \sum_{j=1}^{q} \lambda_{j}h_{j}$

where $\lambda$ are the Lagrange multipliers

First order optimality conditions: $x_{⋆}$ is a local minimizer of $f \Rightarrow \exists \lambda_{⋆}$ such that: $\begin{cases} \nabla_{x} \mathcal{L}(x^{*}, \lambda^{*}) = 0_{n} \\ \nabla_{\lambda} \mathcal{L}(x^{*}, \lambda^{*}) = 0_{q}\\ \end{cases}$

Inequality constraints

Definition (active / inactive):

• The $i$-th constraint is active at $x$ if
• The $i$-th constraint is inactive at $x$ if $g_{i}(x) < 0$.

Lagrange multipliers constraints:

• $g(x) \leq 0 \Rightarrow \lambda \in \mathbb{R}_{-}^{p}$
• $g(x) \geq 0 \Rightarrow \lambda \in \mathbb{R}_{+}^{p}$

Karush-Kuhn-Tucker (KKT) conditions:

If $x^{⋆}$ is a local solution of $min_{x} f(x)$ s.t. $g(x)\geq 0_{p}$ then there exists $\lambda^{*}$ s.t.

Inequality constraints:

Necessary condition for a local minimizer

First order optimality condition: $x^{}$ is local minimizer $\Rightarrow x^{}$ satisfies the KKT conditions.

Second order optimality condition.

• Let $A(x)$ denote the set of active constraints at $x$
• Let $F(x)$ denote the set of feasible directions at $x$.

• Let $C(x,\lambda)={w\in F(x)

  [\nabla g_{i}(x)]^{T}w=0 \forall i\in A(x) \text{ with } \lambda_{i} >0.}$

If $x^{*}$ satisfies the KKT conditions and

then $x^{*}$ is a strict local minimizer of the inequality constrained problem.

General case: inequality and equality constraints

Definition (Lagrangian function):

with $\lambda \leq 0_{p}$.

KKT conditions: If $x^{⋆}$ is a local minimizer, then there exists $λ^{⋆}$ and $μ^{⋆}$ such that:

Other approaches

Gradient projection algorithm

Principle:

1. Line minimization: $x_{k+1} =x_{k} +\alpha_{k}d_{k}$
2. Projection onto convex set: $x_{k+1} = proj(x_{k+1}, \mathcal{D})$

Interior and exterior point approaches

Method (Interior point approaches): Constrained minimization is replaced by the unconstrainted minimization of the augmented criterion.

Examples: Ridge regression and LASSO are both expressible under this form. $Replace min_{x\geq 0}f(x) by min_{x\geq 0}(f(x-\zeta)\sum_{i=1}^{n}log(x_{i}))$

Method (“Exterior” approaches): Repeat:

• Minimize $K$ with respect to $x$ (unconstrained).
• Minimize $K$ with respect to $p$ (easy): $pi = max(x_{i} , 0)$.

Examples: Quadratic penalty and ADMM: $Replace min_{x\geq 0}f(x) by min_{x, p\geq 0} (\mathcal{K}(x,p;\zeta ) = f(x) +\zeta\mid\mid x-p \mid\mid^{2})\text{ with }\zeta \rightarrow \infty$

Special case: linear programming

Property (Orthogonal projection): The solution $x^{⋆}$ has at least $(n − m)$ zero coordinates.

Principle of the simplex algorithm

1. Decompose $A=[A_{B},A_{N}]$ with $A_{B}$ of size $m\times m$, and $A_{N}$ of size $m × (n − m) $.
2. Set $x^{B} = \begin{pmatrix} x_{B} \ 0{n-m} \end{pmatrix} \text{ with } x{B} = A_{B}^{-1}b$
3. $x_{B}$ is a feasible point if $x_{B} ≥ 0{m}$. The objective function is equal to $f(x{B}) = c_{B}^{T} A_{B}^{−1}b$
4. The simplex algorithm searches for the best decomposition $A = [A_{B}, A_{N}]$. The subset $B$ is updated at each iteration in such a way that $f(x_{B})$ is decreasing.

Special case: quadratic programming (QP)

QP with equality constraints

Interior point approach:

1. Assumption: $rank(A) = m$. Let $A = [A_{1}, A_{2}] \in \mathbb{R}^{m\times m}$ invertible and let $x = [x_{1}, x_{2}]$.
2. Incorporate the constraint: $x_{1} = A_{1}^{-1}(b-A_{2}x_{2})$
3. Solve the unconstrained problem $min_{x_{2}}\mathcal{Q}(A^{-1}(b-A_{2}x_{2}), x_{2})$

KKT conditions:

The Lagrangian function is:

Solve the system:

QP with inequality constraints

Principle of the active-set algorithm

1. Solve a sequence of QP problems with equality constraints.
2. Use a mechanism to add or remove active constraints.

Definition (Active set): $A(x) = {i : a_{i}^{T} x = b_{i}$ is defined as the set of active constraints at x.

Method: From a feasible point x_{k}:

1. Solve QP with equality constraints on $\mathcal{A}(x_{k})$ only. It yields $\tilde{x}_{k+1}$
2. If $\tilde{x}_{k+1}$ feasible:
   1. $x_{k+1} = \tilde{x}_{k+1}$
   2. Compute the Lagrange multipliers

Sequential Quadratic Programming (SQP)