0
$\begingroup$

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)$?

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ – copper.hat Dec 20 '16 at 22:02
1
$\begingroup$

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$.

Note:

${\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$.

$\endgroup$
4
  • $\begingroup$ $\max\{0,x^3\}$ is concave? Seems convex to me. $\endgroup$ – Michael Grant Dec 20 '16 at 22:39
  • 1
    $\begingroup$ @MichaelGrant: Thanks, I meant $\min$. $\endgroup$ – copper.hat Dec 20 '16 at 22:42
  • $\begingroup$ Why is $L(0,\lambda)=1$ it becaue you took $c=1$? $\endgroup$ – Boby Dec 21 '16 at 13:24
  • $\begingroup$ @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. $\endgroup$ – copper.hat Dec 21 '16 at 15:20

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.