jarirepo/feasrgn

Finds the feasible region from a set of constant, linear and nonlinear inequalities

Piecewise linear feasible region
Finds the piecewise linear feasible region from a set of constraints functions (inequalities) derived within the actual problem domain.

y 'sign' f1(x)
y 'sign' f2(x)
:
y 'sign' fn(x)

where 'sign' can be any inequality sign '<'|'<='|'>'|'>=' and f(x) is the constraints function which is either constant, linear or possibly nonlinear

Description
The algorithm makes no assumptions on the specified constraints functions which can be either constant, linear or possibly nonlinear. The constraints functions are initially represented by anonymous functions which will be converted into piecewise linear functions within the specified interval xmin<=x<=xmax for the independent variable.
The resolution of the discrete grid is controlled by (dx).

It works out the feasible region by first sorting the sampled functions followed by detection of their intersections which will be injected into the discrete x-grid so that they can be included in the final feasible region boundary. The final feasible region is then found by scanning along the discrete x-grid for valid (non-conflicting) constraints.

The output is ultimately a closed piecewise linear boundary B representing the feasible region to be used in solving 2-dimensional optimization problems.

Possibly multiple feasible regions is not handled which could yield unexpected results.

Dependencies:
Package: feasrgn

Usage example:

import feasrgn.*

cfcn = {'y','>', @(x) .65*(x-1).^2-3; ...
'y','<=',@(x) -1.25*x.^2+6; ...
'y','>=', @(x) .8*(x+1.25).^3-1.025*(x+.5); ...
'y','>', @(x) .5*ones(size(x)); ...
'y','<=',@(x) 3.5*ones(size(x)); ...
'y','<=',@(x) -3*x+2; ...
'y','<=',@(x) 3-.5*x };

opts = struct('xmin',-3,'xmax',3,'dx',0.05); % also possible to set opts={}

frgn = feasrgn(cfcn,opts);

% Plot
% (All options can be modified via the handle object obj)
figure;
obj = feasrgnplot(frgn,...
'LineStyle','none',...
'LineWidth',2,...
'FillColor',[0 .45 .85],...
'FaceAlpha',.9,...
'NodeLabel','S',...
'NodeShape','o',...
'NodeSize',5,...
'NodeColor',[0 0 .75],...
'NodeFontSize',8,...
'DisplayNodes',true,...
'DisplayNodeValues',true,...
'DisplayQueryPoint',false,...
'NodeValueFormat','(%.2f; %.2f)',...
'DisplayConstraints',true,...
'DisplayLegend',true,...
'DisplayInnerPoints',true,...
'UPointCount',30,...
'VPointCount',20);

% Change some plot style properties (any change will directly affect the output)
obj.nodeshape = 's';
obj.nodelabel = 'P';
...

% Test if query point q is inside the feasible region boundary
q = [1;2];
if obj.isPtInside( q )
% code
end

% Generated inner boundary points
% (Resolution can be controlled by obj.upointcount and obj.vpointcount)
frgn.Gx
frgn.Gy

The inner points can be used to evaluate the objective function in the actual optimization problem.