Minimizing the values in an underdetermined Matrix - minimize with constraints

6 views (last 30 days)
I'm new to MATLAB, and there is probably a very simple way to do this. I have a linear set of equations Ax=b. I have matrix A and matrix b, and I need to solve for the smallest values in matrix x that satisfy the equation. The solution is underdetermined. Is there a way to do this? Essentially I need to minimize the components in the matrix x subject to constraints. Mathematica has the NMinimize function which looks perfect, except I cannot find an equivalent in MATLAB. fmincon does not seem to work for matrix entries.
Thanks

Accepted Answer

Richard Brown
Richard Brown on 4 Jul 2012
Edited: Richard Brown on 5 Jul 2012
edit: fixed mistake in call to linprog
To perform L1 minimisation, you'll need access to an LP solver. If you have the optimization toolbox, linprog is your friend.
The easiest way to do it is as follows:
Define a vector t of the same length as x such that -t <= x <= t
The linear program is then
minimise t(1) + ... + t(n)
subject to A*x = b
-x - t <= 0
x - t <= 0
To solve it in MATLAB, I'll assume you have an m x n matrix A, and m x 1 vector b
[m, n] = size(A);
f = [zeros(n, 1); ones(n, 1)];
Ai = [-eye(n), -eye(n); eye(n), -eye(n)];
bi = zeros(2*n, 1);
x = linprog(f, Ai, bi, [A, zeros(m, n)], b);
x = x(1:n);
  6 Comments
Giorgio
Giorgio on 30 Jun 2016
Thank you for this helpful code! How should I modify the matrix Ai in order not to have negative results (x>=0)?
Torsten
Torsten on 30 Jun 2016
[m, n] = size(A);
f = [zeros(n, 1); ones(n, 1)];
Ai = [-eye(n), -eye(n); eye(n), -eye(n)];
bi = zeros(2*n, 1);
lb = zeros(2*n, 1);
ub = Inf(2*n, 1);
x = linprog(f, Ai, bi, [A, zeros(m, n)], b, lb, ub);
x = x(1:n);
Best wishes
Torsten.

Sign in to comment.

More Answers (1)

Richard Brown
Richard Brown on 4 Jul 2012
Assuming you want a minimal Euclidean norm solution, there's no built-in function, but I can offer you a two-line solution:
[Q, R] = qr(A', 0);
x = Q * (R' \ b);
If you want a minimal 1 or infinity norm solution, then you can cast the problem as a linear program.
  6 Comments
Joseph
Joseph on 4 Jul 2012
x = fmincon(@(x) norm(x,1), zeros(1,length(A)),[],[],A,b)
The above worked for me. Thanks Teja. I actually tried the above but without the @x - What does the @x do?
Richard Brown
Richard Brown on 5 Jul 2012
Edited: Richard Brown on 5 Jul 2012
Glad that worked for you. When I tried it on some random examples (even small ones), your call to fmincon with default parameters didn't converge. This isn't surprising, because the 1-norm objective isn't differentiable, and fmincon is designed for smooth problems.
I would still recommend using an LP based solution if you're interested in performance - I'd expect you'd get 10x or better speed performance from linprog for your problem

Sign in to comment.

Products

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!