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.

Improve this question
$\endgroup$
4
  • $\begingroup$ KKT is only necessary, not sufficient.... $\endgroup$
    – Suvrit
    Commented Sep 26, 2015 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
    Commented Oct 16, 2015 at 17:27
  • $\begingroup$ can you give a proof for your claim? $\endgroup$
    – behrad mahboobi
    Commented Oct 18, 2015 at 19:28
  • $\begingroup$ i have fixed the strict inequality, thanks for pointing out. $\endgroup$
    – behrad mahboobi
    Commented Oct 18, 2015 at 19:30

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
7
  • $\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
    Commented Oct 31, 2015 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
    Commented Oct 31, 2015 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
    Commented Oct 31, 2015 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
    Commented Oct 31, 2015 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
    Commented Nov 1, 2015 at 3:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .