Global Optimizationproblem using Global Search

Hello, i am trying to use the globalSearch function to solve the following Optimization Problem:

min - x(3)
s.t. -x(1) -x(2) <= 0
-10*x(1)+x(1)^2-4*x(2)+x(2)^2+x(3) <= 0
3x(1) + x(2) <= 12
2x(1) + x(2) <= 9
x(1) + 2x(2) <= 12
x(1), x(2) >= 0

If you try a bit out you see that x(1) = 4, x(2) = 0, x(3) = 24 is the optimal solution.

But my Matlab Code gives a different solution and i do not know why.

Here my Code:

f=@(x)-x(3);
x0 = [0,0,0];
lb = [0,0,-Inf];
gs = GlobalSearch;
A = [-1 -1 0;
    3 1 0;
    2 1 0;
    1 2 0];
b = [0; 12; 9; 12];
nonlincon = @constr;
problem = createOptimProblem('fmincon','x0',x0,'objective',f,'lb',lb,'Aineq',A,'bineq',b,'nonlcon',nonlincon)
x = run(gs,problem)

I would be thankful if someone could tell me if I did a mistake somewhere.

[Walter Roberson]

-x(1) -x(2) <= 0

okay, so x(1) + x(2) >= 0

x(1), x(2) >= 0

But if x(1) and x(2) are both >= 0, then their sum is certain to be at least 0. So it looks like that first constraint is redundant ?

[Torsten]

Where do you define the function handle for the quadratic constraint ?

[Walter Roberson]

nonlincon = @constr;

defines that handle?

[Torsten]

function [c,ceq] = constr(x)
  c = -10*x(1)+x(1)^2-4*x(2)+x(2)^2+x(3);
  ceq = [];
end

?

I get

x(1) = 3.5000    x(2) = 1.5000   x(3) = 26.5000

as optimal solution.

[Matt J]

Since the problem convex, and therefore has no non-global minima, it is strange to use GlobalSearch in this case. Just use fmincon.

[Daniela Würmseer]

I used fmincon already before but the solution was not the right one so i tried GlobalSearch.

@Torsten could you tell me how your Code looks like to get this result? Iam new to matlab so perhaps i did something wrong?

Thank you for all of your answers.

[Torsten]

function main
  f=@(x)-x(3);
  x0 = [0,0,0];
  lb = [0,0,-Inf];
  A = [-1 -1 0;
       3 1 0;
       2 1 0;
       1 2 0];
  b = [0; 12; 9; 12];
  nonlcon = @constr;
  sol =  fmincon (f, x0, A, b, [], [], lb, [], nonlcon)
end

function [c,ceq] = constr(x)
  c = -10*x(1)+x(1)^2-4*x(2)+x(2)^2+x(3);
  ceq = [];
end

Answer 1

[Matt J]

We can verify that Torsten's solution is feasible as below. Since it gives a better objective function value than your experimental solution, your solution cannot be the correct one.

A = [-1 -1 0;
    3 1 0;
    2 1 0;
    1 2 0];
b = [0; 12; 9; 12];
constr = @(x) -10*x(1)+x(1)^2-4*x(2)+x(2)^2+x(3);

x=[3.5000    1.5000   26.5000]';

b-A*x

ans = 4×1

5.0000 0 0.5000 5.5000

constr(x)

ans = 0

[Daniela Würmseer]

Hello, thank you for your answer. How am I able to get this answer with matlab? Because Global Search and fmincon gives me a different answer. (Iam new to Matlab so perhaps my Code is wrong?)

I tried (in the upper Code)

x = fmincon(f,x0,A,b,[],[],lb,[],nonlincon)

instead of

problem = createOptimProblem('fmincon','x0',x0,'objective',f,'lb',lb,'Aineq',A,'bineq',b,'nonlcon',nonlincon)

x = run(gs,problem)

[Matt J]

f=@(x)-x(3);
x0 = [0,0,0];
lb = [0,0,-Inf];
A = [-1 -1 0;
    3 1 0;
    2 1 0;
    1 2 0];
b = [0; 12; 9; 12];
nonlincon = @constr;
[x,fval]=fmincon(f, [0,0,0],A,b,[],[],lb,[],nonlincon)

Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

x = 1×3

3.5000 1.5000 26.5000

fval = -26.5000

function [c,ceq] = constr(x)
c = -10*x(1)+x(1)^2-4*x(2)+x(2)^2+x(3);
ceq = [];
end

[Daniela Würmseer]

Thank you now it works. I had the same code I think but without the "fval".

[Daniela Würmseer]

Iam still trying to learn matlab better, but by some OptimizationProblems i still dont get the right solution and I dont know why. By the following Problem the optimal solution can be only x = (0,0,0,0) because of the Aeq constraint and the lb but my code gives another solution:

f=@(x)-x(3)-x(4);

x0 = [0,0,0,0];

lb = [0,0,0,0];

A = [3 1 0 0;

2 1 0 0;

1 2 0 0];

b = [12; 9; 12];

Aeq = [-1 -1 -2 -3.5];

beq = 0;

nonlincon = @constr;

[x,fval] = fmincon(f,x0,A,b,Aeq,beq,lb,[],nonlincon)

function [c,ceq] = constr(x)

c = [];

ceq = [-10*x(1) + x(1)^2 -4*x(2)+x(2)^2 - 5*x(3) - 1.5*x(4)];

end

Solution :

x = 1×4

10-10 ×

0.2778 0.2503 0.2008 0.6934

fval = -8.9416e-11

Perhaps one of the guys who answered before @Torsten or @Matt J could look at this code and could spot what iam always doing wrong. Thank you.

[Matt J]

i still dont get the right solution and I dont know why

What do you mean "still"? I thought we established that you were getting the right solution all along.

That seems to be the case here again. The soluton you've shown is very close to x = (0,0,0,0).

[Daniela Würmseer]

Sorry, i think the word "still" was misplaced here. I was just not sure about my Code but you are right i was not seeing the "10-10 x" in the solution and like this the solution is really close to x = (0,0,0,0,0).

Thank you for the help.

Answer 2

[Matt J]

In fact, the problem can also be solved with quadprog, since it is equivalent to,

min -10*x(1)+x(1)^2-4*x(2)+x(2)^2
s.t. 
3x(1) + x(2) <= 12
2x(1) + x(2) <= 9
x(1) + 2x(2) <= 12
x(1), x(2) >= 0

and since the objective function of the reformulated problem is srictly convex, it establishes that the solution is also unique:

f=@(x)-x(3);
x0 = [0,0,0];
lb = [0,0];

A =[3 1;
    2 1;
    1 2];
b = [12; 9; 12];

H=2*eye(2);
f=[-10;-4];

[x12,x3]=quadprog(H,f,A,b,[],[]);

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

x=[x12;-x3]'

x = 1×3

3.5000 1.5000 26.5000