[Csdp] hinge loss with slack variables

[Brian Borchers]

On Thu, Aug 8, 2013 at 8:11 PM, Nicolas Bock <nicolasbock at gmail.com> wrote:

> I am sorry, I oversimplified the problem. Suppose the cost function is
> more complicated, and looks something like this:
>
> max_{X} Tr( C_{1} X + [ C_{2} X ]_{+} )
>
>
This kind of problem can't be reformulated as an SDP because the problem
can (in general) be nonconvex, and SDP's are always convex optimization
problems.

For example, consider the problem

max (x-2)_{+} + (2-x)_{+} + 2
subject to 1 <= x <= 3

It's easy to see that the objective function is | x-2 | + 2.   There are
isolated local optimal solutions at x=1 and x=3, so this is a nonconvex
optimization problem.

This problem can be put into your form, although it's a bit cumbersome.
 Let X be a 6x6 matrix.

Let C_{1}=0.

Let C_{2}=[1 -1 0 0 0 0; -1 0 0 0 0 0; 0 0 -1 1 0 0; 0 0 1 0 0 0; 0 0 0 0 0
0; 0 0 0 0 0 0].

We'll encode x in the X(1,1) position and also make it appear in X(3,3).
 This can be done by adding the linear
constraint

X(1,1)-X(3,3)=0

We'll also make some constant entries in X, with X(1,2)=X(2,1)=2,
X(2,2)=10, and X(4,4)=10.  These are all very simple linear constraints.

We'll enforce the constraint x>=1 with the linear constraint

X(1,1)-X(5,5)=1

Here X(5,5)>=0 because X is PSD.

Similarly, we'll enforce the constraint x<=3 with the linear constraint

X(1,1)+X(6,6)=3

where again, X(6,6)>=0 by the positive semidefiniteness of X.

If you examine the objective function and the matrix C_{2} given above,
you'll see that

tr(C_{1}X+(C_{2}X)+)=tr((C_{2}X)+)=(x-2)_{+} + (-2)_{+} + (2-x)_{+} +
(2)_{+} = | x - 2 | + 2

Since we've put a nonconvex optimization problem (maximization of a convex
function with isolated local maxima) into your form, your form can't
generally be translated into an SDP.

Now it might be that you have more specific information about your problem
that does ensure that your optimization problem is a convex optimization
problem.  If that's the case, then you'll have to use this specific
information in any reformulation into SDP form.

-- 
Brian Borchers                          borchers at nmt.edu
Department of Mathematics      http://www.nmt.edu/~borchers/
New Mexico Tech                       Phone: (575) 322-2592
Socorro, NM 87801                   FAX: (575) 835-5366
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/csdp/attachments/20130808/cb45e270/attachment.html>