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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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

Improve this answer
$\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$
    – Sainath Adapa
    Commented 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$
    – Sainath Adapa
    Commented 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$
    – Markus Schweighofer
    Commented Oct 24, 2012 at 7:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .