Is this a known result?

173 Views Asked by At

I heard the following result and I am wondering if anyone can verify its correctness and also provide a source to cite.

If the Lagrangian $L(x,\lambda)$ is convex in $x$ at the optimal Lagrange multiplier $\lambda^*$, that is, $L(x,\lambda^*)$ is convex in $x$, then the KKT conditions are necessary and sufficient for optimality.

1

There are 1 best solutions below

1
On BEST ANSWER

You at least need differentiability for existence of KKT. But if you focus on sufficiency, you can say this:

Sufficiency:

Suppose your problem is to minimize $f(x)$ over a convex set $X$ and subject to $g_k(x)\leq 0$ for all $k \in \{1, \ldots, K\}$ (call this Probelm P1). Define: $$ L(x, \lambda) = f(x) + \sum_{k=1}^K\lambda_k g_k(x) $$ Assume that $\lambda^*$ is a vector with nonnegative components. Assume that $L(x,\lambda^*)$ is a convex function over $x \in X$. Assume we have a vector $x^* \in X$ for which the following "KKT conditions" hold: \begin{align} &\nabla f(x^*) + \sum_{k=1}^K \lambda_k^* \nabla g_k(x^*) = 0 \\ & g_k(x^*) \leq 0 \: \: \forall k \in \{1, \ldots, K\} \\ &\lambda_k^* \geq 0 \: \: \forall k \in \{1, \ldots, K\} \\ &\lambda_k^*g_k(x^*) = 0 \: \: \forall k \in \{1, \ldots, K\} \end{align} We want to show that $x^*$ is an optimal solution to the problem P1. The above assumptions show that $x^*$ satisfies the constraints (namely, $x^* \in X$ and $g_k(x^*) \leq 0$ for all $k \in \{1, \ldots, K\}$). The derivative assumptions also show that $x^*$ is a point of zero-derivative for the function $L(x, \lambda^*)$. Since this function is convex in $x$, $x^*$ must minimize $L(x,\lambda^*)$ over all $x \in X$. Thus, for all $x \in X$ we have: $$ L(x^*,\lambda^*) \leq L(x,\lambda^*) $$ That is, for all $x \in X$: $$ f(x^*) + \underbrace{\sum_{k=1}^K\lambda_k^*g_k(x^*)}_{zero} \leq f(x) + \sum_{k=1}^K\lambda_k^*g_k(x) $$ Thus, if $x$ is a vector in $X$ that satisfies the constraints $g_k(x) \leq 0$ for all $k$, then $\sum_{k=1}^K\lambda_k^*g_k(x) \leq 0$ (recall that $\lambda_k^*\geq 0$ for all $k$) and the above inequality reduces to $f(x^*) \leq f(x)$, meaning that $x^*$ is an optimal solution to problem P1.