Simple least-squares problem violates my constraint

Hi all.

Apologies beforehand if this has already been answered. I have seen a couple of threads touching on the same issue, but without providing a satisfactory answer.

I basically have a power control problem, and need to find the optimal power control vector for an overdetermined linear system of equations. For some runs I get negative(!) transmit powers, and can’t figure out the reason why. I provide code for one such run below. CVX returns that the problem has been solved, but I would’ve thought that it would provide some error for violating the constraint.

Thanks in advance for your help on what is probably a trivial question with a trivial solution.

A = 1.0e+07*[0.5486,0.0115 ; 0.0045,0.0001; 0.1677,0.0043 ; 8.0777,0.1686;0.0007 , 0.0128];
n = 2; m = 5; pmax = 0.25;
b = pmaxones(m,1);
l = zeros(n,1);
u = pmax
ones(n,1);

cvx_begin
variable x(n)
minimize( norm(A*x-b) )
subject to
l <= x <= u
cvx_end

x

I ran this using SeDuMi and SDPT3, and the smallest component of x was respectively -9e10 and -4e-8. This is essentially within solver tolerance of the lower bound value of zero, so it is not considered to be a violation of the constraint.

Your problem has bad scaling. The optimal solution is very close to being [0;0]. If you divide each of A and b by 1e5, then the minimum component of x is -1e-12 and -4e-11 for SeDuMi and SDPT3 respectively. You can read http://cvxr.com/cvx/doc/solver.html#controlling-precision and also search for occurrences of “tolerance” in the CVX User Guide.

Hi Mark, thanks for your informative reply.

I’m still a bit unsure though as to what the general rule should be to deal with this phenomenon. Imagine a Monte Carlo simulation where the matrix A is different in each run and where the elements of A can differ with several orders of magnitude in any given run.

I guess for this particular problem the solution would be to
(1) go with the negative powers whenever they appear as long as (0-tol)<=p, where “tol” is some tolerance (maybe the same as the solver’s precision?)
(2) make every power that lies between (0-tol)<=p<0 equal to zero. If the power is negative for p<(0-tol), then I would output an error.

What do you think? What would you do in this case?

If CVX declares success, I recommend you accept the solution. If it is required for your usage that the solution not violate the bounds by even the smallest amount, then it is probably reasonable to move the solution to the violated bound, 0, in your example. Another option is to specify a small number, q, and specify your bounds as l + q <= x <= u - q .with q at least as big as the solver tolerance. That way, the solution returned should satisfy your unadjusted constraints, even though it may remove some solutions from consideration which in reality are feasible.

I am scaling my matrices with an order of magnitude in a way so that the largest order of magnitude of any element in the scaled matrix is two. Seems to work as good as it can, I guess.

Thanks for your help.

I was just going to suggest scaling; I’m glad that’s working for you.