Optimization Toolbox

Linear Least Squares with Bound Constraints

Many situations give rise to sparse linear least squares problems, often with bounds on the variables. The next problem requires that the variables be nonnegative. This problem comes from fitting a function approximation to a piecewise linear spline. Specifically, particles are scattered on the unit square. The function to be approximated is evaluated at these points, and a piecewise linear spline approximation is constructed under the condition that (linear) coefficients are not negative. There are 2000 equations to fit on 400 variables.

load particle   % Get C, d
lb = zeros(400,1);
[x,resnorm,residual,exitflag,output] = ... 
              lsqlin(C,d,[],[],[],[],lb);

The default diagonal preconditioning works fairly well.

exitflag =
     1
resnorm =
    22.5794
output = 
        algorithm: 'large-scale: trust-region reflective Newton'
    firstorderopt: 2.7870e-005
       iterations: 10
     cgiterations: 42

For bound constrained problems, the first-order optimality is the infinity norm of v.*g, where v is defined as in Box Constraints, and g is the gradient.

The first-order optimality can be improved (decreased) by using a sparse QR-factorization in each iteration: set PrecondBandWidth to inf.

options = optimset('PrecondBandWidth',inf);
[x,resnorm,residual,exitflag,output] = ... 
              lsqlin(C,d,[],[],[],[],lb,[],[],options);

The number of iterations and the first-order optimality both decrease.

exitflag =
     1
resnorm =
    22.5794
output = 
        algorithm: 'large-scale: trust-region reflective Newton'
    firstorderopt: 5.5907e-015
       iterations: 12
     cgiterations: 11

Quadratic Minimization with a Dense but Structured Hessian

Linear Programming with Equalities and Inequalities