Interior-Point-Legacy Algorithm
The 'interior-point-legacy'
method is based
on LIPSOL (Linear Interior Point Solver, [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 Interior-Point-Legacy Linear Programming.
The first stage of the algorithm might involve some preprocessing
of the constraints (see Interior-Point-Legacy Linear Programming). Several conditions might
cause linprog
to exit with an infeasibility message.
In each case, linprog
returns a negative exitflag
,
indicating to indicate failure.
If a row of all zeros is detected in Aeq
,
but the corresponding element of beq
is not zero,
then 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-side entry.
If one of the elements of x
is
found not to be bounded below, then 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, then 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, then 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, then 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 can cause such a row to occur. |
When the preprocessing finishes, the iterative part of the algorithm
begins until the stopping criteria are met. (For more information
about residuals, the primal problem, the dual problem, and the related
stopping criteria, see Interior-Point-Legacy Linear Programming.) If the residuals are growing
instead of getting smaller, or the residuals are neither growing nor
shrinking, one of the two following termination messages is displayed,
respectively,
One or more of the residuals, duality gap, or total relative error
has grown 100000 times greater than its minimum value so far:
or
One or more of the residuals, duality gap, or total relative error
has stalled:
After one of these messages is displayed, it is followed by
one of the following messages indicating that the dual, the primal,
or both appear to be infeasible.
The dual appears to be infeasible (and the
primal unbounded). (The primal residual < OptimalityTolerance.)
The primal appears to be infeasible (and
the dual unbounded). (The dual residual < OptimalityTolerance.)
The dual appears to be infeasible (and the
primal unbounded) since the dual residual > sqrt(OptimalityTolerance).
(The primal residual < 10*OptimalityTolerance.)
The primal appears to be infeasible (and
the dual unbounded) since the primal residual > sqrt(OptimalityTolerance).
(The dual residual < 10*OptimalityTolerance.)
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.
For example, the primal (objective) can be unbounded and the
primal residual, which is a measure of primal constraint satisfaction,
can be small.
Interior-Point Algorithm
The 'interior-point'
algorithm is similar
to 'interior-point-legacy'
, but with a more efficient
factorization routine, and with different preprocessing. See Interior-Point linprog
Algorithm.
Dual-Simplex Algorithm
For a description, see Dual-Simplex Algorithm.
Active-Set and Simplex Algorithms
The 'active-set'
algorithm 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]. The
algorithm finds an initial feasible solution by first solving another
linear programming problem. For details, see Active-Set linprog
Algorithm.
For a description of the 'simplex'
algorithm,
see linprog
Simplex Algorithm.
linprog
gives a warning
when the problem 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.