linprog (Optimization Toolbox)

Solve a linear programming problem

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

Syntax

x = linprog(f,A,b,Aeq,beq)
x = linprog(f,A,b,Aeq,beq,lb,ub)
x = linprog(f,A,b,Aeq,beq,lb,ub,x0)
x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
[x,fval] = linprog(...)
[x,fval,exitflag] = linprog(...)
[x,fval,exitflag,output] = linprog(...)
[x,fval,exitflag,output,lambda] = linprog(...)

Description

linprog solves linear programming problems.

x = linprog(f,A,b)

solves min f'*x such that A*x <= b.

x = linprog(f,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 = linprog(f,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 = linprog(f,A,b,Aeq,beq,lb,ub,x0)

sets the starting point to x0. This option is only available with the medium-scale algorithm (options.LargeScale is 'off'). The default large-scale algorithm will ignore any starting point.

x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)

minimizes with the optimization parameters specified in the structure options.

[x,fval] = linprog(...)

returns the value of the objective function fun at the solution x: fval = f'*x.

[x,lambda,exitflag] = linprog(...)

returns a value exitflag that describes the exit condition.

[x,lambda,exitflag,output] = linprog(...)

returns a structure output that contains information about the optimization.

[x,fval,exitflag,output,lambda] = linprog(...)

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 linprog 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.
	`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. At this time the `'iter'` level only works with the large-scale algorithm.
	`LargeScale` - Use large-scale algorithm if possible when set to `'on'`. Use medium-scale algorithm when set to `'off'`. `MaxIter` - Maximum number of iterations allowed. `TolFun` - Termination tolerance on the function value.
`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).

Examples

Find x that minimizes

subject to

First, enter the coefficients:

f = [-5; -4; -6]
A =  [1 -1  1
      3  2  4
      3  2  0];
b = [20; 42; 30];
lb = zeros(3,1);

Next, call a linear programming routine:

[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb);

Entering x, lambda.ineqlin, and lambda.lower gets

x = 
     0.0000
    15.0000
     3.0000
lambda.ineqlin =
     0
     1.5000
     0.5000
lambda.lower =
     1.0000
     0
     0

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

Algorithm

Large-scale optimization. The large-scale method is based on LIPSOL ([3]), which is a variant of Mehrotra's predictor-corrector algorithm ([2]), a primal-dual interior-point method. A number of preprocessing steps occur before the algorithm begins to iterate. See the linear programming section in the Large-Scale Algorithms chapter.

Medium-scale optimization. linprog uses a projection method as used in the quadprog algorithm. linprog is an active set method and is thus a variation of the well-known simplex method for linear programming [1]. It finds an initial feasible solution by first solving another linear programming problem.

Diagnostics

Large-scale optimization. The first stage of the algorithm may involve some preprocessing of the constraints (see the "Large-Scale Linear Programming" section of the Large-Scale Algorithms chapter). Several possible conditions might occur that cause linprog to exit with an infeasibility message. In each case, the exitflag argument returned by linprog will be set to a negative value to indicate failure.

If a row of all zeros is detected in Aeq but the corresponding element of beq is not zero, the exit message is

Exiting due to infeasibility:   an all zero row in the constraint 
matrix does not have a zero in corresponding right hand size 
entry.

If one of the elements of x is found to not be bounded below, the exit message is

Exiting due to infeasibility:   objective f'*x is unbounded below.

If one of the rows of Aeq has only one nonzero element, the associated value in x is called a singleton variable. In this case, the value of that component of x can be computed from Aeq and beq. If the value computed violates another constraint, the exit message is

Exiting due to infeasibility: Singleton variables in equality 
constraints are not feasible.

If the singleton variable can be solved for but the solution violates the upper or lower bounds, the exit message is

Exiting due to infeasibility: singleton variables in the equality 
constraints are not within bounds.

Note:
The preprocessing steps are cumulative. For example, even if your constraint matrix does not have a row of all zeros to begin with, other preprocessing steps may cause such a row to occur.

Once the preprocessing has finished, the iterative part algorithm begins until the stopping criteria is met. (See the "Large-Scale Linear Programming" section of the Large-Scale Algorithms chapter for more information about residuals, the primal problem, the dual problem, and the related stopping criteria.) If the residuals are growing instead of getting smaller, or the residuals are neither growing nor shrinking, one of the two following termination messages will display, respectively,

One or more of the residuals, duality gap, or total relative error
has grown 100000 times greater than its minimum value so far:

One or more of the residuals, duality gap, or total relative error 
has stalled:

After one of these messages displays, it will be followed by one of the following six messages indicating if it appears the dual, the primal, or both are infeasible. The messages differ according to how the infeasibility or unboundedness was measured.

The dual appears to be infeasible (and the primal unbounded).(The 
primal residual < TolFun)

The primal appears to be infeasible (and the dual unbounded). The 
dual residual < TolFun)

The dual appears to be infeasible (and the primal unbounded) since 
the dual residual > sqrt(TolFun).(The primal residual < 
10*TolFun)

The primal appears to be infeasible (and the dual unbounded) since 
the primal residual > sqrt(TolFun).(The dual residual < 
10*TolFun)

The dual appears to be infeasible and the primal unbounded since 
the primal objective < -1e+10 and the dual objective < 1e+6.

The primal appears to be infeasible and the dual unbounded since 
the dual objective > 1e+10 and the primal objective > -1e+6.

Both the primal and the dual appear to be infeasible.

Note that, for example, the primal (objective) can be unbounded and the primal residual, which is a measure of primal constraint satisfaction, can be small.

Medium-scale optimization. linprog gives a warning when the solution is infeasible:

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

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

When the equality constraints are inconsistent, linprog gives

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

Unbounded solutions result in the warning

Warning: The solution is unbounded and at infinity;
the constraints are not restrictive enough

In this case, linprog returns a value of x that satisfies the constraints.

Limitations

Medium-scale optimization. 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.