lsqlin (Optimization Toolbox)

Solve the constrained linear least-squares problem

where C, A, and Aeq are matrices and d, b, beq, lb, ub, and x are vectors.

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,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 problem above 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, 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.

x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options)

minimizes with the optimization parameters specified in the structure options.

[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.

Arguments

The arguments passed into the function are described in Table 1-1. The arguments returned by the function are described in Table 1-2. Details relevant to lsqlin are included below for options, exitflag, lambda, and output.


`options`	Optimization parameter options. You can set or change the values of these parameters using the `optimset` function. Some parameters apply to all algorithms, some are only relevant when using the large-scale algorithm, and others are only relevant when using the medium-scale algorithm. We start by describing the `LargeScale` option since it states a preference for which algorithm to use. It is only a preference since 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 will be used. The parameter to set an algorithm preference: `LargeScale` - Use large-scale algorithm if possible when set to `'on'`. Use medium-scale algorithm when set to `'off'`.
	Parameters used by both the large-scale and medium-scale algorithms: `Diagnostics` - Print diagnostic information about the function to be minimized. `Display` - Level of display. `'off'` displays no output; `'iter'` displays output at each iteration; `'final'` displays just the final output.
	`MaxIter` - Maximum number of iterations allowed. `TolFun` - Termination tolerance on the function value.
	Parameters used by the large-scale algorithm only: `MaxPCGIter` - Maximum number of PCG (preconditioned conjugate gradient) iterations (see the Algorithm section below). `PrecondBandWidth` - Upper bandwidth of preconditioner for PCG. By default, diagonal preconditioning is used (upper bandwidth of 0). For some problems, increasing the bandwidth reduces the number of PCG iterations. `TolPCG` - Termination tolerance on the PCG iteration. `TypicalX` - Typical `x` values.
`exitflag`	Describes the exit condition: `> 0` indicates that the function converged to a solution `x`. `0` indicates that the maximum number of function evaluations or iterations was reached. `< 0` indicates that the function did not converge to a solution.
`lambda`	A structure containing the Lagrange multipliers at the solution `x` (separated by constraint type): `lambda.lower` for the lower bounds `lb`. `lambda.upper` for the upper bounds `ub`. `lambda.ineqlin` for the linear inequalities. `lambda.eqlin` for the linear equalities.
`output`	A structure whose fields contain information about the optimization: `output.iterations` - The number of iterations taken. `output.algorithm` - The algorithm used. `output.cgiterations` - The number of PCG iterations (large-scale algorithm only). `output.firstorderopt` - A measure of first-order optimality (large-scale algorithm only).

Examples

Find the least-squares solution to the over-determined system

subject to

and

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 gets

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, \ should be used: x= A\b.

In general lsqlin locates a local 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, then lsqlin prefers that the corresponding components of ub (or lb) be set 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 [2]. Each iteration involves the approximate solution of a large linear system using the method of preconditioned conjugate gradients (PCG). See the trust-region and preconditioned conjugate gradient method descriptions in the Large-Scale Algorithms chapter.

Medium-scale optimization. lsqlin with options.LargeScale set to 'off', or when linear inequalities or equalities are given, is based on quadprog, which uses an active set method similar to that described in [1]. It finds an initial feasible solution by first solving a linear programming problem. See the quadratic programming method discussed in the Introduction to Algorithms chapter.

Diagnostics

Large-scale optimization. The large-scale code does not allow equal upper and lower bounds. For example if lb(2)==ub(2), then lsqlin gives the 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, the medium-scale algorithm must be used 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 code, lsqlin warns that the matrices will be converted to full:

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

lsqlin gives a warning when the solution is infeasible:

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 parameter in options, are 'off' and 'final'; iterative output using 'iter' is not available.