# Convex optimization approximation

Consider the optimization problem $\mathcal{P}_0$

\begin{equation*} \begin{aligned} & \underset{x\in \mathbb{R}^2}{\text{minimize}} & & \left\| x-p \right\|^2 \\ & \text{subject to} & & \ A x \leq b, & \ \ x_1^2 + x_2^2 = 1 \end{aligned} \end{equation*}

where $p \in \mathbb{R}^2$ is a parameter, and $x^*(p)$ is the optimal solution.

I am looking for a $convex$ optimization problem $\mathcal{P}$ such that $x^*(p)$ "approximates" the optimal solution of $\mathcal{P}$.

• Typo: $A x \leq b$. – user693 Aug 18 '14 at 7:25
• Hardly I guess, the norm equality ruins it all. Try relaxing to $x_1^2+x_2^2\leq 1$? – Troy Woo Aug 18 '14 at 7:37
• Yes, $x_1^2 + x_2^2 \leq 1$ was the only thing I came up with. I would like something better. – user693 Aug 18 '14 at 7:48
• You're not going to get one, I'm afraid. But this is only in $\mathbb{R}^2$, right? Just sample the unit disk, then, and pick the best result. Do a local search if you want to refine further. – Michael Grant Aug 18 '14 at 12:45
• Since you're looking to convexify I'm assuming you also want to generalize to higher dimension. But in the 2-D case you can do something better right? For instance you can find the closest point on the circle from p quite easily. If that's in your set you're done. If not I think it might be possible to show that the minimizer is one of the "end points" of the segment, both of which should be computable by solving a convex problem each. This is just conjecture though and not sure how it would generalize to higher dimension. – wonko Aug 18 '14 at 15:18

There is a whole field devoted to this problem. Look up material on semidefinite relaxations, sum-of-squares and moment methods. Papers by Jean Bernard Lasserre, such as "Global optimization with polynomials and the problem of moments" SIAM J. Optimization 11, pp 796--817. " might be a good start.

There is software for the problem too, such as the MATLAB toolboxes sostools, gloptipoly and YALMIP. For reference, here is a quick test with YALMIP (developed by me). I solve the naive relaxation discussed in the comments (which typically yields a poor solution), the global optimization problem using YALMIPs built-in global solver (solving a nonconvex quadratic problem in $R^2$ is trivial), and using a semidefinite relaxation (which typically solves the problem here exactly, i.e., the semidefinite relaxation is tight and the solution $x$ can be recovered)

% Random problem
p = randn(2,1);
A = randn(10,2);
b = A*[1;0] + rand(10,1);
p = randn(2,1);

% Naive relaxation
x = sdpvar(2,1);
Constraints = [A*x <= b,x'*x <= 1];
Objective = (x-p)'*(x-p);
solvesdp(Constraints,Objective)
% Display solution
[double(x)' double(Objective)]

% True global solution
Constraints = [A*x <= b,x'*x == 1];
Objective = (x-p)'*(x-p);
solvesdp(Constraints,Objective,ops)
ops = sdpsettings('solver','bmibnb');
[double(x)' double(Objective)]

% First semidefinite relaxation
[~,extractedsolutions] = solvemoment(Constraints,Objective,[],1)
relaxdouble(Objective)
extractedsolutions{1}