2
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Typo: $A x \leq b$. $\endgroup$ – user693 Aug 18 '14 at 7:25
  • 1
    $\begingroup$ Hardly I guess, the norm equality ruins it all. Try relaxing to $x_1^2+x_2^2\leq 1$? $\endgroup$ – Troy Woo Aug 18 '14 at 7:37
  • $\begingroup$ Yes, $x_1^2 + x_2^2 \leq 1$ was the only thing I came up with. I would like something better. $\endgroup$ – user693 Aug 18 '14 at 7:48
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Aug 18 '14 at 12:45
  • 1
    $\begingroup$ 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. $\endgroup$ – wonko Aug 18 '14 at 15:18
3
$\begingroup$

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}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.