1
$\begingroup$

In this link https://www.cs.cmu.edu/~ggordon/10725-F12/slides/16-kkt.pdf you can find this:

enter image description here

And in the Nonlinear programming book by Bazaraa page 207 you can find this:

enter image description here

My question is

Are those conditions equivalent?

Why?

What are other varieties of KKT conditions?

$\endgroup$
2
$\begingroup$

Notice that if the convex functions $f, h_i$ (for $i = 1,\ldots,m$) and $\ell_j$ (for $j = 1,\ldots, r$) are differentiable, then $\partial f(x) = \{ \nabla f(x) \}$, and similarly for $h_i$ and $\ell_j$, so the condition $$ 0 \in \partial f(x) + \sum_{i=1}^m u_i \partial h_i(x) + \sum_{j=1}^r v_j \partial \ell_j(x) $$ reduces to $$ 0 = \nabla f(x) + \sum_{i=1}^m u_i \nabla h_i(x) + \sum_{j=1}^r v_j \nabla \ell_j(x). $$

The first version of the KKT conditions is very nice because it does not require the functions $f, h_i$, and $\ell_j$ to be differentiable. However, the first version is only useful (I believe) in the case where these functions are convex. (For a convex function $f$, the subdifferential $\partial f(x)$ is often a useful substitute for $\nabla f(x)$.)

On the other hand, the second version of the KKT conditions requires these functions to be differentiable, but it is useful even in cases where these functions are nonconvex.

$\endgroup$
  • $\begingroup$ A big difference that I notice is the feasible point $\overline x$ mentioned in the second version and not if the first version of the KKT conditions. Could we say that $0 = \nabla f(\overline x) + \sum_{i=1}^m u_i \nabla h_i(\overline x) + \sum_{j=1}^r v_j \nabla \ell_j(\overline x)\iff 0 \in \partial f(x) + \sum_{i=1}^m u_i \partial h_i(x) + \sum_{j=1}^r v_j \partial \ell_j(x)$ $\endgroup$ – user441848 Jul 1 '18 at 1:28
  • $\begingroup$ Or why the fesible point $\overline x$ is not mentioned in the first version? $\endgroup$ – user441848 Jul 1 '18 at 1:31
  • $\begingroup$ I think that $x$ vs. $\bar{x}$ is just a different choice of notation. The first version of the KKT conditions explicitly states that $h_i(x) \leq 0$ and $\ell_i(x) = 0$, which is just an explicit way to say that $x$ is feasible. $\endgroup$ – littleO Jul 1 '18 at 1:39
  • $\begingroup$ hmm I think both explicitly states the constraints conditions $h_i(x)\le0,\ell_i(x)=0$ and $g_i(x)\le0,h_i(x)=0$, but only second version of KKT conditions mention feasibility of point $\overline x.$ $\endgroup$ – user441848 Jul 1 '18 at 1:46
  • 1
    $\begingroup$ @user441848 I think that's because Theorem 4.3.8 was written or edited by someone in the department of redundancy department. $\endgroup$ – Mark L. Stone Jul 1 '18 at 17:52

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.