Relation between formulating the KKT conditions via gradients vs subdifferentials

2.1k Views Asked by At

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?

1

There are 1 best solutions below

7
On BEST ANSWER

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.