Proving the set $\left\lbrace \frac{(x + y)^2}{\sqrt{y}} \leq x - y + 5, y > 0 \right\rbrace$ is convex

Question

I have recently picked up a course on Convex Analysis in my spare time, but feel I'm not quite up to speed with the 'tricks' for proving a set is convex.

I have managed to prove this by moving all terms involving $x$ and $y$ to one side, then brute force computing the Hessian and showing it's positive definite, then concluding that the sub-level set of a convex function is convex. But is there a neater way of showing this using some of the 'tricks' shown, for example, in Boyd & Vandenberghe?

For reference, here is a plot from WolframAlpha:

Answer 1

The constraints can be reformulated as linear matrix inequalities (LMIs). In the book "Convex Optimization" by Boyd and Vandenberghe, LMI first shows up in the Example 2.10. Please see the following:

First, reformulate the constraint $\frac{(x+y)^2}{\sqrt{y}} \leq x - y + 5$ as a matrix inequality. Moving everything to one side, we have $x - y + 5 - \frac{(x+y)^2}{\sqrt{y}} \geq 0$. Follow Appendix A.5.5 in Boyd and Vandenberghe and define $A:=\sqrt{y}, B:=(x+y), C:=x-y+5$, we have the original inequality as $S:=C - B^\top A^{-1}B \geq 0$. Note that $A=\sqrt{y} > 0$ as $y>0$. Observe that $S$ is actually the Schur complement of $A$ in $X$ defined in the following: $$X:=\begin{bmatrix} x-y+5 & x+y \\ x+y & \sqrt{y} \end{bmatrix}.$$ With the condition for positive definiteness of Schur complement, the following is true: $$ A > 0, S > 0 \Leftrightarrow X \succ 0 \tag{1}.$$ Hence, the first constraint with fraction can be rewritten as the matrix inequality $X\succ 0$.

Second, we introduce a slack variable $s$ and reform LMI (1) as the following constraints: $$\begin{align} \begin{bmatrix} x-y+5 & x+y \\ x+y & s \end{bmatrix} \succ 0 \tag{2} \\ \sqrt{y} > s > 0 \tag{3} \end{align}$$ Lastly, taking square of the first part of inequality (3) on both side and appy Schur complement again to get the following LMI: $$ \begin{bmatrix} y & s \\ s & 1 \end{bmatrix} > 0 \tag{4} $$

With the above three steps, you can represent the set in your problem as the set described by LMI (2) and (4). Since the LMI are affine in all decision variables, the set is convex.

Answer 2

You can reformulate as SOCP by introducing four variables $z_i$ and the following constraints: \begin{align} z_1 &\ge 0 \\ z_2 &\ge 0 \\ z_3 &= 0.5\\ x - y - 2 z_2 &\ge -5\\ 2y z_3 &\ge z_1^2\\ 2z_2 z_1 &\ge z_4^2\\ x + y - z_4 &= 0 \end{align}

---

By request, here is the SAS code I used:

proc optmodel;
   var x;
   var y >= 0;
   con (x+y)^2/sqrt(y) <= x - y + 5;
   expand / conic;
quit;

The output is:

Var x                                                                                             
Var y >= 0                                                                                        
Var _ADDED_VAR_[1] >= 0                                                                           
Var _ADDED_VAR_[2] >= 0                                                                           
Fix _ADDED_VAR_[3] = 0.5                                                                          
Var _ADDED_VAR_[4]                                                                                
Constraint _ACON_[1]: - x + y + 2*_ADDED_VAR_[2] <= 5                                             
Constraint _ADDED_CON_[1]: RSOC(y, _ADDED_VAR_[3], _ADDED_VAR_[1])                                
Constraint _ADDED_CON_[2]: RSOC(_ADDED_VAR_[2], _ADDED_VAR_[1], _ADDED_VAR_[4])                   
Constraint _ADDED_CON_[3]: - _ADDED_VAR_[4] + x + y = 0