Main Content

Solve Feasibility Problem

Some problems require you to find a point that satisfies all constraints, with no objective function to minimize. For example, suppose that you have the following constraints:

(y+x2)2+0.1y21yexp(-x)-3yx-4.

Do any points (x,y) satisfy the constraints? To find out, write a function that returns the constraints in a structure field Ineq. Write the constraints in terms of a two-element vector x=(x1,x2) instead of (x,y). Write each inequality as a function c(x), meaning the inequalities c(x)0, by subtracting the right side of each inequality from both sides. To enable plotting, write the function in a vectorized manner, where each row represents one point. The code for this helper function, named objconstr, appears at the end of this example.

Plot the points where the three functions satisfy equalities for -2x2 and -4y2, and indicate the inequalities by plotting level lines for function values equal to –1/2.

[XX,YY] = meshgrid(-2:0.1:2,-4:0.1:2);
ZZ = objconstr([XX(:),YY(:)]).Ineq;
ZZ = reshape(ZZ,[size(XX),3]);
h = figure;
ax = gca;
contour(ax,XX,YY,ZZ(:,:,1),[-1/2 0],'r','ShowText','on');
hold on
contour(ax,XX,YY,ZZ(:,:,2),[-1/2 0],'k','ShowText','on');
contour(ax,XX,YY,ZZ(:,:,3),[-1/2 0],'b','ShowText','on');
hold off

Figure contains an axes object. The axes object contains 3 objects of type contour.

The plot shows that feasible points exist near [1.75,–3].

Set lower bounds of –5 and upper bounds of 3, and solve the problem using surrogateopt.

rng(1) % For reproducibility
lb = [-5,-5];
ub = [3,3];
[x,fval,exitflag,output,trials] = surrogateopt(@objconstr,lb,ub)

Figure Optimization Plot Function contains an axes object. The axes object with title Maximum Constraint Violation: -0.0659563, xlabel Iteration, ylabel Constraint violation contains 2 objects of type scatter. These objects represent Best function value, Best function value (infeasible).

surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.
x = 1×2

    1.7553   -3.0551

fval =

  1x0 empty double row vector
exitflag = 
0
output = struct with fields:
        elapsedtime: 36.8879
          funccount: 200
    constrviolation: -0.0660
               ineq: [-0.0660 -0.2280 -0.8104]
           rngstate: [1x1 struct]
            message: 'surrogateopt stopped because it exceeded the function evaluation limit set by ...'

trials = struct with fields:
       X: [200x2 double]
    Ineq: [200x3 double]

Check the feasibility at the returned solution x.

disp(output.ineq)
   -0.0660   -0.2280   -0.8104

Equivalently, evaluate the function objconstr at the returned solution x.

disp(objconstr(x).Ineq)
   -0.0660   -0.2280   -0.8104

Equivalently, examine the Ineq field in the trials structure for the solution x. First, find the index of x in the trials.X field.

indx = ismember(trials.X,x,'rows');
disp(trials.Ineq(indx,:))
   -0.0660   -0.2280   -0.8104

All constraint function values are negative, indicating that the point x is feasible.

View the feasible points evaluated by surrogateopt.

opts = optimoptions("surrogateopt");
indx = max(trials.Ineq,[],2) <= opts.ConstraintTolerance; % Indices of feasible points
figure(h);
hold on
plot(trials.X(indx,1),trials.X(indx,2),'*')
xlim([1 2])
ylim([-3.5 -2.5])
hold off

Figure contains an axes object. The axes object contains 4 objects of type contour, line. One or more of the lines displays its values using only markers

This code creates the objconstr helper function.

function f = objconstr(x)
c(:,1) = (x(:,2) + x(:,1).^2).^2 + 0.1*x(:,2).^2 - 1;
c(:,2) = x(:,2) - exp(-x(:,1)) + 3;
c(:,3) = x(:,2) - x(:,1) + 4;
f.Ineq = c;
end

See Also

Related Topics