Optimization when beq is zeros

3 views (last 30 days)
Bryce on 12 Apr 2011
Hello,
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.
Thanks.
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.

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 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