Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Lower bound of a non-convex program through the dual problem in Matlab

Subject: Lower bound of a non-convex program through the dual problem in Matlab

From: Nazmul Islam

Date: 19 Jan, 2013 07:23:08

Message: 1 of 6

I want to get the lower bound of a non-convex program through the dual problem. Can I do it using the standard Matlab optimization toolboxes?

For example, I have the following problem:

min f0(x)
s.t. f1(x) <= 0

Here, f1(x) is non-convex. Let, the lagrange dual function, g(p) = inf_x (f0(x) + p*f1(x).
The optimal dual solution: max_p g(p). This dual solution is a lower bound of my original primal problem.

Can I obtain this dual solution, i.e., the lower bound, using Matlab optimization toolboxes? I know that I cannot get the global minimum through the primal problem since it is non-convex. Any help will be appreciated.

Thanks,

Nazmul

Subject: Lower bound of a non-convex program through the dual problem in Matlab

From: Bruno Luong

Date: 19 Jan, 2013 10:16:08

Message: 2 of 6

Use fmincon with interior-point method. I believe it minimizes the dual-gap.

Bruno

Subject: Lower bound of a non-convex program through the dual problem in Matlab

From: Nazmul Islam

Date: 22 Jan, 2013 17:33:09

Message: 3 of 6

Dear Bruno,

Thanks for your reply. I tried the 'interior-point-method' to solve the following (trial) optimization problem:

min_x exp(-x) * cos(2*pi*x)
s.t. x >= 0

I used the following options:

options = optimset('Display','off','Algorithm','interior-point','MaxFunEvals', 5000,'TolFun', 1e-6,'TolX',1e-6,'TolCon',1e-6, 'MaxIter', 500,'Display','off');

[x,netval,exitflag] = fmincon(@NonConvexFunction,x0,[],[],[],[],0,[]); %% 0 is the %% lower bound of x

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.

Please also inform me if you know of any other software that provides bounds for non-convex problems.

Thanks,

Nazmul


"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kddrp8$p10$1@newscl01ah.mathworks.com>...
> Use fmincon with interior-point method. I believe it minimizes the dual-gap.
>
> Bruno

Subject: Lower bound of a non-convex program through the dual problem in Matlab

From: Bruno Luong

Date: 22 Jan, 2013 17:41:09

Message: 4 of 6

"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

Subject: Lower bound of a non-convex program through the dual problem in Matlab

From: Nazmul Islam

Date: 22 Jan, 2013 19:38:08

Message: 5 of 6

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

Subject: Lower bound of a non-convex program through the dual problem in Matlab

From: Johan Lofberg

Date: 23 Jan, 2013 08:59:09

Message: 6 of 6

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

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us