Why is fmincon giving me a wrong answer depending on which initial feasible point I am using?

I am using fmincon to solve a minimization problem with nonlinear constraints. The problem is that, it is giving me a wrong answer, a point that is not a minimizer (not even close), and that is not within the tolerance. I made sure to use a feasible initial point.

However, when I use another initial feasible point, it gives me a correct answer.

Here is the problem:

min f = 100*(x(2)-x(1)^2)^2+(1-x(1))^2;
s.t. constraints= [1-(x(1)*x(2));-x(1)-(x(2))^2;x(1)-0.5]   <= 0

The minimizer is [0.5 ; 2] with optimal objective value: 306.5000

However when I use the feasible initial point x0=[-1 ; -2], this gives me the answer: [-0.7921; -1.2624] (which is not feasible and has an f value of 360.3798 !!) (to within options.TolCon = 1e-06)

and when I use the initial point x0=[0.4;4], this gives me the correct answer [.5;2].

Note that my constraints do not require the variables to be non-negative.

Any idea what I am doing wrong here?

Answer 1

[Shashank Prasanna]

Del, it is untrue that x0=[-1 ; -2] is feasible. Lets take a look at your constraint:

1-x1*x2  <= 0            ==> x1 and x2 should be of the same sign

-x1-x2^2 <= 0            ==> x1 >= 0 (Hmmm, x2 is always +ve implies x1 >= 0)

x1 - 0.5 <= 0            ==> x1 < 1/2 (this is a bound constraint, put it in ub)

your second constraint is not satisfied by the initial point.

[Shashank Prasanna]

btw since you are solving the rosenbrock problem, but with different constraints, feel free to go through this documentation page:

http://www.mathworks.com/help/optim/ug/example-nonlinear-constrained-minimization.html#brg0p3g-2

[Del]

why is my second constraint not satisfied by the initial point?

-(-1)-(-2)^2= -3 <=0 right?

And why is x2 always positive?

[Shashank Prasanna]

My bad, you are right. But the real reason you are getting different results is because your objective function is now discontinuous due to the constraints and different starting points is putting your value in different "islands" If you run the following code it should be come very clear to you:

clear all 
close all
[X Y] = meshgrid(-5:0.05:5,-5:0.05:5);
F = 100*(Y-X.^2).^2+(1-X)^2;
surf(X,Y,F,'EdgeColor','none')
shading interp,view(2)
% 
C1 = X.*Y>=1;
F1=F;
F1(~C1)=NaN;
figure, surf(X,Y,F1,'EdgeColor','none')
shading interp,view(2)

C2 = X+Y.^2 >=0;
F2=F1;
F2(~C2)=NaN;
figure, surf(X,Y,F2,'EdgeColor','none')
shading interp,view(2)

C3 = X<=0.5;
F3=F2;
F3(~C3)=NaN;
figure, surf(X,Y,F3,'EdgeColor','none')
shading interp,view(2)

hold on
plot(-0.7921,-1.2624,'*r')
plot(0.5,2,'*r')

[Shashank Prasanna]

Each plot represents a progressive removal of constrain-ted regions.

[Del]

ok, I see, so maybe, it is because fmincon finds the local min that is closest to the initial point provided, and not the global min.

[Shashank Prasanna]

Of course :) thats the reason we have the global optimization toolbox. Fmincon is a gradient based method, if there are discontinuities gradient doesn't help. Try global search or even ga from the global optim toolbox.

[Walter Roberson]

fmincon does not necessarily find the local min that is "closest" to the initial point. If the local min is narrow enough, the gradient calculations could overshoot it and continue on to another local min.

[Del]

what does it mean for a local min to be narrow?

[Sean de Wolski]

@Del:

x = 1:0.1:10;
y = 1- sqrt(x);
y(15) = y(15)-0.3;
plot(x,y)

Basically if you're sledding down that hill, there is a chance the sled might jump the gap.

Answer 2

[Greg Heath]

Since the problem is only 2-dimensional, you can start by plotting the four separate contour plots of f, C1, C2 and C3. Then the three overlays of the contours for the Cis(red,blue,green), i = 1,2,3 on top of the contours for f(black)

Hope this helps.

Thank you for formally acceptin my answer.

Greg