Why are the KKT conditions sufficient in this case?

Question

I need to solve this problem:

minimize $f(x,y)=5x-xy-50+10y$

subject to:

$g_1(x,y)=18-xy\leq0$

$g_2(x,y)=x+y-11\leq0$

$x,y\geq0$

I found the optimal solution: $(x,y)=(6,3)$ But the Hessian matrix of the objective function is indefinite. My question is, why are the KKT conditions sufficient in this case? Or if they are not, then according to what sufficient condition is the optimal solution correct?

Thanks in advance!

Answer 1

Suggestion: can you show it is quasi-convex?

$$\forall h,\, Df(x)\cdot h = 0 \Longrightarrow h^T\cdot D^2f(x) \cdot h \ge 0$$

That is, we only care about the directions $h$ that are orthogonal to the gradient.

$$f_x\cdot h_1+f_y\cdot h_2=(5-y)h_1+(10-x)h_2 = 0\Rightarrow h_2=\dfrac{5-y}{10-x}h_1$$ $$ h^T\cdot D^2f(x) \cdot h = -2h_1\cdot h_2$$ $$ -2\dfrac{5-y}{10-x}h_1^2 \ge 0\Leftrightarrow \mathrm{sign} \;y-5=\mathrm{sign}\, 10-x$$

That is, either $y> 5$ implies $x<10$ or $y<5$ implies $x>10$.

Maybe we could make an argument this happens in the constrain set? Not sure, again just a suggestion too long to be a comment.

Answer 2

In non-convex quadratic optimization, where your problem belongs to, everything is possible. A solution can be KKT point or cannot be a KKT point. This depends from case to case and it is hard to say before solving the problem. However, for small quadratic problems with just a few constraints. Also proving that one KKT point is a local optimum can be extremely difficult.

In non-convex quadratic programming, one possible way to prove optimality of some point is to solve the dual problem. If you solve the dual problem and the minimum value find in the original problem coincides with the value of the dual problem then you are done. (See http://en.wikipedia.org/wiki/Quadratic_programming for quadratic programming and http://www.stanford.edu/class/ee392o/relaxations.pdf for Lagrange duality in quadratic programming).

Note that the latter strategy is not always possible since there can be the duality gap, that is, there is no equality of the optimum values of the dual and the primal problem.