Авторизация
Поиск по указателям
Wright S. J. — Primal-dual interior-point methods
Обсудите книгу на научном форуме Нашли опечатку?
Название: Primal-dual interior-point methodsАвтор: Wright S. J. Аннотация: In the past decade, primal-dual algorithms have emerged as the most important and useful algorithms from the interior-point class. This book presents the major primal-dual algorithms for linear programming in straightforward terms. A thorough description of the theoretical properties of these methods is given, as are a discussion of practical and computational aspects and a summary of current software. This is an excellent, timely, and well-written work. The major primal-dual algorithms covered in this book are path-following algorithms (short- and long-step, predictor-corrector), potential-reduction algorithms, and infeasible-interior-point algorithms. A unified treatment of superlinear convergence, finite termination, and detection of infeasible problems is presented. Issues relevant to practical implementation are also discussed, including sparse linear algebra and a complete specification of Mehrotra's predictor-corrector algorithm. Also treated are extensions of primal-dual algorithms to more general problems such as monotone complementarity, semidefinite programming, and general convex programming problems.
Язык: Рубрика: Математика /Статус предметного указателя: Готов указатель с номерами страниц ed2k: ed2k stats Год издания: 1987Количество страниц: 310Добавлена в каталог: 05.11.2010Операции: Положить на полку |
Скопировать ссылку для форума | Скопировать ID
Предметный указатель
Simplex method, software for 257 Simplex method, vertex solutions and 33 150 Singular value decomposition (SVD) 246—247 Skew-symmetric matrices 179 191 243 Slack variables 3 22 46 163 226 227 Software for primal-dual methods 2 17 22 32 107 193 204 207 209—210 215 230—232 257-263 Solution set, boundedness of 26—27 177 183 184 237 Solution set, closedness of 24 Solution set, dual ( 24 Solution set, existence of 24—26 Solution set, nonemptiness of 26—27 Solution set, primal ( 24 56 Solution set, primal-dual ( 24 255 Solution set, unboundedness of 217 230 Sparse matrices 16 17 164 189 209 Sparse matrices, storage of 253—254 Spurious solutions 5 7 12 Standard form 2 13 22—23 47 65 107 124 Standard form, dual of 3 Standard form, transformation to 22 46 229 Starting points, feasible 107 Starting points, feasible, expense of calculating 177 Starting points, feasible, for HSD formulation 184 Starting points, infeasible 11—12 115 177 Starting points, infeasible, and HSD formulation 183 Starting points, infeasible, and simplified HSD formulation 183 Starting points, infeasible, hot starts 224—225 Starting points, infeasible, polynomial complexity and 108 115 117—118 125 Starting points, infeasible, practical choice of 224—225 Step equations 16 210 Step equations, for convex programming 165 Step equations, from infeasible points 12 104 129 Step equations, generic (with centering) 8 71 Step equations, ill conditioning of 17 Step equations, iterative solution of 234 Step equations, unique solution of 32 Step length, lower bound on, for Algorithm IPF 118—120 Step length, lower bound on, for Algorithm LPF 97—100 137 Step length, lower bound on, for Algorithm PC 94—95 105 Strict complementarity 21 101—103 121 123 144—146 148 150 162 217 241 244-245 Strict complementarity, example of 28 Strict complementarity, for LCP 162 245 Strictly feasible set, boundedness of solution set and 26—27 30—31 237 Strictly feasible set, dual 26 Strictly feasible set, emptiness of 29 107 124 Strictly feasible set, emptiness of, infeasible starting points and 30 Strictly feasible set, monotone LCP and 159 Strictly feasible set, primal 26 Strictly feasible set, primal-dual ( 5—10 18 19 29—31 55 66 67 71 72 83—85 91 94—96 99 101 123 144 146 177 181 237 Strongly polynomial algorithms 58 63 Sufficient decrease condition 108 110 124 125 166 186 Superlinear convergence 2 10 12—13 43 96 109 127 128 135—145 154 155 162 171 252 supernodes 214—215 234 259 260 Superquadratic convergence 198 199 Surplus variables 180 184 Symmetric indefinite matrices, factorizations of 17 220—224 229 Symmetric indefinite matrices, factorizations of, Bunch Parlett 222—223 234 Symmetric indefinite matrices, factorizations of, Bunch — Kaufman 222 223 Symmetric indefinite matrices, factorizations of, sparse Bunch Parlett 223—224 Symmetric matrices 13 16 17 19 210 211 254 Taylor series approximation 200 201 203 245 Termination criteria 209 225—226 Theorem of the alternative 27 Trajectories to solution set 14—16 200 201 203 207 Trajectories to solution set, curvature of 15 202 Trajectory-following algorithms 193 202 207 Triangle inequality 116 Triangular matrices 211 234 247 Turing machine 52 54 59 62 254—255 Unboundedness of objective function 46 177 231 Variational inequality, monotone 167—168 Vertex 33—34 54 55 Vertex solution 56 57 150 224 225 258 optimal”) World Wide Web 45 174 210 232 257
Реклама
) 
) 
) 
) 
|
|
О проекте