Wright S. J. — Primal-dual interior-point methods :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Красота

Wright S. J. — Primal-dual interior-point methods

Wright S. J. — Primal-dual interior-point methods

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: 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

Предметный указатель

$P_{*}$ linear complementarity problem      173
factorization      31 54 63 232 247—249
$\epsilon(A,b,c)$       56 122 128 130 145—146 148 149 152—154 204
$\epsilon(A,b,c)$ , definition of      56
$\epsilon(A,b,c)$ , example of noncontinuity      152—154
Adjacency graph      214—216
Adjacency graph, elimination step for      214—215
Affine-scaling algorithm, primal      22 42—44
Affine-scaling algorithm, primal-dual      44—45
Affine-scaling direction, primal-dual      see “Newton step pure”
Algorithm IPF      107—125 128 177 180 185 187 190 224 262
Algorithm IPF, complexity of      112 121
Algorithm IPF, convex programming form of      166—168
Algorithm IPF, definition of      109—110
Algorithm IPF, flexibility in line search      110 125
Algorithm LPF      43 90 96 98 100 102 103 107 108 111 124 128 136 long-step”)
Algorithm LPF+      136—145
Algorithm LPF+, definition of      138—139
Algorithm LPF+, infeasible variant of      154
Algorithm LPF, definition of      96 97
Algorithm MPC      204 206
Algorithm MPC, definition of      195—198
Algorithm MPC, Shamanskii’s algorithm and      199
Algorithm MPC, trajectory following and      201—202
Algorithm PC      84 92 93 95 96 102 103 105 128 predictor-corrector
Algorithm PC, definition of      93
Algorithm PC, LCP form of      159 160
Algorithm PC, superlinear convergence of      128 135—136 145
Algorithm PR      67 68 70—72 79 81
Algorithm PR, definition of      67—68
Algorithm S3      198—199 (see also “Shamanskii’s algorithm”)
Algorithm SPF      84 88 90 91 93 96 102—105 short-step”)
Algorithm SPF, definition of      86
AMPL      258
Analytic center, weighted      42
Armijo condition      see “Sufficient decrease condition”
Augmented system form of step equations      16 17 210 220—221 227 229 230 235 261 factorizations
Barrier function, logarithmic      40 43
Barrier function, logarithmic, defines central path      37 40
Barrier function, logarithmic, for linear program      37 40—43 47
Barrier function, logarithmic, KKT conditions for      39
Barrier function, logarithmic, strict convexity of      37
Basic feasible points      33 54 56
Basis      32—34
Basis, optimal      33 (see also “Vertex solution”)
Basis, optimal, recovery of      57 150—152 225—226
Bounds on variables, upper      226—228
BPMPD      232 258—259
Callable routines      258
Cauchy sequence      144 145
Centering parameter ( $\sigma$ )      7—8 10—12 67—68 79 83—86 91—93 95—97 104 108 137 158 186 189 193—196 198 199 201 205-206 249
Centering parameter ( $\sigma$ ), adaptive choice of      14 15
Central path      7—9 14 30 43 85 152 153 196 225
Central path, existence of      36—40 69
Central path, geometry of      45 154 203 204
Central path, LCP form of      159
Central path, neighborhoods of      9—10 83—85 90—100 129 174 225
Central path, neighborhoods of, $\mathcal{N}_{-\infty}(\gamma)$       9 19 43 84 85 96—105 108 130 133 135 137 144 146 147 155 159
Central path, neighborhoods of, $\mathcal{N}_{2}(\theta)$       9 10 43 84—92 94—98 103—105 135 159
Central path, neighborhoods of, $\mathcal{N}_{\infty}(\theta)$       84
Central path, neighborhoods of, infeasible      12 109 111 134 166 186 190 199 203 205
Central path, relationship to KKT conditions      7 36 83
Central path, SDP form of      171
Cholesky factorization, sparse      17 211—221 228—230 234 235
Cholesky factorization, sparse, dense column handling      17 219 220 233—234 259 260
Cholesky factorization, sparse, multiprocessor implementation      212 234—235
Cholesky factorization, sparse, small pivot handling      17 216 219 230 232—233
Cholesky factorization, sparse, small pivot handling, diagonal pivoting      218 235 236
Cholesky factorization, sparse, small pivot handling, skipping      218—219
Cholesky factorization, sparse, stability of      212 216
Combinatorial optimization      14 22 170
Compact set      39 186
Complementarity      4 7 23 158
complexity      21 239
Complexity, algebraic      50 60
Complexity, average-case      50 51 57
Complexity, bit      50 51 60
Complexity, general references for      49
Complexity, interior-point methods and      49
Complexity, polynomial      1 17—18 34 44 45 61—62 66—68 70 77- 80 84 85 87—88 90 95—97 100 104 108 109 112 114 159 168 185
Complexity, practical performance and      58
Complexity, problem size      51
Complexity, worst-case      50 51 57
Condition number      212 217 247
Conditioning of coefficient matrices      216—218 220
Conjugate gradient algorithm, preconditioned      234 260 262
Constraint qualification      165 241
Convex functions      164 168 240 242 250
Convex programming      157 164—167 243 250 261
Convex sets      164 167 240 242
Corrector steps      85 92 93 95 105 194—197 199 202 203 206 207
Corrector steps, multiple      199 202—204 259 260
CPLEX Parallel Barrier      234
CPLEX/Barrier      226 232 259
CPLEX/Simplex      232
Cramer’s Rule      53
Crossover to simplex      see “Basis optimal recovery
Data string      see “Problem data”
Degenerate LCP      173—174
Degenerate LCP, no superlinear convergence      174
Degree of a node      213 214
Dense matrices      17 189
Diagonal matrices      16 89 130 131 217 227 246 249 261
Dikin’s algorithm      see “Affine-scaling algorithm primal”
Divergence of iterates      177 185 188
Dual degenerate linear programs      174
Dual slack variables      3
Dual variables      3
Duality measure ( $\mu$ ), definition of      7
Duality theory      2—4 23—29
Efficient algorithms      see “Polynomial algorithms”
Eigenvalues      217
Ellipsoid algorithm      18 49—51 53 57
Exponential algorithms      50
Farkas’s lemma      24 34—35 45
Fast step      138—142 144
Feasible set, dual      23
Feasible set, existence of solutions and      24—26
Feasible set, monotone LCP and      159
Feasible set, polygonal form of      33 54 55 57
Feasible set, primal      3 23 33
Feasible set, primal-dual ( $\mathcal{F}$ )      5 9 23 162 185 187—188
Fill-in      212—213 235
Finite termination      55—57 60 62 127 128 146—149 154 174 204 225
Finite termination, superlinear convergence and      149
Floating-point arithmetic      57 59 62
Floating-point arithmetic, error analysis of      59
Framework PD      8 11 14 15 18 67 84 86 92 158 170 193 202
Framework PD, LCP form of      158
Free variables      17 221 228—230 258
Free variables, splitting of      22 46 163 174 226 228—230
Full rank of       31—32 37 54 63 155 186 191 211 217
Function long-step      137 139 141 142
GAMS      258
Gaussian elimination      31
Geometric linear complementarity problem      173
Global convergence      12 67 88 111 128 159
Goldman — Tucker theorem      21 162 182 241 245
Goldman — Tucker theorem, proof of      35—36
Goldman — Tucker theorem, statement of      28
hessian      240
Hoffman’s lemma      124 148 248—249
Homogeneous problem, definition of      180
Homogeneous self-dual (HSD) formulation      107 178 183—185
Homogeneous self-dual (HSD) formulation, definition of      183
Homogeneous self-dual (HSD) formulation, detection of infeasibility      185
Homogeneous self-dual (HSD) formulation, implementation of      190
Homogeneous self-dual (HSD) formulation, recovery of primal-dual solution      185
Homogeneous self-dual (HSD) formulation, simplified      174 178—183 185
Homogeneous self-dual (HSD) formulation, simplified, detection of infeasibility      182 183

Homogeneous self-dual (HSD) formulation, simplified, implementation of      188—190
Homogeneous self-dual (HSD) formulation, simplified, lack of strictly feasibility      181
Homogeneous self-dual (HSD) formulation, simplified, recovery of primal-dual solution      181—182
HOPDM      203 232 259—260
Horizontal linear complementarity problem (hLCP)      160—162
Horizontal linear complementarity problem (hLCP), strict complementarity and      162
Indicators      154—155
Infeasible linear programs      2 25—26 177 178 181—183
Infeasible-interior-point algorithms      2 11—12 81 107—125 133 178 180 183 188 189
Infeasible-interior-point algorithms, convex programming and      166
Infeasible-interior-point algorithms, finite termination and      146
Infeasible-interior-point algorithms, LCP form of      158
Infeasible-interior-point algorithms, termination test for      186—188
Integer programming      22 57
Integer programming, software for      257
Interior — Point Methods Online      174 257
Iteration sequence, convergence of      103 144—145 162
Iteration sequence, limit points of      100—104 108 121 123 127 186
Jacobian      6 13 127 129 164 198 241
Karmarkar’s      18 41 44 65
Karmarkar’s algorithm      1 17—18 41 49 53 58 65
Karmarkar’s algorithm, complexity of      18 42 50 62
Karush Kuhn Tucker (KKT) conditions      3—5 7 9 13 19 23—25 45—47 56 83 147 158 161 170 171 175 179 208 226—229 236 240—241 243
Karush Kuhn Tucker (KKT) conditions, for convex programming      164
Karush Kuhn Tucker (KKT) conditions, for convex quadratic programming      163
Karush Kuhn Tucker (KKT) conditions, sufficiency of      24 47 132 242—243
Khachiyan’s algorithm      see “Ellipsoid algorithm”
Lagrange multipliers      4 241 243
Lagrangian function      165
LAPACK      248
Line search heuristics      80
Linear complementarity problem (LCP), monotone      13 14 43 109 139 154 157—162 167
Linear complementarity problem (LCP), monotone, definition of      157—158
Linear complementarity problem (LCP), monotone, equivalent formulations of      13 160—162
Linear complementarity problem (LCP), monotone, relationship to convex quadratic programming      13 163—164 171—173
Linear complementarity problem (LCP), monotone, strict complementarity and      162
Linear convergence, Q-linear      111 121 140 252
Linear convergence, R-linear      111 121 253
Linear least-squares problems      17 147 224 250
Linear programming, general references for      21 257
LIPSOL      198 204 219 232 260—261
Logarithm, natural      61 68 70 143 245—246
LOQO      198 232 261
Mehrotra’s predictor-corrector algorithm      2 14—16 85 193—208 210 234
Mehrotra’s predictor-corrector algorithm, motivation for      194—195
Mehrotra’s predictor-corrector algorithm, superquadratic convergence of      198—199
Mehrotra’s predictor-corrector algorithm, variants of      204—207
Minimum-degree orderings      213—216 235 260 262
Minimum-local-fill orderings      215 216 259 261
Mixed monotone linear complementarity problem (mLCP)      160—164 174 179 189 191 227
Mixed monotone linear complementarity problem (mLCP), step equations for      161
Mixed monotone linear complementarity problem (mLCP), strictly complementary solutions of      162 179 181 182 244—245
MPS input format      258
NEOS Server      257 263
Nested-dissection orderings      216 235
NETLIB      190 207
Network optimization      21 58 234
Network optimization, software for      257
Newton Barrier XPRESS — MP      261—262
Newton step, pure      6—8 12 15 44 127—135 137 138 154 174 194—197 199 200 202 206 207 249
Newton’s method      4 6 12 14 41 83 127 136 149 158 165
Newton’s method, Kantorovich analysis of      127 129
Nonconvex problems      14
Nondegenerate solution      13 199
Nonlinear complementarity problems, monotone      14 43 157 167
Nonlinear equations      6 12 198
Nonnegative orthant      6 11 13 33
Normal equations form of step equations      16—17 210 215 220 221 228- 234 259 260 262 sparse”)
Opening the cone      137—139
Optimization problems      1 60 239
Optimization problems, constrained      3 4 39 45 104 240
Optimization problems, global solutions of      240 242
Optimization problems, local solutions of      240 242
Optimization problems, unconstrained      149
Order notation      239
Ordinary differential equations      92 199
orthogonal matrices      155 246 247
OSL      262—263
Pairwise products      7—9 11 36 37 79 84—86 89 109 141 196 197 204 205
Partition $\mathcal{B}\bigcup\mathcal{N}$       27—29 32 56 121 128 131 145—149 217
Path-following algorithms      2 9—10 14 50 107 121 144 174 203 217
Path-following algorithms, complexity of      61—62 68 84 95—96 100 159
Path-following algorithms, finite termination and      146
Path-following algorithms, homotopy methods and      9
Path-following algorithms, long-step      10 43 85 90 96—100 102 103 109
Path-following algorithms, motivation for      83
Path-following algorithms, predictor-corrector (Mizuno — Todd-Ye)      10 44 84 91—96 102 103 105
Path-following algorithms, relationship to potential-reduction algorithms      78 81
Path-following algorithms, short-step      10 43 84—91 102 104
Path-following algorithms, strictly complementary limit points of      181
PCX      198 258 263
Permutation matrices      54 211 212 248
Polynomial algorithms      50 52 57 58 60 63 135 polynomial”)
Positive definite matrices      211 (see also “Semidefinite matrices”)
Positive semidefinite matrices      13 19
Potential function      10
Potential function, Tanabe — Todd — Ye, quadratic approximation to      70—78
Potential function, Tanabe — Todd — Ye, relationship to $\mu$       67 69
Potential function, Tanabe — Todd — Ye, SDP form of      171
Potential function, Tanabe — Todd-Ye      11 19 44 65—81
Potential-reduction algorithms      2 10—44 65—81
Potential-reduction algorithms, centrality of iterates      78—79
Potential-reduction algorithms, complexity of      70 77—80 84
Potential-reduction algorithms, practical variants of      80
Potential-reduction algorithms, pure primal      62 81
Predictor steps      84 92—96 105 135 194
Preprocessing      see “Presolving”
Presolving      209 220 230 232
Primal degenerate linear programs      174
Problem data      51 59 60 152 255
Problem data, definition of      51
Problem data, integer      51 54 56 58 63
Problem data, rational      51
Problem data, storage of      51 53
Problem dimension      58
Problem dimension, definition of      51
Procedure FT      55—57 128 147 152 154—155
Procedure FT, definition of      146—147
Procedure OB — D      151—152
Procedure OB — P      151
Q-order of convergence      142 144 154 252
Quadratic convergence      127 252
Quadratic programming, convex      2 13 14 19 131 133 134 157 160 163—164 174—175 261
Quadratic programming, convex, quadratically constrained      167 170
Quadratic programming, convex, relationship to LCP      13
Rank of matrices      246 249 250
Rank-deficient matrices      211 247
Rational arithmetic      52—54 57 59
Rational-number model      49 52 59—60 255
Rational-number model, emulated on Turing machine      52 54
Real-number (BSS) model      50 59 60 63
Remaining matrix      213 235
Renegar’s algorithm      41—42 44 53 65
Residuals      11 12 109 111 129 134 155 167 185—189 191 206 226 229
Roundoff error      59 60 62 217
Roundoff error, unit      212 221
Safe step      138—140 142
Schur complement      233 260
Self-concordancy      166 168
Self-dual linear programs      178—180 184 191
Self-dual linear programs, mLCP formulation of      180 184 243—245
Semidefinite matrices      158 163 174 210 218 240
Semidefinite programming (SDP)      13 157 167—171 174
Shamanskii’s algorithm      193 198—199
Sherman — Morrison — Woodbury formula      189 220 233 236 250—251 260
Simplex method      1 32 33 225 232 234
Simplex method, complexity of      17 49 50 57
Simplex method, hot-starting of      225
Simplex method, Klee — Minty example      18 57
Simplex method, performance of      17

1 2

Реклама

© Электронная библиотека попечительского совета мехмата МГУ, 2004-2024

Электронная библиотека мехмата МГУ

Valid HTML 4.01!

|

Valid CSS!

О проекте