Solve linear system of equations with constains

Hello everyone. I have a linear system of equations that make a matrix, L*x=R. x is composed on many variables, e.g. x=[x1 x2 x3 x4 ... xN]. I want to solve this system of equation with constraints x1>|x2|>|x3|>|x4|...>|xN|. Can I use lsqlin(L,R) with some additional input to realize it?

Many thanks.

Answer 1

[Matt J]

If you make the change of variables x(i)=u(i)-v(i) with linear constraints

u(i)>=0,
v(i)>=0, 
u(i)+v(i)>=u(i+1)+v(i+1)

and modify your least squares objective from norm(L(u-v)-R)^2 to

   norm(L(u-v)-R)^2 + C*( norm(u)^2 + norm(v)^2)

then for a sufficiently small choice of C>0, this should give an equivalent solution. It's not ideal, since it forces you to re-solve with multiple choices of C, but on the other hand, it allows you to pose this as a convex problem.

[Xin]

Thanks for your answer. That seems to make a lot of sense. I am wondering how should I solve for u and v. Do I need to solve 2*N variable instead of N variables?

[Matt J]

Yes. After you solve for u and v, you would map back to x just by using the change of variables formula x=u-v.

[Xin]

Hi Matt. I really appreciate your help. I have given it a try and it seems that this is a bit confusing. A numerical example, let x(i)=1 and x(i-1)=2, then we can set up u(i)=100 v(i)=99; and u(i-1)=4 v(i-1)=2, which satisfy the relation. However, we could also switch it to u(i)=100 v(i)=95 and u(i-1)=4 v(i-1)=2, which gives you x(i)=5 x(i-1)=2 that does not satisfy the requirement.

Could you please elaborate the equation you give me. Thanks a lot.

[Matt J]

Sorry, I meant

u(i)+v(i)>=u(i+1)+v(i+1)

I've edited my post accordingly.

Basically, the transformation x=u-v has no unique choice of [u,v], but the minimum-norm choice of [u,v] is unique and must satisfy either u=0 or v=0. Hence |x|=u+v and therefore

u(i)+v(i)>=u(i+1)+v(i+1)

is the same as

||x(i)|| >= ||x(i+1)||

[Xin]

Thanks Matt. As for changing the objective function, do you know any matlab function that does so, for example lsqlin or linsolve etc. So far as I know lsqlin only minimize norm(L*x-R)^2.

Thanks!

[Matt J]

The modified objective function is linear least squares in [u,v] so lsqlin still applies.

[Xin]

I have looked into lsqlin function but did not find how to change the objective. Then how do I change the objective from min 0.5*(NORM(C*x-d)).^2 to min 0.5*(NORM(C*x-d)).^2+ C*( norm(u)^2 + norm(v)^2)?

Thanks!

[Matt J]

It just requires a different choice of input matrices C,d. For example, the terms

( norm(u)^2 + norm(v)^2)

is the same as

   norm( C*[u;v]-d )^2

where C=speye(2*N) and d=zeros(2*N,1).