MATLAB Answers

Optimization when beq is zeros

3 views (last 30 days)
Bryce on 12 Apr 2011
I do not yet have the optimization toolbox, but would like to ask if it can solve the following problem.
minimize c'*x
such that Aeq*x = beq, where beq = zeros and zeros < x
and zeros means a column vector of appropriate size in all cases. Please note that zeros < x, not zeros <= x. Of course, I realize that a trivial solution exists (x = zeros), but I seek a non-trivial solution.
In case anybody is wondering, this is a solution of a matrix null space problem with a constraint that all elements of the null space vector > 0.
Bryce on 13 Apr 2011
The null space problem is A*x = zeros(n,1), where [m,n] = size(A). Therefore, x = zeros(n,1) is always a (trivial) solution, but the null space problem is to find x ~= 0.
For my problem, c is ones(length(x),1). I should have mentioned that earlier. Ideally I would minimize the 1-norm of x, which is the same as min( ones' * x) as long as all(x>=0).
Also, I can find solutions via Z = null(A), which returns a matrix Z that is size n x r, were r is the nullity of A. That is, each column of Z will satisfy the null space condition, A*Z(:,j) = zeros, 1<j<=r and the columns of Z are a basis set for the null space of A. Therfore, linear combinations of the columns of Z are also solutions.
However, Z contains elements that are < 0, and it is unlikely that I can find any column of Z s.t. all(Z(:,j)) >= 0 for an arbitrary A.
Thanks for any help that you can provide.

Sign in to comment.

Answers (1)

Laura Proctor
Laura Proctor on 12 Apr 2011
You can check out the FMINCON function as a start.
Take a look at the Optimization Toolbox Tutorial to see a demo of two different nonlinear solvers.
There's also a webinar called Tips & Tricks - Getting Started Using Optimization with MATLAB that could be pretty helpful.
Teja Muppirala
Teja Muppirala on 13 Apr 2011
Any nontrivial solution could only be a linear combination of the columns obtained when you evaluate:
M = null(Aeq) * null(c'*null(Aeq))
I guess you could rephrase your question as:
Does there exist a z such that
M*z > 0

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!