Optimization when beq is zeros

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.

[Andrew Newell]

How do you know that all zeros is a trivial solution? Are all the components of c nonnegative?

[Bryce]

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.

Answer 1

[Laura Proctor]

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.

[Bryce]

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]

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