Optimization Toolbox™

lsqlin - Solve constrained linear least-squares problems

Equation

Solves least-squares curve fitting problems of the form

Syntax

x = lsqlin(C,d,A,b)
x = lsqlin(C,d,A,b,Aeq,beq)
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub)
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0)
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options)
x = lsqlin(problem)
[x,resnorm] = lsqlin(...)
[x,resnorm,residual] = lsqlin(...)
[x,resnorm,residual,exitflag] = lsqlin(...)
[x,resnorm,residual,exitflag,output] = lsqlin(...)
[x,resnorm,residual,exitflag,output,lambda] = lsqlin(...)

Description

x = lsqlin(C,d,A,b) solves the linear system C*x = d in the least-squares sense subject to A*x ≤ b, where C is m-by-n.

x = lsqlin(C,d,A,b,Aeq,beq) solves the preceding problem while additionally satisfying the equality constraints Aeq*x = beq. Set A = [] and b = [] if no inequalities exist.

x = lsqlin(C,d,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables in x so that the solution is always in the range lb ≤ x ≤ ub. Set Aeq = [] and beq = [] if no equalities exist.

x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0) sets the starting point to x0. Set lb = [] and b = [] if no bounds exist.

x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options) minimizes with the optimization options specified in the structure options. Use optimset to set these options.

x = lsqlin(problem) finds the minimum for problem, where problem is a structure described in Input Arguments.

Create the structure problem by exporting a problem from Optimization Tool, as described in Exporting to the MATLAB^® Workspace.

[x,resnorm] = lsqlin(...) returns the value of the squared 2-norm of the residual, norm(C*x-d)^2.

[x,resnorm,residual] = lsqlin(...) returns the residual C*x-d.

[x,resnorm,residual,exitflag] = lsqlin(...) returns a value exitflag that describes the exit condition.

[x,resnorm,residual,exitflag,output] = lsqlin(...) returns a structure output that contains information about the optimization.

[x,resnorm,residual,exitflag,output,lambda] = lsqlin(...) returns a structure lambda whose fields contain the Lagrange multipliers at the solution x.

Note   If the specified input bounds for a problem are inconsistent, the output x is x0 and the outputs resnorm and residual are []. Components of x0 that violate the bounds lb ≤ x ≤ ub are reset to the interior of the box defined by the bounds. Components that respect the bounds are not changed. If no x0 is provided, x0 is set to the zero vector. If any component of this zero vector x0 violates the bounds, x0 is set to a point in the interior of the box defined by the bounds.

Input Arguments

Function Arguments contains general descriptions of arguments passed into lsqlin. Options provides the options values specific to lsqlin.

Output Arguments

Function Arguments contains general descriptions of arguments returned by lsqlin. This section provides function-specific details for exitflag, lambda, and output:

Options

Optimization options used by lsqlin. You can set or change the values of these options using the optimset function. Some options apply to all algorithms, some are only relevant when you are using the large-scale algorithm, and others are only relevant when using the medium-scale algorithm. See Optimization Options for detailed information.

The LargeScale option specifies a preference for which algorithm to use. It is only a preference, because certain conditions must be met to use the large-scale algorithm. For lsqlin, when the problem has only upper and lower bounds, i.e., no linear inequalities or equalities are specified, the default algorithm is the large-scale method. Otherwise the medium-scale algorithm is used:

Medium-Scale and Large-Scale Algorithms

These options are used by both the medium-scale and large-scale algorithms:

Large-Scale Algorithm Only

These options are used only by the large-scale algorithm:

W = jmfun(Jinfo,Y,flag,p1,p2,...)

[F,Jinfo] = fun(x)

Examples

Find the least-squares solution to the overdetermined system C·x = d, subject to A·x ≤ b and lb ≤ x ≤ ub.

First, enter the coefficient matrices and the lower and upper bounds.

C = [
    0.9501    0.7620    0.6153    0.4057
    0.2311    0.4564    0.7919    0.9354
    0.6068    0.0185    0.9218    0.9169
    0.4859    0.8214    0.7382    0.4102
    0.8912    0.4447    0.1762    0.8936];
d = [
    0.0578
    0.3528
    0.8131
    0.0098
    0.1388];
A =[ 
    0.2027    0.2721    0.7467    0.4659
    0.1987    0.1988    0.4450    0.4186
    0.6037    0.0152    0.9318    0.8462];
b =[
    0.5251
    0.2026
    0.6721];
lb = -0.1*ones(4,1);
ub = 2*ones(4,1);

Next, call the constrained linear least-squares routine.

[x,resnorm,residual,exitflag,output,lambda] = ...
                    lsqlin(C,d,A,b,[ ],[ ],lb,ub);

Entering x, lambda.ineqlin, lambda.lower, lambda.upper produces

x =
   -0.1000
   -0.1000
    0.2152
    0.3502
lambda.ineqlin =
         0
    0.2392
         0
lambda.lower =
    0.0409
    0.2784
         0
         0
lambda.upper =
         0
         0
         0
         0

Nonzero elements of the vectors in the fields of lambda indicate active constraints at the solution. In this case, the second inequality constraint (in lambda.ineqlin) and the first lower and second lower bound constraints (in lambda.lower) are active constraints (i.e., the solution is on their constraint boundaries).

Notes

For problems with no constraints, use \ (matrix left division). For example, x= A\b.

Because the problem being solved is always convex, lsqlin will find a global, although not necessarily unique, solution.

Better numerical results are likely if you specify equalities explicitly, using Aeq and beq, instead of implicitly, using lb and ub.

Large-Scale Optimization

If x0 is not strictly feasible, lsqlin chooses a new strictly feasible (centered) starting point.

If components of x have no upper (or lower) bounds, set the corresponding components of ub (or lb) to Inf (or -Inf for lb) as opposed to an arbitrary but very large positive (or negative in the case of lower bounds) number.

Algorithm

Large-Scale Optimization

When the problem given to lsqlin has only upper and lower bounds; i.e., no linear inequalities or equalities are specified, and the matrix C has at least as many rows as columns, the default algorithm is the large-scale method. This method is a subspace trust-region method based on the interior-reflective Newton method described in [1]. Each iteration involves the approximate solution of a large linear system using the method of preconditioned conjugate gradients (PCG). See Trust-Region Methods for Nonlinear Minimization and Preconditioned Conjugate Gradients.

Medium-Scale Optimization

lsqlin, with the LargeScale option set to 'off' with optimset, or when linear inequalities or equalities are given, is based on quadprog, which uses an active set method similar to that described in [2]. It finds an initial feasible solution by first solving a linear programming problem. See Quadratic Programming.

Diagnostics

Large-Scale Optimization

The large-scale method does not allow equal upper and lower bounds. For example, if lb(2) == ub(2), then lsqlin gives the following error:

Equal upper and lower bounds not permitted
in this large-scale method.
Use equality constraints and the medium-scale
method instead.

At this time, you must use the medium-scale algorithm to solve equality constrained problems.

Medium-Scale Optimization

If the matrices C, A, or Aeq are sparse, and the problem formulation is not solvable using the large-scale method, lsqlin warns that the matrices are converted to full.

Warning: This problem formulation not yet available
for sparse matrices.
Converting to full to solve.

When a problem is infeasible, lsqlin gives a warning:

Warning: The constraints are overly stringent;
     there is no feasible solution.

In this case, lsqlin produces a result that minimizes the worst case constraint violation.

When the equality constraints are inconsistent, lsqlin gives

Warning: The equality constraints are overly stringent;
     there is no feasible solution.

Limitations

At this time, the only levels of display, using the Display option in options, are 'off' and 'final'; iterative output using 'iter' is not available.

References

[1] Coleman, T.F. and Y. Li, "A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on Some of the Variables," SIAM Journal on Optimization, Vol. 6, Number 4, pp. 1040-1058, 1996.

[2] Gill, P.E., W. Murray, and M.H. Wright, Practical Optimization, Academic Press, London, UK, 1981.

See Also

\ (matrix left division), lsqnonneg, quadprog, optimtool

lsqcurvefit

lsqnonlin