Hi All,

I have a question regarding SeDuMi input structure of a SDP relaxation for polynomial programming problems. (I searched through the forum to find a similar topic, but could not see one. Hope I am not replicating a discussion.)

Here is an example of a polynomial programming problem of order 3, with 3 variables. (Sherali and Tuncbilek, 1992).
[img]http://sedumi.ie.lehigh.edu/images/fbfiles/images/PolyProgProb.png[/img]

Accordingly, I define the matrix variable Y, which yields:
[img]http://sedumi.ie.lehigh.edu/images/fbfiles/images/MatrixY.png[/img]

Here is my YALMIP input for SeDuMi:
[img]http://sedumi.ie.lehigh.edu/images/fbfiles/images/YALMIP.png[/img]

Given that I impose PSD on Y(1:4, 1:4)
Q1: Do I need to include equality constraints?
[img]http://sedumi.ie.lehigh.edu/images/fbfiles/images/EqualityCons.png[/img]
Q2: Do I need to impose bounds on variables of degree 4?

I know that I would need to include them if the program was of order 4. Since the degree is 3, these variables do not show up in objective function, original constraints, and LMI constraint. So, I think I shouldn't include them.

Thanks in advance for your help :)
Evrim

Ps. I am not sure if the images appear correctly.

Q1: Yes, how would those connections otherwise be known to the solver?

Q2: Well, not for the first order relaxation. All the nonlinearities in your problem are in the Y matrix

Having said that, I hope you know that YALMIP can do all this for you. It is the moement relaxation module you are reimplementing here

objective = x1*x2*x3+x1^2-...
constraints = [4*x1+3x2...
solvemoment(constraints,objective,[],2)

This will setup the moment matrices etc automatically. What happens is basically this (the moment module is more general etc)
Moment = monolist([x1,x2,x3],2)*monolist([x1,x2,x3],2)'
solvesdp([constraints,M>0],objective,sdpsettings('relax',1))

Using the relax options in YALMIP means that all monomials are treated as independent variables.

Thank you very much for your quick reply!

I am not sure what "solvemoment" command does for this example. In Lasserre's work, the original constraints are also utilized within the SDP relaxations. However, I just want to have one LMI constraint, which is on the matrix Y (or a submatrix of it).

I use solvemoment command, and SeDuMi gives -119 as the objective function value, which coincides with the optimal objective value of the original polynomial programming problem.

On the other hand, if I use the following code, then I get an objective value of -175, which shows that there is a significant difference between these two relaxations.
Y = sdpvar(10,10);
Objective = [Y(4,6)+Y(2,2)-2*Y(2,3)-3*Y(2,4)+5*Y(3,4)-Y(4,4)+5*Y(1,3)+Y(1,4)];
Constraints = [4*Y(1,2)+3*Y(1,3)+Y(1,4) < 20, Y(1,2)+2*Y(1,3)+Y(1,4) > 1,
Y(1,1) == 1, Y > 0,

2 <Y(1,2) <5, 0 <Y(1,3) < 10, 4 <Y(1,4) <8, 4 <Y(2,2) <25, 0 <Y(2,3) < 50, 0 <Y(3,3) <100, 8 <Y(2,4) < 40, 0 <Y(3,4) <80, 16 <Y(4,4) < 64, 8 <Y(2,5) <125, 0 <Y(3,5) < 250, 16 <Y(4,5) < 200, 0 <Y(3,6) < 500, 0 <Y(4,6) < 400, 32 <Y(4,7) <320,
0 <Y(3,8) < 1000, 0 <Y(4,8) < 800, 0 <Y(4,9) < 640, 64 <Y(4,10) <512, 16 <Y(5,5) < 625, 0<Y(5, 6)<1250, 0< Y(6, 6) <2500, 32 <Y(5,7)<1000, 0 < Y(6,7) <2000, 64 <Y(7, 7)<1600, 0<Y(6, 8) <5000, 0<Y(7,8)<4000, 0<Y(8,8)<10000, 0<Y(7,9)<3200, 0<Y(8,9)<8000, 0<Y(9,9)<6400, 128<Y(7,10)<2560, 0<Y(9, 10)<5120, 0<Y(10,10)<4096,

Y(2,2) == Y(1,5), Y(2,3) == Y(1,6), Y(2,4) == Y(1,7), Y(3,3) == Y(1,8), Y(3,4) == Y(1,9), Y(4,4) == Y(1,10), Y(3,5) == Y(2,6), Y(4,5) == Y(2,7), Y(3,6) == Y(2,8), Y(4,6) == Y(2,9),
Y(4,7) == Y(2,10), Y(4,6) == Y(3,7), Y(4,8) == Y(3,9), Y(4,9) == Y(3,10), Y(6,6) == Y(5,8), Y(6,7) == Y(5,9), Y(7,7) == Y(5,10), Y(7,8) == Y(6,9), Y(7,9) == Y(6,10), Y(9,9) == Y(8,10) ];
solvesdp(Constraints,Objective)

In the above relaxation, I have Y>0. When I change it to Y(1:4, 1:4)>0, I get an objective function value of -191. This is the relaxation I am interested in.

One other modification: Using Y(1:4, 1:4) > 0, remove equality constraints and remove bounds on degree-four variables. Now, the objective function value is again -191. If these consraints are redundant, I don't want to include them, since they probably worsen SeDuMi's performance, especially for larger problems.

Now, as I return back to my original question, the removal of equality constraints (Question 1) and bounds on degree 4 variables (Question 2) does not change the objective function value for this example. My intuition is that since these variables are not involved in objective function, constraints and within Y(1:4, 1:4) (on which I impose PSD), the objective function value will not change anyways.

I would like to hear your ideas about it.
Evrim

solvemoment is Lasserres relaxation. In this particular case, the objective involves 3rd order terms, hence "Y" has size 10 in the problem that solvemoment sets up (since products of quadratic monomials will be required)

Since all constraints are linear, the localizing LMI constraints will be able to exploit up to quadratic terms. You are simply skipping these terms so your relaxation will not be as strong. The problem YALMIP compile looks like this
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| ID| Constraint| Type|
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| #1| Numeric value| Matrix inequality (polynomial) 10x10|
| #2| Numeric value| Matrix inequality (polynomial) 4x4|
| #3| Numeric value| Matrix inequality (polynomial) 4x4|
| #4| Numeric value| Matrix inequality (polynomial) 4x4|
| #5| Numeric value| Matrix inequality (polynomial) 4x4|
| #6| Numeric value| Matrix inequality (polynomial) 4x4|
| #7| Numeric value| Matrix inequality (polynomial) 4x4|
| #8| Numeric value| Matrix inequality (polynomial) 4x4|
| #9| Numeric value| Matrix inequality (polynomial) 4x4|
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Just because a term doesn't show up in the objective doesn't mean that you don't need to constrain it with all information you have. There are coupling effects in the problem. Otherwise, it would never make sense to user increasingly larger semidefinite relaxation (which just introduce higher and higher ("unused") orders)

As I understand this is a Lifted LMI Relaxation where the 1st order moment matrix (say M1) is used. Though a bit high on complexity, if we consider the 2nd order moment matrix (say M2, also M1 is a subset of M2), the constraints will be expressed in terms of M1 and M2>=0 should be added. We get a tighter bound. Please clarify if this procedure can be applied.

Regards,
Parker.