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:


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. The axes 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. The axes with title Maximum Constraint Violation: -0.0799947 contains 2 objects of type line. These objects represent Best function value (infeasible), Best function value.

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

    1.7312   -3.0312

fval =

  1x0 empty double row vector
exitflag = 0
output = struct with fields:
        elapsedtime: 28.9464
          funccount: 200
    constrviolation: -0.0800
               ineq: [-0.0800 -0.2083 -0.7625]
           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.

   -0.0800   -0.2083   -0.7625

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

   -0.0800   -0.2083   -0.7625

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');
   -0.0800   -0.2083   -0.7625

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
hold on
xlim([1 2])
ylim([-3.5 -2.5])
hold off

Figure contains an axes. The axes contains 4 objects of type contour, line.

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;

See Also

Related Topics