0
$\begingroup$

I just have learned a nice necessary and sufficient condition for convex optimization KKT form but i can't find exercises or examples for this. Can someone help me? ( some examples or exercies or book that have exercises about this)


Consider convex optimization problem (P):

minimize $f(x)$

subject to $g_i(x) \leq 0$ for $i=1,..,m$

$x \in \Omega$

Where $f: \mathbb{R}^n \to \mathbb{R}$ is convex function and $\Omega$ is a nonempty, convex set.

Slater's condition constraint qualification (CQ) holds in (P) if there exists $u \in \Omega$ such that $g_i(u)<0$ for all $i=1,..,m$.

Theorem: [Karush-Kuhn-Tucker Optimality Conditions in Convex Programming] Suppose that Slater's CQ holds in (P). Then $x^*$ is an optimal solution to (P) if and only if there exist nonnegative Lagrange multipliers $(\lambda_1,..,\lambda_m) \in \mathbb{R}^m$ such that

$$0 \in \partial f(x^*) + \sum_{i=1}^m \lambda_i \partial g_i(x^*) + N(x^*,\Omega)$$

See: http://people.scs.carleton.ca/~bertossi/dmbi/material/Convex%20Analysis.pdf (page 138)

$\endgroup$
0
$\begingroup$

There are examples and exercises for KKT conditions and Slater's constraint qualification in chapter 5 of Boyd and Vandenberghe "Convex Optimization", which is available for free at the author's website https://web.stanford.edu/~boyd/cvxbook/ .

$\endgroup$
  • $\begingroup$ Thank you @Mark L.Stone but i find its definition and proposition different from my book. (My book uses normal cone but Boyd's book doesn't). Can you suggest other sources? $\endgroup$ – Desunkid May 20 '18 at 15:22
  • 1
    $\begingroup$ I think the Boyd and Vandenberghe presentation is more concrete and easier to follow. If you read and understand that, it should be easier to get back to your book and understand the more general treatment. Among other things, your book is trying to prepare you for nondifferentiable functions, which makes things more complicated. $\endgroup$ – Mark L. Stone May 20 '18 at 15:30

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.