optimization problem with square root and quadratic

1.2k Views Asked by At

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?