# optimization problem with square root and quadratic

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?

• 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. – LinAlg Feb 6 at 19:46
• 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. – Alex Shtof Feb 7 at 6:32