**Fields Institute Communications**

Volume: 18;
1998;
250 pp;
Hardcover

MSC: Primary 68; 90;

Print ISBN: 978-0-8218-0825-2

Product Code: FIC/18

List Price: $89.00

Individual Member Price: $71.20

**Electronic ISBN: 978-1-4704-2986-7
Product Code: FIC/18.E**

List Price: $89.00

Individual Member Price: $71.20

# Topics in Semidefinite and Interior-Point Methods

Share this page *Edited by *
*Panos M. Pardalos; Henry Wolkowicz*

A co-publication of the AMS and Fields Institute

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

#### Table of Contents

# Table of Contents

## Topics in Semidefinite and Interior-Point Methods

- Cover Cover11
- Title page iii4
- Contents v6
- Preface vii8
- Optimality conditions and sensitivity analysis of cone-constrained and semi-definite programs 122
- Testing the feasibility of semidefinite programs 1738
- Polyhedra, spectrahedra, and semidefinite programming 2748
- Infinite-dimensional semidefinite programming: Regularized determinants and self-concordant barriers 3960
- A tour d’horizon on positive semidefinite and Euclidean distance matrix completion problems 5172
- Semidefinite programming and graph equipartition 7798
- The totally nonnegative completion problem 97118
- The multi-SAT algorithm 109130
- How efficiently can we maximize threshold pseudo-Boolean functions? 127148
- Faster algorithm for shortest network under given topology 137158
- Bayesian heuristic approach (BHA) and applications to discrete optimization 153174
- Approximation clustering: A mine of semidefinite programming problems 167188
- A long-step path following algorithm for semidefinite programming problems 181202
- Cutting plane algorithms for semidefinite relaxations 197218
- Infeasible-start semidefinite programming algorithms via self-dual embeddings 215236
- Solution of the trust region problem via a smooth unconstrained reformulation 237258
- Back Cover Back Cover1272

#### Readership

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