3
$\begingroup$

In standard convex programming, the objective function and each of the constraint inequalities are convex. in such case, if the KKT condition hold for a point, and Slater condition is also hold for the solution space, that point is global optimum. However what if one of the constraint isn't convex but the solution space is convex?

for example suppose that $g_1(\mathbf{x}),g_2(\mathbf{x})$ be two nonconvex functions and the set $S=\{\mathbf{x} | g_1(\mathbf{x})\le0 ,g_2(\mathbf{x})\le0\}$ is convex. Is the same result from KKT condition held? or is it hold with a different constraint qualification? or is not generally applicable in these case?

Actually I need a proof which KKT condition (with/without new constraint qualification) is applicable otherwise a counterexample.

$\endgroup$
  • $\begingroup$ KKT is only necessary, not sufficient.... $\endgroup$ – Suvrit Sep 26 '15 at 2:02
  • $\begingroup$ Since you have strict inequalities in your $S$, the KKT conditions are $\nabla f(\bar x) = 0$ and by convexity of $f$, this is a global minimizer. Did you mean non-strict inequalities? Then, the result should hold, maybe even without a CQ. $\endgroup$ – gerw Oct 16 '15 at 17:27
  • $\begingroup$ can you give a proof for your claim? $\endgroup$ – behrad mahboobi Oct 18 '15 at 19:28
  • $\begingroup$ i have fixed the strict inequality, thanks for pointing out. $\endgroup$ – behrad mahboobi Oct 18 '15 at 19:30
2
$\begingroup$

Let me sketch a proof that the KKT conditions imply global optimality in the case that the objective $f$ and $S$ is convex. No constraint qualification is needed.

Let us assume that the KKT conditions hold at $x$. For simplicity, let both inequality constraints be active at $x$, i.e., $g_1(x) = g_2(x) = 0$.

First, you always have $$T_S(x) \subset \{d : g_1'(x) \, d \le 0, g_2'(x) \, d \le 0\}.$$ Here, $T_S(x)$ is the tangent cone of $S$ at $x$.

The KKT conditions imply (use Farkas' Lemma) $$-\nabla f (x) \in \{d : g_1'(x) \, d \le 0, g_2'(x) \, d \le 0\}^\circ.$$ Here, $(\cdot)^\circ$ refers to the polar cone.

Hence, $$-\nabla f(x) \in T_S(x)^\circ.$$ In view of convexity of $f$ and $S$ this last condition implies (actually it is equivalent to) global optimality of $x$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ what if both constraints aren't active in the same time ? can we claim that in any conditoon KKT condition result in $$-\nabla f (x) \in \{d : g_1'(x) \, d \le 0, g_2'(x) \, d \le 0\}^\circ.$$, independent of the convesity of $f,S$? $\endgroup$ – behrad mahboobi Oct 31 '15 at 19:07
  • $\begingroup$ Then, you write down the same proof, but leave out the non-active constraints. This is typically done by introducing the set $A(x) = \{i : g_i(x) = 0\}$ of active constraints. $\endgroup$ – gerw Oct 31 '15 at 19:09
  • $\begingroup$ then we reduce to a nonconvex set to obtain a tangent cone which tangent cone is only defined for convex sets! $\endgroup$ – behrad mahboobi Oct 31 '15 at 19:33
  • $\begingroup$ No. $S$ is always convex by assumption. You only drop the non-active constraints in the proof, exactly at those points, where the derivatives $g_i'(x)$ appear. $\endgroup$ – gerw Oct 31 '15 at 19:49
  • $\begingroup$ thank you so much Gerw, do u proposed any text book in this field that cover tangent cone, fakas lemma and related topics in convex analysis? $\endgroup$ – behrad mahboobi Nov 1 '15 at 3:39

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.