Optimization when beq is zeros

4 views (last 30 days)
Bryce
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.
  2 Comments
Andrew Newell
Andrew Newell on 12 Apr 2011
How do you know that all zeros is a trivial solution? Are all the components of c nonnegative?
Bryce
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.
  2 Comments
Bryce
Bryce on 13 Apr 2011
Thanks for the response. I have scoured the optimization toolbox help files, including fmincon and linprog. On first glance it appears that either will find a solution to my problem. But I am concerned that it will return the trivial solution. I quickly implemented an interior point solver, which is similar to optimization toolbox's linprog technique, via this tutorial
http://www.cas.mcmaster.ca/~cs777/presentations/NumericalIssue.pdf
It quickly found the global/trivial solution. I see that fmincon has a couple of other algorithm choices available, SQP and Trusted Region. The tutorials that you mentioned above are useful for understanding how to use the functions, but don't really comment on limitations with respect to trivial solutions.
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.

Categories

Find more on Get Started with Optimization Toolbox in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!