Second order optimal condition for this question

Question

I am trying to solve a very simple constrained optimization problem below:

P: $\min{x_1 + x_2}$

subject to

$ x_1 \geq 0$

$ x_2 \geq 0$

$ (2x_1+x_2)^2 = 4$

By solving the KKT condition, I have the KKT point as $(x_1,x_2,\lambda_1,\lambda_2,\mu)=(1,0,0,\frac{1}{2},-\frac{1}{8})$ and I know it is a global minima. However, when I checked the second order condition (sufficient condition), it turned out the Tagent Space (Cone) $\{d\neq0: \nabla h\cdot d=0, \nabla g_1 \cdot d\leq0, \nabla g_2\cdot d=0\}$ is empty, and thus cannot tell whether the Hessian of restricted Lagragian function is positive definite or not. In fact, if I don't use the Cone, the Hessian of the restricted Lagragian $\nabla_{xx}\bar{L}(x, \bar{\lambda},\bar{\mu})$ is negative definite, which contradicts the fact that the solution is a local min.

Could anyone help to answer my question? What should we do if the cone set is empty?

Thanks in advance.

Answer 1

Rewritting the problem: $$ \mathscr{P}: \min x_1+x_2, \\(2x_1+x_2)^2-4=0, \\-x_1\le0,\\ -x_2\le0 $$

Then the KKT conditions are: $$ L=(x_1+x_2)+\mu_1(-x_1)+\mu_2(-x_2)+\lambda_1((2x_1+x_2)^2-4) $$ Stationarity: $$ \nabla_{x_1}L=1-\mu_1 +\lambda_14(2x_1+x_2)=0\\ \nabla_{x_2}L=1 -\mu_2 +\lambda_12(2x_1+x_2)=0 $$ Feasibility (this is normally redundant and serves only to expose $\nabla L$) $$ \nabla_{\mu_1}L=-x_1\le0\\ \nabla_{\mu_2}L=-x_2\le0\\ \nabla_{\lambda_1}L=(2x_1+x_2)^2-4=0 $$ Slackness: $$ \mu_1x_1=0\\ \mu_2x_2=0 $$ The specified point of the full problem is: $[x_1 \ x_2 \ \mu_1 \ \mu_2 \ \lambda_1]=[1 \ 0 \ 0 \ 1/2 \ -1/8]$.

The tangent cone for the solution is evaluated for all the active constraints (Mangasarian-Fromovitz constraint qualification), which are only the active inequalities plus the equalities (which will always be active!): $$ \nabla g_1 \cdot d = \le 0\\ \nabla h_1 \cdot d = 0\\ $$ The condition in this form is trivially met for the given point.

The full Hessian of the active constraints must be semi-positive $d'Ld>0$ for $\nabla g_1 d=0$ and $\nabla h_1 d=0$, the orthogonal directions of the active constraints.

Hence in the full Hessian: $$ \nabla^2 L= \left[ \begin{array}{ccccc} 8\lambda_1 &4\lambda_1 &-1 &0 &4(2x_1+x_2)\\ 4\lambda_1 &2\lambda_1 &0 &-1 &2(2x_1+x_2)\\ -1 &0 &0 &0 &0\\ 0 &-1 &0 &0 &0\\ 4(2x_1+x_2) &2(2x_1+x_2) &0 &0 &0 \end{array} \right] = \left[ \begin{array}{c} -1 &-2 &-1 &0 &8\\ -1/2 &-1/4 &0 &-1 &4\\ -1 &0 &0 &0 &0\\ 0 &-1 &0 &0 &0\\ 8 &4 &0 &0 &0 \end{array} \right] $$

we discard the 3rd row and column for considering the direction $[1 \ 2 \ 0 \ 0 \ 0]$ for the $h_1$ constraint active, and the rest inactive, and we have the reduced hessian, which is positive definite: $$ L(d)=d'[-1 2][-1 -2;-1/2 -1/4][-1;2]d=3d^2 $$

Note that we cannot choose any other direction without breaking feasibility. So the critical point is a minimum.

Answer 2

That is a very good question. It is all a matter of definition. Let $\bar{x}$ be the point being analyzed and

$$K= \{d\in \Bbb R^n: \nabla h(\bar{x})\cdot d=0, \nabla g_{I(\bar{x})}(\bar{x}) \cdot d\leq0, \nabla g_2(\bar{x})\cdot d=0\},$$ be the tangent cone at $\bar{x}.$ Here $I(\bar{x})=\{i: g_i(\bar{x})=0\}$ is the set of active constraints. Recall that the second order sufficient condition states:

$$\textrm{ If } \nabla f(\bar{x})=0 \textrm{ and } d^T\nabla^2f(\bar{x})d>0 \;\forall \;d\in K\setminus\{0\}, \textrm{ then } \bar{x} \textrm{ is a local minimum }.$$ Well, you can easily see now that this condition holds by vacuity in your problem because there is no $d\in K\setminus\{0\}.$ Hence the point is in fact a local minimum.

EDIT: Since the OP asked for a reference, I would like to further elaborate on that point. I haven't seen this exactly, in the literature, but it is easy to see this fact from the proof of the second order sufficient condition, see Bazaraa. This proof goes as follows: they assume that $\bar{x}$ is not a global minimum, and from there they build a sequence $\{d_n\}$ such that $\|d_n\|=1,$ and $d_n\to d \in K.$

If $K=\{0\},$ we now obtain a contradiction because $\|d\|=1,$ so that $d\neq 0.$ Hope this helps.