|
|
Re: Lower bound of a non-convex program through the dual problem in Matlab
Posted:
Jan 23, 2013 3:59 AM
|
|
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
|
|
