[Lecture notes] Optimization III. Convex Analysis, Nonlinear Programming Theory, Standard Nonlinear Programming Algorithms

Convex sets in Rn Definition and basic properties A convex set Examples of convex sets Affine subspaces and polyhedral sets Unit balls of norms Ellipsoids Neighbourhood of a convex set Inner description of convex sets: Convex combinations and convex hull Convex combinations Convex hull Simplex Cones Calculus of convex sets Topological properties of convex sets The closure The interior The relative interior Nice topological properties of convex sets Main theorems on convex sets Caratheodory Theorem Radon Theorem Helley Theorem Polyhedral representations and Fourier-Motzkin Elimination Polyhedral representations Every polyhedrally representable set is polyhedral! (Fourier-Motzkin elimination) Some applications Calculus of polyhedral representations General Theorem on Alternative and Linear Programming Duality Homogeneous Farkas Lemma General Theorem on Alternative Application: Linear Programming Duality Separation Theorem Separation: definition Separation Theorem Supporting hyperplanes Polar of a convex set and Dubovitski-Milutin Lemma Polar of a convex set Dual cone Dubovitski-Milutin Lemma Extreme points and Krein-Milman Theorem Extreme points: definition Krein-Milman Theorem Example: Extreme points of a polyhedral set. Structure of polyhedral sets Main result Theory of Linear Programming Structure of a polyhedral set: proofs Convex functions Convex functions: first acquaintance Definition and Examples Elementary properties of convex functions Jensen's inequality Convexity of level sets of a convex function What is the value of a convex function outside its domain? How to detect convexity Operations preserving convexity of functions Differential criteria of convexity Gradient inequality Boundedness and Lipschitz continuity of a convex function Maxima and minima of convex functions Subgradients and Legendre transformation Proper functions and their representation Subgradients Legendre transformation Convex Programming, Lagrange Duality, Saddle Points Mathematical Programming Program Convex Programming program and Lagrange Duality Theorem Convex Theorem on Alternative Cone constrained case Lagrange Function and Lagrange Duality Lagrange function Convex Programming Duality Theorem Dual program Cone constrained forms of Lagrange Function, Lagrange Duality, and Convex Programming Duality Theorem Conic Programming and Conic Duality Theorem Optimality Conditions in Convex Programming Saddle point form of optimality conditions Karush-Kuhn-Tucker form of optimality conditions Optimality conditions in Conic Programming Duality in Linear and Convex Quadratic Programming Linear Programming Duality Quadratic Programming Duality Saddle Points Definition and Game Theory interpretation Existence of Saddle Points Optimality Conditions First Order Optimality Conditions Second Order Optimality Conditions Nondegenerate solutions and Sensitivity Analysis Concluding Remarks Optimization Methods: Introduction Preliminaries on Optimization Methods Classification of Nonlinear Optimization Problems and Methods Iterative nature of optimization methods Convergence of Optimization Methods Rates of convergence Global and Local solutions Line Search Zero-Order Line Search Fibonacci search Golden search Bisection Curve fitting Newton's method Regula Falsi (False Position) method Cubic fit Safeguarded curve fitting Inexact Line Search Armijo's rule Goldstein test Gradient Descent and Newton Methods Gradient Descent The idea Standard implementations Convergence of the Gradient Descent General Convergence Theorem Limiting points of Gradient Descent Rates of convergence Rate of global convergence: general C1,1 case Rate of global convergence: convex C1,1 case Rate of convergence in the quadratic case Conclusions Basic Newton's Method The Method Incorporating line search The Newton Method: how good it is? Newton Method and Self-Concordant Functions Preliminaries Self-concordance Self-concordant functions and the Newton method Self-concordant functions: applications Around the Newton Method Newton Method with Cubic Regularization Implementing the algorithm Modified Newton methods Variable Metric Methods Global convergence of a Variable Metric method Implementations of the Modified Newton method Modifications based on Spectral Decomposition Levenberg-Marquardt Modification Choleski Factorization Conjugate Gradient Methods Conjugate Gradient Method: Quadratic Case CG: Initial description Iterative representation of the Conjugate Gradient method CG and Three-Diagonal representation of a Symmetric matrix Rate of convergence of the Conjugate Gradient method Conjugate Gradient algorithm for quadratic minimization: advantages and disadvantages Extensions to non-quadratic problems Global and local convergence of Conjugate Gradient methods in nonquadratic case Quasi-Newton Methods The idea The Generic Quasi-Newton Scheme Implementations Davidon-Fletcher-Powell method The Broyden family Convergence of Quasi-Newton methods Global convergence Local convergence Appendix: derivation of the BFGS updating formula Convex Programming Preliminaries Subgradients of convex functions Separating planes The Ellipsoid Method The idea The Center-of-Gravity method From Center-of-Gravity to the Ellipsoid method The Algorithm How to represent an ellipsoid The Ellipsoid algorithm The Ellipsoid algorithm: rate of convergence Ellipsoid method for problems with functional constraints Ellipsoid method and Complexity of Convex Programming Complexity: what is it? Computational Tractability = Polynomial Solvability R-Polynomial Solvability of Convex Programming Polynomial solvability of Linear Programming Polynomial Solvability of Linear Programming over Rationals Some History Khachiyan's Theorem Step 1: from Optimization to Feasibility Step 2: from Feasibility to Solvability From Solvability back to Feasibility More History Active Set and Penalty/Barrier Methods Primal methods Methods of Feasible Directions Active Set Methods Active Set scheme: the idea Active Set scheme: implementation Active Set Scheme: convergence Standard applications: Linear and Quadratic Programming Penalty and Barrier Methods The idea Penalty methods Convergence Properties of the path x*() Barrier methods Self-concordant barriers and path-following scheme Path-following scheme Applications Concluding remarks Augmented Lagrangians Main ingredients Local Lagrange Duality ``Penalty cocknification'' Putting things together: Augmented Lagrangian Scheme Solving auxiliary primal problems (P) Solving the dual problem Dual rate of convergence Adjusting penalty parameter Incorporating Inequality Constraints Convex case: Augmented Lagrangians; Decomposition Augmented Lagrangians Lagrange Duality and Decomposition Sequential Quadratic Programming SQP methods: Equality Constrained case Newton method for systems of equations The method Local quadratic convergence Solving (KKT) by the Newton method Nonsingularity of KKT points Structure and interpretation of the Newton displacement The case of general constrained problems Basic SQP scheme Quasi-Newton Approximations Linesearch, Merit functions, global convergence l1 merit function SQP Algorithm with Merit Function Concluding remarks Prerequisites from Linear Algebra and Analysis Space Rn: algebraic structure A point in Rn Linear operations Linear subspaces Linear independence, bases, dimensions Linear mappings and matrices Space Rn: Euclidean structure Euclidean structure Inner product representation of linear forms on Rn Orthogonal complement Orthonormal bases Affine subspaces in Rn Affine subspaces and affine hulls Intersections of affine subspaces, affine combinations and affine hulls Affinely spanning sets, affinely independent sets, affine dimension Dual description of linear subspaces and affine subspaces Affine subspaces and systems of linear equations Structure of the simplest affine subspaces Space Rn: metric structure and topology Euclidean norm and distances Convergence Closed and open sets Local compactness of Rn Continuous functions on Rn Continuity of a function Elementary continuity-preserving operations Basic properties of continuous functions on Rn Differentiable functions on Rn The derivative Derivative and directional derivatives Representations of the derivative Existence of the derivative Calculus of derivatives Computing the derivative Higher order derivatives Calculus of Ck mappings Examples of higher-order derivatives Taylor expansion Symmetric matrices Spaces of matrices Main facts on symmetric matrices Variational characterization of eigenvalues Corollaries of the VCE Positive semidefinite matrices and the semidefinite cone