Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Software » comp.soft-sys.matlab

Topic: Lower bound of a non-convex program through the dual problem in Matlab
Replies: 5   Last Post: Jan 23, 2013 3:59 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Johan Lofberg

Posts: 39
Registered: 11/6/06
Re: Lower bound of a non-convex program through the dual problem in Matlab
Posted: Jan 23, 2013 3:59 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

With, YALMIP, you can solve small problems to global optimality. By tweaking the options, you can tell it to give up early and return a valid lower bound (on the minimization objective)

sdpvar x
Constraints = [0<= x <= 50];
Objective = exp(-x).*cos(2*pi*x);
options = sdpsettings('solver','bmibnb');
% Solved to global optimality after 5 calls to fmincon
% (and a bunch of LP calls for bound propagation)
solvesdp(Constraints, Objective,options);

% terminate early and extract lower bound
options = sdpsettings('solver','bmibnb','savesolveroutput',1,'bmibnb.maxiter',1);
solvesdp(Constraints, Objective,options);
sol.solveroutput.lower_hist(end)

Might be an overly complex strategy though, in the sense that it implements a branch-and-bound strategy (you would thus have a b&b code compute lower bounds in your b&b code...)


"Nazmul Islam" wrote in message <kdmpr0$k31$1@newscl01ah.mathworks.com>...
> Bruno,
>
> That's a good observation! :) I am actually maximizing an integer non-concave nonlinear program :S. I am using branch and bound to solve the problem, i.e.:
>
> 1. I make some decision on the integer variables.
>
> 2. For each decision variable, I try to get an upper and lower bound of the problem.
>
> 3. I compare the bounds of different branches (integer variables) and remove the worse ones.
>
> 4. After some iterations, I will stop, pick the best branch (integer variable) and hopefully know how far I am from the optimum (using the best upper bound).
>
> Any feasible solution of a non-concave program can be treated as its lower bound. But, I need some ways to calculate a good upper bound (not +Inf :) ). I am looking for some software that can help me.
>
> Thanks,
>
> Nazmul
>
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kdmivl$nth$1@newscl01ah.mathworks.com>...

> > "Nazmul Islam" wrote in message <kdmigl$mcj$1@newscl01ah.mathworks.com>...
> >

> > >
> > > Unfortunately, my solution is getting stuck at a local minimum. Please let me know if I can get the lower bounds of this problem through the interior point method.

> >
> > -Inf is lower-bound. Of course it is useless answer, nevertheless it is a correct answer (You never explain why you need a lower-bound for).
> >
> > Bruno




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.