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:
How to get the global minimum by 'fmincon' ?

Subject: How to get the global minimum by 'fmincon' ?

From: Maite Li

Date: 2 May, 2011 15:25:20

Message: 1 of 4

Hi all,
I'm trying to solve an optimization problem by using the function 'fmincon'.
This optimization problem is:
min sum{1/[w*log2(1 + (P_i * H_i)/(alpha_i * w * N0 * t * d^e))]},
under these constraints:
sum(P_i) = P_tot, sum(alpha_i) = 1, 0 < P_i < P_s, 0 < alpha_i < 1 for all i,
where P_i and alpha_i are the optimizing variables and the others are fixed parameters.

Now I get two solutions for this problem. One is derived by myself using the dual decomposition method, and the other one is got from the function 'fmincon' by using the following codes:
    P0 = zeros(t+1,1);
    alpha = ones(t+1,1);
    alpha(1:end) = 1/(t+1);
    P_0 = [P0;alpha];
        
    A_eq = zeros(2,2*(t+1));
    A_eq(1,1:t+1) = 0;
    A_eq(1,t+2:end) = 1;
    A_eq(2,1:t+1) = T_v;
    A_eq(2,t+2:end) = 0;
    B_eq = [1;P_tot];

    lb = zeros(2*(t+1),1);
    lb(1:end) = 0.0001;
    ub = zeros(2*(t+1),1);
    ub(1:end) = P_s;
        
    % warning off;
    options = optimset('fmincon');
    options = optimset(options,'Display','iter');
    options = optimset(options,'Algorithm','interior-point');
        
    [P_opt,P_opt_out,exitflag,out_put] = fmincon(@(P) sum(10^6./(w.*log2(1 + (P(1:t_v+1)'.*H)./(P(t_v+2:end)'.*T_v*w*N)))),P_0,[],[],A_eq,B_eq,lb,ub,@(P) nonlcon(P,H,w,N,T_v,t_v),options);

Here comes the problem: the first solution, which I derived myself, is slightly better than the second. I've simulated and checked for many times, and the only explanation I've got is that the fmincon function can't find the global minimum!

Now I need some help to find this global minimum either by fmincon or by some other possible ways. I really appreciate any suggestions or opinions.

Thank you in advance!

 

Subject: How to get the global minimum by 'fmincon' ?

From: Srikanth

Date: 2 May, 2011 15:51:53

Message: 2 of 4

On May 2, 8:25 am, "Maite Li" <bestcrui...@gmail.com> wrote:

> Now I need some help to find this global minimum either by fmincon or by some other possible ways. I really appreciate any suggestions or opinions.
>
> Thank you in advance!

Getting global minimum for nonlinear and nonconvex problems is hard -
for example, consider sin(1/x)+x. Clearly, as you go closer to zero,
sin(1/x) oscillates between -1 and 1, while the additional x is like a
ramp. So you can get arbitrarily close to -1 without actually ever
reaching it. Expecting an optimizer to get the global solution is
unreasonable. While this problem is academic, it illustrates the
point.

In general, you can use multi-start methods - run fmincon with a large
number of initial conditions scattered around the domain. Hopefully,
you get atleast one initial guess close to the global solution, which
should converge to the global minimizer.

Also, you can set the tolerance for the options - when it should
terminate the minimization (i.e. set step sizes, and solution
tolerances very low). This will increase the execution time, but it
should get closer to a local minimizer. If your solution and Matlab's
solution are close together, this alone might be sufficient to get you
to the desired solution.

hth
Srikanth

Subject: How to get the global minimum by 'fmincon' ?

From: Maite Li

Date: 2 May, 2011 22:42:04

Message: 3 of 4

Srikanth <skt@xdtech.com> wrote in message <6c6dc700-5c3d-4456-afa3-35fa4296880f@h36g2000pro.googlegroups.com>...
> On May 2, 8:25 am, "Maite Li" <bestcrui...@gmail.com> wrote:
>
> > Now I need some help to find this global minimum either by fmincon or by some other possible ways. I really appreciate any suggestions or opinions.
> >
> > Thank you in advance!
>
> Getting global minimum for nonlinear and nonconvex problems is hard -
> for example, consider sin(1/x)+x. Clearly, as you go closer to zero,
> sin(1/x) oscillates between -1 and 1, while the additional x is like a
> ramp. So you can get arbitrarily close to -1 without actually ever
> reaching it. Expecting an optimizer to get the global solution is
> unreasonable. While this problem is academic, it illustrates the
> point.
>
> In general, you can use multi-start methods - run fmincon with a large
> number of initial conditions scattered around the domain. Hopefully,
> you get atleast one initial guess close to the global solution, which
> should converge to the global minimizer.
>
> Also, you can set the tolerance for the options - when it should
> terminate the minimization (i.e. set step sizes, and solution
> tolerances very low). This will increase the execution time, but it
> should get closer to a local minimizer. If your solution and Matlab's
> solution are close together, this alone might be sufficient to get you
> to the desired solution.
>
> hth
> Srikanth

Hi Srikanth,

thank you so much for your help! I figured out this convex thing and changed several options, including the starting point, maximum iteration times and also the element you mentioned, the tolerance. Finally it worked out!
Now I do have a good solution which is better than the one I derived. But here comes another problem: how to prove that this solution is the global minimum? Do you know any methods about this?

Best regards,
Maite Li

Subject: How to get the global minimum by 'fmincon' ?

From: Srikanth

Date: 5 May, 2011 16:30:39

Message: 4 of 4

> But here comes another problem: how to prove that this solution is the global minimum? Do you know any methods about this?

Hi
I'm not sure of any method to prove that the solution is a global
minimum for general nonlinear functions. For convex functions,
however, the minimum will be a global minimum. However, the minimizer
itself might not be unique (think about the function y(x1,x2) = x1^2.
It is convex, and the minimum is zero, but the entire line x1=0 is are
minimizers).

hth
Srikanth

Tags for 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