From Mosek’s cookbook we know:
The feasibility system \{ t > 0, t(\frac{x}{t})^2 \le y \} in \mathbb{R}^3
can be coded as[y + t, y - t, 2 * x] in JuMP.SecondOrderCone()
In this tutorial we aim to solve the following nonconvex program (NC) via a convex relaxation (CR).
(NC) \quad v := \max_w \{ w^2 + 2w : 0 \le w \le 1\}
Even a junior can tell correctly that v = 3, which is attained when w = 1.
Nonetheless, today we approach this problem from another standpoint.
We first do a reformulation.
-\frac{v}{2} = \min_w \{ -w - \frac{w^2}{2} : 0 \le w \le 1 \}
We recognize \frac{w^2}{2} as a special convex function.
It is special in that the its conjugate function admits of the same form.
And since it is proper, closed and convex, its biconjugate equals itself.
Therefore we have \frac{w^2}{2} = \sup_y \{w y - \frac{y^2}{2}\}, or -\frac{w^2}{2} = \inf_y \{\frac{y^2}{2} - w y\}.
Hence -\frac{v}{2} = \min_{w, y} \{ -w - wy + \frac{y^2}{2} : 0 \le w \le 1 \}
There are 3 objective terms, -w is simple, -wy is a standard bilinear term (also simple).
The 3rd term \frac{y^2}{2} is a convex term.
We again testified the fact ‘in a lifted space, undesirable terms can be made convex’ cf. here.
We introduce an epigraphical variable for the 3rd term, thereby
-\frac{v}{2} = \min_{w, y, u} \{ -w - wy + \frac{u}{2} : 0 \le w \le 1, y^2 \le u \}
We then rename the decisions: x := [w, y, u] \in \mathbb{R}^3
Here we are ready to write the code of the convex relaxation program
# start a pristine Julia REPL
import JuMP
import MosekTools
CR = JuMP.Model(() -> MosekTools.Optimizer()) # CR = Convex Relaxation
JuMP.@variable(CR, x[1:3])
JuMP.@variable(CR, X[eachindex(x), eachindex(x)], Symmetric)
# JuMP.@constraint(CR, [1 transpose(x); x X] in JuMP.PSDCone()); # SDP cut
JuMP.set_lower_bound(x[1], 0); JuMP.set_upper_bound(x[1], 1); # the linear constraints
JuMP.@constraint(CR, C1, [x[3] + 1, x[3] - 1, 2 * x[2]] in JuMP.SecondOrderCone()) # the epigraphical convex constraint
# the following 2 constraints are valid inequalities, they are so good such that the above SDP cut can be relaxed
JuMP.@constraint(CR, [X[1, 3] + x[1], X[1, 3] - x[1], 2 * X[1, 2]] in JuMP.SecondOrderCone()) # derived from C1 × lower_bound_constraint
JuMP.@constraint(CR, [x[3] - X[1, 3] + (1 - x[1]), x[3] - X[1, 3] - (1 - x[1]), 2 * (x[2] - X[1, 2])] in JuMP.SecondOrderCone()) # derived rom C1 × upper_bound_constraint
JuMP.@objective(CR, Min, -x[1] - X[1, 2] + x[3] / 2)
JuMP.optimize!(CR)
@assert JuMP.termination_status(CR) == JuMP.OPTIMAL
JuMP.value(x[1]) # = 1.0, i.e. the optimal `w` in (NC),
JuMP.objective_bound(CR) # lb = -1.5, this dual bound is indeed tight
From the experiment results we conclude that v \le 3, yet the solution returned by (CR) can let v take 3.
Therefore w = 1 is also an optimal solution of (NC).