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's gravatar image

accept rate: 20%

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%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

edited 26 Dec '14, 11:01

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

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

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 ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 22 Dec '14, 16:14

Seen: 1,814 times

Last updated: 29 Dec '14, 11:56

OR-Exchange! Your site for questions, answers, and announcements about operations research.