Interior point polynomial time methods in convex programming.. lecture notes

✍ Scribed by Nemirovski A.

• Publisher: Technion
• Year: 1996
• Tongue: English
• Leaves: 299
• Category: Library

✦ Table of Contents

Introduction to the Course
Some history
The goal: poynomial time methods
The path-following scheme
What is inside: self-concordance
Structure of the course
Self-concordant functions
Examples and elementary combination rules
Properties of self-concordant functions
Exercises: Around Symmetric Forms
Self-concordant barriers
Definition, examples and combination rules
Properties of self-concordant barriers
Exercises: Self-concordant barriers
Basic path-following method
Situation
F-generated path-following method
Basic path-following scheme
Convergence and complexity
Initialization and two-phase path-following method
Concluding remarks
Exercises: Basic path-following method
Conic problems and Conic Duality
Conic problems
Conic duality
Fenchel dual to (P)
Duality relations
Logarithmically homogeneous barriers
Exercises: Conic problems
Basic properties of cones
More on conic duality
Complementary slackness: what it means?
Conic duality: equivalent form
Exercises: Truss Topology Design via Conic duality
The method of Karmarkar
Problem setting and assumptions
Homogeneous form of the problem
The Karmarkar potential function
The Karmarkar updating scheme
Overall complexity of the method
How to implement the method of Karmarkar
Exercises on the method of Karmarkar
The Primal-Dual potential reduction method
The idea
Primal-dual potential
The primal-dual updating
Overall complexity analysis
Large step strategy
Exercises: Primal-Dual method
Example: Lyapunov Stability Analysis
Long-Step Path-Following Methods
The predictor-corrector scheme
Dual bounds and Dual search line
Acceptable steps
Summary
Exercises: Long-Step Path-Following methods
How to construct self-concordant barriers
Appropriate mappings and Main Theorem
Barriers for epigraphs of functions of one variable
Fractional-Quadratic Substitution
Proof of Theorem 10.1
Proof of Proposition 10.1
Exercises on constructing self-concordant barriers
Epigraphs of functions of Euclidean norm
How to guess that -lnDetx is a self-concordant barrier
"Fractional-quadratic" cone and Truss Topology Design
Geometrical mean
Applications in Convex Programming
Linear Programming
Quadratically Constrained Quadratic Programming
Approximation in Lp norm
Geometrical Programming
Exercises on applications of interior point methods
(Inner) and (Outer) as convex programs
Problem (Inner), polyhedral case
Problem (Outer), polyhedral case
Problem (Outer), ellipsoidal case
Semidefinite Programming
A Semidefinite program
Semidefinite Programming: examples
Linear Programming
Quadratically Constrained Quadratic Programming
Minimization of Largest Eigenvalue and Lovasz Capacity of a graph
Dual bounds in Boolean Programming
Problems arising in Control
Interior point methods for Semidefinite Programming
Exercises on Semidefinite Programming
Sums of eigenvalues and singular values
Hints to exercises
Solutions to exercises
Appendix I: Surface-Following Interior Point methods
Introduction
Surfaces of analytic centers: preliminaries
Self-concordant functions and barriers
Surface of analytic centers
Tracing surfaces of analytic centers: motivation
The surface-following'' scheme Surface of analytic centers: general definition Tracing a surface of analytic centers: basic scheme Dual bounds Basic assumption Dual bounds Dual search line Main results on tracing a surface Acceptable stepsizes Centering property Solving convex programs via tracing surfaces Assumption on the structure of F Preliminary remarks How to trace S3(c,f,d) Application examples Combination rulesBuilding blocks''
Appendix II: Robust Truss Topology Design
Introduction
Truss Topology Design with Robustness Constraints
Trusses, loads, compliances
Robustness constraint: Motivation
Selection of scale matrix Q
Semidefinite reformulation of (TDrobust)
Deriving a dual problem to (TDsd)
A simplification of the dual problem (D)
Recovering the bar volumes
A dual problem to (TDfn)
Solving (TDfn)and (TDfn*)via interior point methods
Numerical Examples
Concluding remarks
Appendix III: Minicourse on Polynomial Time Optimization Algorithms
Polynomial methods in Convex Programming: what is it?
The concept
Algorithms polynomial modulo oracle
Interior point polynomial methods: introduction
Self-concordance-based approach
Preliminaries: Newton method and self-concordance
First fruits: the method of Karmarkar
Path-following interior point methods
The standard path-following scheme
Surface-following scheme
Applications
Linear Programming
Quadratically Constrained Convex Quadratic Programming
Semidefinite Programming
Geometric Programming
Approximation in