2
$\begingroup$

$$ \text{minimize } x_1 $$ $$\text{subject to} $$ $$ x_1^2 + (x_2-1)^2 \le 1 $$$$x_1^2 + (x_2+1)^2 \le 1$$

For the solution of this optimization problem, by using Lagrangian $$L(x,\lambda) = \lambda_0x_1 + \lambda_1(x_1^2 + (x_2-1)^2 -1) +\lambda_2(x_1^2 + (x_2+1)^2-1)$$

from KKT conditions I conclude that $\lambda_0 = 0$, $\lambda_1 = \lambda_2$ ( for the only feasible solution)

I know that $\lambda_0 = 0$ means optimal solution does not depend on the objective function. But what should I infer from $\lambda_1 = \lambda_2$? Also it means KKT conditions do not hold?

Note: Slater's condition is not satisfied for this problem.

$\endgroup$
  • $\begingroup$ How did you reach any of these conclusions? If you have specific $f_1$ and $f_2$, please tell us what they are. $\endgroup$ – Mark L. Stone Nov 4 '17 at 16:02
  • $\begingroup$ @MarkL.Stone I edited my question for specific $f_1$ and $f_2$ $\endgroup$ – Pumpkin Nov 5 '17 at 17:36
1
$\begingroup$

KKT conditions are NOT satisfied at the optimum $[0;0]$, which as you said is the only feasible point.

The nonlinear inequality constraints can not be strictly satisfied, hence, as you said, the Slater condition is not satisfied.

The gradient of constraint 1 at the optimum = $[0;-2]$.

The gradient of constraint 2 at the optimum = $[0;2]$.

The gradients of the nonlinear constraints are not linearly independent at the optimum, hence the Linearly Independent Constraint Qualification is not satisfied at the optimum.

Indeed, as it turns out, the KKT conditions are not satisfied at exactly the optimum. There are no (non-negative) Lagrange multipliers which make the gradient of the Lagrangian close to being the zero vector at the optimum. However, for a very slight perturbation away from the optimum, (non-negative) Lagrange multipliers can be found (via constrained linear least squares) which make the gradient of the Lagrangian very close to being the zero vector at the optimum. Therefore, such a very close to optimum point can achieve a very good KKT optimality score, and be declared optimal for some reasonable KKT optimality tolerance.

As an illustration of coming close to satisfying KKT optimality conditions, I ran my own nonlinear optimizer and got an "optimal" point, which in reality is slightly infeasible, of $1e-5*[-0.997888668876936;0.000000000003149]$. Using Lagrange multipliers of $1.0e+04 * [2.505289510463797; 2.505289510463796]$, the gradient of the Lagrangian is $1e-8*[-0.589922777294305; -0.002182787284255]$ and the constraints are each violated by 9.957812352467954e-11. From a practical optimization perspective, that optimization problem is solved, and the KKT conditions satisfied to a reasonable tolerance. However, the theoretical lack of KKT conditions holding exactly, can add some difficulty for certain solvers.

| cite | improve this answer | |
$\endgroup$

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.