Maximize a distance

[Marc Wijnand]

Is there a possibility to find the maximum distance of an sdpvariable x, element of a set X, to a set Y?

For example:

The variable

x=sdpvar(2,1)

belongs to an ellipse of the form x'Px<=a:

P=[4 1; 1 3];
a=100;
constraints=[x'*P*X<=a];

I define Y as the square between the points (3,3), (-3,3), (-3,-3), (3,-3) with the MPT toolbox as

Y=Polyhedron('A',[eye(2);-eye(2)],'b',3*ones(4,1));

The question is now how to maximize the distance from x to Y, over all x in the ellipse. This has following form:

cost=-distance(Y,x)
optimize(constraints,cost)

Here, the MPT function distance(A,a) is used, which computes the distance of a point a to a set A. However, this function does not accept Yalmip's sdpvariables as arguments.

Any comments?

[Johan Löfberg]

As said on the MPT forum, you generally cannot mix MPT stuff in YALMIP models. You have to convert

Easiest to not involve MPT at all

x = sdpvar(2,1)
y = sdpvar(2,1);
constraints1=[x'*P*X<=a];
constraints2=[-3 <= y <= 3];
cost = -(x-y)'*(x-y);

Of course, your main problem know is the fact that you've just defined a nonconvex quadratically constrained problem.

If you absolutely want to use the polyhedron object, you can do

constraints2=ismember(y,Y);

[Mark L. Stone]

Johan, I think this may have come up before on this forum, but YALMIP can invoke cplexqcp with a non-psd matrix Q.  Then cplexqcp fails.  Meanwhile, YALMIP could have used another solver.  I tried solving your formulation without specifying solver, and it chose cplexqcp.  Meanwhile, fmincon and knitro were available, and in fact both could solve to a local optimum (but I needed to specify a non-default starting point to get what turned out to be a globally optimal solution, as opposed to the default x=y=[0;0]).

a=1;P=eye(2);

x = sdpvar(2,1)
y = sdpvar(2,1);

constraints1=[x'*P*x<=a];

constraints2=[-3 <= y <= 3];
cost = -(x-y)'*(x-y);

optimize([constraints1,constraints2],cost,sdpsettings('debug',1))

Presolve time = 0.00 sec. (0.00 ticks)
Error using cplexqcp (line 652)
CPLEX Error  5002: Q in %s is not positive semi-definite.

+++++++++++++++

BMIBNB using CPLEX LP, lower and upper solver solved the problem.

++++++++++++++

BARON failed (with or without 'usex0',1), but I can't tell you whose fault is it is (YALMIP side or BARON's matbar side). I used BARON 14.4.0 with matbar v 1.69 (which is the most recent) under MATLAB R2014A win64 and YALMIP R20150204.

optimize([constraints1,constraints2],cost,sdpsettings('solver','baron','debug',1))

MATLAB/BARON Interface Version: v1.69 [12-October-2014]
===========================================================================
 BARON version 14.4.0. Built: WIN-64 Tue Dec 2 15:07:16 EST 2014 
 
 If you use this software, please cite:
 Tawarmalani, M. and N. V. Sahinidis, A polyhedral
 branch-and-cut approach to global optimization,
 Mathematical Programming, 103(2), 225-249, 2005.
 
 BARON is a product of The Optimization Firm, LLC. http://www.minlp.com/
 Parts of the BARON software were created at the
 University of Illinois at Urbana-Champaign.
===========================================================================
ERROR: Two consecutive operators found in line 34
BARON: Syntax error.  Execution will stop
ans =
    yalmiptime: 0.0587
    solvertime: 0.3223
          info: 'Other identified error (BARON)'
       problem: 11

[Mark L. Stone]

I think it's clear, but just to be a bit more explicit, in my opinion, YALMIP should have recognized cplex as being an inapplicable solver in this case.

[Marc Wijnand]

Thank you for the clarification about mixing MPT and YALMIP.

My goal is to use a custom distance function rather than the Euclidean distance, in order to check whether the set X is contained in Y (see for example the figure attached).

Analogously to the MPT function distance(A,a), I want to define a custom distance function mydistance(x,Y) that takes as arguments 1. an sdpvariable x that is member of a constraint set X and 2. a constraint set Y. Mydistance(x,Y) calculates the shortest Eucledian distance between x and any y in Y, as long as x in not a member of Y; if x is member of Y (on its boundary or in its interior), it gives the value 0.
Maximizing mydistance(x,Y) with the constraint that x is member of X yields thus a positive number when there is a part of X that is not contained in Y; and returns 0 if X lies entirely inside Y.

Any hints on how to proceed?

[Johan Löfberg]

Computing this (Hausdorff?) distance to detect inclusion does not sound like a good idea. If you know both sets are polyhedral, you should use dedicated methods for that, and if you know they are ellipsoidal, there are dedicated methods for that. The mixed case you have should also be easy to write a test for

The most generic optimization based approach I can think of, which works for polyhedral Y, it to pose it as a bilvel optimization problem, which will have terrible complexity, as the inner program KKT introduced integer variables, and the outer program is nonconvex quadratic

x = sdpvar(2,1);

y = sdpvar(2,1);

X = x'*[2 1;2 2]*x <= 1;

Y = [-.5 <= y <= .5]

plot(X,[],'r');

plot(Y,[],'y');

[KKTmodel] = kkt(Y,(x-y)'*(x-y),x);

Model = [X,KKTmodel];

optimize([Model,-100 <= recover(depends(Model)) <= 100],-(x-y)'*(x-y),sdpsettings('solver','bmibnb'))

hold on

plot(value(x(1)),value(x(2)),'k*')

plot(value(y(1)),value(y(2)),'k*')

[Johan Löfberg]

cplex supports nonconvex qps, but not qcqps, so I'll have to separate those cases better

the baron failure can be fixed by cleaning up the function definition. add

obj = strrep(obj,'+-','-');

on line 23 in callbaron.m

[Mark L. Stone]

Johan, thanks. That works now in BARON.