Minimizing the values in an underdetermined Matrix - minimize with constraints

4 次查看（过去 30 天）
Joseph
Joseph 2012-7-4
评论： Torsten 2016-6-30
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

请先登录，再回答此问题。

采纳的回答

Richard Brown
Richard Brown 2012-7-4
编辑：Richard Brown 2012-7-5
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 个评论
显示 4更早的评论
Giorgio
Giorgio 2016-6-30
Thank you for this helpful code! How should I modify the matrix Ai in order not to have negative results (x>=0)?
Torsten
Torsten 2016-6-30
[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.

请先登录，再进行评论。

更多回答（1 个）

Richard Brown
Richard Brown 2012-7-4
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 个评论
显示 4更早的评论
Joseph
Joseph 2012-7-4
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 2012-7-5
编辑：Richard Brown 2012-7-5
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

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Linear Programming and Mixed-Integer Linear Programming 的更多信息

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by