
Aspects of Semidefinite Programming
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
In this monograph the basic theory of interior point algorithms is explained. This includes the latest results on the properties of the central path as well as the analysis of the most important classes of algorithms. Several "classic" applications of semidefinite programming are also described in detail. These include the Lovász theta function and the MAX-CUT approximation algorithm by Goemans and Williamson.
Audience: Researchers or graduate students in optimization or related fields, who wish to learn more about the theory and applications of semidefinite programming.
More details
Other editions
Additional editions

Content
Preamble All convex optimization problems can in principle be restated as so-called conic linear programs (conic LP's for short); these are problems where the objective function is linear, and the feasible set is the intersection of an affine space with a convex cone. For conic LP's, all nonlinearity is therefore hidden in the definition of the convex cone. Conic LP's also have the strong duality property under a constraint qualification: if the affine space intersects the relative interior of the cone, it has a solvable dual with the same optimal value (if the dual problem is feasible).
A special subclass of conic LP's is formed if we consider cones which are selfdual. There are three such cones over the reals: the positive orthant in the Lorentz (or ice-cream or second order) cone, and the positive semidefinite cone. These cones respectively define the conic formulation of linear programming (LP) problems, second order cone (SOC) programming problems, and semidefinite programming (SDP) problems. The self-duality of these cones ensures a perfect symmetry between primal and dual problems, i.e. the primal and dual problem can be cast in exactly the same form. As discussed in Chapter 1, LP and SCO problems may be viewed as special cases of SDP.
Some fundamental theoretical properties of semidefinite programs (SDP's) will be reviewed in this chapter. We define the standard form for SDP's and derive the associated dual problem. The classical weak and strong duality theorems are proved to obtain necessary and sufficient optimality conditions for the standard form SDP. Subsequently we review the concepts of degeneracy and maximal complementarity of optimal solutions.
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.