<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Aug 8, 2013 at 8:11 PM, Nicolas Bock <span dir="ltr"><<a href="mailto:nicolasbock@gmail.com" target="_blank">nicolasbock@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">I am sorry, I oversimplified the problem. Suppose the cost function is more complicated, and looks something like this:<div>
<br></div><div>max_{X} Tr( C_{1} X + [ C_{2} X ]_{+} )</div><div><br></div></div></blockquote><div><br></div><div>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. </div>
<div> </div><div>For example, consider the problem</div><div> </div><div>max (x-2)_{+} + (2-x)_{+} + 2</div><div>subject to 1 <= x <= 3</div><div><br></div><div>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. </div>
<div><br></div><div>This problem can be put into your form, although it's a bit cumbersome. Let X be a 6x6 matrix. </div><div><br></div><div>Let C_{1}=0. </div><div><br></div><div>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].</div>
<div><br></div><div>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</div><div>constraint</div><div> </div><div>X(1,1)-X(3,3)=0</div><div><br></div><div>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. </div>
<div> </div><div>We'll enforce the constraint x>=1 with the linear constraint </div><div><br></div><div>X(1,1)-X(5,5)=1</div><div><br></div><div>Here X(5,5)>=0 because X is PSD. </div><div><br></div><div>Similarly, we'll enforce the constraint x<=3 with the linear constraint</div>
<div><br></div><div>X(1,1)+X(6,6)=3</div><div><br></div><div>where again, X(6,6)>=0 by the positive semidefiniteness of X. </div><div> </div><div>If you examine the objective function and the matrix C_{2} given above, you'll see that </div>
<div> </div><div>tr(C_{1}X+(C_{2}X)+)=tr((C_{2}X)+)=(x-2)_{+} + (-2)_{+} + (2-x)_{+} + (2)_{+} = | x - 2 | + 2</div><div><br></div><div>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. </div>
<div><br></div><div>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. </div>
<div><br></div></div>-- <br>Brian Borchers <a href="mailto:borchers@nmt.edu" target="_blank">borchers@nmt.edu</a><br>Department of Mathematics <a href="http://www.nmt.edu/~borchers/" target="_blank">http://www.nmt.edu/~borchers/</a><br>
New Mexico Tech Phone: (575) 322-2592<br>Socorro, NM 87801 FAX: (575) 835-5366
</div></div>