Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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

share|improve this answer
    
I have edited the question, I hope the question is clearer now. I am reading through your slides. It is very informational. Thanks. –  Sainath adapa Oct 23 '12 at 2:33
    
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? –  Sainath adapa Oct 23 '12 at 2:55
    
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). –  Markus Schweighofer Oct 24 '12 at 7:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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