# Non-Convex Optimization and Lagrangian Optimization

Let $f,g: \mathcal{X} \to \mathbb{R}$. Let $f$ and $g$ be concave. We want to solve the following opitmization problem \begin{align} \max_{x \in \mathcal{X}} f(x) \\ \text{ s.t. } g(x) \le c \end{align} where $c\ge 0$.

My question: Since $g(x)$ is not convex the above problem does not fall into the category of convex optimization.

Keeping the above in mind, would the Lagrangian approach still given a neccesary codition on the optimality?

That is if we define \begin{align} L(x)=f(x)-\lambda (c-g(x)) \end{align}

then the optimall solution must be a stationary point of $L(x)$?

• Generally you need some regularity conditions, so it is not true in general. Take any $f(x) = x$ and $g(x) = c+x^2$, then the solution is $x=0$ but clearly $L(0,\lambda) \neq 0$ for any $\lambda$. – copper.hat Dec 20 '16 at 22:02

Take $f(x) = x$, $c=0$ and $g(x) = \min(0,x^3)$. Note that $f,g$ are concave.
The solution is $x=0$, but $g'(0) = 0$, hence for any $\lambda$ we have ${\partial L(0,\lambda) \over \partial x} = 1$.
${\partial L(x,\lambda) \over \partial x} = {\partial f(x) \over \partial x} + \lambda {\partial g(x) \over \partial x}$, and so we have ${\partial L(0,\lambda) \over \partial x} = 1$.
• $\max\{0,x^3\}$ is concave? Seems convex to me. – Michael Grant Dec 20 '16 at 22:39
• @MichaelGrant: Thanks, I meant $\min$. – copper.hat Dec 20 '16 at 22:42
• Why is $L(0,\lambda)=1$ it becaue you took $c=1$? – Boby Dec 21 '16 at 13:24
• @Boby: I'm sorry, I had a typo. above. The $L(0,\lambda)$ should have been the partial with respect to $x$. I have fixed it. – copper.hat Dec 21 '16 at 15:20