Interior point polynomial time methods in convex programming

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 rules ``Building 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