Consider the optimization problem \begin{align} \max_{\mathbf{y\in\mathbb{R}^N}}~~\mathbf{y}^T\mathbf{b}+\beta\sqrt{c-\mathbf{y}^T\mathbf{Ay}} \\s.t.~~\mathbf{0}\leq\mathbf{y}\leq \mathbf{1} \end{align} where $\mathbf{A}$ is a $N\times N$ positive definite matrix, $\mathbf{b}$ is a real vector and $\beta >0$ are given. Is this a convex problem? I think by composition and since square root is a increasing function, this is a convex problem. Now, I re-wrote it as \begin{align} \max_{\mathbf{y\in\mathbb{R}^N}}~~&\mathbf{y}^T\mathbf{b}+\beta t \\s.t.~~&\mathbf{0}\leq\mathbf{y}\leq \mathbf{1} \\ &t^2 = c-\mathbf{y}^T\mathbf{Ay},~t\geq 0 \end{align} However, this is not convex since the equality constraint is not linear. I again re-wrote it as \begin{align} \max_{\mathbf{y\in\mathbb{R}^N}}~~&\mathbf{y}^T\mathbf{b}+\beta t \\s.t.~~&\mathbf{0}\leq\mathbf{y}\leq \mathbf{1} \\ &t^2 \leq c-\mathbf{y}^T\mathbf{Ay},~t\geq 0 \end{align} Note that now this is a convex problem. It is ok to convert the equality to inequality because at the optimum it will be an equality. This can be proven by contradiction. If there was a gap, then one could increase $t$ so that the objective increases which is a contradiction. Are these steps correct?

  • $\begingroup$ Yup, that is how it's done! You can formulate the final constraints as a second order conic constraint to feed it to an efficient solver. $\endgroup$ – LinAlg Feb 6 at 19:46
  • $\begingroup$ It is convex indeed, since this is a maximization of a concave function (the square-root term is concave). Making it a minimization problem, and flipping the signs, makes the problem convex. $\endgroup$ – Alex Shtof Feb 7 at 6:32

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.