Introduction to Linear Optimization

✍ Scribed by Arkadi Nemirovski

• Publisher: World Scientific Pub Co Inc
• Year: 2024
• Tongue: English
• Leaves: 649
• Category: Library

✦ Synopsis

The book presents a graduate level, rigorous, and self-contained introduction to linear optimization (LO), the presented topics being

1. expressive abilities of LO;
2. geometry of LO - structure of polyhedral sets, LO duality and its applications;
3. traditional LO algorithms - primal and dual simplex methods, and network simplex method;
4. polynomial time solvability of LO via ellipsoid algorithm;
5. conic programming with emphasis on expressing abilities of second order and semidefinite optimization, and polynomial time primal-dual interior point algorithms for linear and semidefinite optimization.

✦ Table of Contents

Contents
Preface
About the Author
Main Notational Conventions
1. Introduction to LO: Examples of LO Models
1.1 LO program: Definition
1.1.1 An LO program
1.1.2 LO terminology
1.2 Examples of LO models
1.2.1 Examples of LO models in Operations Research
1.2.1.1 Diet problem
1.2.1.2 Production planning
1.2.1.3 Inventory
1.2.1.4 Transportation and network flows
1.2.2 Engineering examples
1.2.2.1 Fitting parameters in linear regression models
1.2.2.2 Sparsity-oriented signal processing and ℓ1 minimization
1.2.2.3 ∗How good is ℓ1 minimization in the compressed sensing context?
1.2.2.4 ∗Supervised binary machine learning via LP support vector machines
1.3 What can be reduced to LO?
1.3.1 Preliminaries
1.3.2 Polyhedral representations of sets and functions: Definitions and Fourier–Motzkin elimination
1.3.2.1 Fourier–Motzkin elimination
1.3.3 Polyhedral representations of sets and functions: Calculus
1.4 ∗Fast polyhedral approximation of the second-order cone
1.5 Exercises
Part I Geometry of Linear Optimization
2. Polyhedral Sets and their Geometry
2.1 Preliminaries: Linear and affine subspaces, convexity
2.1.1 Linear subspaces
2.1.1.1 Linear subspaces: Definition and examples
2.1.1.2 Calculus of linear subspaces
2.1.1.3 Linear subspaces: Linear span, dimension, linear independence, bases
2.1.1.4 “Inner” and “outer” description of a linear subspace
2.1.2 Affine subspaces
2.1.2.1 Affine subspace: Definition and examples
2.1.2.2 Calculus of affine subspaces
2.1.2.3 Affine subspaces: Affine span, affine dimension, affine independence, affine bases
2.1.2.4 “Inner” and “outer” description of an affine subspace
2.1.3 Convexity
2.1.3.1 Calculus of convex sets and functions
2.1.3.2 Convex combinations and convex hull, dimension
2.1.3.3 Relative interior
2.1.3.4 “Inner” and “outer” representations of convex sets
2.1.4 Cones
2.2 Preparing tools
2.2.1 Caratheodory theorem
2.2.1.1 Caratheodory theorem in conic form and Shapley–Folkman Theorem
2.2.2 Radon Theorem
2.2.3 Helly Theorem
2.2.4 Homogeneous Farkas Lemma
2.3 Faces, vertices, recessive directions, extreme rays
2.3.1 Faces
2.3.2 Vertices, a.k.a. extreme points
2.3.2.1 Definition and characterization
2.3.2.2 Example: Extreme points of the intersection of || · ||∞- and || · ||1 balls
2.3.2.3 Example: Extreme points of the set of double stochastic matrices
2.3.3 Recessive directions
2.3.3.1 Definition and characterization
2.3.3.2 Recessive subspace and decomposition
2.3.4 Bases and extreme rays of a polyhedral cone
2.4 Structure of polyhedral sets
2.4.1 First step
2.4.1.1 Immediate corollaries
2.4.1.2 Minimality of the representation stated in Theorem 2.12
2.4.2 Second step
2.4.2.1 Separation theorem for convex sets
2.4.3 Immediate corollaries
2.4.4 ∗Extending calculus of polyhedral representability
2.4.4.1 ∗Polyhedral representation of recessive cone
2.4.4.2 ∗Polyhedral representation of perspective transform
2.4.4.3 ∗When is the convex hull of finite union of polyhedral sets polyhedral?
2.5 Exercises
3. Theory of Systems of Linear Inequalities and Duality
3.1 General theorem on alternative
3.1.1 GTA: Formulation, proof, different versions
3.1.1.1 Corollaries of GTA
3.1.2 Answering questions
3.1.3 Certificates in linear optimization
3.1.3.1 Certifying feasibility/infeasibility
3.1.3.2 Certifying boundedness/unboundness
3.1.3.3 Certifying solvability/insolvability
3.1.3.4 Certifying optimality/nonoptimality
3.1.3.5 A corollary: Faces of a polyhedral set revisited
3.2 LO duality
3.2.1 The dual of an LO program
3.2.2 Linear programming duality theorem
3.3 Immediate applications of duality
3.3.1 Optimality conditions in LO
3.3.2 Geometry of a primal–dual pair of LO programs
3.3.3 Antagonistic bilinear games
3.3.3.1 Games: Preliminaries
3.3.3.2 Saddle points in bilinear polyhedral games
3.3.4 ∗Extending calculus of polyhedral representability
3.3.4.1 ∗Polyhedral representability of Legendre transform
3.3.4.2 ∗Support functions of polyhedral sets
3.3.5 Polyhedral representability of the cost function of an LO program, a.k.a. sensitivity analysis
3.3.5.1 Opt(c, b) as a function of b
3.3.5.2 Law of diminishing marginal returns
3.3.5.3 Opt(c, b) as a function of c
3.3.6 Applications in robust LO
3.3.6.1 Data uncertainty in LO: Sources
3.3.6.2 Data uncertainty: Dangers
3.3.6.3 Uncertain linear problems and their robust counterparts
3.3.6.4 Robust counterpart of uncertain LO
3.3.6.5 Tractability of the RC
3.3.7 ∗Application: Synthesis of linear controllers
3.3.7.1 ∗Discrete time linear dynamical systems
3.3.7.2 ∗Affine control
3.3.7.3 ∗Design specifications and the analysis problem
3.3.7.4 ∗Synthesis problem
3.3.7.5 ∗Purified outputs and purified-output-based control laws
3.3.7.6 ∗Tractability of the synthesis problem
3.3.7.7 ∗Clearing debts: Justification of Proposition 3.9
3.3.8 ∗Extending calculus of polyhedral representability: Majorization
3.3.8.1 ∗Preliminaries
3.3.8.2 ∗Majorization
3.3.8.3 ∗Majorization principle
3.4 Exercises
Part II Classical Algorithms of Linear Optimization: The Simplex Method
4. Simplex Method
4.1 Simplex method: Preliminaries
4.2 Geometry of an LO program in the standard form
4.2.1 The dual of an LO program in the standard form
4.2.2 Bases and basic feasible solutions
4.3 Simplex method
4.3.1 Primal simplex method
4.3.2 Tableau implementation and example
4.3.3 Preventing cycling
4.3.4 How to start the PSM
4.3.5 Dual simplex method
4.3.5.1 A step of the dual Simplex method
4.3.5.2 Dual Simplex method: Convergence
4.3.6 Warm start
4.3.6.1 New variable is added
4.3.6.2 Changes in the cost vector c
4.3.6.3 Changes in the right-hand side vector b
4.3.6.4 Change in a nonbasic column of A
4.3.6.5 New equality constraint is added to the primal problem
4.4 Exercises
5. The Network Simplex Algorithm
5.1 Preliminaries on graphs
5.1.1 Undirected graphs
5.1.2 Directed graphs
5.2 The network flow problem
5.3 The network simplex algorithm
5.3.1 Preliminaries
5.3.2 Bases and basic feasible solutions
5.3.2.1 Basic solutions are tree solutions
5.3.3 Reduced costs
5.3.4 Updating basic feasible solution
5.3.5 Network simplex algorithm: Summary and remarks
5.4 Capacitated network flow problem
5.4.1 Preliminaries: Primal Simplex method with bounds on variables
5.4.1.1 Bases and basic solutions to (5.7)
5.4.1.2 Reduced costs
5.4.1.3 A step of the algorithm
5.4.2 Network PSM for capacitated network flow problem
5.5 Exercises
Part III Complexity of Linear Optimization and the Ellipsoid Method
6. Polynomial Time Solvability of Linear Optimization
6.1 Complexity of LO: Posing the question
6.1.1 Models of computations
6.1.2 Complexity status of the Simplex method
6.1.3 ∗Classes P and NP
6.2 The Ellipsoid Algorithm
6.2.1 Problem and assumptions
6.2.2 The Ellipsoid Algorithm
6.3 Polynomial solvability of LO with rational data
6.4 The Ellipsoid Algorithm and computations
6.4.1 Illustration: Cutting stock problem
Part IV Conic Programming and Interior Point Methods
7. Conic Programming
7.1 Conic programming: Preliminaries
7.1.1 Euclidean spaces
7.1.1.1 Linear forms on Euclidean spaces
7.1.1.2 Conjugate mapping
7.1.2 Cones in Euclidean spaces
7.2 Conic problems
7.2.1 Relations between LO, CQO and SDO
7.3 Conic duality
7.3.1 Conic duality: Derivation
7.3.2 Conic duality theorem
7.3.2.1 Refinement
7.3.3 Consequences of conic duality theorem
7.3.3.1 Optimality conditions in conic programming
7.3.3.2 A surrogate of GTA
7.3.4 Sensitivity analysis
7.3.4.1 The cost function as a function of c
7.3.4.2 The cost function as a function of (b, r)
7.3.5 Geometry of primal–dual pair of conic problems
7.4 Conic representations of sets and functions
7.4.1 Calculus of K-representability: Calculus rules
7.4.2 Calculus of K-representability: Expressive abilities of CQO and SDO
7.5 Exercise for Chapters 6, 7
8. Interior Point Methods for LO and Semidefinite Optimization
8.1 SDO program and its dual
8.1.1 The problem dual to (P)
8.1.2 Geometric form of the primal–dual pair (P), (D)
8.2 Path-following interior point methods for (P), (D): Preliminaries
8.2.1 Log-det barrier
8.2.2 Path-following scheme: The idea
8.3 Path-following interior point methods for (P), (D): Constructions & results
8.3.1 Central path: Existence and characterization
8.3.1.1 Duality gap along the primal–dual central path and around it
8.3.2 Conceptual path-following scheme
8.3.2.1 Primal path-following method
8.3.3 Primal–dual path-following methods
8.3.3.1 Monteiro–Zhang’s family of path-following IPMs
8.3.3.2 Primal–dual short-step path-following methods based on commutative scalings
8.3.3.3 ∗Proof of Theorem 8.2
8.4 How to start path-tracing
8.4.1 Tracing auxiliary path
8.4.2 ∗∗Infeasible start path-following method
Appendix A Prerequisites from Linear Algebra
A.1 Space Rn: Algebraic structure
A.1.1 A point in Rn
A.1.2 Linear operations
A.1.2 Linear operations
A.1.3 Linear subspaces
A.1.4 Linear independence, bases, dimensions
A.1.5 Linear mappings and matrices
A.1.6 Determinant and rank
A.1.6.1 Determinant
A.1.6.2 Rank
A.2 Space Rn: Euclidean structure
A.2.1 Euclidean structure
A.2.2 Inner product representation of linear forms on Rn
A.2.3 Orthogonal complement
A.2.4 Orthonormal bases
A.3 Affine subspaces in Rn
A.3.1 Affine subspaces and affine hulls
A.3.2 Intersections of affine subspaces, affine combinations and affine hulls
A.3.3 Affinely spanning sets, affinely independent sets, affine dimension
A.3.4 Dual description of linear subspaces and affine subspaces
A.3.4.1 Affine subspaces and systems of linear equations
A.3.5 Structure of the simplest affine subspaces
Appendix B Prerequisites from Real Analysis
B.1 Space Rn: Metric structure and topology
B.1.1 Euclidean norm and distances
B.1.2 Convergence
B.1.3 Closed and open sets
B.1.4 Local compactness of Rn
B.2 Continuous functions on Rn
B.2.1 Continuity of a function
B.2.2 Elementary continuity-preserving operations
B.2.3 Basic properties of continuous functions on Rn
B.3 Differentiable functions on Rn
B.3.1 The derivative
B.3.2 Derivative and directional derivatives
B.3.3 Representations of the derivative
B.3.4 Existence of the derivative
B.3.5 Calculus of derivatives
B.3.6 Computing the derivative
B.3.7 Higher-order derivatives
B.3.8 Calculus of Ck mappings
B.3.9 Examples of higher-order derivatives
B.3.10 Taylor expansion
Appendix C Symmetric Matrices
C.1 Spaces of matrices
C.2 Eigenvalue decomposition
C.3 Variational characterization of eigenvalues
C.3.1 Corollaries of the VCE
C.4 Positive semidefinite matrices and semidefinite cone
Bibliography
Solutions to Selected Exercises
Index