8  Summary of KKT with proofs

Author

Affiliation

Enrico Bertolazzi

University of Trento, Department of Industrial Engineering

The Lagrange-multiplier theorem can be extended to inequality constraints. Consider the nonlinear programming (NLP) problem

\begin{aligned} \textrm{minimize:} \quad & f(\bm{x}) \\[0.5em] \textrm{subject to:}\quad & h_i(\bm{x})=0 \quad &i&=1,2,\ldots,m \\[0.5em] & g_i(\bm{x})\geq 0\quad &i&=1,2,\ldots,p \end{aligned} \tag{8.1}

introducing the slack variables e_i for i=1,2,\ldots,p and the vector \bm{y}^T=(\bm{x}^T,\bm{e}^T) the new problem

\begin{aligned} \textrm{minimize:}\quad && \mathsf{f}(\bm{y}) &=f(\bm{x}) \\[0.5em] \textrm{subject to:}\quad && \mathsf{h}_i(\bm{y}) &= h_i(\bm{x})=0\quad &i&=1,2,\ldots,m \\[0.5em] && \mathsf{h}_{i+m}(\bm{y}) &= g_i(\bm{x})-e_i^2 = 0\quad &i&=1,2,\ldots,p \end{aligned} \tag{8.2}

Using this formulation we deduce:

Lemma 8.1 (First-order KKT conditions) Defining the Lagrangian: \mathcal{L}(\bm{x},\bm{\lambda},\bm{\mu}) = f(\bm{x}) -\sum_{k=1}^m \lambda_k h_k(\bm{x}) -\sum_{\ell=1}^p \mu_\ell g_\ell(\bm{x}) \tag{8.3}

Assume that f, h_i, and g_i are continuously differentiable and that a constraint qualification, such as LICQ, holds at the local minimizer \bm{x}^\star. The first-order KKT conditions for Equation 8.1 are:

\begin{aligned} \nabla_x\mathcal{L}(\bm{x}^\star,\bm{\lambda},\bm{\mu}) &=\bm{0}^T, \\[1em] h_k(\bm{x}^\star) &= 0, \qquad & k & =1,2,\ldots m\\[1em] \mu_\ell g_\ell(\bm{x}^\star) & = 0,\quad g_\ell(\bm{x}^\star)\geq 0\quad & \ell&=1,2,\ldots p,\\[1em] \mu_\ell &\geq 0, \qquad &\ell&=1,2,\ldots,p. \end{aligned}

The last two lines are, respectively, complementary slackness and dual feasibility. Thus g_\ell(\bm{x}^\star)>0 implies \mu_\ell=0. LICQ means that the gradients of the equality constraints and active inequality constraints are linearly independent.

NoteProof.

with the extended Lagrangian function:

\mathcal{L}^e(\bm{x},\bm{e},\bm{\lambda},\bm{\mu}) = f(\bm{x}) -\sum_{k=1}^m \lambda_k h_k(\bm{x}) -\sum_{\ell=1}^p \mu_\ell \left(g_\ell(\bm{x})-e_\ell^2\right) \tag{8.4}

The first order condition becomes

\begin{aligned} \nabla_x\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) &= \nabla f(\bm{x}^\star) -\sum_{k=1}^m \lambda_k\nabla h_k(\bm{x}^\star) -\sum_{k=1}^p \mu_k\nabla g_k(\bm{x}^\star)=\bm{0}^T, \\[1em] \nabla_e\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) &= 2(\mu_1 e_1,\ldots,\mu_p e_p)=\bm{0}^T, \\[1em] \nabla_{\lambda_k}\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) & = h_k(\bm{x}^\star)= 0, \\[1em] \nabla_{\mu_\ell}\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) & = g_\ell(\bm{x}^\star) = e_\ell^2 \geq 0, \end{aligned}

Notice that \mu_\ell e_\ell = 0 is equivalent to \mu_\ell e_\ell^2 = 0 and thus \mu_\ell g_\ell(\bm{x}^\star) = 0. Moreover \nabla_x\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu})= \nabla_x\mathcal{L}(\bm{x}^\star,\bm{\lambda},\bm{\mu}). The sign condition \mu_\ell\geq0 does not follow from stationarity with respect to e_\ell alone; it follows from the second-order necessary condition in a pure slack direction for an active inequality. \square

second order condition become:

Lemma 8.2 (second order necessary condition) Using the Lagrangian Equation 8.3, the second order condition for problem Equation 8.2 become:

\begin{aligned} \bm{z}^T\nabla^2_x\mathcal{L}(\bm{x}^\star,\bm{\lambda},\bm{\mu})\bm{z} & \geq 0, \\[0.5em] \mu_\ell & \geq 0, \qquad \ell = 1,2,\ldots,p \end{aligned}

for all \bm{z} in the kernel of the gradient of the active constraints.

NoteProof.

Using Lagrangian Equation 8.4 with the slack functions the necessary condition become

\bm{z}^T \nabla^2_{(x,e)}\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu})\bm{z}\geq 0

for all \bm{z} in the kernel of matrix \begin{pmatrix} \nabla_x \bm{h}(\bm{x}^\star) & \bm{0} \\[0.5em] \nabla_x \bm{g}(\bm{x}^\star) & -2\,\textrm{diag}(e_1,\ldots,e_p) \end{pmatrix} \tag{8.5}

where

\nabla^2_{(x,e)}\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) = \begin{pmatrix} \nabla^2_x\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) & \bm{0} \\[0.5em] \bm{0} & \nabla^2_e\mathcal{L}(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) \end{pmatrix} \tag{8.6}

and \nabla_x\nabla_e^T\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu})=\bm{0}. Moreover

\begin{aligned} \nabla^2_x\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) &= \nabla^2 f(\bm{x}^\star) -\sum_{k=1}^m \lambda_k\nabla^2 h_k(\bm{x}^\star) -\sum_{\ell=1}^p \mu_\ell\nabla^2 g_\ell(\bm{x}^\star), %\\ %\nabla_x\nabla_e^T\mathcal{L}(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) &=& %\bm{0}, \\ \nabla^2_e\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) &= 2\,\textrm{diag}(\mu_1,\mu_2,\ldots,\mu_p). \end{aligned}

After reordering, we can separate the constraints as follows:

\bm{g}(\bm{x})=\begin{pmatrix} \bm{g}^{(A)}(\bm{x})\\ \bm{g}^{(I)}(\bm{x}) \end{pmatrix} \;\textrm{and}\; \left\{\begin{aligned} g_\ell(\bm{x}^\star)&=e_\ell^2=0,\; &\ell&=1,2,\ldots,r\\ g_\ell(\bm{x}^\star)&=e_\ell^2>0,\; &\ell&=r+1,r+2,\ldots,p \end{aligned}\right.

The group of constraints \bm{g}^{(A)}(\bm{x}^\star) that are zeros are the active constraints, the remaining \bm{g}^{(I)}(\bm{x}^\star) are the inactive ones. Thus, Equation 8.5 in more details becomes

\begin{pmatrix} \nabla \bm{h}(\bm{x}^\star) & \bm{0} & \bm{0} \\[0.5em] \nabla \bm{g}^{(A)}(\bm{x}^\star) & \bm{0} & \bm{0} \\[0.5em] \nabla \bm{g}^{(I)}(\bm{x}^\star) & \bm{0} & -\bm{E} \end{pmatrix}, \quad \bm{E}= 2\,\textrm{diag}(e_{k+1},\ldots,e_p). \tag{8.7}

and

\nabla^2_e\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) = \begin{pmatrix} \bm{M} & \bm{0} \\ \bm{0} & \bm{0} \end{pmatrix}, \quad \bm{M} = 2\,\textrm{diag}(\mu_1,\mu_2,\ldots,\mu_r) \tag{8.8}

The kernel of Equation 8.7 can be written as

\underline{\mathbf{K}} = \begin{pmatrix} \bm{K}^{a} & \bm{0} \\[0.5em] \bm{0} & \bm{I} \\[0.5em] \bm{E}^{-1}\nabla_x \bm{g}^{(I)}(\bm{x}^\star) \bm{K}^{a}& \bm{0} \end{pmatrix}, \tag{8.9}

where \bm{K}^{a} is the kernel of active constraints given by the matrix

\begin{pmatrix} \nabla \bm{h}(\bm{x}^\star) \\[0.5em] \nabla \bm{g}^{(A)}(\bm{x}^\star) \end{pmatrix} \quad\implies\quad \begin{pmatrix} \nabla \bm{h}(\bm{x}^\star) \\[0.5em] \nabla \bm{g}^{(A)}(\bm{x}^\star) \end{pmatrix} \bm{K}^{a}=\bm{0} \tag{8.10}

thus \bm{z} can be written as \bm{z}=\underline{\mathbf{K}}\bm{d} and thus second order condition \bm{z}^T \nabla^2_{(x,e)}\mathcal{L}(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu})\bm{z}\geq 0 become

0 \leq \bm{d}^T \left[\underline{\mathbf{K}}^T \nabla^2_{(x,e)}\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) \underline{\mathbf{K}}\right]\bm{d}, \qquad \bm{d}\in\Bbb{R}^s

and using Equation 8.9 with Equation 8.6 and Equation 8.8

\begin{aligned} &\left[\underline{\mathbf{K}}^T \nabla^2_{(x,e)}\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) \underline{\mathbf{K}}\right] \\ &\qquad= \underline{\mathbf{K}}^T \begin{pmatrix} \nabla^2_x\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) & \bm{0} & \bm{0} \\[0.5em] \bm{0} & \bm{M} & \bm{0} \\[0.5em] \bm{0} & \bm{0} & \bm{0} \end{pmatrix} \underline{\mathbf{K}}, \\[1em] &\qquad= \underline{\mathbf{K}}^T \begin{pmatrix} \nabla^2_x\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu})\bm{K}^{a} & \bm{0} \\[0.5em] \bm{0} & \bm{M} \\[0.5em] \bm{0} & \bm{0} \end{pmatrix}, \\[1em] &\qquad= \begin{pmatrix} \bm{K}^{a,T}\nabla^2_x\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu})\bm{K}^a & \bm{0} \\[0.5em] \bm{0} & \bm{M} \end{pmatrix} \end{aligned} \tag{8.11}

Using the equality \nabla^2_x\mathcal{L}^e(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu}) = \nabla^2_x\mathcal{L}(\bm{x}^\star,\bm{\lambda},\bm{\mu}) \tag{8.12}

the second order condition becomes: \nabla^2_x\mathcal{L}(\bm{x}^\star,\bm{\lambda},\bm{\mu}) must be positive semi-definite in the kernel of the gradient of the active constraints. The matrix \bm{M} must be semi-positive definite or equivalenty \mu_\ell\geq 0 for all the multipliers of the not-active constraints (remember that for the active constraints must be \mu_\ell=0). \square

Lemma 8.3 (second order sufficient condition) Using the Lagrangian Equation 8.3, the second order sufficient condition for problem Equation 8.2 become:

\begin{aligned} \bm{z}^T\nabla^2_x\mathcal{L}(\bm{x}^\star,\bm{\lambda},\bm{\mu})\bm{z} & \geq \epsilon \|\bm{z}\|^2, \\[0.5em] \mu_\ell & = 0, \qquad \textrm{for $g_\ell(\bm{x}^\star)>0$} \\[0.5em] \mu_\ell & > 0, \qquad \textrm{for $g_\ell(\bm{x}^\star)=0$} \end{aligned}

for all \bm{z} in the kernel of the gradient of the active constraints.

NoteProof.

Using Equation 8.11 with Equation 8.12 the sufficient condition become that the hessian satisfy

\bm{z}^T\nabla^2_x\mathcal{L}(\bm{x}^\star,\bm{\lambda},\bm{\mu})\bm{z} \geq \epsilon \|\bm{z}\|^2 % \bm{0} & \bm{M} % \end{pmatrix} %\end{aligned}

for all \bm{z} in the kernel of the gradients of active constraints.

And matrix \bm{M} must be positive definite, or \mu_\ell>0 for all inactive constraints. \square

The last two lemma can be resumed in:

NoteFirst and second order KKT condition

• First order condition: for the NLP Equation 8.1

  \begin{aligned} (a) & \qquad &\nabla_x\mathcal{L}(\bm{x},\bm{\lambda},\bm{\mu}) & = \bm{0} \\ (b) & \qquad &h_k(\bm{x}) &= 0 \\ (c) & \qquad &\mu_\ell g_\ell(\bm{x}) &=0 \\[1em] (d) & \qquad &g_\ell(\bm{x}) &\geq 0 \\ (e) & \qquad &\mu_\ell & \geq 0 \end{aligned}

• Second order condition:
  The matrix \bm{K} is the kernel of the gradient of the active constraints.

  • Necessary: the matrix \bm{K}^{a,T}\nabla^2_x\mathcal{L}(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu})\bm{K}^a, must be semi-positive defined.

  • Sufficient: the matrices \bm{K}^{a,T}\nabla^2_x\mathcal{L}(\bm{x}^\star,\bm{e},\bm{\lambda},\bm{\mu})\bm{K}^a, must be positive defined and \mu_\ell>0 for the active constraints, i.e., when g_\ell(\bm{x}^\star)=0.

8.1 Constrained minima, NLP problem

Consider the constrained minimization problem

\begin{aligned} \textrm{minimize:}\quad && f(\bm{x})& \\[0.5em] \textrm{subject to:}\quad && h_i(\bm{x}) &=0\quad &i&=1,2,\ldots,m \\[0.5em] && g_\ell(\bm{x}) &\geq 0\quad &\ell&=1,2,\ldots,p \end{aligned} \tag{8.13}

NoteSolution Algorithm

1. Compute the Lagrangian Function: The Lagrangian function is defined as: \mathcal{L}(\bm{x}, \bm{\lambda}, \bm{\mu}) = f(\bm{x}) - \sum_{k=1}^m \lambda_k h_k(\bm{x}) - \sum_{\ell=1}^p \mu_\ell g_\ell(\bm{x}).

2. Solve the Nonlinear System: We need to solve the following system of equations: \begin{aligned} \nabla_x \mathcal{L}(\bm{x}, \bm{\lambda}, \bm{\mu}) &= \bm{0}, \\[0.5em] h_k(\bm{x}) &= 0, \quad & k&=1,2,\ldots,m, \\[0.5em] \mu_\ell g_\ell(\bm{x}) &= 0, \quad & \ell&=1,2,\ldots,p. \end{aligned} Ensure to keep only the solutions where \mu_k^\star \geq 0 and g_k(\bm{x}^\star) \geq 0.

3. Check Active Constraints: For each solution point (\bm{x}^\star, \bm{\lambda}^\star, \bm{\mu}^\star):

   • Compute \nabla \bm{h}(\bm{x}^\star) and \nabla g_\ell(\bm{x}^\star) for the active constraints (g_\ell(\bm{x}^\star) = 0).
   • Verify that these gradients are linearly independent.

4. Compute the Kernel Matrix: Construct the matrix \bm{K}^a representing the kernel of \nabla \bm{h}(\bm{x}^\star) along with the gradients \nabla g_k(\bm{x}^\star) for the active constraints where \mu_k > 0.

5. Compute the Reduced Hessian: The reduced Hessian is calculated as: \bm{H} = \bm{K}^{a,T}\nabla_x^2\mathcal{L}(\bm{x}^\star, \bm{\lambda}^\star)\bm{K}^a

6. Evaluate Conditions:

   • Necessary Condition: Ensure that \bm{H} is semi-positive definite.
   • Sufficient Condition: Confirm that \bm{H} is positive definite and that \mu_\ell > 0 for all active constraints.

Definition 8.1 (ammissibile point) A point \bm{x}^\star is admissible if

\begin{aligned} h_k(\bm{x}^\star) &= 0 \qquad & k&=1,2, \ldots ,m\\ g_\ell(\bm{x}^\star) &\geq 0 \qquad & \ell&=1,2, \ldots ,p\\ \end{aligned}

Definition 8.2 (Feasible region) \begin{aligned} \mathcal{F} = \Big\{ \bm{x}\in\Bbb{R}^n\;|\; & h_k(\bm{x})=0,\quad & k&=1,2,\ldots,m,\\ & g_\ell(\bm{x}) \geq 0,\quad & \ell&=1,2,\ldots,p, \Big\} \end{aligned}

is called the feasible region or set of feasible points.

Definition 8.3 (active constraints) The following set

\mathcal{A}(\bm{x}^\star) = \{ k\;|\; g_k(\bm{x}^\star)=0\}

is named active constraints set. This set can be split in two subsets

\begin{aligned} \mathcal{A}^+(\bm{x}^\star,\bm{\mu }^*) &= \{ k\;|\; g_k(\bm{x}^\star)=0,\quad \mu ^*_k>0\} \\ \mathcal{A}^0(\bm{x}^\star,\bm{\mu }^*) &= \{ k\;|\; g_k(\bm{x}^\star)=0,\quad \mu ^*_k=0\} \end{aligned}

\mathcal{A}^+(\bm{x}^\star,\bm{\mu }^*) are the strongly active constraints and \mathcal{A}^0(\bm{x}^\star,\bm{\mu }^*) are the weakly active constraints.

Obviously

\mathcal{A}^0(\bm{x}^\star,\bm{\mu }^*)\bigcap \mathcal{A}^+(\bm{x}^\star,\bm{\mu }^*)=\emptyset \quad\textrm{and}\quad \mathcal{A}^0(\bm{x}^\star,\bm{\mu }^*)\bigcup \mathcal{A}^+(\bm{x}^\star,\bm{\mu }^*)=\mathcal{A}(\bm{x}^\star)

8.2 Constrained minima and KKT

Here, we present classical theorems of constrained minimization, including those by Karush, Kuhn, Tucker, and others, without providing detailed proofs.

The following theorem (see [1]) establishes the necessary conditions for constrained minima. Note that no specific conditions on the constraints are required.

Theorem 8.1 (Fritz John) If the functions f(\bm{x}), g_1(\bm{x}), \ldots, g_p(\bm{x}), are differentiable, then a necessary condition that \bm{x}^\star be a local minimum to problem:

\begin{aligned} \textrm{minimize:}\qquad & f(\bm{x}) \\[0.5em] \textrm{subject to:}\qquad & g_i(\bm{x})\geq 0\qquad &i=1,2,\ldots,p \end{aligned}

is that there exist scalars \mu_0^\star, \mu_1^\star, \ldots, \mu_p^\star, (not all zero) such that the following inequalities and equalities are satisfied:

\begin{aligned} \nabla_x \mathcal{L}(\bm{x}^\star,\bm{\mu}^*) &=\bm{0}^T & \\ \mu_k^*g_k(\bm{x}^\star) &= 0,\qquad & k&=1,2,\ldots,p; \\ \mu_k^* &\geq 0,\qquad & k&=0,1,2,\ldots,p; \end{aligned}

where

\mathcal{L}(\bm{x},\bm{\mu}) = \mu_0 f(\bm{x}) -\sum_{k=1}^p \mu_k\,g_k(\bm{x})

In [2] the authors showed that if a condition, called the first order constraint qualification, holds at \bm{x}^\star, \bm{\lambda}^\star then \lambda_0 can be taken equal to 1.

Definition 8.4 (Constraints qualification LI) Let be the unilateral and bilateral constraints \bm{g}(\bm{x}) and \bm{h}(\bm{x}), the point \bm{x}^\star is admissible if

g_k(\bm{x}^\star) \geq 0, \qquad h_k(\bm{x}^\star) = 0.

The constraints \bm{g}(\bm{x}) and \bm{h}(\bm{x}) are qualified at \bm{x}^\star if the point \bm{x}^\star is admissible and the vectors

\{\nabla g_k(\bm{x}^\star)\;:\;k\in \mathcal{A}(\bm{x}^\star)\}\; \bigcup\; \{ \nabla h_1(\bm{x}^\star),\nabla h_2(\bm{x}^\star),\ldots,\nabla h_m(\bm{x}^\star)\}

are linearly independent.

The next theorems are taken from [4] and [3].

Theorem 8.2 (First order necessary conditions) Let f\in C^1(\Bbb{R}^n) and the constraints \bm{g}\in C^1(\Bbb{R}^n,\Bbb{R}^p) and \bm{h}\in C^1(\Bbb{R}^n,\Bbb{R}^m). Suppose that \bm{x}^\star is a local minima of Equation 8.13 and that the constraints qualification LI holds at \bm{x}^\star. Then there are Lagrange multiplier vectors \bm{\lambda} and \bm{\mu} such that the following conditions are satisfied at (\bm{x}^\star,\bm{\lambda},\bm{\mu}):

\begin{aligned} \nabla_x \mathcal{L}(\bm{x}^\star,\bm{\lambda},\bm{\mu}) & =\bm{0}^T & \\[0.5em] h_k(\bm{x}^\star) &=0,\qquad & k&=1,2,\ldots,m; \\[0.5em] \mu_\ell^*g_k(\bm{x}^\star) &= 0,\qquad & \ell&=1,2,\ldots,p; \\[0.5em] \mu_\ell^*&\geq 0,\qquad & \ell&=1,2,\ldots,p; \end{aligned}

where

\mathcal{L}(\bm{x},\bm{\lambda},\bm{\mu}) = f(\bm{x}) -\sum_{k=1}^m \lambda_k\,h_k(\bm{x}) -\sum_{\ell=1}^p \mu_\ell\,g_\ell(\bm{x})

Theorem 8.3 (Second order necessary conditions) Let f\in C^2(\Bbb{R}^n) and the constraints \bm{g}\in C^2(\Bbb{R}^n,\Bbb{R}^p) and \bm{h}\in C^2(\Bbb{R}^n,\Bbb{R}^m).

Let \bm{x}^\star satisfying the first order necessary conditions, a necessary condition for \bm{x}^\star be a local minima is that the m+p scalars (Lagrange Multiplier) of the first order necessary condition satisfy:

\bm{d}^T \nabla_x^2 \mathcal{L}(\bm{x}^\star,\bm{\lambda}^*,\bm{\mu}^*) \bm{d} \color{blue}\geq 0

for all \bm{d} such that:

\nabla h_k(\bm{x}^\star)\bm{d} =0, \qquad \textrm{for}\quad k=1,2,\ldots,m

and for all active inequalities \ell\in \mathcal{A}(\bm{x}^\star):

Noteeasy condition

\color{blue}\nabla g_\ell(\bm{x}^\star)\bm{d} \color{blue}=0

Notemore accurate condition

\begin{aligned} \color{DarkGreen}\nabla g_\ell(\bm{x}^\star)\bm{d}&=0 \quad\textrm{and}\quad\mu_\ell>0\\[1em] \color{DarkGreen}\nabla g_\ell(\bm{x}^\star)\bm{d}& \geq 0 \quad\textrm{and}\quad\mu_\ell=0 \end{aligned}

Remark 8.1. The conditions

\begin{aligned} \color{DarkGreen} \nabla g_\ell(\bm{x}^\star)\bm{d}=0, \qquad & \color{DarkGreen} \textrm{if $\ell\in \mathcal{A}(\bm{x}^\star)$ and $\mu_\ell>0$} \\[1em] \color{DarkGreen} \nabla g_\ell(\bm{x}^\star)\bm{d}\geq 0, \qquad & \color{DarkGreen} \textrm{if $\ell\in \mathcal{A}(\bm{x}^\star)$ and $\mu_\ell=0$} \end{aligned}

restrict the space of direction to be considered. If changed with

{\color{blue}\nabla g_\ell(\bm{x}^\star)\bm{d}=0,}\qquad {\color{blue}\textrm{if $\ell\in \mathcal{A}(\bm{x}^\star)$}}

Theorem 8.3 is still valid cause necessary condition is tested in a smaller set.

Theorem 8.4 (Second order sufficient conditions) Let f\in C^2(\Bbb{R}^n) and the constraints \bm{g}\in C^2(\Bbb{R}^n,\Bbb{R}^p) and \bm{h}\in C^2(\Bbb{R}^n,\Bbb{R}^m).

Let \bm{x}^\star satisfying the First order necessary conditions, a sufficient condition for \bm{x}^\star be a local minima is that the m+p scalars (Lagrange Multiplier) of the first order necessary condition satisfy:

\bm{d}^T \nabla_x^2 \mathcal{L}(\bm{x}^\star,\bm{\lambda}^*,\bm{\mu}^*) \bm{d}\color{blue}\;\;>\;\; 0

for all \bm{d}\neq\bm{0} such that

\nabla h_k(\bm{x}^\star)\bm{d} =0, \qquad \textrm{for}\quad k=1,2,\ldots,m

and for all active inequalities \ell\in \mathcal{A}(\bm{x}^\star):

Noteeasy condition

\color{blue}\nabla g_\ell(\bm{x}^\star)\bm{d}=0, \quad\textrm{and}\quad \mu_\ell>0

Notemore accurate condition

\begin{aligned} \color{blue}\nabla g_\ell(\bm{x}^\star)\bm{d}=0,\quad & \color{blue}\textrm{and}\quad \mu_k>0 \\ \color{Magenta}\nabla g_k\ell(\bm{x}^\star)\bm{d}\geq 0, \quad & \color{Magenta}\textrm{and} \quad \mu_\ell=0 \end{aligned}

Remark 8.2. The condition

{\color{Magenta}\nabla g_k(\bm{x}^\star)\bm{d}\geq 0,\qquad \textrm{if $k\in \mathcal{A}(\bm{x}^\star)$ and $\mu_k=0$}}

restrict the space of direction to be considered. If omitted the Theorem 8.4 is still valid cause sufficient condition is tested in a larger set.

8.3 Other constraints qualifications

In the study of optimality condition the constraints and its gradients cannot be arbitrary. They must satisfy additional analytic/geometric properties. This properties are named constraints qualification. The easiest qualification (but also compelling) is linear independence (LI)

Definition 8.5 (Constraints qualification LI) Given the inequality constraints \bm{g}(\bm{x}) and equality constraints \bm{h}(\bm{x}), we will say than an admissible point \bm{x}^\star is qualified if the vectors

\{\nabla g_k(\bm{x}^\star)\;:\;k\in \mathcal{A}(\bm{x}^\star)\} \;\bigcup\; \{ \nabla h_1(\bm{x}^\star),\nabla h_2(\bm{x}^\star),\ldots ,\nabla h_m(\bm{x}^\star)\}

are linearly independent.

Mangasarian-Fromovitz qualification

This qualification is less stringent of the previous

Definition 8.6 (Mangasarian-Fromovitz qualification) Given the inequality constraints \bm{g}(\bm{x}) and equality constraints \bm{h}(\bm{x}), we will say than an admissible point \bm{x}^\star is qualified if does not exists a linear combination

\sum_{\ell\in \mathcal{A}(\bm{x}^\star)}^m \alpha_\ell \nabla g_\ell(\bm{x}^\star)+ \sum_{k=1}^m \beta _k \nabla h_k(\bm{x}^\star) = \bm{0}

with \alpha_\ell\geq 0 for \ell\in \mathcal{A}(\bm{x}^\star) and \alpha_\ell and \beta _k not all zero. That is, there is no non trivial linear combination for the null vector with \alpha _\ell\geq 0 for \ell\in \mathcal{A}(\bm{x}^\star).

Garth P. McCormick qualification

Definition 8.7 (Garth P. McCormick constraints qualification (1 order)) Given an admissible point \bm{x}^\star the constraints are first order qualified if for all direction \bm{d} that satisfy

\begin{aligned} \nabla h_k(\bm{x}^\star)\bm{d} &=0,\quad k\in \{1,2, \ldots ,m\}, \\ \nabla g_\ell(\bm{x}^\star)\bm{d} &\geq 0,\quad \ell\in\mathcal{A}(\bm{x}^\star), \end{aligned}

exists a curve \bm{x}\in \mathtt{C}^1(\Bbb{R},\Bbb{R}^n) and an \varepsilon>0 such that for 0<t<\varepsilon.

\begin{aligned} \bm{x}(0)&=\bm{x}^\star,\quad & h_k(\bm{x}(t))&=0, \quad k\in \{1,2, \ldots ,m\}, \\ \bm{x}'(0) &=\bm{d}, \quad & g_\ell(\bm{x}(t))&\geq 0, \quad \ell\in \{1,2, \ldots ,p\}. \end{aligned}

Definition 8.8 (Garth P. McCormick constraints qualification (2 order)) Given an admissible point \bm{x}^\star the constraints are second order qualified if for all direction \bm{d} that satisfy

\begin{aligned} \nabla h_k(\bm{x}^\star)\bm{d} &=0,\qquad k\in \{1,2, \ldots ,m\}, \\ \nabla g_\ell(\bm{x}^\star)\bm{d}&=0,\qquad \ell\in \mathcal{A}(\bm{x}^\star), \end{aligned}

exists a curve \bm{x}\in \mathtt{C}^2(\Bbb{R},\Bbb{R}^n) and an \varepsilon>0 such that for 0<t<\varepsilon.

\begin{aligned} \bm{x}(0) &=\bm{x}^\star, \quad & h_k(\bm{x}(t))&= 0,\quad & k &\in \{1,2, \ldots ,m\}, \\ \bm{x}'(0) &=\bm{d}, \quad & g_\ell(\bm{x}(t))&=0,\quad & \ell & \in \mathcal{A}(\bm{x}^\star). \end{aligned}

[1]

F. John. 1948. Extremum Problems with Inequalities as Subsidiary Conditions. In Studies and essays: Courant anniversary volume, K. O. Friedrichs, O. E. Neugebauer and J. J. Stoker (eds.). Wiley-Interscience, New York, 187–204.

[2]

H. W. Kuhn and A. W. Tucker. 1951. Nonlinear programming. In Proceedings of the second berkeley symposium on mathematical statistics and probability, 1951. University of California Press, Berkeley, California, 481–492.

[3]

G. McCormick. 1967. Second order conditions for constrained minima. SIAM Journal on Applied Mathematics 15, 3 (1967), 641–652. https://doi.org/10.1137/0115056

[4]

Jorge Nocedal and Stephen J. Wright. 2006. Numerical optimization (2nd ed.). Springer Science & Business Media. https://doi.org/10.1007/978-0-387-40065-5