7 Inequality constraints
Let’s introduce now the problem of minimizing a function f(\bm{x}):\Bbb{R}^n\rightarrow R considering a set of p inequalities constrains in the form g_k(\bm{x}) \geq 0.
\begin{aligned} \textrm{minimize:} \qquad & f(\bm{x}) \\ \textrm{subject to:}\qquad & g_k(\bm{x}) \geq 0 \qquad k = 1,\dots,p \end{aligned}
The first approach to this problem is by trying to transform the inequality constraints g_k into equality one (so having h_k(\bm{x}) = 0). This can be done considering that each constraint can be expressed as
g_k(\bm{x}) = \varepsilon_k^2 \geq 0 \quad \implies \quad h_k(\bm{x},\varepsilon_k) = g_k(\bm{x}) - \varepsilon_k^2 = 0
Doing this process for each constraint we can determine a minimization problem that depends both on the function variable \bm{x} but also on the so called slack variables \bm{\varepsilon}:
\begin{aligned} \textrm{minimize:} \qquad & f(\bm{x}) \\ \textrm{subject to:}\qquad & h_k(\bm{x}, \bm{\varepsilon}) = 0 \qquad k = 1,\dots,p \end{aligned}
This kind of problem increases the computational costs because it increases the variable to minimize from n to n+p.
We used the expression \varepsilon_k^2 and not \varepsilon_k because with this expression we don’t need to specify one more inequality \varepsilon_k \geq 0.
Example 7.1 Let’s consider the following problem:
\begin{aligned} \textrm{minimize:} \qquad & f(x,y) = x^2 \\ \textrm{subject to:}\qquad & x^2+y^2\leq 1 \\ & x+y \geq 0 \end{aligned}
In order to solve this problem we have to reduce the inequality constraints to equality ones; considering the first constraint, that has to be expressed in the form g_1(x,y) \geq 0 and so
\begin{aligned} g_1(x,y) & = 1 -x^2-y^2 \geq 0 \\ & \Downarrow \\ h_1(x,y,\varepsilon_1) & = 1-x^2-y^2-\varepsilon_1^2 \end{aligned}
At the same way it’s possible to express the second inequality as the a constraint
h_2(x,y,\varepsilon_2) = x+y-\varepsilon_2^2
With this expression being set the problem reduces to the form
\begin{aligned} \textrm{minimize:} \qquad & f(x,y,\epsilon_1,\epsilon_2) = x^2 \\ \textrm{subject to:}\qquad & h_1(x,y,\epsilon_1,\epsilon_2) = 1- x^2 - y^2 - \epsilon_1^2 = 0 \\ & h_2(x,y,\epsilon_1,\epsilon_2) = x+y - \varepsilon_2^2 = 0 \end{aligned}
With the problem this stated we can build the lagrangian that depend’s on both the original variables x,y but also the slack variables \epsilon_1,\epsilon_2 and so
\begin{aligned} \mathcal{L}(\underbrace{x,y,\epsilon_1,\epsilon_2}_{\bm{x}},\underbrace{\lambda_1,\lambda_2}_{\bm{\lambda}}) &= f(\bm{x}) - \lambda_1 h_1(\bm{x}) - \lambda_2 h_2(\bm{x}) \\ & = x^2 - \lambda_1 \big( 1- x^2-y^2-\epsilon_1^2 \big) - \lambda_2 \big( x+y-\epsilon_2^2 \big) \end{aligned}
To find the local minimum point we can start using the first necessary condition of the lagrangian multiplier, so by determining all the stationary point such that \nabla \mathcal{L} = \bm{0}; in practise this means solving the following non linear system of 6 equations in 6 variables:
\left\{ \begin{aligned} \partial/\partial_x \mathcal{L}:&& 2x -2\lambda_1x -\lambda_2 &= 0 \\ \partial/\partial_y \mathcal{L} :&& 2\lambda_1 y - \lambda_2 &= 0\\ \partial/\partial_{\epsilon_1}\mathcal{L} :&& 2\lambda_1\epsilon_1 &= 0 \\ \partial/\partial_{\epsilon_2}\mathcal{L} :&& 2\lambda_2 \epsilon_2 &= 0 \\ \partial/\partial_{\lambda_1} \mathcal{L} :&& x^2+y^2 + \epsilon_1^2-1 &= 0 \\ \partial/\partial_{\lambda_2}\mathcal{L} :&& x + y - \epsilon_2^2 &= 0 \end{aligned} \right.
Solving minimization problems with inequality constraints can be tricky using the lagrangian multiplier method and so other algorithm (like the KKT that’s going to be explained) are usually preferred. However this kind of system can be solved by cases; considering in fact the second and third equations we can discriminate the solution considering the various combination when \epsilon_1, \epsilon_2 are equal (or not) to zero.
Considering for example the case \epsilon_1 = \epsilon_2 = 0 the non linear system reduces to the form
\left\{ \begin{aligned} 2x - 2\lambda_1 x - \lambda_2 &= 0 \\ 2\lambda_1 y - \lambda_2 &= 0 \\ x^2+y^2-1 &= 0 \\ x + y &= 0 \end{aligned} \right.
Considering that the first two expressions are linear in respect to \lambda_1,\lambda_2 it’s possible to determine their value directly in terms of x,y:
\lambda_1 = \frac{x}{y-x} \qquad \lambda_2 = 2 \frac{xy}{y-x}
Considering instead the last 2 equations we have a non linear system that can be also computed by cases; from the last equation we have in fact that y = -x and so
1-x^2-x^2 = 0 \qquad \implies \quad x = \pm \frac{1}{\sqrt{2}}
At this end of this process we defined two stationary points for the lagrangian:
\begin{aligned} \big(x,y,\epsilon_1,\epsilon_2,\lambda_1,\lambda_2\big) & = \left( \frac 1 {\sqrt 2} , - \frac{1}{\sqrt 2},0,0,-\frac 1 2, \frac{\sqrt 2}{2} \right), \\ \big(x,y,\epsilon_1,\epsilon_2,\lambda_1,\lambda_2\big) & = \left( - \frac 1 {\sqrt 2} , \frac{1}{\sqrt 2},0,0,\frac 1 2, -\frac{\sqrt 2}{2} \right). \end{aligned}
Solving symbolically this system of equation with a computer the lonely real solution of the problem (that determines a local minimum) is expressed in the form
\big(x,y,\epsilon_1,\epsilon_2,\lambda_1,\lambda_2\big)=\left( 0, \sqrt{-\epsilon_1^2 + 1 }, \epsilon_1 ,\sqrt[4]{1 - \epsilon_1^2}, 1, 1 \right)
In order for the square roots to exists the value \epsilon_1^2 should fit inside the range [0,1] and so the local minimum of the problem can be found on the vertical line
(x,y) = (0,k) \qquad k \in [0,1]
Karush-Kuhn-Tucker conditions
The Karush-Kuhn-Tucker (KKT) conditions are a set of necessary and sufficient conditions (first and second order) that allows to describe if a point \bm{x}^\star is a minimum point of a minimization problem subjected to equality and inequality constraints, so for the problem
\begin{aligned} \textrm{minimize:} \qquad & f(\bm{x}) \\ \textrm{subject to:}\qquad \ & h_k(\bm{x}) = 0 \qquad && k=1,\dots, m\\ & g_k(\bm{x}) \geq 0 &&k = 1,\dots,p \end{aligned}
where f,h_k,g_k: \Bbb{R}^n\rightarrow \Bbb{R} are real evaluated function.
In order to describe this conditions it’s important to define *set of the active constraints** \mathcal{A} as
\mathcal{A}(\bm{x}^\star) = \big\{ k \ | \ g_k(\bm{x}^\star) = 0 \big\}
This means that given the constraints g\in C(\Bbb{R}^n) it’s defined as if it happens that the point \bm{x}^\star is such that g(\bm{x}^\star) = 0, so in practical way it’s in the between activating and not activating the constraints.
Qualified constraints
Given \bm{g}\in C^1(\Bbb{R}^p,\Bbb{R}^n) and \bm{h} \in C^1(\Bbb{R}^m,\Bbb{R}^n) respectively the inequality and equality constraints map, then a point \bm{x}^\star is defined qualified if the gradients of the active constraints (and the equality ones) are linearly independent, and so
\big\{ \nabla g_k(\bm{x}^\star) \ : \ k \in \mathcal A(\bm{x}^\star) \big\} \bigcup \big\{ \nabla h_1(\bm{x}^\star),\dots, \nabla h_m(\bm{x}^\star) \big\}
are linearly independent
Example 7.2 (qualification of a point) Considering the minimization problem started in example Example 5.2 stated as
\begin{aligned} \textrm{minimize:} \qquad & f(x,y,z) = x - y + z^2 \\ \textrm{subject to:} \qquad & h_1(x,y,z) = x^2 + y^2 - 2 = 0 \\ & h_2(x,y,z) = x+z-1 = 0 \end{aligned}
and considering the candidate point of minimum (resulting from the solution of the non-linear system)
\begin{aligned} x^\star &= \frac{\sqrt 3}{2} - \frac{1}{2}\\ y^\star &= \frac 1 2 + \frac{\sqrt 3}{2} \\ z^\star &= \frac 3 2 - \frac{\sqrt 3}{2} \\ \lambda_1^\star & = \frac{1}{2} - \frac{\sqrt3}{2} \\ \lambda_2^\star &= 3-\sqrt{3} \end{aligned}
In order to check if the chosen point is qualified it’s necessary to check if the gradients of the equality constraint and the active ones (that in this case are not present because there aren’t inequality constraints) are linearly independent. In order to solve this problem firstly we need to build the matrix H represent the gradients of the constraints:
H(x,y,z) = \begin{bmatrix} \nabla h_1(x,y,z) \\ \nabla h_2(x,y,z) \end{bmatrix} = \begin{bmatrix} 2x & 2y & 0 \\ 1 & 0 & 1 \end{bmatrix}
\implies \qquad H^\star= H(x^\star,y^\star,z^\star) = \begin{bmatrix} \sqrt 3 - 1 & 1 + \sqrt 3 & 0 \\ 1 & 0 & 1 \end{bmatrix}
It’s straightforward to see that the lines of the matrix H^\star are linearly independent, considering in fact the rank of H^\star by analysing the columns we see that’s equal to 2, so equalizing the number of the constraints.
KKT first order necessary condition
Let f\in C^1(\Bbb{R}^n) a function to minimize subjected to the inequality
\bm{g}\in C^1(\Bbb{R}^n,\Bbb{R}^p)
and equality
\bm{h} \in C^1(\Bbb{R}^n,\Bbb{R}^m)
constraint maps. If \bm{x}^\star satisfy constraint qualification then necessary condition for \bm{x}^\star to be a local minima is that that exists m+p scalars \lambda_i,\mu_j such that all the following conditions are satisfied:
\begin{aligned} \nabla_{\bm{x}} \mathcal{L} \big(\bm{x}^\star,\bm{\lambda}^\star,\bm{\mu}^\star\big) & = \bm{0} \\ h_k\big(\bm{x}^\star\big) & = 0 \qquad && k = 0,\dots, m\\ g_k\big(\bm{x}^\star\big) & \geq 0 && k = 0,\dots, p \\ \mu_k^\star g_k\big(\bm{x}^\star\big) & = 0 && k = 0,\dots, p \\ \mu_k^\star & \geq 0 && k = 0,\dots,p \end{aligned} \tag{7.1}
where the lagrangian is in this case defined as
\mathcal{L}(\bm{x},\bm{\lambda},\bm{\mu}) = f(\bm{x}) - \sum_{k=1}^p \mu_k g_k(\bm{x}) - \sum_{k=1}^m \lambda_k h_k(\bm{x})
Example 7.3 Solving minimization problem with the KKT conditions is generally more easier; considering the case of the minimization problem in Example 7.1 the lagrangian will depend only on 4 parameter (instead of 6 as in that example):
\mathcal{L}(x,y,\mu_1,\mu_2) = x^2 - \mu_1\big(1-x^2-y^2\big) - \mu_2\big(x+y\big)
Using the first order KKT condition the main non linear system to solve is in the form
\left\{\begin{aligned} \left.\begin{aligned} 2x +2\mu_1x - \mu_2 &= 0 \\ 2 \mu_1 y - \mu_2 &= 0 \end{aligned} \right\} & \quad \nabla_{\bm{x}} \mathcal{L}\big(\bm{x}, \bm{\lambda}\big) \\ \left. \begin{aligned} \mu_1\big(1-x^2-y^2\big) & = 0 \\ \mu_2 \big(x+y\big) & = 0 \end{aligned} \right\} & \quad \mu_k g_k\big(\bm{x} \big) = 0\\ \mu_1,\mu_2 \geq 0 \quad & \end{aligned} \right.
This system of four non linear equations (the conditions \mu_1,\mu_2\geq0 are easier to consider) can be solved by cases:
If \mu_1 = \mu_2 = 0 then the last two equalities are always verified, while the first two becomes
\begin{cases} 2x = 0 \\ 0 = 0 \end{cases} this means that x = 0, while y is a free parameter that must satisfy both the constraints x+y\geq 0 (so that y \geq 0) and 1-x^2-y^2 \geq 0 (and so 1-y^2 \geq 0 that determines -1 \leq y \leq 1): considering both condition at the same time we have that \begin{aligned} & \begin{cases} y \geq 0 \\ -1 \leq y \leq 1 \end{cases} \quad \implies \quad \\[1em] & \textrm{solution: } x = \mu_1 = \mu_2 = 0 \quad y \in [0,1] \end{aligned}
When considering \mu_1 \neq 0 and \mu_2 = 0 the system of equations become \begin{cases} 2x + 2 \mu_1x = 0 \\ 2\mu_1 y = 0 \\ \mu_1\big(1-x^2-y^2\big) = 0 \end{cases} Based on the assumption of the value \mu_1, from the second equation we determine that y must be equal to 0 and so the third equation becomes 1-x^2 = 0 whose solutions are \pm 1. Considering that the first equation can be factorised as 2x(1+\mu_1) = 0 (and x\neq 0), then in order to satisfy the relation \mu_1 must be -1, but this imply that \mu_1 is negative and it’s an unacceptable solution, so for \mu_1 \neq 0,\mu_2=0 no solutions of the system can be found;
Considering instead \mu_1 = 0 and \mu_2 \neq 0 the system becomes \begin{cases} 2x - \mu_2 = 0 \\ -\mu_2 = 0 \\ \mu_2(x+y) = 0 \end{cases} The second equation states that \mu_2 must be equal to 0 and so the solution of this problem is the same as the first case considered;
Considering both variables \mu_1,\mu_2 \neq 0 we have to solve the full systems; considering the last two equations we have that \begin{aligned} & \begin{cases} x+y = 0 \\ 1-x^2-y^2 = 0 \end{cases} \\ & \implies\quad x = -y \\ & \implies\quad 1-2x^2 = 0 \end{aligned} and so it means that the two possible solution for the systems are (x,y) = \left( \pm \frac{1}{\sqrt{2}}, \mp \frac{1}{\sqrt{2}} \right). Considering the first case where x = 1/\sqrt 2 the first two equations become \begin{aligned} & \begin{cases} \frac{2}{\sqrt 2} (1+\mu_1) - \mu_2 = 0 \\ -\frac 2 {\sqrt 2} \mu_1 - \mu_2 = 0 \end{cases} \\ & \implies \quad \mu_2 = - \frac 2 {\sqrt 2} \mu_1 \\ & \implies \quad \frac{4}{\sqrt 2} \mu_1 + \frac{2}{\sqrt 2} = 0 \\ & \implies \quad \mu_1 = - \frac{1}{2} \qquad \mu_2 = \frac{1}{\sqrt{2}} \end{aligned} In this case \mu_1 < 0 is an unacceptable solution of the problem, and also considering the point x = -1/\sqrt{2} the system becomes with no considerable solutions \begin{aligned} & \begin{cases} -\dfrac{2}{\sqrt 2} (1+\mu_1) - \mu_2 = 0 \\ \dfrac{2}{\sqrt 2} \mu_1 - \mu_2 = 0 \end{cases} \\ & \implies \quad \mu_1 = -\frac{1}{2}\quad \mu_2 = - \frac{1}{\sqrt{2}} \end{aligned}
With all this considerations done the point of local minimum relies on the points
(x,y) = (0,k) \qquad k\in[0,1]
KKT second order necessary conditions
Given a function f \in C^1(\Bbb{R}^n) to minimize subject to the equality \bm{h}\in C^1(\Bbb{R}^n,\Bbb{R}^m) and inequality \bm{g}\in C^1(\Bbb{R}^n,\Bbb{R}^p) constraint maps, then necessary conditions for a point \bm{x}^\star (that satisfies the constraints) to be a local minima is that exists m+p scalars \lambda_i,\mu_i such that satisfy the first order conditions (Equation 7.1) and
\bm{z}^T \, \nabla^2_{\bm{x}} \mathcal{L}\big(\bm{x}^\star,\bm{\lambda}^\star,\bm{\mu}^\star\big) \, \bm{z} \geq 0 \tag{7.2}
for all vector \bm{z} such that
\begin{aligned} (i) \qquad && \nabla h_k(\bm{x}^\star) \bm{z} & = 0 && k = 1,\dots,m \\ (ii) \qquad &&\nabla g_k(\bm{x}^\star) \bm{z} & = 0 && \textrm{for all } k\in \mathcal{A}(\bm{x}^\star) \textrm{ and } \mu_k > 0 \\ (iii) \qquad &&\nabla g_k(\bm{x}^\star) \bm{z} & \geq 0 && \textrm{for all } k\in \mathcal{A}(\bm{x}^\star) \textrm{ and } \mu_k = 0 \end{aligned}
In general the conditions (ii) and (iii) are hard to verify and so to have a less accurate necessary condition (by having a smaller set of possible vector \bm{z}), and so improving the chance of considering point that don’t belong to the original domain, this two conditions can be substitute with the expression
\nabla g_k(\bm{x}^\star) \bm{z} = 0 \qquad \textrm{for all } k \in \mathcal{A}(\bm{x}^\star)
In other words, the second-order necessary condition (and similarly the sufficient one) states (from Equation 7.2) that the matrix \nabla^2_{\bm{x}}\mathcal{L} must be positive semidefinite on the kernel of the active and equality constraints.
Example 7.4 (kernel of the active constraints) Continuing examples Example 5.2 and Example 7.2, on the minimum candidate point (x^\star,y^\star,z^\star) we have the following matrix for the active constraints:
H^\star= \begin{bmatrix} \sqrt{3}- 1 & 1 + \sqrt{3} & 0 \\ 1 & 0 & 1 \end{bmatrix}
Computing the kernel of the active constraints means so solving the following system of linear equation determined by H^\star \bm{x} = \bm{0} and so
\begin{bmatrix} \sqrt 3 - 1 & 1 + \sqrt 3 & 0 \\ 1 & 0 & 1 \end{bmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix}0 \\ 0\end{pmatrix}
resulting in
\begin{cases} (\sqrt 3 - 1) x + (1 + \sqrt 3) y = 0 \\ x + z = 0 \end{cases}
Having 3 unknowns but only 2 equation means that we have to solve the problem in a parametric form; chosen z = t we have x = -t and so y = t \frac{\sqrt 3 - 1}{\sqrt 3 + 1}; choosing t = \sqrt 3 + 1 (to simplify the results) we obtain the generator K of the kernel as
\bm{K} = \begin{pmatrix} -\sqrt 3 - 1 \\ \sqrt 3 - 1 \\ \sqrt 3 +1 \end{pmatrix}
KKT second order sufficient conditions
Given a function f \in C^1(\Bbb{R}^n) to minimize subject to the equality \bm{h}\in C^1(\Bbb{R}^n,\Bbb{R}^m) and inequality \bm{g} \in C^1(\Bbb{R}^n,\Bbb{R}^p) constraint maps, then sufficient condition for a point \bm{x}^\star (that satisfies the constraints) to be a local minima is that exists m+p scalars \lambda_i,\mu_i such that satisfy the first order conditions (Equation 7.1) and
\bm{z}^T \, \nabla^2_{\bm{x}} \mathcal{L}\big(\bm{x}^\star,\bm{\lambda}^\star,\bm{\mu}^\star\big) \, \bm{z} > 0
for all vector \bm{z} such that
\begin{aligned} (i) \qquad && \nabla h_k(\bm{x}^\star) \bm{z} & = 0 && k = 1,\dots,m \\ (ii) \qquad &&\nabla g_k(\bm{x}^\star) \bm{z} & = 0 && \textrm{for all } k\in \mathcal{A}(\bm{x}^\star) \textrm{ and } \mu_k > 0 \\ (iii) \qquad &&\nabla g_k(\bm{x}^\star) \bm{z} & \geq 0 && \textrm{for all } k\in \mathcal{A}(\bm{x}^\star) \textrm{ and } \mu_k = 0 \end{aligned}
As in the previous case in order to have simpler calculation the third equation (iii) can be dropped (and so we obtain less accurate solution of the local minima).
Example 7.5 (second order check) Given the problem started in example Example 5.2 and carried on up to Example 7.4 states as
\begin{aligned} \textrm{minimize:} \qquad & f(x,y,z) = x - y + z^2 \\ \textrm{subject to:} \qquad & h_1(x,y,z) = x^2 + y^2 - 2 = 0 \\ & h_2(x,y,z) = x+z-1 = 0 \end{aligned}
we found a candidate for minimum point in
\begin{aligned} x^\star &= \frac{\sqrt 3}{2} - \frac 1 2 \\ y^\star &= \frac 1 2 + \frac{\sqrt 3} 2 \\ z^\star & = \frac 3 2 - \frac{\sqrt 3}{2} \\ \lambda_1^\star &= \frac 1 2 - \frac{\sqrt3}{2} \\ \lambda_2^\star &= 3-\sqrt 3 \end{aligned}
that present the matrix \bm{H}^\star for the active constraints with related kernel \bm{K}:
\bm{H}^\star= \begin{bmatrix} \sqrt 3 - 1 & 1 + \sqrt 3 & 0 \\ 1 & 0 & 1 \end{bmatrix} \qquad \bm{K} = \begin{bmatrix} -\sqrt 3 - 1 \\ \sqrt 3 - 1 \\ \sqrt 3 + 1 \end{bmatrix}
In order to check the second order necessary/sufficient condition we have to compute the hessian matrix \nabla^2_{\bm{x}} \mathcal{L} of the lagrangian that’s
\begin{aligned} \nabla^2_{\bm{x}} \mathcal{L} = \bm{L} & = \begin{bmatrix} -2 \lambda_1 & 0 & 0 \\ 0 & -2 \lambda_1 & 0 \\ 0 & 0 & 2 \end{bmatrix} \qquad \implies\\ \bm{L}^\star &= \begin{bmatrix} \sqrt 3 - 1 & 0 & 0 \\ 0 & \sqrt 3 - 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \end{aligned}
We have now to determine if this resulting matrix is (semi-)positive defined or not in the kernel of active constraints in order to determine if the point is a minimum or not; this mean performing the following matrix multiplication:
\begin{aligned} \alpha \bm{K}^T \bm{L}^\star \bm{K} \alpha & = \alpha \begin{bmatrix} -\sqrt 3 - 1 & \sqrt{3} - 1 & \sqrt{3} + 1 \end{bmatrix} \\ &\qquad \begin{bmatrix} \sqrt 3 - 1 & 0 & 0 \\ 0 & \sqrt 3 - 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} -\sqrt 3 - 1 \\ \sqrt 3 - 1 \\ \sqrt 3 + 1 \end{bmatrix}\alpha \\ & = \alpha \begin{bmatrix} -\sqrt 3 - 1 & \sqrt 3 - 1 & \sqrt 3 + 1 \end{bmatrix} \begin{bmatrix} -2 \\ 4 -2\sqrt 3 \\ \sqrt 3 + 1 \end{bmatrix}\alpha \\ & = \alpha \big( 2\sqrt{3} +2 + 4\sqrt{3} - 4 -6 + 2\sqrt{3} + 3 + 2\sqrt{3} +1 \big) \alpha \\ & = \big(10 \sqrt{3} - 4\big)\alpha^2 \end{aligned}
Observing that for \alpha \neq 0 the product is always greater then zero we have that the hessian L^\star is positive defined in the kernel of the active constraints, satisfying the second order sufficient condition that allow so to state that
\bm{x}^\star = \left( \frac{\sqrt{3}}{2} - \frac{1}{2}, \frac{1}{2}+ \frac{\sqrt{3}}{2}, \frac{3}{2}- \frac{\sqrt{3}}{2} \right) is a minimum.
Example 7.6 Given the problem
\begin{aligned} \textrm{minimize:}&& f(x,y) &= x^2 - xy \\ \textrm{subject to:}&& g_1(x,y) &= 1-x^2-y^2 \geq 0 \\ && g_2(x,y) &= 1- (x-1)^2-y^2 \geq 0 \end{aligned}
To solve this kind of problem using the KKT conditions we firstly need to build the lagrangian of the problem that’s equal to
\begin{aligned} \mathcal{L}(x,y,\mu_1,\mu_2) & = x^2-xy - \mu_1 \big(1-x^2-y^2\big) \\ & - \mu_2 \big[ 1- (x-1)^2 - y^2 \big] \end{aligned}
At this point it’s possible to construct the non linear system of equation whose solution are the stationary points candidate to be local minimum:
\left\{\begin{aligned} \left. \begin{aligned} 2x - y +2\mu_1 x + 2\mu_2(x-1) &= 0 \\ -x + 2 \mu_1 y +2 \mu_2 y &= 0 \end{aligned} \right\} & \quad \nabla_{\bm{x}} \mathcal{L}\big(\bm{x}, \bm{\lambda}\big) \\ \left. \begin{aligned} \mu_1 \big(1-x^2-y^2\big) & = 0 \\ \mu_2 \big[ 1- (x-1)^2 - y^2 \big] & = 0 \end{aligned} \right\} & \quad \mu_k g_k\big (\bm{x} \big) = 0\\ \mu_1,\mu_2 \geq 0 \quad & \end{aligned} \right.
This system can be solved by cases of the value of \mu_i and in particular
when \mu_1 = \mu_2 = 0 the system reduces to the form \begin{cases} 2x - y = 0 \\ - x = 0 \end{cases} \quad \implies \quad x = y = 0 This solution satisfy the constraints, in fact g_1(0,0) = 1 \geq 0 and g_2(0,0) = 0 \geq 0, so this point can be used to compute the second order conditions;
considering all the other cases of \mu_j the only other analytical solution to the system, found with
Mathematica, determines the point (x,y,\mu_1,\mu_2) = \left( \frac 1 2, \frac{\sqrt 3}{2}, \frac 1{\sqrt 3} - \frac 12 , \frac 1 2 - \frac{\sqrt{3}}{6} \right)
In order to consider now the second order necessary/sufficient conditions we have firstly to evaluate the gradient \nabla \bm{g} of the inequality constraint map (in respect to the variables x,y) resulting in the matrix
\nabla \bm{g} = \begin{bmatrix} -2x & -2y \\ - 2(x-1) & -2y^2 \end{bmatrix}
For the second order conditions is also important to define the hessian matrix of the lagrangian respect to the variables x,y:
\nabla_{\bm{x}}^2 \mathcal{L} = \begin{bmatrix} 2 + 2\mu1 + 2 \mu2 & -1 \\ -1 & 2\mu_1 + 2\mu_2 \end{bmatrix}
We have now to check the conditions for the two local minima candidates:
- in the first case when x=y = \mu_1 = \mu_2 = 0 the set of the active constraints is just the second inequality g_2: in fact we have that g_1(0,0) = 1 \neq 0 while g_2(0,0) = 0. In respect to this vector we have to compute it’s kernel (to determine the direction z on which verify the KKT condition) and in particular \nabla g_2(0,0) = \begin{bmatrix} 0\\ 2 \end{bmatrix} \quad \implies \quad \ker\big\{ \nabla g_2(0,0) \} = \alpha\begin{bmatrix} 1 \\ 0\end{bmatrix} Evaluating the expression \bm{z}^T \, \nabla_{\bm{x}}^2 \mathcal{L} \, \bm{z} for \bm{z}\in \ker\{\nabla g_2\} we obtain that \alpha \begin{bmatrix} 1 & 0 \end{bmatrix}\begin{bmatrix} 2 & - 1 \\ - 1 & 2\end{bmatrix}\begin{bmatrix}1 \\ 0\end{bmatrix} \alpha = 2\alpha^2
Example 7.7 (Sample Exam Question) Given the problem
\begin{aligned} \textrm{minimize:} \qquad & f(x,y,z) = x - y + z^2 \\ \textrm{subject to:} \qquad & h(x,y,z) = x^2 + y^2 - 2 = 0 \\ & g(x,y,z) = x^2-1 \geq 0 \end{aligned}
the solution can be obtained by using the KKT condition; in order to use them we firstly need to define the lagrangian
\mathcal{L} = f - \lambda h - \mu g
of the problem that in this is of the form
\mathcal{L}(x,y,z,\lambda,\mu) = x - y + z^2 - \lambda\big(x^2+y^2-2\big) - \mu \big(x^2 - 1\big)
The first order necessary condition allows to build the system of non-linear equation whose solution are candidates to be minimum point of f (respect to the constrains set), and so we have
\begin{cases} 1 -2 \lambda x - 2\mu x = 0 & : \partial/\partial_x \mathcal{L} \\ -1 - 2\lambda y = 0 & : \partial/\partial_y \mathcal{L} \\ -2z = 0 & : \partial/\partial_z \mathcal{L} \\ x^2 + y^2 - 2 = 0 & : h \\ x^2-1 \geq 0 & : g\\ \mu(x^2-1) = 0 &: \mu g\\ \mu \geq 0 & : \mu \end{cases}
Verifying that the point \bm{x}^\star = (1,1,0) is a candidate minimum with \lambda^\star = -\frac1 2 and \mu^\star = 1 (substituting the values in the system, all the relation are satisfied), the associated set of active constraints is represented by both h (in fact 1+1-2=0) and g (indeed 1-1=0) whose gradient can be regarded as
\begin{aligned} \nabla \mathcal A & = \begin{bmatrix} \nabla h \\ \nabla g \end{bmatrix} = \begin{bmatrix} 2x & 2y & 0 \\ 2x & 0 & 0 \end{bmatrix} \quad \implies \quad \\ \bm{H} & = \nabla \mathcal A(\bm{x}^\star) = \begin{bmatrix} 2 & 2 & 0 \\ 2 & 0 & 0 \end{bmatrix} \end{aligned}
The constraints are so qualified because the gradients are linearly independent and related kernel, obtained by solving the equation H\bm{x} = \bm{0}, gives a generator of the space in the form of \bm{K} = (0,0,1).
In order to determine if \bm{x}^\star is a minimum point using the second order necessary/sufficient KKT conditions it’s mandatory to compute the hessian \nabla^2_{\bm{x}} \mathcal{L} of the lagrangian:
\begin{aligned} \nabla^2_{\bm{x}}\mathcal{L} & = \begin{bmatrix} -2(\lambda+\mu) & 0 & 0 \\ 0 & -2\lambda & 0 \\ 0 & 0 & - 2 \end{bmatrix} \quad \implies \quad \\ \bm{L} & = \nabla^2_{\bm{x}} \mathcal{L}(\bm{x}^\star) = \begin{bmatrix} -1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 2 \end{bmatrix} \end{aligned}
We now need to check if the matrix \bm{L} is (semi-)positive defined in the kernel of the active constraints, and so we have to compute
\begin{aligned} \alpha\bm{K}^T\bm{L}\bm{K} \alpha & = \alpha \begin{bmatrix} 0 & 0 & 1\end{bmatrix}\begin{bmatrix} -1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 2 \end{bmatrix} \begin{bmatrix} 0 \\0 \\ 1 \end{bmatrix}\alpha \\ & = \alpha \begin{bmatrix}0 & 0 & 1\end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ 2 \end{bmatrix} \alpha \\ & = 2\alpha^2 \end{aligned}
Observing that this product is always greater then zero for \alpha \neq 0, then it means that L is positive defined in the kernel of the active constraints and so
\bm{x}^\star = (1,1,0) \qquad \textrm{is a minimum point}
Example 7.8 (Sample Exam Question) Given the problem
\begin{aligned} \textrm{minimize:} \qquad & f(x,y,z) = x^2-y+z \\ \textrm{subject to:} \qquad & h(x,y,z) = y-x = 1 \\ & g_1(x,y,z) = x\geq 1 \\ & g_2 (x,y,z) = z \geq 1 \end{aligned}
the associated lagrangian is
\begin{aligned} \mathcal{L}(x,y,z,\lambda,\mu_1,\mu_2) & = x^2-y+z - \lambda(y-x-1) \\ & - \mu_1 (x-1) - \mu_2(z-1) \end{aligned}
The nonlinear system associated with the first-order necessary KKT condition is therefore
\begin{cases} 2x + \lambda - \mu_1 = 0 & : \partial/\partial_x \mathcal{L}\\ -1 - \lambda = 0 &: \partial/\partial_y \mathcal{L} \\ 1 - \mu_2 = 0 & : \partial/\partial_z \mathcal{L} \\ y-x-1 = 0 & : h \\ x-1 \geq 0 & : g_1 \\ z-1 \geq 0 & : g_2 \\ \mu_1(x-1) = 0 & : \mu_1 g_1 \\ \mu_2(z-1) = 0 & : \mu_2 g_2 \\ \mu_1,\mu_2 \geq 0 \end{cases}
The lonely solution of this system is the one
\begin{aligned} x^\star &= 1 \\ y^\star &= 2 \\ z^\star &=1 \\ \lambda^\star &= - 1 \\ \mu_1^\star &= \mu_2^\star &= 1 \end{aligned}
For such point the set of active constraint \mathcal{A} is determined by all the constraints \{h,g_1,g_2\} (in fact g_1(\bm{x}^\star) = g_2(\bm{x}^\star) = 0) whose gradient is so
\bm{H} = \begin{bmatrix} \nabla h \\ \nabla g_1 \\ \nabla g_2 \end{bmatrix} = \begin{bmatrix} -1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}
This is a 3\times 3 matrix with linearly independent columns/rows and so the kernel obtained by solving \bm{H}\bm{z} = \bm{0} consist only in the null vector \bm{z} = \bm{0}. Determined the hessian
\bm{L} = \nabla_{\bm{x}} ^2 \mathcal{L} = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}
we have that \bm{z}^T \bm{L} \bm{z} is always zero in the kernel of the active constraints, meaning that the necessary condition is satisfied, but not the sufficient and so we are in the grey zone on which the point might (or not) be a local minima.