Can one solve optimization problem(in Matlab) with conditional constraint that depends on the decision variables?

Hello

My original problem is: Find maximal volume ellipsoid(or ellipse if ), it's size is limited by constraints, n can be higher than 3

min

s.t and for where m is the number of nonlinear inequality constraints

My idea is to create a function that checks if the equation(which is the ellipsoid) has any solution with the inequality system, that is, intersects the subspace described by the inequalities. The function returns 0 if no intersection, and 1 if they intersect each other.

Then my problem would become this:

min

s.t

So the real question is: can you solve a problem like this in Matlab? You would set the intersects variable(with the mentioned function) to 0 or 1 for each the solver tries, and accept it if the variable is 0 for the current .

[Torsten]

Why don't you just define r1,...,rn, x1,...,xn as decision variables, use "fmincon" and set all your constraints directly in function "nonlcon" of "fmincon" ?

[Richárd Tóth]

I've tried it: Problem appears unbounded.

can't be used as decision variables

[Torsten]

And why do you think the new formulation will change anything ?

If the inequalities f_i(x1,...,x_n) <= 0 don't bound the x_i, your problem is indeed unbounded.

[Richárd Tóth]

One of my constraints was incorrect, but it's still not working. Check my code( so we are looking for an ellipse), the objective function is

function f = objfun(rx)
f = -1*rx(1)*rx(2);

The constraints(they form 2x2 square around the origin)

function [c,ceq] = nonlcon(rx)
n=2;
r=rx(1:n);
x=rx(n+1:end);
K1=x(1)+2;
K2=-x(1)-2;
K3=x(2)+2;
K4=-x(2)-2;
c=[K1,K2,K3,K4];
ceq=x(1)^2/r(1)^2 + x(2)^2/r(2)^2 - 1;
end

And the fmincon call

x0 = [1,1,1,1];  %this already looks wrong, I don't see why should we search for x_1 and x_2
[x,fval] = fmincon(@objfun,x0,[],[],[],[],[],[],@nonlcon);

This should give a solution where and instead it's something like

gets a value of , which is impossible when the ellipse must be in the 2x2 square

[Bruno Luong]

You might just make a mistake in your formulation, something such as ri>=0 or xi>=0 as constraints is missing?

[Richárd Tóth]

I think the constraints on the original problem are wrong, the constraint is that the ellipsoid with radiuses r_1,...,r_n has no intersection with any of the inequalities. How you write real constraints of that is what I must figure out.

[Bruno Luong]

the constraint is that the ellipsoid with radiuses r_1,...,r_n has no intersection with any of the inequalities.

Sorry I don't understand what you meant by "ellipsoid has no intersection with inequalities".

In my world ellipsoid is a geometry object, inequalities is a logical algebraic expression. I don't know what is the intersection of the two.

[Richárd Tóth]

I should have said: the ellipsoid has no intersection point with any of the subspaces which correspond to each of the inequalities. The ellipse has algebraic form too(it's equation) and the inequalities have geometric meaning too, for example the inequality is a half plane.

Let me illustrate in 2D what I mean:

the ellipse is

consider the following inequality:

if ,then there is no solution to this system:

So the ellipse has no intersection with the half plane .

By increasing and/or the system will have at least one solution sooner or later.

[Bruno Luong]

In that case I would say your formulation of nonlinear constraint function as read here

function [c,ceq] = nonlcon(rx)
n=2;
r=rx(1:n);
x=rx(n+1:end);
K1=x(1)+2;
K2=-x(1)-2;
K3=x(2)+2;
K4=-x(2)-2;
c=[K1,K2,K3,K4];
ceq=x(1)^2/r(1)^2 + x(2)^2/r(2)^2 - 1;
end 

tell the minimizer will try to find ONE point X on the ellipsoid that satiesfies the 4 inequalities, meaning there is at least one point in the ellipsoid in the intersection of 4 half planes. This is NOT the same as there is no intersection with each of the half plane.

As implemented this constrain cannot force the ellipsoid to be bounded.

The constraint will not limit the side of the ellipsoid. So FMINCON gives you the cost function which goes to minus infinity. FMINCON is correct just your formulation does not reflect the problem you want to solve.

What I suspect is that you want something like this

c(x) <= 0 for ALL points X such that

x(1)^2/r(1)^2 + x(2)^2/r(2)^2 - 1 = 0.

[Richárd Tóth]

You are correct, that describes the constraints exactly. However, I don't think you can write up real constraints from that, or can you? It would become a semi infinite optimization problem, but you don't have the sample set X explicitly, it's not something like X={(0.1,0.1) (0.2,0.2)... } when you could iterate through X and check the c constraints. You simply can't discretize X in this case in my opinion.

[Bruno Luong]

No, but you can use the Euler-Lagrange trick I show in this post to reduce the infinite number of points to test to a finite number of points.

You might also use Torsen fmincon within fmincon, but I won't fully trust fmincon (in your case it is OK since all object are semi-convex), and it is quite a hammer tool.

[Richárd Tóth]

Hmm, let's say I manage to create the finite X which stores the points using your recommended method, can I simply use fseminf after that? What about sampling? Do I simply ignore it? Can I do that?

https://www.mathworks.com/help/optim/ug/one-dimensional-semi-infinite-constraints.html

Instead of w1 and w2 I have an X matrix where each row stores a point(x1,...,xn coordinates).

The ( ) constraint would look like ?

(Or maybe I can include the sampling interval into the calculation of the points.)

[Bruno Luong]

% Constraints that define the domaine where the ellipsoid must be in
% D = {x : A*x <= b}
% E include in D
A = [ 1   0;
     -1   0;
      0   1;
      0  -1];
b = [2;
     2;
     2;
     2];

r0 = zeros(2,1);
lb = zeros(2,1);
ub = inf(2,1);
areafun = @(r) -prod(r);
nlcon =  @(r) testinsideD(r, A, b);
r = fmincon(areafun, r0, [], [], [], [], lb , ub, nlcon)

 function [c,ceq] = testinsideD(r, A, b)
 nc = size(A,1);
 c = zeros(nc,1);
 for i=1:nc
     % point on ellipsoid that satisfies K-T condition
     x0 = A(i,:).';
     x = x0 ./ norm(x0./r);;
     c(i) = A(i,:)*x - b(i);
 end
 ceq = [];
 end

Edit: use the sign la lambda, code is simpler

[Richárd Tóth]

I don't really understand what's happening in the for loop, that is when you check if the ellipse fulfils the current iteration's constraint. As I see you are not generating a set of the ellipse's points to iterate through them and check each constraint, so what's happening?

[Bruno Luong]

The loop iterates on plane constraints.

Well no that the whole advantage of such technique, I only need to check those which verifie the KT condition and there is only one of them per plane. As I told you the KT condition allows to reduce infinite number of points to finite (here is 1 per plane). No longer need to generate a bunch of points.

If you don't understand you need to read careful about theory of about KT condition.

[Richárd Tóth]

thanks for the help