Inequality constraints for optimizer

Hello,

I want the solution (x,y) of my optimization problem to belong to a specific region of the search-space as depicted below. This region can have an arbitrary shape.

1st case: The red region is known, by knowing the equation of each red line (segment). Is it possible to create a set of inequalities?

2nd case: The red region is known, by knowing the coordinates of all points of its perimeter. Is it possible to create a set of inequalities?

Thanks in advance.

Answer 1

[Matt J]

Assuming the region is convex, the answer is yes in both cases. Otherwise, the answer is no - inequalitites will not be enough to specify a nonconvex polygon.

[Alan Weiss]

To expand on Matt's answer, for convex regions you would generally use a set of linear inequality constraints.

Alan Weiss

MATLAB mathematical toolbox documentation

[John Kioulaxidis]

Thank both of you for the answers. Indeed, let's assume it is a convex region.

1st case: The (line) equations of the sides of the region are known. I guess it is easy then to procceed according to linear inequality constraints

2nd case: To better explain, let's assume that my convex region is in fact a grid of points with known coordinates. I dont know which points define the boundaries of the region or any any line equations. How is it possible to define this region by linear inequalities?

[Matt J]

For the second case, you can use vert2lconin

https://www.mathworks.com/matlabcentral/fileexchange/30892-analyze-n-dimensional-polyhedra-in-terms-of-vertices-or-in-equalities

[A,b]=vert2lcon(V);

Although the instructions assume the rows of V are the vertices of the polygon, it will actually work if there are additional points as well.

[John Kioulaxidis]

Wow this function is what I needed. Thanks

Answer 2

[Bruno Luong]

% Your points that define the domain
xg = randn(10,1);
yg = randn(10,1);

% The domain is concerted to the set defined by inequalities { xy :  A*xy <= b  }
xyg = [xg(:) yg(:)];
K = convhull(xyg);
xyh = xyg(K,:);
dxy = diff(xyh,1,1);
A = [dxy(:,2),-dxy(:,1)];
b =  sum(A.*xyh(1:end-1,:),2);

% Check with grid points
close all
xi = linspace(min(xg),max(xg),30);
yi = linspace(min(yg),max(yg),30);
[X,Y] = ndgrid(xi,yi);
xy = [X(:),Y(:)]';
in = all(A*xy <= b,1); % inequalities
plot(xg,yg,'+',...
     xyh(:,1),xyh(:,2),'-k',...
     X(in),Y(in),'or', ...
     X(~in),Y(~in),'.y');

[John Kioulaxidis]

Thank you for the answer. Function convhull seems quite interesting..