I am doing the additional exercises of the book Convex Optimization, and I am stuck at question 3.32 (page 29 of this pdf).

The problem is:

$$ \begin{aligned} & \text{minimize} && f_0(x)\\ & \text{subject to} && \sum_i^m(1 + \lambda f_i(x))_+ \le m - k\\ &&& \lambda > 0 \end{aligned} $$

where $(\cdot )_+$ represents $\max\{\cdot,\ 0\}$, and $f_0, f_i$ are convex functions.

The author gives a hint that, to solve this problem using convex optimization, we may use the change of variables.

My question is, as far as I know, this problem is already a convex optimization problem, because the expression

$$ \sum_i^m(1 + \lambda f_i(x))_+ - m + k $$

is convex for both $\lambda$ and $x$. Then what's the point of changing variables here?

  • $\begingroup$ Note the subscript "+" on the $(1+\lambda f_{i}(x))_{+}$. This function isn't affine in $\lambda$. $\endgroup$ – Brian Borchers Nov 29 '17 at 5:17
  • $\begingroup$ @BrianBorchers oh yes, thanks for pointing out. But it's still convex on $\lambda$ isn't it? $\endgroup$ – hklel Nov 29 '17 at 5:25
  • $\begingroup$ If you can show that $(1_\lambda f_{i}(x))_{+}$ is a convex function of $x$ and $\lambda$, then you've got a convex optimization problem. The author seems to want you to further simplify the problem into some standard form that you can solve. For the last part of the problem you'll need to do this in the particular case where $f_{i}(x)$ is affine. $\endgroup$ – Brian Borchers Nov 29 '17 at 5:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.