Library of Congress |

Library of Congress

Matches in Library of Congress for { <http://lccn.loc.gov/2002071070> ?p ?o. }

Showing items 1 to 21 of 21 with 100 items per page.

2002071070 contributor B9241416.
2002071070 created "2002.".
2002071070 date "2002".
2002071070 date "2002.".
2002071070 dateCopyrighted "2002.".
2002071070 description "Includes bibliographical references and index.".
2002071070 description "Machine generated contents note: 1. INTRODUCTION -- 1.1 Problem statement -- 1.2 The importance of semidefinite programming -- 1.3 Special cases of semidefinite programming -- 1.4 Applications in combinatorial optimization -- 1.5 Applications in approximation theory -- 1.6 Engineering applications -- 1.7 Interior point methods -- 1.8 Other algorithms for SDP -- 1.9 The complexity of SDP -- 1.10 Review literature and internet resources -- Part I Theory and Algorithms -- 2. DUALITY, OPTIMALITY, AND DEGENERACY -- 2.1 Problems in standard form -- 2.2 Weak and strong duality -- 2.3 Feasibility issues -- 2.4 Optimality and complementarity -- 2.5 Degeneracy -- 3. THE CENTRAL PATH -- 3.1 Existence and uniqueness of the central path -- 3.2 Analyticity of the central path -- 3.3 Limit points of the central path -- 3.4 Convergence in the case of strict complementarity -- 3.5 Convergence proof in the absence of strict complementarity -- 3.6 Convergence rate of the central path -- 4. SELF-DUAL EMBEDDINGS -- 4.1 Introduction -- 4.2 The embedding strategy -- 4.3 Solving the embedding problem -- 4.4 Interpreting the solution of the embedding problem -- 4.5 Separating small and large variables -- 4.6 Remaining duality and feasibility issues -- 5. THE PRIMAL LOGARITHMIC BARRIER METHOD -- 5.1 Introduction -- 5.2 A centrality function -- 5.3 The projected Newton direction for the primal barrier functioi -- 5.4 The affine-scaling direction -- 5.5 Behaviour near the central path -- 5.6 Updating the centering parameter -- 5.7 Complexity analysis -- 5.8 The dual algorithm -- 5.9 Large update methods -- 5.10 The dual method and combinatorial relaxations -- 6. PRIMAL-DUAL AFFINE-SCALING METHODS -- 6.1 Introduction -- 6.2 The Nesterov-Todd (NT) scaling -- 6.3 The primal-dual affine-scaling and Dikin-type methods -- 6.4 Functions of centrality -- 6.5 Feasibility of the Dikin-type step -- 6.6 Complexity analysis for the Dikin-type method -- 6.7 Analysis of the primal-dual affine-scaling method -- 7. PRIMAL-DUAL PATH-FOLLOWING METHODS -- 7.1 The path-following approach -- 7.2 Feasibility of the full NT step -- 7.3 Quadratic convergence to the central path -- 7.4 Updating the barrier parameter p -- 7.5 A long step path-following method -- 7.6 Predictor-corrector methods -- 8. PRIMAL-DUAL POTENTIAL REDUCTION METHODS -- 8.1 Introduction -- 8.2 Determining step lengths via plane searches of the potential -- 8.3 The centrality function I -- 8.4 Complexity analysis in a potential reduction framework -- 8.5 A bound on the potential reduction -- 8.6 The potential reduction method of Nesterov and Todd -- Part II Selected Applications -- 9. CONVEX QUADRATIC APPROXIMATION -- 9.1 Preliminaries -- 9.2 Quadratic approximation in the univariate case -- 9.3 Quadratic approximation for the multivariate case -- 10. THE LOVASZ 0-FUNCTION -- 10.1 Introduction -- 10.2 The sandwich theorem -- 10.3 Other formulations of the 0-function -- 10.4 The Shannon capacity of a graph -- 11. GRAPH COLOURING AND THE MAX-K-CUT PROBLEM -- 11.1 Introduction -- 11.2 The 0-approximation of the chromatic number -- 11.3 An upper bound for the optimal value of MAX-k-CUT -- 11.4 Approximation guarantees -- 11.5 A randomized MAX-k-CUT algorithm -- 11.6 Analysis of the algorithm -- 11.7 Approximation results for MAX-k-CUT -- 11.8 Approximate colouring of n-colourable graphs -- 12. THE STABILITY NUMBER OF A GRAPH -- 12.1 Preliminaries -- 12.2 The stability number via copositive programming -- 12.3 Approximations of the copositive cone -- 12.4 Application to the maximum stable set problem -- 12.5 The strength of low-order approximations -- 12.6 Related literature -- 12.7 Extensions: standard quadratic optimization -- 13. THE SATISFIABILITY PROBLEM -- 13.1 Introduction -- 13.2 Boolean quadratic representations of clauses -- 13.3 From Boolean quadratic inequality to SDP -- 13.4 Detecting unsatisfiability of some classes of formulae -- 13.5 Rounding procedures -- 13.6 Approximation guarantees for the rounding schemes -- Appendices -- A- Properties of positive (semi)definite matrices -- A.1 Characterizations of positive (semi)definiteness -- A.2 Spectral properties -- A.3 The trace operator and the Frobenius norm -- A.3 The trace operator and the Frobenius norm -- A.4 The Lowner partial order and the Schur complement theorem -- B- Background material on convex optimization -- B.1 Convex analysis -- B.2 Duality in convex optimization -- B.3 The KKT optimality conditions -- C- The function log det(X) -- D- Real analytic functions -- E- The (symmetric) Kronecker product -- E.1 The Kronecker product -- E.2 The symmetric Kronecker product -- F- Search directions for the embedding problem -- G- Regularized duals -- References -- Index.".
2002071070 extent "xvi, 283 p. :".
2002071070 identifier "1402005474 (alk. paper)".
2002071070 identifier 2002071070-d.html.
2002071070 identifier 2002071070.html.
2002071070 isPartOf "Applied optimization ; v. 65".
2002071070 issued "2002".
2002071070 issued "2002.".
2002071070 language "eng".
2002071070 publisher "Dordrecht ; Boston : Kluwer Academic Publishers,".
2002071070 subject "519.7/2 21".
2002071070 subject "T57.74 .K59 2002".
2002071070 tableOfContents "Machine generated contents note: 1. INTRODUCTION -- 1.1 Problem statement -- 1.2 The importance of semidefinite programming -- 1.3 Special cases of semidefinite programming -- 1.4 Applications in combinatorial optimization -- 1.5 Applications in approximation theory -- 1.6 Engineering applications -- 1.7 Interior point methods -- 1.8 Other algorithms for SDP -- 1.9 The complexity of SDP -- 1.10 Review literature and internet resources -- Part I Theory and Algorithms -- 2. DUALITY, OPTIMALITY, AND DEGENERACY -- 2.1 Problems in standard form -- 2.2 Weak and strong duality -- 2.3 Feasibility issues -- 2.4 Optimality and complementarity -- 2.5 Degeneracy -- 3. THE CENTRAL PATH -- 3.1 Existence and uniqueness of the central path -- 3.2 Analyticity of the central path -- 3.3 Limit points of the central path -- 3.4 Convergence in the case of strict complementarity -- 3.5 Convergence proof in the absence of strict complementarity -- 3.6 Convergence rate of the central path -- 4. SELF-DUAL EMBEDDINGS -- 4.1 Introduction -- 4.2 The embedding strategy -- 4.3 Solving the embedding problem -- 4.4 Interpreting the solution of the embedding problem -- 4.5 Separating small and large variables -- 4.6 Remaining duality and feasibility issues -- 5. THE PRIMAL LOGARITHMIC BARRIER METHOD -- 5.1 Introduction -- 5.2 A centrality function -- 5.3 The projected Newton direction for the primal barrier functioi -- 5.4 The affine-scaling direction -- 5.5 Behaviour near the central path -- 5.6 Updating the centering parameter -- 5.7 Complexity analysis -- 5.8 The dual algorithm -- 5.9 Large update methods -- 5.10 The dual method and combinatorial relaxations -- 6. PRIMAL-DUAL AFFINE-SCALING METHODS -- 6.1 Introduction -- 6.2 The Nesterov-Todd (NT) scaling -- 6.3 The primal-dual affine-scaling and Dikin-type methods -- 6.4 Functions of centrality -- 6.5 Feasibility of the Dikin-type step -- 6.6 Complexity analysis for the Dikin-type method -- 6.7 Analysis of the primal-dual affine-scaling method -- 7. PRIMAL-DUAL PATH-FOLLOWING METHODS -- 7.1 The path-following approach -- 7.2 Feasibility of the full NT step -- 7.3 Quadratic convergence to the central path -- 7.4 Updating the barrier parameter p -- 7.5 A long step path-following method -- 7.6 Predictor-corrector methods -- 8. PRIMAL-DUAL POTENTIAL REDUCTION METHODS -- 8.1 Introduction -- 8.2 Determining step lengths via plane searches of the potential -- 8.3 The centrality function I -- 8.4 Complexity analysis in a potential reduction framework -- 8.5 A bound on the potential reduction -- 8.6 The potential reduction method of Nesterov and Todd -- Part II Selected Applications -- 9. CONVEX QUADRATIC APPROXIMATION -- 9.1 Preliminaries -- 9.2 Quadratic approximation in the univariate case -- 9.3 Quadratic approximation for the multivariate case -- 10. THE LOVASZ 0-FUNCTION -- 10.1 Introduction -- 10.2 The sandwich theorem -- 10.3 Other formulations of the 0-function -- 10.4 The Shannon capacity of a graph -- 11. GRAPH COLOURING AND THE MAX-K-CUT PROBLEM -- 11.1 Introduction -- 11.2 The 0-approximation of the chromatic number -- 11.3 An upper bound for the optimal value of MAX-k-CUT -- 11.4 Approximation guarantees -- 11.5 A randomized MAX-k-CUT algorithm -- 11.6 Analysis of the algorithm -- 11.7 Approximation results for MAX-k-CUT -- 11.8 Approximate colouring of n-colourable graphs -- 12. THE STABILITY NUMBER OF A GRAPH -- 12.1 Preliminaries -- 12.2 The stability number via copositive programming -- 12.3 Approximations of the copositive cone -- 12.4 Application to the maximum stable set problem -- 12.5 The strength of low-order approximations -- 12.6 Related literature -- 12.7 Extensions: standard quadratic optimization -- 13. THE SATISFIABILITY PROBLEM -- 13.1 Introduction -- 13.2 Boolean quadratic representations of clauses -- 13.3 From Boolean quadratic inequality to SDP -- 13.4 Detecting unsatisfiability of some classes of formulae -- 13.5 Rounding procedures -- 13.6 Approximation guarantees for the rounding schemes -- Appendices -- A- Properties of positive (semi)definite matrices -- A.1 Characterizations of positive (semi)definiteness -- A.2 Spectral properties -- A.3 The trace operator and the Frobenius norm -- A.3 The trace operator and the Frobenius norm -- A.4 The Lowner partial order and the Schur complement theorem -- B- Background material on convex optimization -- B.1 Convex analysis -- B.2 Duality in convex optimization -- B.3 The KKT optimality conditions -- C- The function log det(X) -- D- Real analytic functions -- E- The (symmetric) Kronecker product -- E.1 The Kronecker product -- E.2 The symmetric Kronecker product -- F- Search directions for the embedding problem -- G- Regularized duals -- References -- Index.".
2002071070 title "Aspects of semidefinite programming : interior point algorithms and selected applications / by Etienne de Klerk.".
2002071070 type "text".