10.8. Lagrange Multipliers

Main references for this section are [6, 9, 17].

The material in this section builds up on the material from previous sections. While the material in Constrained Optimization I and Constrained Optimization II doesn’t make specific assumptions on the structure of the constraint set (beyond say convexity and closedness), the material in Linear Constraints deals with a specific structure where the constraint set consists of a system of linear inequalities and equalities. This section focuses on the case where the constraint set consists of a system of smooth inequalities and equalities.

The necessary and/or sufficient conditions for the optimization problems presented in this section admit the existence of a set of nonnegative (for inequality constraints) and real (for equality constraints) scalars known as Lagrange multipliers satisfying a specific system of equations.

1. We generalize the linear inequality and equality constraints in Linear Constraints to allow for smooth inequality and equality constraints.

2. We first consider problems involving minimization of a smooth function over a set of smooth inequalities.

   1. We describe the notion of feasible descent directions.

   2. We show that at local minimizers, there are no feasible descent directions.

   3. We then develop the necessary Fritz-John conditions for the existence of a local minimizer.

   4. We add further constraint qualifications to develop the necessary KKT conditions for the existence of a local minimizer.

3. We then consider the problems involving minimization of a smooth function over a set of sooth inequalities and equalities. We present the KKT conditions for the existence of a local minimizer.

4. We then add convexity in the mix for the cost function and constraint functions.

10.8.1. Inequality Constrained Problems

We start by developing the KKT conditions for the problem of minimizing a smooth function over a set of inequality constraints.

The problem is given as

(10.18)$$\begin{array}{rlrlr}& \text{minimize }& & f(\mathbf{x})& \\ & \text{subject to }& & g_i(\mathbf{x})\le 0,i=1,\dots ,m& \end{array}$$

where $f,g_1,\dots ,g_m:\mathbb{V}\to \mathbb{R}$ are continuously differentiable functions over $\mathbb{V}$.

The constraint set is given by

$$C=\{\mathbf{x}\in \mathbb{V}|g_i(\mathbf{x})\le 0,i=1,\dots ,m\}.$$

10.8.1.1. Feasible Descent Directions

Recall from Definition 10.22 that a descent direction is a direction along which the directional derivative of the cost function is negative; i.e., $f^{\prime }(\mathbf{x};\mathbf{d})<0$. If $f$ is continuously differentiable, this translates to

$$f^{\prime }(\mathbf{x};\mathbf{d})=⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩<0.$$

Recall from Definition 10.23 that given a vector $\mathbf{x}\in C$, a direction $\mathbf{d}\in \mathbb{V}$ is said to be a feasible direction of $C$ at $\mathbf{x}$ if there exists a $\bar{t}>0$ such that

$$\mathbf{x}+t\mathbf{d}\in C\text{ for every }t\in [0,\bar{t}].$$

We now introduce the notion of a feasible descent direction.

Definition 10.28 (Feasible descent direction)

Consider the problem of minimizing a cost function $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ over a constraint set $C\subseteq \mathrm{dom}f$. A nonzero vector $\mathbf{d}$ is called a feasible descent direction at $\mathbf{x}\in C$ if $f^{\prime }(\mathbf{x};\mathbf{d})<0$ and there exists $\bar{t}>0$ such that

$$\mathbf{x}+t\mathbf{d}\in C\text{ for every }t\in [0,\bar{t}].$$

In other words, a feasible descent direction at $\mathbf{x}\in C$ is a feasible direction and a decent direction.

1. If $f$ is continuously differentiable then we must have $⟨\mathbf{d},\mathrm{\nabla }f(\mathbf{x})⟩<0$.

2. If $C$ is convex, then we just need to have $\mathbf{x}+\bar{t}\mathbf{d}\in C$. By virtual of convexity of $C$, every $\mathbf{y}\in [\mathbf{x},\mathbf{x}+\bar{t}\mathbf{d}]\in C$.

Lemma 10.7 (Local minimum and feasible descent directions)

Consider the problem of minimizing a cost function $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ over a constraint set $C\subseteq \mathrm{dom}f$. If ${\mathbf{x}}^{\ast }$ is a local minimizer then there are no feasible descent directions at ${\mathbf{x}}^{\ast }$.

Proof. We prove this by contradiction.

1. Let ${\mathbf{x}}^{\ast }$ be a local minimizer.

2. Assume that $\mathbf{d}\ne \mathbf{0}$ is a feasible descent direction.

3. Then there is an ${ϵ}_1>0$ such that ${\mathbf{x}}^{\ast }+t\mathbf{d}\in C$ for every $t\in [0,{ϵ}_1]$.

4. Also, $f^{\prime }(\mathbf{x};\mathbf{d})<0$.

5. By Definition 9.70, there exists ${ϵ}_2>0$ such that

   $$\frac{f({\mathbf{x}}^{\ast }+t\mathbf{d})-f({\mathbf{x}}^{\ast })}{t}<0\mathrm{\forall }0<t<{ϵ}_2.$$

6. Equivalently, $f({\mathbf{x}}^{\ast }+t\mathbf{d})<f({\mathbf{x}}^{\ast })$ for all $0<t<{ϵ}_2$.

7. Let $ϵ=min({ϵ}_1,{ϵ}_2)$.

8. Then for every $t\in (0,ϵ)$, we have $\mathbf{x}+t\mathbf{d}\in C$ and $f({\mathbf{x}}^{\ast }+t\mathbf{d})<f({\mathbf{x}}^{\ast })$.

9. This contradicts the hypothesis that ${\mathbf{x}}^{\ast }$ is a local minimizer.

10. Hence, there are no feasible descent directions at ${\mathbf{x}}^{\ast }$.

10.8.1.2. Necessary Conditions for Local Optimality

Revising the problem (10.18):

1. A constraint $g_i$ is called active at $\mathbf{x}$ if $g_i(\mathbf{x})=0$.

2. A constraint $g_i$ is called inactive at $\mathbf{x}$ if $g_i(\mathbf{x})<0$.

3. The set of active constraints at a point $\mathbf{x}$ is denoted by

   $$\mathcal{A}(\mathbf{x})=\{i\in 1,\dots ,m|g_i(\mathbf{x})=0\}.$$

We first restate the Lemma 10.7 for the minimization with inequality constraints problem (10.18). The key idea is the lack of feasible descent directions at a local minimizer.

1. $f^{\prime }(\mathbf{x};\mathbf{d})<0$ will indicate that $\mathbf{d}$ is a feasible direction.

2. If a constraint is inactive, then it remains valid in the neighborhood of the local minimizer due to continuity of $g_i$.

3. If a constraint is active, then moving in some directions will lead to invalidation of the constraint while moving in some directions will keep the constraint valid.

4. In particular, if $g_i^{\prime }(\mathbf{x};\mathbf{d})<0$, then moving along $\mathbf{d}$ keeps the $i$-th active constraint valid.

5. Hence, along a feasible descend direction, the directional derivatives of the cost function and the active constraint functions must be negative.

Lemma 10.8 (Local minimum and feasible descent directions for inequality constraints)

Let ${\mathbf{x}}^{\ast }$ be a local minimizer of the optimization problem (10.18):

$$\begin{array}{rlrlr}& \text{minimize }& & f(\mathbf{x})& \\ & \text{subject to }& & g_i(\mathbf{x})\le 0,i=1,\dots ,m& \end{array}$$

where $f,g_1,\dots ,g_m:\mathbb{V}\to \mathbb{R}$ are continuously differentiable functions over $\mathbb{V}$. Let $\mathcal{A}({\mathbf{x}}^{\ast })$ denote the set of active constraints:

$$\mathcal{A}({\mathbf{x}}^{\ast })=\{i|g_i({\mathbf{x}}^{\ast })=0\}.$$

Then there doesn’t exist a vector $\mathbf{d}\in \mathbb{V}$ such that

$$\begin{array}{rl}& ⟨\mathbf{d},\mathrm{\nabla }f({\mathbf{x}}^{\ast })⟩=f^{\prime }({\mathbf{x}}^{\ast };\mathbf{d})<0,\\ & ⟨\mathbf{d},\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })⟩=g_i^{\prime }({\mathbf{x}}^{\ast };\mathbf{d})<0,i\in \mathcal{A}({\mathbf{x}}^{\ast }).\end{array}$$

This result states that local optimality is equivalent to the infeasibility of a certain system of strict inequalities.

Proof. We prove this by contradiction.

1. Let ${\mathbf{x}}^{\ast }$ be a local minimizer.

2. Assume that $\mathbf{d}\ne \mathbf{0}$ be a direction satisfying the constraints above.

3. Then there exists an ${ϵ}_0>0$ such that $f({\mathbf{x}}^{\ast }+t\mathbf{d})<f({\mathbf{x}}^{\ast })$ for every $t\in (0,{ϵ}_0)$.

4. Similarly, there exist ${ϵ}_i>0$ such that $g_i({\mathbf{x}}^{\ast }+t\mathbf{d})<g_i({\mathbf{x}}^{\ast })=0$ for every $t\in (0,{ϵ}_i)$ for every $i\in \mathcal{A}({\mathbf{x}}^{\ast })$.

5. Let $ϵ=min\{{ϵ}_0,\dots ,{ϵ}_m\}$.

6. Then for every $t\in (0,ϵ)$, we have $f({\mathbf{x}}^{\ast }+t\mathbf{d})<f({\mathbf{x}}^{\ast })$ and $g_i({\mathbf{x}}^{\ast }+t\mathbf{d})<0$ for every $i\in \mathcal{A}({\mathbf{x}}^{\ast })$.

7. By the continuity of $g_i$ for all $i$, and the fact that $g_i({\mathbf{x}}^{\ast })<0$ for every $i\notin \mathcal{A}({\mathbf{x}}^{\ast })$, there exists a $\delta >0$ such that for every $t\in (0,\delta )$, $g_i({\mathbf{x}}^{\ast }+t\mathbf{d})<0$ for every $i\notin \mathcal{A}({\mathbf{x}}^{\ast })$.

8. Hence, we conclude that for every $t\in (0,min(ϵ,\delta ))$, we have $f({\mathbf{x}}^{\ast }+t\mathbf{d})<f({\mathbf{x}}^{\ast })$ and $g_i({\mathbf{x}}^{\ast }+t\mathbf{d})<0$ for every $i\in 1,\dots ,m$.

9. But this contradicts the local optimality of ${\mathbf{x}}^{\ast }$.

10.8.1.3. Fritz-John Conditions

Recall that Farkas’ and Gordan’s theorems of the alternative present different pairs of systems where if one system is infeasible then the other must be feasible and vice versa. We can apply Gordan’s theorem to the infeasible system of strict inequalities in Lemma 10.8 to develop the so-called Fritz-John conditions.

Theorem 10.77 (Fritz-John conditions)

Let ${\mathbf{x}}^{\ast }$ be a local minimizer of the optimization problem

$$\begin{array}{rlrlr}& \text{minimize }& & f(\mathbf{x})& \\ & \text{subject to }& & g_i(\mathbf{x})\le 0,i=1,\dots ,m& \end{array}$$

where $f,g_1,\dots ,g_m:\mathbb{V}\to \mathbb{R}$ are continuously differentiable functions over $\mathbb{V}$. Then there exist nonnegative scalar multipliers $t_0,t_1,\dots ,t_m\ge 0$ which are not all zero such that

$$\begin{array}{rl}& t_0\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })=\mathbf{0},\\ & t_i{g}_i({\mathbf{x}}^{\ast })=0,i=1,\dots ,m.\end{array}$$

Proof. From Lemma 10.8, we have that the following system is infeasible.

$$\begin{array}{rl}& ⟨\mathbf{d},\mathrm{\nabla }f({\mathbf{x}}^{\ast })⟩<0,\\ & ⟨\mathbf{d},\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })⟩<0,i\in \mathcal{A}({\mathbf{x}}^{\ast }).\end{array}$$

1. Let $n=\dim \mathbb{V}$.

2. Let there be an isomorphic mapping between $\mathbb{V}$ and ${\mathbb{R}}^n$.

3. For every $\mathbf{x}\in \mathbb{V}$, let $\mathbf{x}$ also denote the corresponding vector in ${\mathbb{R}}^n$.

4. Assume that there are $k$ active constraints at ${\mathbf{x}}^{\ast }$.

5. Construct a $k+1\times n$ matrix $\mathbf{A}$ as follows:

   $$\begin{array}{r}\mathbf{A}=\left[\begin{array}{c}\mathrm{\nabla }f({\mathbf{x}}^{\ast }{)}^T\\ \mathrm{\nabla }{f}_{i_1}({\mathbf{x}}^{\ast }{)}^T\\ ⋮\\ \mathrm{\nabla }{f}_{i_k}({\mathbf{x}}^{\ast }{)}^T\end{array}\right]\end{array}$$

   where $i_1,\dots ,i_k$ denote the indices of active constraints.

6. Then the above system of strict inequalities can be stated as $\mathbf{A}\mathbf{d}\prec \mathbf{0}$.

7. This system of equations is infeasible.

8. Then by Gordan's theorem, the system

   $$\mathbf{t}\ne \mathbf{0},{\mathbf{A}}^T\mathbf{t}=\mathbf{0},\mathbf{t}⪰\mathbf{0}$$

   where $\mathbf{t}\in {\mathbb{R}}^{k+1}$ is feasible.

9. We write $\mathbf{t}=(t_0,t_{i_1},\dots ,t_{i_k})$.

10. The equation ${\mathbf{A}}^T\mathbf{t}=\mathbf{0}$ expands to

    $$t_0\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i\in \mathcal{A}({\mathbf{x}}^{\ast })}{t}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })=\mathbf{0}.$$

11. $\mathbf{t}\ne \mathbf{0}$ means that at least one of $t_0,t_{i_1},\dots ,t_{i_k}\ne 0$.

12. $\mathbf{t}⪰\mathbf{0}$ means that $t_0,t_{i_1},\dots ,t_{i_k}\ge 0$.

13. Now, let $t_i=0$ for all remaining $i\notin \mathcal{A}({\mathbf{x}}^{\ast })$.

14. Then for active constraints, we have $g_i({\mathbf{x}}^{\ast })=0$ and for inactive constraints, we have $t_i=0$.

15. Hence for all constraints, we have $t_i{g}_i({\mathbf{x}}^{\ast })=0$.

16. Hence there exist nonnegative scalar multipliers $t_0,t_1,\dots ,t_m\ge 0$ which are not all zero such that

    $$\begin{array}{rl}& t_0\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })=\mathbf{0},\\ & t_i{g}_i({\mathbf{x}}^{\ast })=0,i=1,\dots ,m.\end{array}$$

The key issue with Fritz-John conditions is that it allows $t_0=0$. The case $t_0=0$ is not particularly useful since it leads to

$$\sum _{i\in \mathcal{A}({\mathbf{x}}^{\ast })}{t}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })=\mathbf{0}.$$

with $t_i\ge 0$ and not all $t_i$ being zero. This means that the gradients of the active constraints are linearly dependent.

1. The case of linearly dependent gradients has nothing to do with the objective function.

2. A number of points might satisfy the Fritz-John conditions and yet not be local minimum points.

3. We can modify the Fritz-John conditions and insist that the gradients of the active constraints be linearly independent.

4. This leads to what are called the KKIT conditions.

10.8.1.4. KKT Conditions

Theorem 10.78 (KKT conditions)

Let ${\mathbf{x}}^{\ast }$ be a local minimizer of the optimization problem

$$\begin{array}{rlrlr}& \text{minimize }& & f(\mathbf{x})& \\ & \text{subject to }& & g_i(\mathbf{x})\le 0,i=1,\dots ,m& \end{array}$$

where $f,g_1,\dots ,g_m:\mathbb{V}\to \mathbb{R}$ are continuously differentiable functions over $\mathbb{V}$. Let $\mathcal{A}({\mathbf{x}}^{\ast })$ denote the set of active constraints:

$$\mathcal{A}({\mathbf{x}}^{\ast })=\{i|g_i({\mathbf{x}}^{\ast })=0\}.$$

Assume that the gradients of the active constraints $\{\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast }){\}}_{i\in \mathcal{A}({\mathbf{x}}^{\ast })}$ are linearly independent.

Then there exist nonnegative scalar multipliers $t_1,\dots ,t_m\ge 0$ which are not all zero such that

$$\begin{array}{rl}& \mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })=\mathbf{0},\\ & t_i{g}_i({\mathbf{x}}^{\ast })=0,i=1,\dots ,m.\end{array}$$

Proof. This is a simple extension of Theorem 10.77.

By Fritz-John conditions, there exist nonnegative scalar multipliers $r_0,r_1,\dots ,r_m\ge 0$ which are not all zero such that

$$\begin{array}{rl}& r_0\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{r}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })=\mathbf{0},\\ & r_i{g}_i({\mathbf{x}}^{\ast })=0,i=1,\dots ,m.\end{array}$$

1. If $r_0=0$, then the set of gradients of active constraints will become linearly dependent.

2. Hence, we must have $r_0>0$.

3. Let $t_i=\frac{r_i}{r_0}$ for every $i=1,\dots ,m$.

4. The result follows.

10.8.2. Inequality and Equality Constrained Problems

We now generalize the KKT conditions to include problems of the form which include both inequality constraints and equality constraints

(10.19)$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & g_i(\mathbf{x})\le 0,& i=1,\dots ,m\\ & & & h_j(\mathbf{x})=0,& j=1,\dots ,p\end{array}$$

where $f,g_1,\dots ,g_m,h_1,\dots ,h_p:\mathbb{V}\to \mathbb{R}$ are continuously differentiable functions over $\mathbb{V}$.

The constraint set is given by

$$C=\{\mathbf{x}\in \mathbb{V}|g_i(\mathbf{x})\le 0,i=1,\dots ,m\text{ and }{h}_j(\mathbf{x})=0,j=1,\dots ,p\}.$$

1. An equality constraint must always be met at a feasible point. Hence there is no need to distinguish between active and inactive equality constraints. All inequality constraints are active.

2. A constraint of the form $h_j(\mathbf{x})=0$ can be converted into two inequality constraints $h_j(\mathbf{x})\le 0$ and $-h_j(\mathbf{x})\le 0$.

Theorem 10.79 (KKT conditions for problems with smooth inequality and equality constraints)

Let ${\mathbf{x}}^{\ast }$ be a local minimizer of the optimization problem (10.19)

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & g_i(\mathbf{x})\le 0,& i=1,\dots ,m\\ & & & h_j(\mathbf{x})=0,& j=1,\dots ,p\end{array}$$

where $f,g_1,\dots ,g_m,h_1,\dots ,h_p:\mathbb{V}\to \mathbb{R}$ are continuously differentiable functions over $\mathbb{V}$. Let $\mathcal{A}({\mathbf{x}}^{\ast })$ denote the set of active inequality constraints:

$$\mathcal{A}({\mathbf{x}}^{\ast })=\{i|g_i({\mathbf{x}}^{\ast })=0\}.$$

Assume that the gradients of the active inequality constraints $\{\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast }){\}}_{i\in \mathcal{A}({\mathbf{x}}^{\ast })}$ and all the equality constraints $\{\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }){\}}_{j=1,\dots ,p}$ are linearly independent.

Then there exist nonnegative scalar multipliers $t_1,\dots ,t_m\ge 0$ and real scalar multipliers $r_1,\dots ,r_p\in \mathbb{R}$ which are not all zero such that

$$\begin{array}{rl}& \mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast })=\mathbf{0},\\ & t_i{g}_i({\mathbf{x}}^{\ast })=0,i=1,\dots ,m.\end{array}$$

10.8.2.1. KKT Points and Regular Points

All the results up to this point define a set of necessary conditions in the form of a system of equations on the constraint functions and their gradients which must be satisfied by every local minimizer of the optimization problem. Besides the local minimizers, other points may also satisfy this system of equations. We now introduce the notion of KKT points which satisfy these equations.

Definition 10.29 (KKT point)

Consider the optimization problem (10.19) where $f,g_1,\dots ,g_m,h_1,\dots ,h_p:\mathbb{V}\to \mathbb{R}$ are continuously differentiable functions over $\mathbb{V}$.

A feasible point ${\mathbf{x}}^{\ast }$ is called a KKT point if there exist nonnegative scalar multipliers $t_1,\dots ,t_m\ge 0$ and real scalar multipliers $r_1,\dots ,r_p\in \mathbb{R}$ which are not all zero such that

$$\begin{array}{rl}& \mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast })=\mathbf{0},\\ & t_i{g}_i({\mathbf{x}}^{\ast })=0,i=1,\dots ,m.\end{array}$$

All the necessary KKT conditions so far can be simply restarted as a local minimizer must be a KKT point if the gradients of active inequality constraints and all equality constraints at the point are linearly independent. We introduce the notion of regularity to capture the linear independence aspect.

Definition 10.30 (Regularity)

Consider the optimization problem (10.19) where $f,g_1,\dots ,g_m,h_1,\dots ,h_p:\mathbb{V}\to \mathbb{R}$ are continuously differentiable functions over $\mathbb{V}$.

A feasible point ${\mathbf{x}}^{\ast }$ is called regular if the gradients of the active inequality constraints $\{\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast }){\}}_{i\in \mathcal{A}({\mathbf{x}}^{\ast })}$ and all the equality constraints $\{\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }){\}}_{j=1,\dots ,p}$ are linearly independent.

With the terminology of these definitions, Theorem 10.79 reduces to: if a regular point is a local minimizer then it must be a KKT point.

The notion of regularity is a kind of constraint qualification.

Example 10.15 (Regular points, KKT points, Local minimizers)

Consider the problem:

$$\begin{array}{rlrl}& \text{minimize }& & x_1+x_2\\ & \text{subject to }& & x_1^2+x_2^2=1.\end{array}$$

The problem structure

1. The ambient space is ${\mathbb{R}}^2$.

2. We have the cost function: $f(\mathbf{x})=x_1+x_2$.

3. The cost function is smooth and convex, in fact linear.

4. We don’t have any inequality constraints.

5. We have one equality constraint.

6. The equality constraint function is given by $h(\mathbf{x})=x_1^2+x_2^2-1$.

7. The equality constraint is $h(\mathbf{x})=0$.

8. $h$ is a smooth function but it is not a convex function.

9. The constraint set is a contour of $h$.

10. The set of feasible points is given by $C=\{\mathbf{x}|h(\mathbf{x})=0\}$.

11. The constraint set is not convex.

12. Hence, it is not a convex optimization problem.

13. However, the constraint set is compact.

14. Hence, due to Theorem 3.85, the function $f$ indeed attains a minimum as well as a maximum value on the $C$.

Gradients

1. We have $\mathrm{\nabla }f(\mathbf{x})=(1,1)$.

2. We have $\mathrm{\nabla }h(\mathbf{x})=(2x_1,2x_2)$.

Irregular points

1. The KKT conditions are applicable only on regular points.

2. We first identify the points which are irregular.

3. The irregular points are points at which the gradients of all active inequality constraints and equality constraints are linearly dependent.

4. Since, we have a single equality constraint, hence the irregular points are those points at which $\mathrm{\nabla }h(\mathbf{x})=\mathbf{0}$.

5. This is given by a single point $(x_1,x_2)=(0,0)$.

6. But $(0,0)\notin C$ since $h((0,0))=-1\ne 0$.

7. Hence, the constraint set $C$ doesn’t contain any irregular points.

8. In other words, every feasible point is a regular point.

9. Hence the KKT conditions are necessary for local optimality.

10. In other words, if a point is a local minimizer then it must be a KKT point.

KKT points

1. To identify the KKT points, we form the Lagrangian

   $$L(\mathbf{x},r)=f(\mathbf{x})+rh(\mathbf{x})=x_1+x_2+r(x_1^2+x_2^2-1).$$

2. The KKT conditions are:

   $$\begin{array}{rl}& {\mathrm{\nabla }}_{x}L(\mathbf{x},r)=\mathrm{\nabla }f(\mathbf{x})+r\mathrm{\nabla }h(\mathbf{x})=0,\\ & h(\mathbf{x})=0.\end{array}$$

3. They expand to

   $$\begin{array}{rl}& 1+2r{x}_1=0,\\ & 1+2r{x}_2=0,\\ & x_1^2+x_2^2-1=0.\end{array}$$

4. From the first two equations, we have $r\ne 0$ and $x_1=x_2=\frac{-1}{2r}$.

5. Plugging it into the third equation, we get

   $${\left(\frac{-1}{2r}\right)}^2+{\left(\frac{-1}{2r}\right)}^2=1.$$

6. This simplifies to $r^2=\frac{1}{2}$.

7. Hence, we have $r=\pm \frac{1}{\sqrt{2}}$.

8. This gives us two different KKT points $(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$ and $(-\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}})$.

The optimal solution

1. By compactness, we know that the minimizer does exist.

2. By regularity, we know that the minimizer must be a KKT point.

3. We have two candidates available.

4. We have $f((-\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}))=-\sqrt{2}$ and $f((\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}))=\sqrt{2}$.

5. Hence the minimizer is given by

   $${\mathbf{x}}^{\ast }=(-\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}})$$

   as it has the smaller value of $f$.

10.8.3. The Convex Case

We now restrict our attention to the case where the cost and constraint functions are convex. In this case, the KKT conditions are also sufficient.

Theorem 10.80 (Sufficient KKT conditions for convex problems (smooth and convex cost and inequality constraints, affine equality constraints))

Let ${\mathbf{x}}^{\ast }$ be a feasible solution of the optimization problem

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & g_i(\mathbf{x})\le 0,& i=1,\dots ,m\\ & & & h_j(\mathbf{x})=0,& j=1,\dots ,p\end{array}$$

where $f,g_1,\dots ,g_m:\mathbb{V}\to \mathbb{R}$ are continuously differentiable convex functions over $\mathbb{V}$ and $h_1,\dots ,h_p:\mathbb{V}\to \mathbb{R}$ are affine functions.

Suppose that there exist nonnegative scalar multipliers $t_1,\dots ,t_m\ge 0$ and real scalar multipliers $r_1,\dots ,r_p\in \mathbb{R}$ which are not all zero such that

$$\begin{array}{rl}& \mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast })=\mathbf{0},\\ & t_i{g}_i({\mathbf{x}}^{\ast })=0,i=1,\dots ,m.\end{array}$$

Then ${\mathbf{x}}^{\ast }$ is an optimal solution of the minimization problem above.

Proof. We are given that ${\mathbf{x}}^{\ast }$ is a feasible point satisfying the KKT conditions.

1. Define the function

   $$s(\mathbf{x})=f(\mathbf{x})+\sum _{i=1}^m{t}_i{g}_i(\mathbf{x})+\sum _{j=1}^p{r}_j{h}_j(\mathbf{x}).$$

2. Since $f$ and $g_i$ are convex and $h_j$ are affine, hence $s$ is convex.

3. Since all of them are continuously differentiable, hence $s$ is also continuously differentiable.

4. We have

   $$\mathrm{\nabla }s(\mathbf{x})=\mathrm{\nabla }f(\mathbf{x})+\sum _{i=1}^m{t}_i\mathrm{\nabla }{g}_i(\mathbf{x})+\sum _{j=1}^p{r}_j\mathrm{\nabla }{h}_j(\mathbf{x}).$$

5. We are given that $\mathrm{\nabla }s({\mathbf{x}}^{\ast })=0$.

6. By Theorem 10.48, ${\mathbf{x}}^{\ast }$ is a minimizer of $s$ over $\mathbb{V}$.

7. Hence $s({\mathbf{x}}^{\ast })\le s(\mathbf{x})$ for every $\mathbf{x}\in \mathbb{V}$.

8. By hypothesis $t_i{g}_i({\mathbf{x}}^{\ast })=0$ for every $i=1,\dots ,m$.

9. Hence $\sum _{i=1}^m{t}_i{g}_i({\mathbf{x}}^{\ast })=0$.

10. Since ${\mathbf{x}}^{\ast }$ is a feasible point, hence $h_j({\mathbf{x}}^{\ast })=0$ for every $j=1,\dots ,p$.

11. Hence $\sum _{j=1}^p{h}_j({\mathbf{x}}^{\ast })=0$.

12. Hence

    $$\begin{array}{rl}f({\mathbf{x}}^{\ast })& =f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{h}_j({\mathbf{x}}^{\ast })\\ & =s({\mathbf{x}}^{\ast })\\ & \le s(\mathbf{x})\\ & =f(\mathbf{x})+\sum _{i=1}^m{t}_i{g}_i(\mathbf{x})+\sum _{j=1}^p{r}_j{h}_j(\mathbf{x})\\ & \le f(\mathbf{x}).\end{array}$$

    The last inequality comes from the fact that $t_i\ge 0$, $g_i(\mathbf{x})\le 0$ and $h_j(\mathbf{x})=0$ for every feasible $\mathbf{x}$.

13. Hence for every feasible $\mathbf{x}$, we have $f({\mathbf{x}}^{\ast })\le f(\mathbf{x})$.

14. Hence ${\mathbf{x}}^{\ast }$ is an optimal point.

10.8.3.1. Slater’s Conditions

In Theorem 10.79, we saw that KKT conditions become necessary for the local optimality of a feasible point only if the feasible point is regular. The regularity was a constraint qualification for the nonconvex smooth optimization problem.

In the convex case, a different condition than regularity can guarantee the necessity of KKT conditions. They are known as Slater’s conditions.

Definition 10.31 (Slater’s conditions)

Let $g_1,\dots ,g_m:\mathbb{V}\to \mathbb{R}$ be convex. We say that the Slater’s condition is satisfied for a set of convex inequalities

$$g_i(\mathbf{x})\le 0,i=1,\dots ,m$$

if there exists a point $\hat{\mathbf{x}}\in \mathbb{V}$ such that

$$g_i(\hat{\mathbf{x}})<0,i=1,\dots ,m.$$

In other words, the Slater’s condition requires the existence of a point which strictly satisfies all the convex inequality constraints.

Slater’s condition is much easier to check since it requires the existence of a single point which strictly satisfies all the convex inequalities.

Theorem 10.81 (Necessity of KKT conditions under Slater’s condition)

Let ${\mathbf{x}}^{\ast }$ be an optimal solution of the optimization problem

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & g_i(\mathbf{x})\le 0,& i=1,\dots ,m\end{array}$$

where $f,g_1,\dots ,g_m:\mathbb{V}\to \mathbb{R}$ are continuously differentiable functions over $\mathbb{V}$. In addition, assume that $g_1,\dots ,g_m$ are convex. Suppose that there exists a point $\hat{\mathbf{x}}\in \mathbb{V}$ such that

$$g_i(\hat{\mathbf{x}})<0,i=1,\dots ,m.$$

Then there exist nonnegative scalar multipliers $t_1,\dots ,t_m\ge 0$ which are not all zero such that

$$\begin{array}{rl}& \mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })=\mathbf{0},\\ & t_i{g}_i({\mathbf{x}}^{\ast })=0,i=1,\dots ,m.\end{array}$$

Proof. This is also derived from Fritz-John conditions Theorem 10.77.

By Fritz-John conditions, there exist nonnegative scalar multipliers $r_0,r_1,\dots ,r_m\ge 0$ which are not all zero such that

$$\begin{array}{rl}& r_0\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{r}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })=\mathbf{0},\\ & r_i{g}_i({\mathbf{x}}^{\ast })=0,i=1,\dots ,m.\end{array}$$

We need to show that $r_0>0$. After that we can pick $t_i=\frac{r_i}{r_0}$ for every $i=1,\dots ,m$ to get the desired result.

1. For contradiction, assume that $r_0=0$.

2. Then we have

   $$\sum _{i=1}^m{r}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })=\mathbf{0}.$$

3. By the gradient inequality, we have

   $$g_i(\mathbf{x})\ge g_i({\mathbf{x}}^{\ast })+⟨\mathbf{x}-{\mathbf{x}}^{\ast },\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })⟩,i=1,\dots ,m.$$

4. Specifically, for the point $\hat{\mathbf{x}}$, we have

   $$0>g_i(\hat{\mathbf{x}})\ge g_i({\mathbf{x}}^{\ast })+⟨\hat{\mathbf{x}}-{\mathbf{x}}^{\ast },\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })⟩,i=1,\dots ,m.$$

5. Multiplying the $i$-th inequality by $r_i\ge 0$ and summing over $i=1,\dots ,m$, we get

   $$0>\sum _{i=1}^m{r}_i{g}_i({\mathbf{x}}^{\ast })+⟨\hat{\mathbf{x}}-{\mathbf{x}}^{\ast },\sum _{i=1}^m{r}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })⟩.$$

   This inequality is strict since not all $r_i$ are $0$ and $r_0=0$.

6. Since $\sum _{i=1}^m{r}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })=\mathbf{0}$, it reduces to

   $$0>\sum _{i=1}^m{r}_i{g}_i({\mathbf{x}}^{\ast }).$$

7. But $r_i{g}_i({\mathbf{x}}^{\ast })=0$ for every $i=1,\dots ,m$. Hence we must have

   $$\sum _{i=1}^m{r}_i{g}_i({\mathbf{x}}^{\ast })=0.$$

8. A contradiction. Hence $r_0>0$ must be true.

10.8.4. A Tangent Cones Perspective

Consider an optimization problem of the form

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & h_i(\mathbf{x})=0,i=1,\dots ,m.\end{array}$$

Assume that $f:\mathbb{V}\to \mathbb{R}$ and $h_i:\mathbb{V}\to \mathbb{R}$ for $i=1,\dots ,m$ are smooth functions.

The constraint set can be written as

$$C=\{\mathbf{x}|h_i(\mathbf{x})=0,i=1,\dots ,m\}.$$

1. Assume that ${\mathbf{x}}^{\ast }$ is a minimizer of this problem.

2. By Theorem 10.72, we must have

   $$-\mathrm{\nabla }f({\mathbf{x}}^{\ast })\in T_C({\mathbf{x}}^{\ast }{)}^{\circ }.$$

Let us now motivate the Lagrange multipliers using a simple problem of linear inequalities.

1. Consider the specific case where

   $$h_i(\mathbf{x})=⟨\mathbf{x},{\mathbf{a}}_i⟩-b_i.$$

2. Consider a matrix $\mathbf{A}$ which consists of ${\mathbf{a}}_1^T,\dots ,{\mathbf{a}}_m^T$ as rows.

3. Put together $b_1,\dots ,b_m$ as a vector $\mathbf{b}$.

4. Then the constraint set can be expressed as

   $$C=\{\mathbf{x}|\mathbf{A}\mathbf{x}=\mathbf{b}\}.$$

5. Assume that ${\mathbf{x}}^{\ast }\in C$ is the local minimizer of $f$.

6. By Example 10.10,

   $$T_C({\mathbf{x}}^{\ast })=\{\mathbf{x}|\mathbf{A}\mathbf{x}=\mathbf{0}\}$$

   which is the nullspace of $\mathbf{A}$.

7. By Example 9.18,

   $$T_C({\mathbf{x}}^{\ast }{)}^{\circ }=T_C({\mathbf{x}}^{\ast }{)}^{\perp }=\mathrm{range}{\mathbf{A}}^T.$$

8. Hence, by the optimality condition, we have

   $$-\mathrm{\nabla }f({\mathbf{x}}^{\ast })\in \mathrm{range}{\mathbf{A}}^T.$$

9. Hence, there exists ${\mathbf{t}}^{\ast }\in {\mathbb{R}}^m$ such that

   $$\mathrm{\nabla }f({\mathbf{x}}^{\ast })+{\mathbf{A}}^T{\mathbf{t}}^{\ast }=0.$$

10. This is equivalent to

    $$\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }{\mathbf{a}}_i=0.$$

11. Since $\mathrm{\nabla }{h}_i({\mathbf{x}}^{\ast })={\mathbf{a}}_i$, hence this is equivalent to

    $$\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{h}_i({\mathbf{x}}^{\ast })=0.$$

This motivates us to define the Lagrangian of $f$ as

$$L(\mathbf{x},\mathbf{t})=f(\mathbf{x})+\sum _{i=1}^m{t}_i{h}_i(\mathbf{x}).$$

The basic Lagrangian theorem states that under suitable conditions, if ${\mathbf{x}}^{\ast }$ is a local minimum of $f$ under the constraint set $C$ then there exist scalars $t_1^{\ast },\dots ,t_m^{\ast }$ called Lagrangian multipliers such that

$$\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{h}_i({\mathbf{x}}^{\ast })=0.$$

1. There are $n$ unknowns in ${\mathbf{x}}^{\ast }$ and $m$ unknowns in ${\mathbf{t}}^{\ast }$.

2. Thus, we have a total of $m+n$ unknowns.

3. The relation above gives us a system of $n$ equations.

4. Together with the $m$ equalities $h_i({\mathbf{x}}^{\ast })=0$, we have a system of $m+n$ equations with $m+n$ unknowns.

5. Thus, the problem of solving a constrained optimization problem is transformed into a problem of solving a system of nonlinear equations.

6. Now, suppose that the tangent cone at ${\mathbf{x}}^{\ast }$ can be written as

   $$T_C({\mathbf{x}}^{\ast })=\{\mathbf{x}|⟨\mathbf{x},\mathrm{\nabla }{h}_i({\mathbf{x}}^{\ast })⟩=0,i=1,\dots ,m\}.$$

7. Letting ${\mathbf{a}}_i=\mathrm{\nabla }{h}_i({\mathbf{x}}^{\ast })$ and following the argument above, we must have

   $$\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{h}_i({\mathbf{x}}^{\ast })=0.$$

8. Thus, if the tangent cone can be represented as above, then if ${\mathbf{x}}^{\ast }$ is a local minimizer, then the Lagrangian multipliers $t_1^{\ast },\dots ,t_m^{\ast }$ must exist.

9. The admittance of Lagrange multipliers at a given ${\mathbf{x}}^{\ast }\in C$ is the property of the constraint set $C$. It is not a property of the optimization problem itself. If $C$ admits Lagrange multipliers at ${\mathbf{x}}^{\ast }$, then there exists a Lagrange multiplier vector at ${\mathbf{x}}^{\ast }$ for every smooth cost function $f$ if ${\mathbf{x}}^{\ast }$ is a local minimizer of $f$.

10.8.5. Enhanced Fritz-John Conditions

We now introduce a more difficult optimization problem

(10.20)$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in C\end{array}$$

where the constraint set $C$ consists of equality and inequality constraints as well as an additional abstract set constraint $X$:

(10.21)$$C=X\cap \{\mathbf{x}|g_i(\mathbf{x})\le 0,i=1,\dots ,m\}\cap \{\mathbf{x}|h_j(\mathbf{x})=0,j=1,\dots ,p\}.$$

We assume that $f$, $g_i$ and $h_j$ are smooth functions from $\mathbb{V}$ to $\mathbb{R}$ and $X$ is a nonempty closed set.

We also introduce $g:\mathbb{V}\to {\mathbb{R}}^m$ as

$$g(\mathbf{x})=(g_1(\mathbf{x}),\dots ,g_m(\mathbf{x}))$$

and $h:\mathbb{V}\to {\mathbb{R}}^p$ as

$$h(\mathbf{x})=(h_1(\mathbf{x}),\dots ,h_p(\mathbf{x})).$$

For every $i=1,\dots ,m$, we define

$$g_i^{+}(\mathbf{x})=max\{0,g_i(\mathbf{x})\}.$$

Correspondingly, we define

$$g^{+}(\mathbf{x})=(g_1^{+}(\mathbf{x}),\dots ,g_m^{+}(\mathbf{x})).$$

Definition 10.32 (Lagrangian function)

For the optimization problem (10.20), the Lagrangian function is defined as

$$L(\mathbf{x},\mathbf{t},\mathbf{r})=f(\mathbf{x})+\sum _{i=1}^m{t}_i{g}_i(\mathbf{x})+\sum _{j=1}^p{r}_j{h}_j(\mathbf{x})$$

where $\mathbf{t}\in {\mathbb{R}}^m$ and $\mathbf{r}\in {\mathbb{R}}^p$.

10.8.5.1. Lagrange Multiplier Vectors

Definition 10.33 (Lagrange multiplier vectors)

We say that a constraint set $C$ as defined in (10.21) admits Lagrange multipliers at a point ${\mathbf{x}}^{\ast }\in C$ if for every smooth cost function $f$ for which ${\mathbf{x}}^{\ast }$ is a local minimum of the problem (10.20), there exist vectors ${\mathbf{t}}^{\ast }=(t_1^{\ast },\dots ,t_m^{\ast })$ and ${\mathbf{r}}^{\ast }=(r_1^{\ast },\dots ,r_p^{\ast })$ that satisfy the following conditions:

(10.22)$$⟨\mathbf{y},(\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }))⟩\ge 0,\mathrm{\forall }\mathbf{y}\in T_X({\mathbf{x}}^{\ast }),$$

(10.23)$$t_i^{\ast }\ge 0,\mathrm{\forall }i=1,\dots ,m,$$

(10.24)$$t_i^{\ast }=0,\mathrm{\forall }i|g_i({\mathbf{x}}^{\ast })<0.$$

A pair $({\mathbf{t}}^{\ast },{\mathbf{r}}^{\ast })$ satisfying these conditions is called a Lagrange multiplier vector corresponding to $f$ and ${\mathbf{x}}^{\ast }$.

1. We also call the Lagrange multiplier vector as simply Lagrange multipliers.

2. The condition (10.23) is the nonnegativity condition of the Lagrangian multipliers for the inequality constraints.

3. The condition (10.24) is the complementary slackness condition.

4. From (10.22), we can see that for each $\mathbf{y}\in T_X({\mathbf{x}}^{\ast })$, the set of Lagrange multiplier vectors corresponding to a given $f$ and ${\mathbf{x}}^{\ast }$ is a closed half-space.

5. Hence, the set of Lagrange multiplier vectors corresponding to a given $f$ and ${\mathbf{x}}^{\ast }$ is an intersection of closed half spaces.

6. Hence the set of Lagrange multiplier vectors is closed and convex. Although it may possibly be empty.

7. The condition (10.22) is referred to as the Lagrangian stationarity condition. It states that the gradient of the Lagrangian function is nonnegative along all tangent directions at the local minimizer.

8. It can be viewed as the necessary condition for ${\mathbf{x}}^{\ast }$ to be a local minimizer of the function $L(\mathbf{x},{\mathbf{t}}^{\ast },{\mathbf{r}}^{\ast })$. See Theorem 10.72.

9. When $X=\mathbb{V}$, then $T_X({\mathbf{x}}^{\ast })=\mathbb{V}$, and this condition reduces to

   $$\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast })=\mathbf{0}.$$

10. When $X$ is convex, then (10.22) reduces to

    $$⟨\mathbf{x}-{\mathbf{x}}^{\ast },(\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }))⟩\ge 0,\mathrm{\forall }\mathbf{x}\in X.$$

    1. $X$ is convex. Hence $\alpha (\mathbf{x}-{\mathbf{x}}^{\ast })$ for $\alpha >0$ is a feasible direction for every $\mathbf{x}\in X$.

    2. Hence, if this inequality holds, then (10.22) holds for every $\mathbf{d}\in F_C(\mathbf{x})$.

    3. Since $X$ is convex, hence $\mathrm{cl}{F}_C(\mathbf{x})=T_C(\mathbf{x})$.

    4. If the inequality (10.22) holds for every $\mathbf{d}\in F_C(\mathbf{x})$, then it will also hold for a closure point of $F_C(\mathbf{x})$.

    5. In other words, if $⟨\mathbf{x},\mathbf{a}⟩\ge 0$ for every $\mathbf{x}\in A$, then for any convergent sequence $\{{\mathbf{x}}_k\}$ of $A$, we have $\underset{k\to \mathrm{\infty }}{lim}⟨{\mathbf{x}}_k,\mathbf{a}⟩\ge 0$. Hence the inequality holds for every closure point also.

11. The Lagrangian stationary condition can also be equivalently written as

    $$-(\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }))\in T_X({\mathbf{x}}^{\ast }{)}^{\circ }.$$

    In other words, the negative gradient of the Lagrangian function must lie in the polar cone of the tangent cone of $X$ at ${\mathbf{x}}^{\ast }$.

12. Recall from Theorem 10.68 that

    $$T_X({\mathbf{x}}^{\ast }{)}^{\circ }\subseteq {\tilde{N}}_X({\mathbf{x}}^{\ast })$$

    where ${\tilde{N}}_X({\mathbf{x}}^{\ast })$ is the normal cone of $X$ at ${\mathbf{x}}^{\ast }$ (in the sense of [9]).

13. Hence the negative gradient of the Lagrangian function must be a normal direction (Definition 10.26) at ${\mathbf{x}}^{\ast }$.

14. If $X$ is regular at ${\mathbf{x}}^{\ast }$ (Theorem 10.70), then we also have

    $$T_X({\mathbf{x}}^{\ast }{)}^{\circ }={\tilde{N}}_X({\mathbf{x}}^{\ast }).$$

10.8.5.2. Enhanced Fritz-John Conditions

We are now ready to present the Enhanced Fritz-John conditions as the necessary conditions for the existence of the local minimizer of the problem (10.20).

Theorem 10.82 (Enhanced Fritz-John conditions)

Let ${\mathbf{x}}^{\ast }$ be a local minimizer of the problem (10.20)-(10.21). Then there exist scalars $t_0^{\ast },t_1^{\ast },\dots ,t_m^{\ast },r_1^{\ast },\dots ,r_p^{\ast }$ satisfying the following conditions.

1. The gradients satisfy the relation:

   $$-(t_0^{\ast }\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }))\in {\tilde{N}}_X({\mathbf{x}}^{\ast }).$$

2. Nonnegativity: $t_i^{\ast }\ge 0$ for every $i=0,\dots ,m$.

3. The scalars $t_0^{\ast },t_1^{\ast },\dots ,t_m^{\ast },r_1^{\ast },\dots ,r_p^{\ast }$ are not equal to $0$.

4. Complementary violation condition: If the index set $I\cup J$ is not empty, where

   $$I=\{i>0|t_i^{\ast }>0\},J=\{j|r_j^{\ast }\ne 0\},$$

   there exists a sequence $\{{\mathbf{x}}_k\}$ of $X$ that converges to ${\mathbf{x}}^{\ast }$ and is such that for all $k$

   $$\begin{array}{rl}& f({\mathbf{x}}_k)<f({\mathbf{x}}^{\ast }),\\ & t_i^{\ast }{g}_i({\mathbf{x}}_k)>0\mathrm{\forall }i\in I,\\ & r_j^{\ast }{h}_j({\mathbf{x}}_k)>0\mathrm{\forall }j\in J,\\ & g_i^{+}({\mathbf{x}}_k)=o(w({\mathbf{x}}_k))\mathrm{\forall }i\notin I,\\ & |h_j({\mathbf{x}}_k)|=o(w({\mathbf{x}}_k))\mathrm{\forall }j\notin J,\end{array}$$

   where $g_i^{+}(\mathbf{x})=max\{0,g_i(\mathbf{x})\}$ and

   $$w(\mathbf{x})=min\{\underset{i\in I}{min}{g}_i^{+}(\mathbf{x}),\underset{j\in J}{min}|h_j(\mathbf{x})|\}.$$

Proof. The proof is based on a quadratic penalty function approach. For each $k\in \mathbb{N}$, we define a penalty function as

$$F^k(\mathbf{x})=f(\mathbf{x})+\frac{k}{2}\sum _{i=1}^m(g_i^{+}(\mathbf{x}){)}^2+\frac{k}{2}\sum _{j=1}^p(h_j(\mathbf{x}){)}^2+\frac{1}{2}\Vert \mathbf{x}-{\mathbf{x}}^{\ast }{\Vert }^2.$$

1. At a feasible point $g_i^{+}(\mathbf{x})=0$ for every $i=1,\dots ,m$ since $g_i(\mathbf{x})\le 0$.

2. At a feasible point $h_j(\mathbf{x})=0$ for every $j=1,\dots ,p$.

3. Hence $F^k(\mathbf{x})=f(\mathbf{x})+\frac{1}{2}\Vert \mathbf{x}-{\mathbf{x}}^{\ast }{\Vert }^2$ at every feasible point $\mathbf{x}\in C$.

4. The term $\frac{1}{2}\Vert \mathbf{x}-{\mathbf{x}}^{\ast }{\Vert }^2$ is a quadratic penalty term penalizing how far we are from the local minimum ${\mathbf{x}}^{\ast }$.

5. The term $\frac{1}{2}(g_i^{+}(\mathbf{x}){)}^2$ is a penalty term denoting how strongly the $i$-th inequality constraint is violated.

6. The term $\frac{1}{2}(h_j(\mathbf{x}){)}^2$ is a penalty term denoting how strongly the $j$-th equality constraint is violated.

7. We have $F^k(\mathbf{x})\le f(\mathbf{x})$ for every $\mathbf{x}\in \mathbb{V}$.

8. At the local minimizer, we have

   $$F^k({\mathbf{x}}^{\ast })=f({\mathbf{x}}^{\ast }).$$

9. $F^k$ is a continuously differentiable function.

10. We note that

    $$\begin{array}{r}\mathrm{\nabla }(g_i^{+}(\mathbf{x}){)}^2=2g_i^{+}(\mathbf{x})\mathrm{\nabla }{g}_i(\mathbf{x});\\ \mathrm{\nabla }(h_j(\mathbf{x}){)}^2=2h_j(\mathbf{x})\mathrm{\nabla }{h}_j(\mathbf{x}).\end{array}$$

11. Hence

    $$\mathrm{\nabla }{F}^k(\mathbf{x})=\mathrm{\nabla }f(\mathbf{x})+k\sum _{i=1}^m{g}_i^{+}(\mathbf{x})\mathrm{\nabla }{g}_i(\mathbf{x})+k\sum _{j=1}^p{h}_j(\mathbf{x})\mathrm{\nabla }{h}_j(\mathbf{x})+(\mathbf{x}-{\mathbf{x}}^{\ast }).$$

We now introduce the penalized problem

$$\begin{array}{rlrl}& \text{minimize }& & F^k(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in X\cap S\end{array}$$

where

$$S=\{\mathbf{x}|\Vert \mathbf{x}-{\mathbf{x}}^{\ast }\Vert \le ϵ\}$$

and $ϵ>0$ is a positive scalar such that $f({\mathbf{x}}^{\ast })\le f(\mathbf{x})$ for all feasible $\mathbf{x}\in C$ with $\mathbf{x}\in S$. Such a positive scalar exists since ${\mathbf{x}}^{\ast }$ is a local minimizer of $f$.

1. The set $S$ is compact and the set $X$ is closed.

2. Hence $X\cap S$ is compact.

3. Hence there exists an optimal minimizer of the above problem for every $k$.

4. Let ${\mathbf{x}}^k$ be a minimizer of $F^k(\mathbf{x})$ over $X\cap S$.

5. Then we have $F^k({\mathbf{x}}^k)\le F^k({\mathbf{x}}^{\ast })$ for every $k$ since ${\mathbf{x}}^{\ast }\in X\cap S$.

6. This is equivalent to

   $$F^k({\mathbf{x}}^k)=f({\mathbf{x}}^k)+\frac{k}{2}\sum _{i=1}^m(g_i^{+}({\mathbf{x}}^k){)}^2+\frac{k}{2}\sum _{j=1}^p(h_j({\mathbf{x}}^k){)}^2+\frac{1}{2}\Vert {\mathbf{x}}^k-{\mathbf{x}}^{\ast }{\Vert }^2\le f({\mathbf{x}}^{\ast })$$

   for every $k$.

7. Since $f$ is continuous and $X\cap S$ is compact, hence $f({\mathbf{x}}^k)$ is bounded for every $k$.

8. It follows that

   $$\begin{array}{rl}& \underset{k\to \mathrm{\infty }}{lim}{g}_i^{+}({\mathbf{x}}^k)=0,i=1,\dots ,m,\\ & \underset{k\to \mathrm{\infty }}{lim}|h_j({\mathbf{x}}^k)|=0,j=1,\dots ,p,\end{array}$$

   otherwise the term on the L.H.S. of the previous inequality will become unbounded and tend to $\mathrm{\infty }$ as $k\to \mathrm{\infty }$.

9. Hence every limit point $\tilde{\mathbf{x}}$ of the sequence $\{{\mathbf{x}}^k\}$ is feasible; i.e., $\tilde{\mathbf{x}}\in C$.

10. Also, since $X\cap S$ is compact, hence every limit point $\tilde{\mathbf{x}}$ of the sequence $\{{\mathbf{x}}^k\}$ belongs to $X\cap S$.

11. From the inequality $F^k({\mathbf{x}}^k)\le f({\mathbf{x}}^{\ast })$, we can also see that

    $$f({\mathbf{x}}^k)+\frac{1}{2}\Vert {\mathbf{x}}^k-{\mathbf{x}}^{\ast }{\Vert }^2\le f({\mathbf{x}}^{\ast })\mathrm{\forall }k.$$

12. Taking the limit as $k\to \mathrm{\infty }$, we obtain

    $$f(\tilde{\mathbf{x}})+\frac{1}{2}\Vert \tilde{\mathbf{x}}-{\mathbf{x}}^{\ast }{\Vert }^2\le f({\mathbf{x}}^{\ast })$$

    for every limit point $\tilde{\mathbf{x}}$.

13. Since $\tilde{\mathbf{x}}\in S$ (near local minimizer) and $\tilde{\mathbf{x}}\in C$ (feasible), we have

    $$f({\mathbf{x}}^{\ast })\le f(\tilde{\mathbf{x}}).$$

14. Combining with the previous inequality, it gives us

    $$\frac{1}{2}\Vert \tilde{\mathbf{x}}-{\mathbf{x}}^{\ast }{\Vert }^2=0.$$

15. Hence, we must have ${\mathbf{x}}^{\ast }=\tilde{\mathbf{x}}$. Hence, the sequence $\{{\mathbf{x}}_k\}$ has a only one limit point.

16. Thus, the sequence $\{{\mathbf{x}}^k\}$ converges to ${\mathbf{x}}^{\ast }$.

17. By the definition of the closed ball $S$, ${\mathbf{x}}^{\ast }$ is an interior point of $S$.

18. Since $lim{\mathbf{x}}^k={\mathbf{x}}^{\ast }$ it follows that ${\mathbf{x}}^k$ is an interior point of $S$ for every $k$ greater than some $k_0$.

19. Hence, due to Theorem 10.72,

    $$-\mathrm{\nabla }{F}^k({\mathbf{x}}^k)\in T_C({\mathbf{x}}^k{)}^{\circ }$$

    holds true for every $k>k_0$.

20. We can write $\mathrm{\nabla }{F}^k({\mathbf{x}}^k)$ as

    $$\mathrm{\nabla }{F}^k({\mathbf{x}}^k)=\mathrm{\nabla }f({\mathbf{x}}^k)+\sum _{i=1}^m{\chi }_i^k\mathrm{\nabla }{g}_i({\mathbf{x}}^k)+\sum _{j=1}^p{\xi }_j^k\mathrm{\nabla }{h}_j({\mathbf{x}}^k)+({\mathbf{x}}^k-{\mathbf{x}}^{\ast })$$

    where ${\chi }_i^k=k{g}_i^{+}({\mathbf{x}}^k)$ and ${\xi }_j^k=k{h}_j({\mathbf{x}}^k)$.

21. Note that by definition ${\chi }_i^k\ge 0$ for every $i=1,\dots ,m$.

22. Accordingly, we have

    $$-(\mathrm{\nabla }f({\mathbf{x}}^k)+\sum _{i=1}^m{\chi }_i^k\mathrm{\nabla }{g}_i({\mathbf{x}}^k)+\sum _{j=1}^p{\xi }_j^k\mathrm{\nabla }{h}_j({\mathbf{x}}^k)+({\mathbf{x}}^k-{\mathbf{x}}^{\ast }))\in T_C({\mathbf{x}}^k{)}^{\circ }$$

    for every $k>k_0$.

23. We define

    $${\delta }^k=\sqrt{1+\sum _{i=1}^m({\chi }_i^k{)}^2+\sum _{j=1}^p({\xi }_j^k{)}^2}.$$

24. By definition ${\delta }^k\ge 1$.

25. We now introduce

    $$\begin{array}{rl}& t_0^k=\frac{1}{{\delta }^k},\\ & t_i^k=\frac{{\chi }_i^k}{{\delta }^k},i=1,\dots ,m,\\ & r_j^k=\frac{{\xi }_j^k}{{\delta }^k},j=1,\dots ,p.\end{array}$$

26. By dividing by ${\delta }^k$ in the previous relation, we obtain

    $${\mathbf{z}}^k=-(t_0^k\mathrm{\nabla }f({\mathbf{x}}^k)+\sum _{i=1}^m{t}_i^k\mathrm{\nabla }{g}_i({\mathbf{x}}^k)+\sum _{j=1}^p{r}_j^k\mathrm{\nabla }{h}_j({\mathbf{x}}^k)+\frac{1}{{\delta }_k}({\mathbf{x}}^k-{\mathbf{x}}^{\ast }))\in T_C({\mathbf{x}}^k{)}^{\circ }$$

    for every $k>k_0$ since $T_C({\mathbf{x}}^k{)}^{\circ }$ is a cone.

27. Note that by construction, we have

    $$(t_0^k{)}^2+\sum _{i=1}^m(t_i^k{)}^2+\sum _{j=1}^p(r_j^k{)}^2=1.$$

28. Hence the sequence $\{(t_0^k,t_1^k,\dots ,t_m^k,r_1^k,\dots ,r_p^k)\}$ is a bounded sequence of ${\mathbb{R}}^{1+m+p}$.

29. Hence, it must have a subsequence that converges to some limit $\{(t_0^{\ast },t_1^{\ast },\dots ,t_m^{\ast },r_1^{\ast },\dots ,r_p^{\ast })\}$.

30. Let

    $${\mathbf{z}}^{\ast }=-(t_0^{\ast }\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast })).$$

31. Along this subsequence, we have ${\mathbf{x}}^k\to {\mathbf{x}}^{\ast }$, ${\mathbf{z}}^k\to {\mathbf{z}}^{\ast }$ and ${\mathbf{z}}^k\in T_X({\mathbf{x}}^k{)}^{\circ }$ for every $k>k_0$.

32. Hence, following the definition of the normal cone (Definition 10.27), after disregarding the first $k_0$ terms of the sequences,

    $${\mathbf{z}}^{\ast }\in {\tilde{N}}_X({\mathbf{x}}^{\ast }).$$

(2) Nonnegativity

1. Since ${\delta }^k\ge 1$, hence $0<t_0^k=\frac{1}{{\delta }^k}\le 1$.

2. Hence $t_0^{\ast }\ge 0$.

3. Since ${\chi }_i^k\ge 0$ for every $i=1,\dots ,m$, hence $t_i^k\ge 0$ for every $i=1,\dots ,m$.

4. Hence $t_i^{\ast }\ge 0$ for every $i=1,\dots ,m$.

(3) Not all zero

1. We have established that for every $k$,

   $$(t_0^k{)}^2+\sum _{i=1}^m(t_i^k{)}^2+\sum _{j=1}^p(r_j^k{)}^2=1.$$

2. Taking the limit over the subsequence, we have

   $$(t_0^{\ast }{)}^2+\sum _{i=1}^m(t_i^{\ast }{)}^2+\sum _{j=1}^p(r_j^{\ast }{)}^2=1.$$

3. Hence, all of them cannot be zero.

(4) Complementary violation conditions

1. Assume that $I\cup J$ is not empty.

2. Let $\mathcal{K}=\{k_1,k_2,\dots ,\}$ denote the index set of the convergent subsequence of $\{(t_0^k,t_1^k,\dots ,t_m^k,r_1^k,\dots ,r_p^k)\}$.

3. Let $i\in I$.

   1. We have $t_i^{\ast }>0$.

   2. Then for all sufficient large $k$ in $\mathcal{K}$, we have $t_i^k{t}_i^{\ast }>0$ as $t_i^k$ should be sufficiently close to $t_i^{\ast }$.

   3. From the definitions of $t_i^k$ and ${\chi }_i^k$, we must have $t_i^k{g}_i^{+}({\mathbf{x}}^k)>0$ for all sufficient large $k$ in $\mathcal{K}$.

   4. By definition, $g_i^{+}({\mathbf{x}}^k)\ge 0$ and $g_i^{+}({\mathbf{x}}^k)>0$ when $g_i({\mathbf{x}}^k)>0$.

   5. Hence we must have $t_i^k{g}_i({\mathbf{x}}^k)>0$ for all sufficient large $k$ in $\mathcal{K}$.

4. Let $j\in J$.

   1. We have $r_j^{\ast }\ne 0$.

   2. Then for all sufficiently large $k$ in $\mathcal{K}$, we have $r_j^k\approx r_j^{\ast }$. Hence $r_j^k\ne 0$ and $r_j^k$ has the same sign as $r_j^{\ast }$.

   3. Hence for all sufficiently large $k$ in $\mathcal{K}$, we have $r_j^k{r}_j^{\ast }>0$.

   4. from the definitions of $r_j^k$ and ${\xi }_j^k$, we see that for all sufficiently large $k$ in $\mathcal{K}$, we must have $r_j^k{h}_j({\mathbf{x}}^k)>0$.

5. Hence for all sufficiently large $k$ in $\mathcal{K}$, we have

   $$t_i^k{g}_i({\mathbf{x}}^k)>0\mathrm{\forall }i\in I\text{ and }{r}_j^k{h}_j({\mathbf{x}}^k)>0\mathrm{\forall }j\in J.$$

6. This means that $g_i^{+}({\mathbf{x}}^k)>0$ for every $i\in I$ and $h_j({\mathbf{x}}^k)\ne 0$ for every $j\in J$ for all sufficiently large $k$ in $\mathcal{K}$.

7. This establishes that for all sufficiently large $k$ in $\mathcal{K}$, we have ${\mathbf{x}}^k\ne {\mathbf{x}}^{\ast }$. Otherwise the inequality and equality constraints cannot be violated.

8. Recall that we established that

   $$F^k({\mathbf{x}}^k)=f({\mathbf{x}}^k)+\frac{k}{2}\sum _{i=1}^m(g_i^{+}({\mathbf{x}}^k){)}^2+\frac{k}{2}\sum _{j=1}^p(h_j({\mathbf{x}}^k){)}^2+\frac{1}{2}\Vert {\mathbf{x}}^k-{\mathbf{x}}^{\ast }{\Vert }^2\le f({\mathbf{x}}^{\ast })$$

   for every $k$.

9. Hence for all sufficiently large $k$ in $\mathcal{K}$, we must have

   $$f({\mathbf{x}}^k)<f({\mathbf{x}}^{\ast })$$

   since at least one of $(g_i^{+}({\mathbf{x}}^k){)}^2$ and $(h_j({\mathbf{x}}^k){)}^2$ is positive for every sufficiently large $k$.

10. We form the desired sequence $\{{\mathbf{x}}_l\}$ satisfying all the necessary criteria by picking up all the entries corresponding to sufficiently large $k$ in $\mathcal{K}$ from $\{{\mathbf{x}}^k\}$.

11. It remains to show the magnitude property of terms $h_j({\mathbf{x}}^k)$ and $g_i^{+}({\mathbf{x}}^k)$.

12. For the remaining argument, without loss of generality, we shall assume that $\{{\mathbf{x}}^k\}$ is the subsequence chosen above.

TBD the argument below is not complete.

1. We see that

   $$\begin{array}{rl}({\delta }^k{)}^2& =1+\sum _{i=1}^m({\chi }_i^k{)}^2+\sum _{j=1}^p({\xi }_j^k{)}^2\\ & =1+\sum _{i=1}^m(k{g}_i^{+}({\mathbf{x}}^k){)}^2+\sum _{j=1}^p(k{h}_j({\mathbf{x}}^k){)}^2\\ & \ge 1+kw({\mathbf{x}}^k{)}^2.\end{array}$$

2. For every $i\notin I$, we have $t_i^{\ast }=0$.

3. Hence $\underset{k\to \mathrm{\infty }}{lim}{t}_i^k=0$.

4. Hence $\underset{k\to \mathrm{\infty }}{lim}\frac{{\chi }_i^k}{{\delta }^k}=0$.

5. Hence

   $$\underset{k\to \mathrm{\infty }}{lim}\frac{({\chi }_i^k{)}^2}{1+\sum _{i=1}^m({\chi }_i^k{)}^2+\sum _{j=1}^p({\xi }_j^k{)}^2}=0.$$

6. Hence

   $$\underset{k\to \mathrm{\infty }}{lim}\frac{(k{g}_i^{+}({\mathbf{x}}^k){)}^2}{1+\sum _{i=1}^m(k{g}_i^{+}({\mathbf{x}}^k){)}^2+\sum _{j=1}^p(h_j({\mathbf{x}}^k){)}^2}=0.$$

7. We have

   $$0\le \frac{(k{g}_i^{+}({\mathbf{x}}^k){)}^2}{1+\sum _{i=1}^m(k{g}_i^{+}({\mathbf{x}}^k){)}^2+\sum _{j=1}^p(h_j({\mathbf{x}}^k){)}^2}\le \frac{(k{g}_i^{+}({\mathbf{x}}^k){)}^2}{1+kw({\mathbf{x}}^k{)}^2}.$$

The complementary violation condition (CV) in (4) is stronger than the traditional complementary slackness (CS) condition.

1. If $t_i^{\ast }>0$ for some inequality constraint $g_i$, then the inequality $g_i(\mathbf{x})\le 0$ must be violated arbitrarily close to ${\mathbf{x}}^{\ast }$.

2. In contrast, the CS condition only states that $g_i({\mathbf{x}}^{\ast })=0$. It doesn’t say anything about the violation of the constraint near the local optimal.

3. CV states that there exists a sequence of $X$ converging to ${\mathbf{x}}^{\ast }$ such that the equality and inequality constraints are violated at every point in the sequence corresponding to the nonzero Lagrangian multipliers.

4. This sequence also has the property that the amount of violation in the constraints corresponding to zero Lagrange multipliers is negligible via the following conditions.

   $$\begin{array}{r}{g}_i^{+}({\mathbf{x}}_k)=o(w({\mathbf{x}}_k))\mathrm{\forall }i\notin I,\\ & |h_j({\mathbf{x}}_k)|=o(w({\mathbf{x}}_k))\mathrm{\forall }j\notin J.\end{array}$$

Corollary 10.6 (Enhanced Fritz-John conditions regular case)

In Theorem 10.82, if $X$ is regular at ${\mathbf{x}}^{\ast }$, then

$$-(t_0^{\ast }\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }))\in T_X({\mathbf{x}}^{\ast }{)}^{\circ }.$$

Equivalently

$$⟨\mathbf{y},(t_0^{\ast }\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }))⟩\ge 0\mathrm{\forall }\mathbf{y}\in T_X({\mathbf{x}}^{\ast }).$$

10.8.5.3. Lagrangian Stationarity

Observation 10.10 (Lagrangian stationarity)

In Theorem 10.82, assume that $X$ is regular at ${\mathbf{x}}^{\ast }$. Further assume that $t_0^{\ast }>0$ is positive.

By normalization of the scalars, the gradient inequality reduces to

$$-(\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }))\in T_X({\mathbf{x}}^{\ast }{)}^{\circ }.$$

Equivalently

$$⟨\mathbf{y},(\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }))⟩\ge 0\mathrm{\forall }\mathbf{y}\in T_X({\mathbf{x}}^{\ast }).$$

This is identical to the Lagrangian stationarity condition (1) in Definition 10.33.

Hence if $X$ is regular at ${\mathbf{x}}^{\ast }$ and $t_0^{\ast }=1$, then the vector $({\mathbf{t}}^{\ast },{\mathbf{r}}^{\ast })=\{t_1^{\ast },\dots ,t_m^{\ast },r_1^{\ast },\dots ,r_m^{\ast }\}$ is a Lagrangian multiplier vector that satisfies the CV condition.

10.8.5.4. LICQ

Observation 10.11 (Linear independence constraint qualification)

In Theorem 10.82, assume that $X=\mathbb{V}$. Then $X$ is normal and $T_X({\mathbf{x}}^{\ast })=\mathbb{V}$.

1. Condition (1) reduces to

   $$t_0^{\ast }\mathrm{\nabla }f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast })=\mathbf{0}.$$

2. Further, add the linear independence constraint qualification (LICQ) assumption at ${\mathbf{x}}^{\ast }$; i.e., the gradients $\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast }),i\in \mathcal{A}({\mathbf{x}}^{\ast })$ and $h_j({\mathbf{x}}^{\ast }),j=1,\dots ,p$ are linearly independent;

3. Then $t_0^{\ast }\ne 0$ must be true.

4. Otherwise, the linear independence condition would be violated.

5. It follows that Lagrangian stationarity is satisfied and there exists a Lagrangian multiplier vector.

6. We thus obtain the classical Lagrangian multiplier theorem based on KKT conditions Theorem 10.79.

10.8.6. Informative Lagrange Multipliers

Lagrange multiplier vectors may provide a significant amount of sensitivity information by indicating which constraints to violate in order to effect a reduction in objective function value. In general, if the multipliers are informative, then the larger the coefficient for a constraint, the more sensitive is the objective function to the cost.

Definition 10.34 (Informative Lagrange multiplier vector)

A Lagrange multiplier vector (as defined in Definition 10.33 for the problem (10.20)) is called an informative multiplier vector if it satisfies the complementary violation condition of enhanced Fritz-John conditions Theorem 10.82.

Definition 10.35 (Minimal Lagrange multiplier vector)

Let ${\mathbf{x}}^{\ast }$ be a local minimum of the problem (10.20). Let $({\mathbf{t}}^{\ast },{\mathbf{r}}^{\ast })$ be a Lagrange multiplier vector (as defined in Definition 10.33). Let $I=\{i|t_i^{\ast }>0\}$ and $J=\{j|r_j\ne 0\}$. Then $({\mathbf{t}}^{\ast },{\mathbf{r}}^{\ast })$ is called a minimal Lagrange multiplier vector if there is no other Lagrange multiplier vector with a support that is strictly contained in $I\cup J$.

Definition 10.36 (Strong Lagrange multiplier vector)

Let ${\mathbf{x}}^{\ast }$ be a local minimum of the problem (10.20). Let $({\mathbf{t}}^{\ast },{\mathbf{r}}^{\ast })$ be a Lagrange multiplier vector (as defined in Definition 10.33). Let $I=\{i|t_i^{\ast }>0\}$ and $J=\{j|r_j\ne 0\}$. Then $({\mathbf{t}}^{\ast },{\mathbf{r}}^{\ast })$ is called a strong Lagrange multiplier vector if it satisfies the following condition:

If the set $I\cup J$ is nonempty, then there exists a sequence $\{{\mathbf{x}}_k\}$ of $X$ such that ${\mathbf{x}}_k\to {\mathbf{x}}^{\ast }$ and for all $k$ we have:

$$\begin{array}{rl}& f({\mathbf{x}}^k)<f({\mathbf{x}}^{\ast });\\ & t_i^{\ast }{g}_i({\mathbf{x}}^k)>0,\mathrm{\forall }i\in I;\\ & r_j^{\ast }{h}_j({\mathbf{x}}^k)>0,\mathrm{\forall }j\in J.\end{array}$$

This condition is slightly weaker than the complementary violation condition. It makes no provisions for ensuring that the constraints corresponding to zero multipliers have negligibly small violation at each ${\mathbf{x}}^k$.

1. Every informative multiplier vector is a strong multiplier vector.

2. Every minimal multiplier vector is a strong multiplier vector.

3. Minimal multipliers are not necessarily informative.

4. Some multiplier vectors are both informative and minimal.

Theorem 10.83 (Existence of informative multipliers)

Let ${\mathbf{x}}^{\ast }$ be a local minimum of the problem (10.20). Assume that the tangent cone $T_X({\mathbf{x}}^{\ast })$ is convex and that the set of Lagrange multiplier vectors is nonempty. Then

1. The set of informative Lagrange multiplier vectors is nonempty.

2. The Lagrange multiplier vector which has the minimum norm is informative.

3. Every minimal Lagrange multiplier vector is strong.

10.8.7. Pseudonormality

The key issue with enhanced Fritz-John conditions is that it allows for $t_0^{\ast }$ to be zero.

1. We now introduce the notion of pseudonormal points in the constraint set $C$.

2. We show that if a local minimizer ${\mathbf{x}}^{\ast }$ is a pseudonormal point, then $t_0^{\ast }\ne 0$.

3. Hence, at pseudonormal points, the constraint set $C$ admits Lagrange multiplier vectors.

Definition 10.37 (Pseudonormal vector)

We say that a feasible vector ${\mathbf{x}}^{\ast }$ for the problem (10.20) is pseudonormal if one cannot find scalars $t_1,\dots ,t_m,r_1,\dots ,r_p$ and a sequence $\{{\mathbf{x}}_k\}$ of $X$ such that

1. The gradients of constraint functions at ${\mathbf{x}}^{\ast }$ satisfy:

   $$-(\sum _{i=1}^m{t}_i\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }))\in {\tilde{N}}_X({\mathbf{x}}^{\ast }).$$

2. Inequality multipliers are nonnegative: $t_i\ge 0$ for every $i=1,\dots ,m$.

3. Multipliers for inactive inequality constraints are zero. $t_i=0$ for every $i\notin \mathcal{A}({\mathbf{x}}^{\ast })$ where $\mathcal{A}({\mathbf{x}}^{\ast })$ denotes the set of active inequality constraints at ${\mathbf{x}}^{\ast }$;

   $$\mathcal{A}({\mathbf{x}}^{\ast })=\{i\in 1,\dots ,m|g_i({\mathbf{x}}^{\ast })=0\}.$$

4. The sequence $\{{\mathbf{x}}_k\}$ converges to ${\mathbf{x}}^{\ast }$ (i.e., ${\mathbf{x}}_k\to {\mathbf{x}}^{\ast }$) and

   $$\sum _{i=1}^m{t}_i{g}_i({\mathbf{x}}_k)+\sum _{j=1}^p{r}_j{h}_j({\mathbf{x}}_k)>0,\mathrm{\forall }k.$$

Theorem 10.84 (Pseudonormality and EFJ scalars)

Let ${\mathbf{x}}^{\ast }$ be a local minimizer for the problem (10.20). Let $t_0^{\ast },t_1^{\ast },\dots ,t_m^{\ast },r_1^{\ast },\dots ,r_p^{\ast }$ be the enhanced Fritz-John scalars satisfying the conditions in Theorem 10.82.

If ${\mathbf{x}}^{\ast }$ is a pseudonormal vector of the constraint set $C$ defined in (10.21), then $t_0^{\ast }\ne 0$.

Proof. We shall show this by contradiction.

1. Assume that ${\mathbf{x}}^{\ast }$ is a local minimizer for the problem (10.20).

2. Then there exist EFJ scalars $t_0^{\ast },t_1^{\ast },\dots ,t_m^{\ast },r_1^{\ast },\dots ,r_p^{\ast }$ satisfying the conditions in Theorem 10.82.

3. For contradiction assume that ${\mathbf{x}}^{\ast }$ is a pseudonormal vector and $t_0^{\ast }=0$.

4. Since $t_0^{\ast },t_1^{\ast },\dots ,t_m^{\ast },r_1^{\ast },\dots ,r_p^{\ast }$ are EFJ scalars, hence

   $$-(\sum _{i=1}^m{t}_i^{\ast }\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^p{r}_j^{\ast }\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast }))\in {\tilde{N}}_X({\mathbf{x}}^{\ast }).$$

5. $t_i^{\ast }\ge 0$ for every $i=1,\dots ,m$.

6. The scalars $t_1^{\ast },\dots ,t_m^{\ast },r_1^{\ast },\dots ,r_p^{\ast }$ are not equal to $0$.

7. Hence the index set $I\cup J$ is not empty, where

   $$I=\{i>0|t_i^{\ast }>0\},J=\{j|r_j^{\ast }\ne 0\}.$$

8. Hence there exists a sequence $\{{\mathbf{x}}_k\}$ of $X$ that converges to ${\mathbf{x}}^{\ast }$ and is such that for all $k$

   $$\begin{array}{rl}& f({\mathbf{x}}_k)<f({\mathbf{x}}^{\ast }),\\ & t_i^{\ast }{g}_i({\mathbf{x}}_k)>0\mathrm{\forall }i\in I,\\ & r_j^{\ast }{h}_j({\mathbf{x}}_k)>0\mathrm{\forall }j\in J,\\ & g_i^{+}({\mathbf{x}}_k)=o(w({\mathbf{x}}_k))\mathrm{\forall }i\notin I,\\ & |h_j({\mathbf{x}}_k)|=o(w({\mathbf{x}}_k))\mathrm{\forall }j\notin J,\end{array}$$

   where $g_i^{+}(\mathbf{x})=max\{0,g_i(\mathbf{x})\}$ and

   $$w(\mathbf{x})=min\{\underset{i\in I}{min}{g}_i^{+}(\mathbf{x}),\underset{j\in J}{min}|h_j(\mathbf{x})|\}.$$

9. Hence the sequence $\{{\mathbf{x}}_k\}$ with ${\mathbf{x}}_k\to \mathbf{x}$ satisfies

   $$\sum _{i=1}^m{t}_i^{\ast }{g}_i({\mathbf{x}}_k)+\sum _{j=1}^p{r}_j^{\ast }{h}_j({\mathbf{x}}_k)>0\mathrm{\forall }k$$

   since at least one of these multipliers is nonzero.

10. Multiplier for every inactive inequality constraint must be zero. Otherwise, the complementary violation condition will be violated.

11. Hence $t_1^{\ast },\dots ,t_m^{\ast },r_1^{\ast },\dots ,r_p^{\ast }$ are the scalars and $\{{\mathbf{x}}_k\}$ is a sequence of $X$ satisfying all the conditions in Definition 10.37.

12. Hence ${\mathbf{x}}^{\ast }$ cannot be a pseudonormal vector of $C$.

10.8.8. Constraint Qualifications

We now introduce different constraint qualifications which ensure that a point ${\mathbf{x}}^{\ast }$ is pseudonormal.

10.8.8.1. Linearly Independent Constraint Qualifications

Criterion 10.1 (CQ1: linearly independent constraint qualifications)

$X=\mathbb{V}$ and ${\mathbf{x}}^{\ast }$ satisfies LICQ; i.e., the active inequality constraint gradients $\mathrm{\nabla }{g}_i({\mathbf{x}}^{\ast })$ for all $iin\mathcal{A}({\mathbf{x}}^{\ast })$ and the equality constraint gradients $\mathrm{\nabla }{h}_j({\mathbf{x}}^{\ast })$ for all $j=1,\dots ,p$ are linearly independent.

10.8.8.2. AHU/MF Constraint Qualifications

10.8.8.3. Affine Equality and Concave Inequality Constraints