5
$\begingroup$

I have a very simple problem: $$ \begin{align*} \begin{array}{ll} \min\limits_{x_1,x_2} & -x_1x_2 \\ \text{s.t.} & x_1 + x_2 - 2 = 0. \end{array} \end{align*} $$

The KKT system gives me $x_1^* = x_2^* = \lambda^* = 1$ where the $*$ denotes the KKT solution and $\lambda$ is the Lagrangian variable. The point $x_1,x_2 = (1,1)$ is the only solution to the KKT system.

Now I need to answer:

Show that this point is a constrained local minimizer.

My idea is that, since there is a single equality constraint with a nonzero gradient, there is no irregular point. Hence, the KKT system includes all of the local minimizers. Since there is one solution, this is the local and global minimizer of the problem.

I think my answer is correct. But, I have a hesitation here, what if this solution was a local maximum? Can it be the case? We know that when the problem is not convex the KKT system returns all the stationary points, and maybe $(1,1)$ is not the minimizer (I know it is but I am wondering conceptually). What is the cleanest way to show that $(1,1)$ is a local minimizer without substituting $x_1 = 2 - x_2$?

$\endgroup$
6
$\begingroup$

You have shown that KKT is necessary for a local minimum. Also that it is necessary for a local maximum. But you have not shown that a local minimum or local maximum exists. Indeed, there is no local maximum.

So is the KKT point you found a local minimum? That is what 2nd order conditions can assess. The 2nd order (KKT) sufficiency conditions (whose requisite applicability conditions are met - I leave the details to you) for a strict local minimum are that the projection of the Hessian of the Lagrangian into the nullspace of the Jacobian of the active constraints is positive definite. Because there are no nonlinear constraints, the Hessian of the Lagrangian is the Hessian of the objective function. There is only one constraint, and it is active. If $Z$ is a basis for the nullspace of the Jacobian of the active constraint, then the projection of the Hessian, $H$, of the objective function into the nullspace of the Jacobian of active constraints is $Z^\top HZ$.

Any non-zero multiple of the column vector $\begin{bmatrix}-1&1\end{bmatrix}^\top$ is a basis for the nullspace of the active constraint $x_1 + x_2 -2 = 0$. Putting it all together, we see that $Z^\top HZ$ is the $1\times1$ matrix $\begin{bmatrix}2\end{bmatrix}$ (or any positive multiple of it), and so is positive definite, completing the proof.

In this case, this winds up being a long-winded way of essentially substituting out one of the variables and seeing that the resulting problem is an unconstrained strictly convex quadratic problem. But the method I outlined is much more general.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! This is very clear to me. $\endgroup$ – independentvariable Jan 1 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.