LpSimplex: Difference between revisions
(Created page with "==Purpose== Solve general linear programming problems. ''lpSimplex ''solves problems of the form <math> \begin{array}{cccccl} \min\limits_{x} & f(x) & = & c^{T}x & & \\s/t...") |
No edit summary |
||
(9 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
[[Category:Solvers]] | |||
==Purpose== | ==Purpose== | ||
Line 13: | Line 14: | ||
where <math>x,x_{L},x_{U}\in \ | where <math>x,x_{L},x_{U}\in \mathbb{R} ^{n}</math> , <math>c \in \mathbb{R}^{n}</math>, <math>A\in \mathbb{R}^{m\times n}</math> and <math>b_{L},b_{U} \in \mathbb{R}^{m}</math>. | ||
==Calling Syntax== | ==Calling Syntax== | ||
<source lang="matlab"> | |||
Result = lpSimplex(Prob) or | Result = lpSimplex(Prob) or | ||
Result = tomRun('lpSimplex', Prob, 1); | Result = tomRun('lpSimplex', Prob, 1); | ||
</source> | |||
== | ==Inputs== | ||
{| | {| class="wikitable" | ||
!''Prob''||colspan="2"|Problem description structure. The following fields are used: | |||
|- | |- | ||
|||''QP.c''||Constant vector. | |||''QP.c''||Constant vector. | ||
Line 39: | Line 41: | ||
|- | |- | ||
|||''x_0''||Starting point. | |||''x_0''||Starting point. | ||
|- | |-valign="top" | ||
|||''Solver.Alg''||Variable selection rule to be used: | |||''Solver.Alg''||Variable selection rule to be used: | ||
0: Minimum reduced cost. | |||
1: Bland's rule (default). | |||
2: Minimum reduced cost. Dantzig's rule. | |||
|- | |-valign="top" | ||
|||''QP.B''||Active set ''B 0 ''at start: | |||''QP.B''||Active set ''B 0 ''at start: | ||
''B''(''i'') = 1: Include variable ''x''(''i'') is in basic set. | |||
''B''(''i'') = 0: Variable ''x''(''i'') is set on its lower bound. | |||
''B''(''i'') = ''-''1: Variable ''x''(''i'') is set on its upper bound. | |||
|-valign="top" | |-valign="top" | ||
|||||Fields used are: ''MaxIter'', ''PriLev'', ''wait'', ''eps_f'', ''eps_Rank'', ''xTol ''and ''bTol''. | |||''optParam''||Structure with special fields for optimization parameters, see [[TOMLAB Appendix A]]. | ||
Fields used are: ''MaxIter'', ''PriLev'', ''wait'', ''eps_f'', ''eps_Rank'', ''xTol ''and ''bTol''. | |||
|} | |} | ||
==Outputs== | |||
{| class="wikitable" | |||
!''Result''||colspan="2"|Structure with result from optimization. The following fields are changed: | |||
{| | |||
|- | |- | ||
|||''x_k''||Optimal point. | |||''x_k''||Optimal point. | ||
Line 80: | Line 81: | ||
|- | |- | ||
|||''xState''||State of each variable, described in Table 150. | |||''xState''||State of each variable, described in Table 150. | ||
|- | |-valign="top" | ||
|||''ExitFlag''||0: Optimal solution found. | |||''ExitFlag''||0: Optimal solution found. | ||
1: Maximal number of iterations reached. | |||
2: Unbounded feasible region. | |||
5: Too many active variables in given initial point. | |||
6: No feasible point found with Phase 1. | |||
10: Errors in input parameters. | |||
11: Illegal initial x as input. | |||
|- | |- | ||
|||''Inform''||If ''ExitF lag > ''0, ''Inform ''= ''ExitF lag''. | |||
|||''Inform''||If ''ExitF lag > ''0, '' | |||
|- | |- | ||
|||''QP.B''||Optimal active set. See input variable ''QP.B''. | |||''QP.B''||Optimal active set. See input variable ''QP.B''. | ||
Line 105: | Line 106: | ||
|||''Iter''||Number of iterations. | |||''Iter''||Number of iterations. | ||
|-valign="top" | |-valign="top" | ||
|||''FuncEv''||Number of function evaluations. Equal to ''Iter''. ''ConstrEv ''Number of constraint evaluations. Equal to ''Iter''. | |||''FuncEv''||Number of function evaluations. Equal to ''Iter''. | ||
|- | |||
|||''ConstrEv''||Number of constraint evaluations. Equal to ''Iter''. | |||
|- | |- | ||
|||''Prob''||Problem structure used. | |||''Prob''||Problem structure used. | ||
Line 120: | Line 123: | ||
==See Also== | ==See Also== | ||
''qpSolve'' | [[qpSolve|''qpSolve'']] |
Latest revision as of 08:13, 16 January 2012
Purpose
Solve general linear programming problems.
lpSimplex solves problems of the form
where , , and .
Calling Syntax
Result = lpSimplex(Prob) or
Result = tomRun('lpSimplex', Prob, 1);
Inputs
Prob | Problem description structure. The following fields are used: | |
---|---|---|
QP.c | Constant vector. | |
A | Constraint matrix for linear constraints. | |
b_L | Lower bounds on the linear constraints. | |
b_U | Upper bounds on the linear constraints. | |
x_L | Lower bounds on the variables. | |
x_U | Upper bounds on the variables. | |
x_0 | Starting point. | |
Solver.Alg | Variable selection rule to be used:
0: Minimum reduced cost. 1: Bland's rule (default). 2: Minimum reduced cost. Dantzig's rule. | |
QP.B | Active set B 0 at start:
B(i) = 1: Include variable x(i) is in basic set. B(i) = 0: Variable x(i) is set on its lower bound. B(i) = -1: Variable x(i) is set on its upper bound. | |
optParam | Structure with special fields for optimization parameters, see TOMLAB Appendix A.
Fields used are: MaxIter, PriLev, wait, eps_f, eps_Rank, xTol and bTol. |
Outputs
Result | Structure with result from optimization. The following fields are changed: | |
---|---|---|
x_k | Optimal point. | |
f_k | Function value at optimum. | |
g_k | Gradient value at optimum, c. | |
v_k | Lagrange multipliers. | |
x_0 | Starting point. | |
f_0 | Function value at start. | |
xState | State of each variable, described in Table 150. | |
ExitFlag | 0: Optimal solution found.
1: Maximal number of iterations reached. 2: Unbounded feasible region. 5: Too many active variables in given initial point. 6: No feasible point found with Phase 1. 10: Errors in input parameters. 11: Illegal initial x as input. | |
Inform | If ExitF lag > 0, Inform = ExitF lag. | |
QP.B | Optimal active set. See input variable QP.B. | |
Solver | Solver used. | |
SolverAlgorithm | Solver algorithm used. | |
Iter | Number of iterations. | |
FuncEv | Number of function evaluations. Equal to Iter. | |
ConstrEv | Number of constraint evaluations. Equal to Iter. | |
Prob | Problem structure used. |
Description
The routine lpSimplex implements an active set strategy (Simplex method) for Linear Programming using an additional set of slack variables for the linear constraints. If the given starting point is not feasible then a Phase I objective is used until a feasible point is found.
M-files Used
ResultDef.m