Klerk de E. — Aspects of Semidefinite Programming :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Klerk de E. — Aspects of Semidefinite Programming

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

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

Название: Aspects of Semidefinite Programming

Автор: Klerk de E.

Аннотация:

This monograph has grown from my PhD thesis Interior point Methods for Semidefinite Programming [39] which was published in December 1997. Since that time, Semidefinite Programming (SDP) has remained a popular research topic and the associated body of literature has grown considerably. As SDP has proved such a useful tool in many applications, like systems and control theory and combinatorial optimization, there is a growing number of people who would like to learn more about this field.

Язык:

Рубрика: Computer science/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 2002

Количество страниц: 283

Добавлена в каталог: 26.06.2009

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

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

$({P}_{g f})$       262
$\delta(X,S,\mu)$       117
$\epsilon$ -optimality      12
$\mathcal{B}$       35
$\mathcal{D}$       22
$\mathcal{D}^{*}$       22
$\mathcal{N}$       35
$\mathcal{P}$       22
$\mathcal{P}^{*}$       22
$\mathcal{T}$       35
$\mu$ -center      115
$\mu$ -update      85 123
$\mu$ -update adaptive      87
$\Phi$       134
$\Psi$       136 137
${\delta}_{d}(S,\mu)$       89
${\delta}_{p}(X,\mu)$       78
(D)      2 22
(P)      2 22
Active constraint      36
Adjacency matrix      161
Adjacency matrix of the pentagon      161
Affine-scaling      15
Affine-scaling primal      81 82
AHO direction      260
Algebraic set      56
Analytic center      51
Analytic center of the duality gap level sets      52
Analytic curve central path as an      46
Analytic extension      248
Analytic extension of the central path      48
Analytic function      247
Approximate graph colouring      183
Approximation algorithm      174
Approximation algorithm for MAX-3-SAT      223
Approximation algorithm for MAX-k-CUT      175
Approximation guarantee      174
Approximation guarantee for global optimization implementable      208
Approximation guarantee for MAX-3-SAT      228
Approximation guarantee for MAX-k-CUT      182
Approximation guarantee for standard quadratic optimization      208
Approximation guarantee for the max. stable set problem      188
Approximation guarantee in the weak sense      207
Arithmetic-geometric inequality      243
Arithmetic-geometric mean inequality      52 53 136 234
Arrow matrix      4
B      50
Barrier parameter      76
Big-M method      16 61
Bit model of computation      17
Block diagonal matrix      230
Boolean quadratic (in)equality      214
Cauchy function      247
Cauchy — Schwartz inequality      88 108 137
Centering component      81
Centering parameter      76
Central path      13 42 52 102
Central path of the embedding problem      67
Central path, analyticity of      46
Central path, convergence rate of      58
Central path, derivatives of      48
Central path, limit point      48
Central path, quadratic convergence to      84 120 122
Central path, tangential direction to      48
Centrality conditions      41
Centrality function      78
Centrality function $\kappa$       102
Centrality function of Faybusovich      78
Centrality function of Jiang      117
Choleski factorization      224 229
Chromatic number      4 158 223
Clause      7 212
Clause-variable matrix      214
CLIQUE      4 222
Clique number      4 158 223
Co-clique      7
Co-clique number      7
Combinatorial optimization      3
Complementary graph      158
Complementary solutions      33
Condition number of the embedding      70
Cone of completely positive martrices      189
Cone of completely positive martrices extreme ray of      190 239
Cone of copositive matrices      189
Cone of nonnegative matrices      189
Cone of positive semidefinite matrices      12
Cone of positive semidefinite matrices, extreme ray of      239
Cone of positive semidefinite matrices, face of      239
Conic duality theorem      28
Conic problem formulation      11 24
Conjugate gradient method      93
Conjunctive normal form (CNF)      212
Convex cone      238
Convex function      149 237
Convex set      237
Copositive matrix      187
Curve selection lemma      56
Cutting plane      220
Cycle (in a graph)      203
Damped NT step      118 124
De-randomization      224
Defect edge      169 222
Degree of a vertex      185
Deterministic rounding      224
Diagonally dominant      172 232
Dihedral angle      226
Dikin ellipsoid      82 100
Dikin-type primal-dual affine-scaling      99
Directional derivative of $\Phi$       137
Directional derivative of $\Psi$       137
Dual barrier function      76
Dual cone      12 178
Dual degeneracy      37
Duality gap      2 25 99 137
Duality gap, after full NT step      119
Duality gap, compact level set of      43
Duality gap, upper bound in terms of $\Phi(X,S)$       137
Ellipsoid method      11 17
Elliptic representations of clauses      215
Epigraph      151 237
Extended Lagrange — Slater dual      262
Extreme point      190
Extreme ray      190 239
Face      261
Face of a convex cone      238
Face of the cone ${S}^{+}_{n}$       34
Feasible direction      24 98
Feasible set      22
Feasible step      24
Frobenius norm      2 44 233
Full NT step      118
Gamma function      183
Gap relaxation      221
Gap-free primal problem      262
Generalised eigenvalues      135
Goldman — Tucker theorem      33
Gradient of log det (X)      243
Gram matrix      178
Heptagon      167
Hessian of log det(X)      244
Homogeneous embedding      16 64
icosahedron      201
Idempotent matrix      177
Ill-posedness      71
Implicit function theorem      46 48
Improving ray      29 69
Incidence vector      158 221
Inclusion-exclusion      225
Independence number      8
Independent set      7

Infeasibility      22
Infeasible-start method      16
Inner iteration      92 124
Integer programming      214
Interior point assumption      23
Interior point methods      11
Jacobian      47
k-cut      169
K-Z relaxation      217 228
KKT conditions      242
KKT point      228 242
Kronecker product      47
Kronecker product, properties of      249
Lagrangian      240
Lagrangian dual      2 241
Lagrangian dual of (P)      22
Lagrangian dual of SDP in conic form      24
Laplacian      6 93
Legal colouring      170 183
Lift-and-project method      8
Linear programming (LP)      3 11
Loewner partial order      2 235
Logarithmic barrier methods      12
Logarithmic Chebychev approximation      9
Logical 'OR' operator      211
Logical variables      211
Long step method      15
Long step method, dual algorithm      92
Long step method, primal-dual algorithm with NT direction      124
Lorentz cone      154
Lovasz sandwich theorem      158 223
Lovasz v-function      4 158 172 189
Lyapunov equation      116 131 250
Machine scheduling      8
Matrix, completely positive      189
Matrix, copositive      10 189
Matrix, diagonally dominant      232
Matrix, idempotent      177
Matrix, nonnegative      189
Matrix, positive semidefinite      2
Matrix, skew-symmetric      105
MAX-2-SAT      7
MAX-3-SAT      7
MAX-3-SAT, approximation guarantee for      228
MAX-BISECTION      7
MAX-CUT      5
MAX-k-CUT      169
MAX-k-SAT      212
Maximal complementarity of optimal solutions      34
Maximal complementarity of the limit point of the central path      48 49
Maximum satisfiability problem      7
Maximum stable set problem      188
Maximum stable set problem, reduction from SAT      212
Multinomial coefficient      197
Multinomial theorem      197
Mutilated chess board formula      219 222
N      50
Negation (of a logical variable)      211
Nesterov — Todd (NT) direction      116
Nesterov — Todd (NT) scaling      98
Non-defect edge      5
NP-complete      212
Optimal partition      35
Optimal solutions      22
Optimal solutions, uniqueness of      37 38
Optimal value of SDP problem      22
Optimality conditions      13 42 242
Optimality conditions for (P) and (D)      33
Optimality conditions for projected Newton direction      79
Optimization software      18
Optimization software, CPLEX      63
Optimization software, DSDP      93
Optimization software, MOSEK      63
Optimization software, SDTP3      15 131
Optimization software, SeDuMi      15 64 131 154
Optimization software, SP      146
Optimization software, XPRESSMP      63
Orthogonal projection      79
Orthogonality property      24 67
Outer iteration      92 124
Path-following method      13
Path-following method, primal      75
Path-following method, primal-dual      115
Pentagon, $v(\overline{G})$ -number of      161
Pentagon, approximations of the stability number of      200
Pentagon, Shannon capacity of      167
Perfect duality      25 73
Perfect graph      162
Petersen graph      169
Petersen graph, maximum stable set of      188
Pigeonhole formula      218 222
Plane search      135 136
Pointed cone      11
Polya's theorem      196
Positive semidefiniteness, characterizations of      229
Potential reduction method      16 133
Potential reduction method by Nesterov and Todd      142
Potential reduction method, general framework      134
Predictor-corrector method      15 115 146
Predictor-corrector method Mizuno — Todd — Ye type      126
Prepositional formula      212
Primal barrier function      42 76
Primal degeneracy      36
Primal-dual affine-scaling      100 109
Primal-dual barrier function      13 117 124
Primal-dual Dikin ellipsoid      99
Primal-dual Dikin-type direction      136
Primal-dual methods      13
Projected Newton direction      78 89
Quadratic approximation      149
Quadratic approximation, multivariate case      152
Quadratic approximation, univariate case      150
Quadratic assignment problem      8
Quadratic least squares      149
Quadratic Programming (QP)      3
Raleigh — Ritz theorem      230
Randomized algorithm      171 174
Randomized algorithm for MAX-k-CUT      175
Randomized algorithm for satisfiable instances of MAX-3-SAT      224
Randomized rounding      224
Randomized rounding for 2-clauses      227
Randomized rounding for 3-clauses      227
Regularization      29 73 261
Relative interior      239
Relative interior of the optimal set      34
Relative volume      228
Resolution      220
Robustness      11
Sandwich theorem      172
Satisfiability problem (SAT)      7 211
Scaled primal-dual direction      98
Scaling matrix      257
Schrijver's v-function      201
Schur complement      235
Schur complement theorem      216 235
SDP problems, complexity of      17
SDP problems, standard form      22
SDTP3      15 131
Search directions      67
Second order cone      3
Second order solution of centering system      130
SeDuMi      15 64 131 154
Self-concordant barrier      12
Self-dual      65 66
Self-dual embedding      16
Self-dual embedding, extended formulation      64
Self-dual embedding, search directions for      257
Semi-colouring      184
Semidefinite feasibility problem      18
Semidefinite feasibility problem, complexity of      18

1 2

О проекте