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

zBirdy
171211
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.

link

answered 26 Dec '14, 10:54

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
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
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 ♦
Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×190
×79

Asked: 22 Dec '14, 16:14

Seen: 1,699 times

Last updated: 29 Dec '14, 11:56

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