Documentation

This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

Linear Least Squares with Bound Constraints

Many situations give rise to sparse linear least-squares problems, often with bounds on the variables. You can use the 'trust-region-reflective' algorithm to solve sparse bound-constrained problems. 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);
options = optimoptions('lsqlin','Algorithm','trust-region-reflective');
[x,resnorm,residual,exitflag,output] = ...
              lsqlin(C,d,[],[],[],[],lb,[],[],options);
Optimization terminated: relative function value changing by less
 than sqrt(OPTIONS.FunctionTolerance), and rate of progress is slow.

The default diagonal preconditioning works fairly well:

exitflag,resnorm,output

exitflag =
     3

resnorm =
   22.5794

output =
  struct with fields:
       iterations: 10
        algorithm: 'trust-region-reflective'
    firstorderopt: 2.7870e-05
     cgiterations: 42
          message: 'Optimization terminated: relative function value changing by less…'

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.

You can improve (decrease) the first-order optimality measure by using a sparse QR factorization in each iteration. To do this, set SubproblemAlgorithm to 'factorization':

options = optimoptions(options,'SubproblemAlgorithm','factorization');
[x,resnorm,residual,exitflag,output] = ... 
              lsqlin(C,d,[],[],[],[],lb,[],[],options);
Optimization terminated: first order optimality with optimality
 gradient norm less than OPTIONS.OptimalityTolerance.

The first-order optimality measure decreases:

exitflag,resnorm,output

exitflag =
     1

resnorm =
   22.5794

output =
  struct with fields:
       iterations: 12
        algorithm: 'trust-region-reflective'
    firstorderopt: 5.5907e-15
     cgiterations: 0
          message: 'Optimization terminated: first order optimality with optimality…'
Was this topic helpful?