A version of KKT theorem. Looking for a reference

Question

I have been told that the following optimization theorem holds and is true. I would like to verify this or find a reference. I have searched some standard books that I know (e.g. Luenberger).

Theorem. Let $X$ be a vectors space. Let $f:S \to \mathbb{R}$ and $h:S \to \mathbb{R}$ be concave functions over a convex subset $S \subset X$. Assume that there exists a point $x_0 \in S$ such that $h(x_0) <0$. Let \begin{align} \text{Obj}=\sup_{x \in S \text{ and } h(x)\le 0} f(x). \,\,\,\, eq.(1) \end{align} Then, there exists a constant $\lambda \ge 0$ such that \begin{align} \text{Obj}= \sup_{x \in S } \left( f(x)-\lambda h(x) \right). \,\,\,\, eq.(2) \end{align} Morover, if the supremum is attainable in eq.(1) by $x^* \in S$ that satisfies $h(x^*)\le 0$, then the supremum is also attainted by $x^*$ in eq.(2).

Another question: Does the fact $h(x)$ is concave make this theorem difficult to show? Here the constraint is $h(x) \le 0$ instead of $h(x) \ge 0$, is this problemtic?

Answer 1

I believe I have a counterexample.

Take $S = X = \mathbb R$ and let $f(x) = -x^2$, $h(x) = 1 - x^4$. Then:

• Maximizing $-x^2$ over all $x$ where $1-x^4 \le 0$ means minimizing $x^2$ over $(-\infty,-1] \cup [1,\infty)$, so the optimal solution is $x^* = \pm1$ with $\text{Obj} = -1$.
• But $-x^2 - \lambda(1-x^4) = \lambda x^4 - x^2 - \lambda$ never has the right supremum. When $\lambda=0$, $-x^2$ is maximized at $0$, and the supremum is also $0$. When $\lambda>0$, the $x^4$ term dominates and we can make $\lambda x^4 - x^2 - \lambda$ arbitrarily large.

You're right that the concavity of $h$ is the problem. If $h$ were convex (or if $h$ were concave but the constraint were $h(x) \ge 0$, which corresponds to $g(x) \le 0$ for the convex function $g(x) = -h(x)$) then this would just be the Slater condition.

Essentially the reason the Slater condition works, but the statement with a concave $h$ does not, is that convex functions can't decrease too quickly. At any point $x_0$ in the domain of a convex function $g$, there exists a slope $d$ such that $g(x) \ge g(x_0) + d(x-x_0)$; we can take $d = g'(x_0)$ if $g'(x_0)$ exists. (There's a dot-product version of this for $\mathbb R^n$, and probably a linear-functional version of this for arbitrary vector spaces $X$.)

As a result, if the condition were $g(x) \le 0$, where $g$ is convex, then we can put a linear lower bound on $g$, so as we get "deeper" into the feasible region $\{x : g(x) \le 0\}$, the value of $-\lambda g(x)$ increases at worst at a constant rate that, by the choice of $\lambda$, we can make as small as we like until it's not worth it. (A constant rate is enough to achieve this because $f(x)$ is concave, so there is also a linear upper bound on $f$.)

But in the example above, the function $h(x)=1-x^4$ decreases very quickly as we go further into the feasible region $\{ x: 1-x^4 \le 0\}$. No matter what the value of $\lambda$ is, if $\lambda>0$, the term $-\lambda(1-x^4)$ rewards us much faster than the $-x^2$ term decreases, so for all $\lambda>0$, we want to go as far into the feasible region as possible.