MATLAB Answers

Optimization when beq is zeros

5 ビュー (過去 30 日間)
Bryce
Bryce 2011 年 4 月 12 日
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 件のコメント

Andrew Newell
Andrew Newell 2011 年 4 月 12 日
How do you know that all zeros is a trivial solution? Are all the components of c nonnegative?
Bryce
Bryce 2011 年 4 月 13 日
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.

サインインしてコメントする。

回答 (1 件)

Laura Proctor
Laura Proctor 2011 年 4 月 12 日
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 件のコメント

Bryce
Bryce 2011 年 4 月 13 日
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 2011 年 4 月 13 日
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

サインインしてコメントする。

Community Treasure Hunt

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

Start Hunting!

Translated by