New Titles  |  FAQ  |  Keep Informed  |  Review Cart  |  Contact Us Quick Search (Advanced Search ) Browse by Subject General Interest Logic & Foundations Number Theory Algebra & Algebraic Geometry Discrete Math & Combinatorics Analysis Differential Equations Geometry & Topology Probability & Statistics Applications Mathematical Physics Math Education

Topics in Semidefinite and Interior-Point Methods
Edited by: Panos M. Pardalos, University of Florida, Gainesville, FL, and Henry Wolkowicz, University of Waterloo, ON, Canada
A co-publication of the AMS and Fields Institute.
 SEARCH THIS BOOK:
Fields Institute Communications
1998; 250 pp; hardcover
Volume: 18
ISBN-10: 0-8218-0825-7
ISBN-13: 978-0-8218-0825-2
List Price: US$84 Member Price: US$67.20
Order Code: FIC/18

This volume contains refereed papers presented at the workshop on "Semidefinite Programming and Interior-Point Approaches for Combinatorial Optimization Problems" held at The Fields Institute in May 1996. Semidefinite programming (SDP) is a generalization of linear programming (LP) in that the nonnegativity constraints on the variables are replaced by a positive semidefinite constraint on matrix variables. Many of the elegant theoretical properties and powerful solution techniques follow through from LP to SDP. In particular, the primal-dual interior-point methods, which are currently so successful for LP, can be used to efficiently solve SDP problems.

In addition to the interesting theoretical and algorithmic questions, SDP has found many important applications in combinatorial optimization, control theory and other areas of mathematical programming. SDP is currently a very hot area of research. The papers in this volume cover a wide spectrum of recent developments in SDP. The volume would be suitable as a textbook for advanced courses in optimization.

Titles in this series are co-published with the Fields Institute for Research in Mathematical Sciences (Toronto, Ontario, Canada).

Graduate students and researchers in mathematics, computer science, engineering and operations.

Theory
• A. Shapiro -- Optimality conditions and sensitivity analysis of cone-constrained and semi-definite programs
• L. Porkolab and L. Khachiyan -- Testing the feasibility of semidefinite programs
• M. V. Ramana -- Polyhedra, spectrahedra, and semidefinite programming
• L. Faybusovich -- Infinite-dimensional semidefinite programming: Regularized determinants and self-concordant barriers
Applications
• M. Laurent -- A tour d'horizon on positive semidefinite and Euclidean distance matrix completion problems
• S. E. Karisch and F. Rendl -- Semidefinite programming and graph equipartition
• C. R. Johnson, B. K. Kroschel, and M. Lundquist -- The totally nonnegative completion problem
• J. Gu -- The multi-SAT algorithm
• M. R. Emamy-K. -- How efficiently can we maximize threshold pseudo-Boolean functions?
• G. Xue, D.-Z. Du, and F. K. Hwang -- Faster algorithm for shortest network under given topology
• A. Mockus, J. Mockus, and L. Mockus -- Bayesian heuristic approach (BHA) and applications to discrete optimization
• B. Mirkin -- Approximation clustering: A mine of semidefinite programming problems
Algorithms
• K. M. Anstreicher and M. Fampa -- A long-step path following algorithm for semidefinite programming problems
• C. Helmberg and R. Weismantel -- Cutting plane algorithms for semidefinite relaxations
• E. De Klerk, C. Roos, and T. Terlaky -- Infeasible-start semidefinite programming algorithms via self-dual embeddings
• S. Lucidi and L. Palagi -- Solution of the trust region problem via a smooth unconstrained reformulation