Efficient constraints declaration

[Dario Marvin]

Hello,

For my semester project I'd like to solve a minimization problem with a quadratic objective function and lots of horribly nonlinear constraints involving all n parameters, with n around 100-200.

Said constraints are declared by multiplying a sdpvar(3,3) object with itself n times in a complex way and setting it to a specific 3x3 matrix I have. For istance, a simplified declaration of my problem would be

[x] = get_constraint(n)

n = 100; % say

x = sdpvar(3,3);

for i = 1:n
    x = x*x;
end

x

end

...
Constraints = [get_constraint(n) = M]; % M is (3x3) known
...

However, simply calling get_constraint(n) requires an horrific amount of time, even for n ~ 10.

So, is there a way to efficiently declare such kind of constraints, without it taking too much time to execute?
And also, do you know of any solver which would be especially effective to solve my problem?

Thanks in advance.

Best Regards,

Dario

[Johan Löfberg]

You don't want to do that. Let's be more modest and set n = 5, and run this

n = 5; % say

x = sdpvar(3,3);

for i = 1:n

    % display number of symbolic monomial terms 

    length(getvariables(x))   

    x = x*x;

end

after running this, make a guesstimate on the number of symbolic terms in involved in the last expression if you increase n to 6, or 100...

BTW, x is symmetric in case you didn't know

users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Basics

Apart from being impossible to describe as you try to do symbolically, it is a horrible nonconvex nonlinear constraint. A better (still nonconvex) model would be to write x as U'*D*U where U'*U=I and D i diagonal, as x^(2n) then at least simplifies to U'*D.^(2*N)*U. Still nasty though

[Johan Löfberg]

and not only is it impossible symbolically, it is nonsense numerically. Let x be scalar. You are then trying to solve x^(2^n) = M, i.e. x^( 1.2677e+30) = M. The solution to this problem will be x=1 in floating-point numerics for any choice of M