1
$\begingroup$

i am trying to solve a general linear objective function with non-linear constraints. Can someone help me solve this. Here is an example of one problem i am trying to solve,

minimize $b$

subject to $b \geq 0$

$yi - xi*m -c \geq 0$ for all i

$yi - xi*m -c \leq b(\sqrt(1+m^2))$ for all i

(xi,yi) = (1,2), (3,5), (9,7), (6,8), (7,6.5), (3,5.8), (10,19), (4,6)

The above problem is an example of what I am trying to solve. The number of (xi,yi) values is in the range of thousands for the real problem.

$\endgroup$

1 Answer 1

1
$\begingroup$

You can try the Lasserre moment relaxations of polynomial optimization problems, see the survey of Monique Laurent:

http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf

The code for your example in YALMIP (a MATLAB package) is:

clear b c m r
sdpvar b c m r

x = [1 2; 3 5; 9 7; 6 8; 7 6.5; 3 5.8; 10 19; 4 6]

constraints = set(b>=0) + set(r^2<=1+m^2) + set(m>=0)
for i = 1 : size(x,1)
constraints = constraints + set(0 <= x(i,2)-x(i,1)*m-c <= b*r)
end

relaxdeg=4

[info,sol,mom,cert]=solvemoment(constraints,b,[],relaxdeg)

sol{1}

This gives the following (at least numerically) optimal solution:

b = 4.7548
c = -9.9939
m = 1.8874
r = 2.1350

For this to work you need an SDP solver like SeDuMi. Implementations of the Lasserre moment approach other than YALMIP are SOSTools, GloptiPoly and SparsePOP. I have also some slides which might be helpful:

http://www.math.uni-konstanz.de/~schweigh/presentations/polopt-kirchberg.pdf

$\endgroup$
3
  • $\begingroup$ I have edited the question, I hope the question is clearer now. I am reading through your slides. It is very informational. Thanks. $\endgroup$ Oct 23, 2012 at 2:33
  • $\begingroup$ if i square the constraints, i can solve through sequential quadratic programming, isn't it?Is there efficient way to solve this problem other than SQP? $\endgroup$ Oct 23, 2012 at 2:55
  • $\begingroup$ I just remarked that I accidentally added the constraint "set(m>=0)". However, without this constraint YALMIP does not find (at least at this relatively low relaxation degree of 4) an optimal solution. And moreover, if you add the constraint "set(m<=0)", then YALMIP gives a lower bound of 11.7390 (at the same relaxation degree) for the true optimal value of the problem with the additional constraint m<=0. Henceforth, the solution I gave above should nevertheless be correct (numerically). $\endgroup$ Oct 24, 2012 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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