Ill-posed quadratic programing with linear inequality constraint

I have the problem

min |Q*x-d| subject to A*x <= b and x>0

The matrix Q has very large condition number. How can I solve this using Matlab? I looked at Hansen's regularization tool package but it does not appear to handle the linear inequality and nonnegativity. Thanks very much for help

Answer 1

[John D'Errico]

An old question, so my answer is completely irrelevant to Benjamin. Sorry about being late on this. But the solution is not that difficult. First, don't use quadprog or quadratic programming for this. The simple solution uses lsqlin anyway.

A = rand(2,10);
b = rand(2,1);
Q = randn(30,9)*randn(9,10);
d = randn(30,1);
lb = zeros(10,1);

So Q is clearly rank deficient. It has rank exactly 9 by construction, and the condition number of Q is effectively a numerical inf in terms of double precision.

rank(Q)

ans = 9

cond(Q)

ans = 1.7291e+16

lsqlin(Q,d,A,b,[],[],lb)

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

ans = 10×1

0.0000 0.0239 0.0000 0.2663 0.0000 0.2278 0.0000 0.0827 0.0000 0.0000

●

Yes, we could solve it using quadprog with a regularization. Entirely doable. But why bother? lsqlin is able to solve it.

[Walter Roberson]

It has rank exactly 9 by construction

Pedantically speaking, it could have lower rank... it just isn't likely!!

For example, a pseudo-random normal distribution that cannot produce 9 zeros in a row is statistically different than a true random number generator. A true random-normal distribution should produce exactly 0 with probability about 0.24 so it should produce 9 zeros in a row about 3 in a million times.

In practice, randn() does not appear to produce exact zeros -- not even 1 in 1e10 tries.

[John D'Errico]

true, in that it could be lower rank. A highly improbable event though.

[John D'Errico]

BTW, one of my first posts using "run". works nice.