Write norm constraint as LMI problem

[Matt B.]

Dear Prof. Löfberg,

I would like to solve a LMI problem while including a norm constraint of the form:

|| x || < y, but I don't know how to write this as a LMI problem ?

Defining ||x|| = x^T * x, I can do something like :

x^T * x - y < 0

and using schur complement end up with something like :

[ -y, x^T;

x,   -I] < 0

But I quite don't know how to get rid of the x in this expression ...

Is there any method to write this norm constraint as a LMI problem ?

Thanks in advance !

Matt.

[Johan Löfberg]

You don't, simply write norm(x)<=y and let YALMIP formulate that as an SOCP and use an SOCP-capable solver.

If you for some weird self-penalizing reason want to write it inefficiently as an LMI, you square it to arrive at x'*x <= y^2, y>=0 which by Schur is [y x';x y*eye(n)] >=0

[Matt B.]

Tanks a lot for your answer.

Let's say I opt for the second solution, the norm constraint should be true for all x in R^n.

So I guess this can not directly be written as  [y x';x y*eye(n)] >=0, because x lies in R^n, and is not a decision variable.

Maybe by defining || x || = x' * M * x or something like this ?

Thanks again,

Matt.

[Matt B.]

in this case, M  would become the decision variable .

I would like to define || x || = x^T M x and end up with a LMI whose variable is M.

Do you think it is possible ?

Thanks again for your consideration.

[Johan Löfberg]

I don't understand what you are asking

norm(x) <= y

and

x^Tx <= y^2, y>=0

and

[y x';x y*eye(n)]

are equivalent conditions

If x is not a decision variable, then norm(x)<=y is a linear inequality and there is no reason to write as SOCP or LMI

[Matt B.]

Sorry for not being clear.

This constraint is part of a larger problem :

I have a dynamical system with state x in R^n. I can write a LMI to study its stability, I obtain a first constraint with decision variable M : LMI(M) < 0.

Now, I would like to add a constraint to impose || f(x) || < y.

I would like to write this constraint as a second LMI to solve both LMI to ensure stability and norm bounded.

Does this make sense ?

[Johan Löfberg]

" would like to define || x || = x^T M x and end up with a LMI whose variable is M."

so sqrt(x'*M*x) <= y. That is not convex in y and M and thus not SDP-representable. Working with M^-1 as the decision variable, or R where M=R'R, will allow a convex form using a Schur complement

norm(f(x)) < y  will typically only be SDP-representable for linear f, or at least it has to be studied on case-by-case