Ex Libris                        Wanted                           
blank

       
blank

blank
blank
blank
blank
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.


: en

: /

:

ed2k: ed2k stats

: 1987

: 310

: 05.11.2010

: | | ID
blank
$P_{*}$ linear complementarity problem      173
$QR$ factorization      31 54 63 232 247249
$\epsilon(A,b,c)$      56 122 128 130 145146 148 149 152154 204
$\epsilon(A,b,c)$, definition of      56
$\epsilon(A,b,c)$, example of noncontinuity      152154
Adjacency graph      214216
Adjacency graph, elimination step for      214215
Affine-scaling algorithm, primal      22 4244
Affine-scaling algorithm, primal-dual      4445
Affine-scaling direction, primal-dual      see Newton step pure
Algorithm IPF      107125 128 177 180 185 187 190 224 262
Algorithm IPF, complexity of      112 121
Algorithm IPF, convex programming form of      166168
Algorithm IPF, definition of      109110
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+      136145
Algorithm LPF+, definition of      138139
Algorithm LPF+, infeasible variant of      154
Algorithm LPF, definition of      96 97
Algorithm MPC      204 206
Algorithm MPC, definition of      195198
Algorithm MPC, Shamanskiis algorithm and      199
Algorithm MPC, trajectory following and      201202
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 135136 145
Algorithm PR      67 68 7072 79 81
Algorithm PR, definition of      6768
Algorithm S3      198199 (see also Shamanskiis algorithm)
Algorithm SPF      84 88 90 91 93 96 102105 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 220221 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 4043 47
Barrier function, logarithmic, KKT conditions for      39
Barrier function, logarithmic, strict convexity of      37
Basic feasible points      33 54 56
Basis      3234
Basis, optimal      33 (see also Vertex solution)
Basis, optimal, recovery of      57 150152 225226
Bounds on variables, upper      226228
BPMPD      232 258259
Callable routines      258
Cauchy sequence      144 145
Centering parameter ($\sigma$)      78 1012 6768 79 8386 9193 9597 104 108 137 158 186 189 193196 198 199 201 205-206 249
Centering parameter ($\sigma$), adaptive choice of      14 15
Central path      79 14 30 43 85 152 153 196 225
Central path, existence of      3640 69
Central path, geometry of      45 154 203 204
Central path, LCP form of      159
Central path, neighborhoods of      910 8385 90100 129 174 225
Central path, neighborhoods of, $\mathcal{N}_{-\infty}(\gamma)$      9 19 43 84 85 96105 108 130 133 135 137 144 146 147 155 159
Central path, neighborhoods of, $\mathcal{N}_{2}(\theta)$      9 10 43 8492 9498 103105 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 211221 228230 234 235
Cholesky factorization, sparse, dense column handling      17 219 220 233234 259 260
Cholesky factorization, sparse, multiprocessor implementation      212 234235
Cholesky factorization, sparse, small pivot handling      17 216 219 230 232233
Cholesky factorization, sparse, small pivot handling, diagonal pivoting      218 235 236
Cholesky factorization, sparse, small pivot handling, skipping      218219
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 1718 34 44 45 6162 6668 70 77- 80 84 85 8788 90 9597 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      216218 220
Conjugate gradient algorithm, preconditioned      234 260 262
Constraint qualification      165 241
Convex functions      164 168 240 242 250
Convex programming      157 164167 243 250 261
Convex sets      164 167 240 242
Corrector steps      85 92 93 95 105 194197 199 202 203 206 207
Corrector steps, multiple      199 202204 259 260
CPLEX Parallel Barrier      234
CPLEX/Barrier      226 232 259
CPLEX/Simplex      232
Cramers Rule      53
Crossover to simplex      see Basis optimal recovery
Data string      see Problem data
Degenerate LCP      173174
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
Dikins 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      24 2329
Efficient algorithms      see Polynomial algorithms
Eigenvalues      217
Ellipsoid algorithm      18 4951 53 57
Exponential algorithms      50
Farkass lemma      24 3435 45
Fast step      138142 144
Feasible set, dual      23
Feasible set, existence of solutions and      2426
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 187188
Fill-in      212213 235
Finite termination      5557 60 62 127 128 146149 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 228230 258
Free variables, splitting of      22 46 163 174 226 228230
Full rank of $A$      3132 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      3536
Goldman Tucker theorem, statement of      28
hessian      240
Hoffmans lemma      124 148 248249
Homogeneous problem, definition of      180
Homogeneous self-dual (HSD) formulation      107 178 183185
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 178183 185
Homogeneous self-dual (HSD) formulation, simplified, detection of infeasibility      182 183
Homogeneous self-dual (HSD) formulation, simplified, implementation of      188190
Homogeneous self-dual (HSD) formulation, simplified, lack of strictly feasibility      181
Homogeneous self-dual (HSD) formulation, simplified, recovery of primal-dual solution      181182
HOPDM      203 232 259260
Horizontal linear complementarity problem (hLCP)      160162
Horizontal linear complementarity problem (hLCP), strict complementarity and      162
Indicators      154155
Infeasible linear programs      2 2526 177 178 181183
Infeasible-interior-point algorithms      2 1112 81 107125 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      186188
Integer programming      22 57
Integer programming, software for      257
Interior Point Methods Online      174 257
Iteration sequence, convergence of      103 144145 162
Iteration sequence, limit points of      100104 108 121 123 127 186
Jacobian      6 13 127 129 164 198 241
Karmarkars      18 41 44 65
Karmarkars algorithm      1 1718 41 49 53 58 65
Karmarkars algorithm, complexity of      18 42 50 62
Karush Kuhn Tucker (KKT) conditions      35 7 9 13 19 2325 4547 56 83 147 158 161 170 171 175 179 208 226229 236 240241 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 242243
Khachiyans 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 157162 167
Linear complementarity problem (LCP), monotone, definition of      157158
Linear complementarity problem (LCP), monotone, equivalent formulations of      13 160162
Linear complementarity problem (LCP), monotone, relationship to convex quadratic programming      13 163164 171173
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 260261
Logarithm, natural      61 68 70 143 245246
LOQO      198 232 261
Mehrotras predictor-corrector algorithm      2 1416 85 193208 210 234
Mehrotras predictor-corrector algorithm, motivation for      194195
Mehrotras predictor-corrector algorithm, superquadratic convergence of      198199
Mehrotras predictor-corrector algorithm, variants of      204207
Minimum-degree orderings      213216 235 260 262
Minimum-local-fill orderings      215 216 259 261
Mixed monotone linear complementarity problem (mLCP)      160164 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 244245
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      261262
Newton step, pure      68 12 15 44 127135 137 138 154 174 194197 199 200 202 206 207 249
Newtons method      4 6 12 14 41 83 127 136 149 158 165
Newtons 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      1617 210 215 220 221 228- 234 259 260 262 sparse)
Opening the cone      137139
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      262263
Pairwise products      79 11 36 37 79 8486 89 109 141 196 197 204 205
Partition $\mathcal{B}\bigcup\mathcal{N}$      2729 32 56 121 128 131 145149 217
Path-following algorithms      2 910 14 50 107 121 144 174 203 217
Path-following algorithms, complexity of      6162 68 84 9596 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 96100 102 103 109
Path-following algorithms, motivation for      83
Path-following algorithms, predictor-corrector (Mizuno Todd-Ye)      10 44 84 9196 102 103 105
Path-following algorithms, relationship to potential-reduction algorithms      78 81
Path-following algorithms, short-step      10 43 8491 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      7078
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 6581
Potential-reduction algorithms      2 1044 6581
Potential-reduction algorithms, centrality of iterates      7879
Potential-reduction algorithms, complexity of      70 7780 84
Potential-reduction algorithms, practical variants of      80
Potential-reduction algorithms, pure primal      62 81
Predictor steps      84 9296 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      5557 128 147 152 154155
Procedure FT, definition of      146147
Procedure OB D      151152
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 163164 174175 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      5254 57 59
Rational-number model      49 52 5960 255
Rational-number model, emulated on Turing machine      52 54
Real-number (BSS) model      50 59 60 63
Remaining matrix      213 235
Renegars algorithm      4142 44 53 65
Residuals      11 12 109 111 129 134 155 167 185189 191 206 226 229
Roundoff error      59 60 62 217
Roundoff error, unit      212 221
Safe step      138140 142
Schur complement      233 260
Self-concordancy      166 168
Self-dual linear programs      178180 184 191
Self-dual linear programs, mLCP formulation of      180 184 243245
Semidefinite matrices      158 163 174 210 218 240
Semidefinite programming (SDP)      13 157 167171 174
Shamanskiis algorithm      193 198199
Sherman Morrison Woodbury formula      189 220 233 236 250251 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
blank
blank
blank
HR
@Mail.ru
       © , 2004-2022
   | Valid HTML 4.01! | Valid CSS!