How to minimize a function when subjected to multiple constraints?

I am being asked to minimize this function subjected to given restraints:

 f(x)=-(x1)2 -0.5 (x2)3 subjected to

2x1 +3x2 ≤12,  
x1 +x2 ≤ 8,
1/x1 -0.5 x2 ≤ 0
-x1 ≤ 0,
-x2 ≤ 0.

My code so far:

clc
clear
[x1,x2]=meshgrid(0:0.5:10.0,0:0.5:10.0);
f=-x1.^2-.5*x2.^3;
g1=1./x1-.5*x2;
g2=2*x1+3*x2-12;
g3=x1+x2-8;
cla reset
axis auto
xlabel('x1'), ylabel('x2')
hold on 
cv1=[0.005];
const1=contour(x1,x2,g1,cv1,'g-');
% clabel(const1)
text(.8,2.8,'g1')
cv2=[0.005];
const2=contour(x1,x2,g2,cv2,'b-');
%clabel(const2)
text(2,3,'g2')
cv3=[0.005];
const3=contour(x1,x2,g3,cv3,'r-');
%clabel(const3)
text(6,2,'g3')
fv=[-12,-16,-20,-24,-28,-30];
fs=contour(x1,x2,f,fv,'k--');
clabel(fs)
hold off

I do not have any packages installed, and I am having problems finding the intersection points.

Thanks in Advance

[Walter Roberson]

Should that function have x1^2 and x2^3 rather than x1 multiplied by 2 and x2 multiplied by 3 ?

[Walter Roberson]

This is the sort of problem that would normally be solved with a fmincon. Do you have the Optimization Toolbox?

[Grant]

My professor showed me an optimization algorithm he discovered and it looks like it would do wonderful for your problem. You can easily write the algorithm without using any kind of toolboxes as well.

The algorithm goes like this:

1. Start by scattering a number of random guess (that we'll call players) all uniformly across the search space.
2. Calculate the fitness of each individual player.
3. Find the worst player and have it "jump" over the best player by picking a random location along a projected vector through the best point (the angle of the jump should be anywhere within 180degrees)
4. Each time you do a leap you halve the distance of the jump and you only need to calculate the fitness of the player that just jumped so it doesn't require too many objective function calls
5. Stop the program when the distance between jumps is within the tolerance you set or if the fitness of the best player is within the tolerance you set.

I have an example i coded up really quickly on my github and you can find it here: https://github.com/grantmwilliams/general_algorithms/tree/master/Research_Area_and_AI_and_Machine_Learning/Leap%20Frog%20Algorithm

Please note that i have some fluff in there that is not needed (like any of the plotting stuff), so feel to take any of that out, and although i've commented the code as best i can please feel free to ask any questions if you do choose to try out the algorithm.

Answer 1

[Walter Roberson]

f = @(x1,x2) -x1.^2-.5*x2.^3;
g1 = @(x1,x2) 1./x1-.5*x2;
g2 = @(x1,x2) 2*x1+3*x2-12;
g3 = @(x1,x2) x1+x2-8;
fx = @(x) f(x(:,1), x(:,2)) + ...
     1E20 * (x(:,1) < 0) + ...
     1E20 * (x(:,2) < 0) + ...
     1E20 * (g1(x(:,1),x(:,2)) > 0) + ...
     1E20 * (g2(x(:,1),x(:,2)) > 0) + ...
     1E20 * (g3(x(:,1),x(:,2)) > 0);
 N = 50;
 [X1,X2] = ndgrid(linspace(0,6,N), linspace(0,4,N));
 X12 = [X1(:),X2(:)];
 nrow = size(X12,1);
 xvals = zeros(nrow,2);
 fvals = zeros(nrow,1);
 for K = 1 : nrow
   [xvals(K,:), fvals(K)] = fminsearch(fx, X12(K,:), ...
       struct('MaxFunEvals',10000,'MaxIter',20000));
 end
 [minf, minidx] = min(fvals);
 disp(minf), disp(xvals(minidx,:))
 R = fvals .* (fvals < 0);
 scatter3(xvals(:,1),xvals(:,2),R)

You can refine after this, but the minima are pretty close to f ~= -29.7216518405542 near x1 = 5.44948942552185 and x2 = 0.367006979797786 . Incidentally, 1./x1-.5*x2 and 2*x1+3*x2-12 turn out to be key constraints there; at the minimum value, the two constraints are satisfied only by a hair, and it is plausible that the theoretical minimum is right at the boundaries of the two.