# Karush Kuhn Tucker Conditions

 0 2 Hello, do you need any constraint qualifications for the KKT conditions to be optimal for the following problem(here) I have a linear objective, and linear inequalities, and quadratically constrained equalities. x^t * H * x + D*x + C = 0 the matrix H is a diagonal matrix and positive definite, C = 0, and D is a full of negative ones. Do i need any constraint qualifications or are the KKT points always optimal? asked 22 Dec '14, 16:14 zBirdy 171●2●11 accept rate: 20%

 2 KKT conditions are necessary but not sufficient for optimality, regardless of any constraint qualifications. Consider the following problem: $\begin{array}{lrcl} \textrm{maximize} & y\\ \textrm{s.t.} & x^{2}+y^{2}-x-y & = & 0\\ & x & \le & 1\\ & y & \le & 2\\ & x & \ge & 0\\ & y & \ge & -2 \end{array}$ which fits your format. It is easy to check that $$(x,y)=(\frac{1}{2},\frac{1-\sqrt{2}}{2})$$ and $$(x,y)=(\frac{1}{2},\frac{1+\sqrt{2}}{2})$$ are both KKT points, with multipliers $$\lambda=-\frac{1}{\sqrt{2}}$$ and $$\lambda=\frac{1}{\sqrt{2}}$$ respectively for the equality constraint (and zero multipliers for the inequalities, since the inequalities are slack at both points). The first point is a minimum, not a maximum, so it is clearly not optimal. answered 26 Dec '14, 10:54 Paul Rubin ♦♦ 14.6k●4●12 accept rate: 19% thank you for your response i am sorry unfortunately i made an error in the notation above. The quadratically constrained are: x^2-x = 0, y^2-y = 0, ... for all variables. Also we are minimizing. (27 Dec '14, 22:46) zBirdy but i'm pretty sure a similar example can be found. so is there a sufficient condition for those problems? (27 Dec '14, 22:56) zBirdy 1 Constraint qualifications requirements are a part of the KKT stipulations. A sufficient condition for a KKT point to be optimal is if the problem is convex (minimizing convex objective, affine equality constraints, convex inequality constraints, and convex feasible set). However, your equality constraints are non-convex -- their feasible values {0,1} are disconnected. It seems that you are trying to model discrete states using continuous variables. This leads to a degenerate formulation that unfortunately does not work. (28 Dec '14, 00:31) Gilead ♦ yes but is there no sufficient condition which tells me wich point of the feasible values is optimal? (so there are no kkt's aquivalent for non convex?) (29 Dec '14, 06:30) zBirdy 2 Now that's a different question. Another set of conditions, SOSC (Second Order Sufficient conditions) is used to check if a point is a (local) optimum. However, your problem remains ill-posed due to constraint qualification violations. There have been attempts at continuous reformulations that don't violate CQ's (see here), but in practice they don't seem to work so well. (29 Dec '14, 11:45) Gilead ♦
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: