Introduction to Continuous Optimization (Springer Optimization and Its Applications, 172)

"This self-contained monograph presents the reader with an authoritative view of Continuous Optimization, an area of mathematical optimization that has experienced major developments during the past 40 years. The book contains results which have not yet been covered in a systematic way as well as a summary of results on NR theory and methods developed over the last several decades. The readership is aimed to graduate students in applied mathematics, computer science, economics, as well as researchers working in optimization and those applying optimization methods for solving real life problems. Sufficient exercises throughout provide graduate students and instructors with practical utility in a two-semester course in Continuous Optimization. The topical coverage includes interior point methods, self-concordance theory and related complexity issues, first and second order methods with accelerated convergence, nonlinear rescaling (NR) theory and exterior point methods, just to mention a few. The book contains a unified approach to both interior and exterior point methods with emphasis of the crucial duality role. One of the main achievements of the book shows what makes the exterior point methods numerically attractive and why. The book is composed in five parts. The first part contains the basics of calculus, convex analysis, elements of unconstrained optimization, as well as classical results of linear and convex optimization. The second part contains the basics of self-concordance theory and interior point methods, including complexity results for LP, QP, and QP with quadratic constraint, semidefinite and conic programming. In the third part, the NR and Lagrangian transformation theories are considered and exterior point methods are described. Three important problems in finding equilibrium are considered in the fourth part. In the fifth and final part of the book, several important applications arising in economics, structural optimization, medicine, statistical learning theory, and more, are detailed. Numerical results, obtained by solving a number of real life and test problems, are also provided."-- Provided by publisher Preface Contents 1 Introduction 2 Elements of Calculus and Convex Analysis 2.0 Introduction 2.1 Elements of Calculus 2.1.1 Differentiation of Scalar Functions 2.1.2 Differentiation of Vector Functions 2.1.3 Second Derivatives 2.1.4 Convex Functions in Rn 2.1.5 Strictly and Strongly Convex Functions in Rn 2.2 Convex Sets 2.2.1 Open and Closed Sets 2.2.2 Convex Sets 2.2.3 Affine Sets 2.2.4 Cones 2.2.5 Recession Cones 2.2.6 Polyhedrons and Polytopes 2.3 Closed Convex Functions 2.3.1 Operations on Closed Convex Functions 2.3.2 Projection on a Closed Convex Set 2.3.3 Separation Theorems 2.3.4 Some Properties of Convex Functions 2.3.4.1 Continuity of Convex Functions 2.3.4.2 Differentiability of Convex Functions 2.3.5 Subgradients 2.3.6 Support Functions 2.4 The Legendre–Fenchel Transformation 2.4.1 Basic LF Transformation Property 2.4.2 The LF Identity and the LF Invariant 3 Few Topics in Unconstrained Optimization 3.0 Introduction 3.1 Optimality Conditions 3.1.1 First-Order Necessary Condition 3.1.2 Second-Order Necessary Condition 3.1.3 Second-Order Sufficient Condition 3.2 Nondifferentiable Unconstrained Minimization 3.2.1 Subgradient Method 3.3 Gradient Methods 3.3.1 Gradient Method 3.3.2 Fast Gradient Method 3.3.3 Gradient Method for Strongly Convex Functions 3.4 Method Regularization 3.5 Proximal Point Method 3.6 Newton's Method and Regularized Newton Method 3.6.1 Introduction 3.6.2 Newton's Method 3.6.3 Local Quadratic Convergence of Newton's Method 3.6.4 Damped Newton Method 3.6.5 Global Convergence of DNM and Its Complexity 3.6.6 Regularized Newton Method 3.6.7 Local Quadratic Convergence Rate of RNM 3.6.8 Damped Regularized Newton Method 3.6.9 The Complexity of DRNM 3.6.10 Newton's Method as an Affine Invariant 4 Optimization with Equality Constraints 4.0 Introduction 4.1 Lagrangian and First-Order Optimality Condition 4.2 Second-Order Necessary and Sufficient Optimality Condition 4.3 Optimality Condition for Constrained Optimization Problems with Both Inequality Constraints and Equations 4.4 Duality for Equality-Constrained Optimization 4.5 Courant's Penalty Method as Tikhonov's Regularization for the Dual Problem 4.6 Gradient Methods for ECO 4.7 Newton's Method for Nonlinear System of Equations 4.8 Newton's Method for ECO 4.9 Augmented Lagrangian 4.10 The Multipliers Method and the Dual Quadratic Prox 4.11 Primal–Dual AL Method for ECO 5 Basics in Linear and Convex Optimization 5.0 Introduction 5.1 Linear Programming 5.1.1 Primal and Dual LP Problems 5.1.2 Optimality Condition for LP Problem 5.1.3 Farkas Lemma 5.2 The Karush–Kuhn–Tucker's Theorem 5.3 The KKT's Theorem for Convex Optimization with Linear Constraints 5.4 Duality in Convex Optimization 5.5 Wolfe's Duality 5.6 LP Duality 5.7 Some Structural LP Properties 5.8 Simplex Method 5.9 Interior Point Methods 5.9.1 Newton Log– Barrier Method for LP 5.9.2 Primal–Dual Interior Point Method 5.9.3 Affine Scaling Method 5.10 SUMT as Dual Interior Regularization 5.10.1 Log–Barrier Method and Its Dual Equivalent 5.10.2 Hyperbolic Barrier as Dual Parabolic Regularization 5.10.3 Exponential Penalty as Dual Regularization with Shannon's Entropy Function 5.10.4 Log–Sigmoid Method as Dual Regularization with Fermi–Dirac's Entropy Function 5.10.5 Interior Distance Functions 5.11 Primal–Dual IPM for Convex Optimization 5.12 Gradient Projection Method 5.12.1 Convergence of the GP Method 5.12.2 Fast GP Method 5.12.3 GP Method for Strongly Convex Function 5.13 Quadratic Programming 5.13.1 Dual GP Method for QP 5.13.2 Dual Fast Gradient Projection Method 5.14 Quadratic Programming Problems with Quadratic Constraints 5.15 Conditional Gradient Method 5.16 Primal–Dual Feasible Direction Method 6 Self-Concordant Functions and IPM Complexity 6.0 Introduction 6.1 LF Invariant and SC Functions 6.2 Basic Properties of SC Functions 6.3 Newton's Method for Minimization of SC Functions 6.4 SC Barrier 6.5 Path-Following Method 6.6 Applications of ν-SC Barrier. IPM Complexity for LP and QP 6.6.1 Linear and Quadratic Optimization 6.6.2 The Lorentz Cone 6.6.3 Semidefinite Optimization 6.7 Primal–Dual Predictor–Corrector for LP 7 Nonlinear Rescaling: Theory and Methods 7.0 Introduction 7.1 Nonlinear Rescaling 7.1.1 Preliminaries 7.1.2 Constraints Transformation and Lagrangian for the Equivalent Problem: Local Properties 7.1.3 Primal Transformations and Dual Kernels 7.1.4 NR Method and Dual Prox with -Divergence Distance 7.1.5 Q-Linear Convergence Rate 7.1.6 Stopping Criteria 7.1.7 Newton NR Method and ``Hot'' Start Phenomenon 7.2 NR with ``Dynamic'' Scaling Parameters 7.2.0 Introduction 7.2.1 Nonlinear Rescaling as Interior Quadratic Prox 7.2.2 Convergence of the NR Method 7.2.3 Rate of Convergence 7.2.4 Nonlinear Rescaling for LP 7.3 Primal–Dual NR Method for Convex Optimization 7.3.0 Introduction 7.3.1 Local Convergence of the PDNR 7.3.2 Global Convergence of the PDNR 7.4 Nonlinear Rescaling and Augmented Lagrangian 7.4.0 Introduction 7.4.1 Problem Formulation and Basic Assumptions 7.4.2 Lagrangian for the Equivalent Problem 7.4.3 Multipliers Method 7.4.4 NRAL and the Dual Prox 8 Realizations of the NR Principle 8.0 Introduction 8.1 Modified Barrier Functions 8.1.0 Introduction 8.1.1 Logarithmic MBF 8.1.2 Convergence of the Logarithmic MBF Method 8.1.3 Convergence Rate 8.1.4 MBF and Duality Issues 8.2 Exterior Distance Functions 8.2.0 Introduction 8.2.1 Exterior Distance 8.2.2 Exterior Point Method: Convergence and Convergence Rate 8.2.3 Stopping Criteria 8.2.4 Modified Interior Distance Functions 8.2.5 Local MIDF Properties 8.2.6 Modified Center Method 8.2.7 Basic Theorem 8.3 Nonlinear Rescaling vs. Smoothing Technique 8.3.0 Introduction 8.3.1 Log-Sigmoid Transformation and Its Modification 8.3.2 Equivalent Problem and LS Lagrangian 8.3.3 LS Multipliers Method as Interior Prox with Fermi–Dirac Entropy Distance 8.3.4 Convergence of the LS Multipliers Method 8.3.5 The Upper Bound for the Number of Steps 8.3.6 Asymptotic Convergence Rate 8.3.7 Generalization and Extension 8.3.8 LS Multipliers Method for Linear Programming 9 Lagrangian Transformation and Interior Ellipsoid Methods 9.0 Introduction 9.1 Lagrangian Transformation 9.2 Bregman's Distance 9.3 Primal LT and Dual Interior Quadratic Prox 9.4 Convergence Analysis 9.5 LT with Truncated MBF and Interior Ellipsoid Method 9.6 Lagrangian Transformation and Dual Affine Scaling Method for LP 10 Finding Nonlinear Equilibrium 10.0 Introduction 10.1 General NE Problem and the Equivalent VI 10.2 Problems Leading to NE 10.2.1 Convex Optimization 10.2.2 Finding a Saddle Point 10.2.3 Matrix Game 10.2.4 J. Nash Equilibrium in n-Person Concave Game 10.2.5 Walras–Wald Equilibrium 10.3 NE for Optimal Resource Allocation 10.3.1 Introduction 10.3.2 Problem Formulation 10.3.3 NE as a VI 10.3.4 Existence and Uniqueness of the NE 10.4 Nonlinear Input–Output Equilibrium 10.4.1 Introduction 10.4.2 Preliminaries 10.4.3 Problem Formulation 10.4.4 NIOE as a VI 10.4.5 Existence and Uniqueness of the NIOE 10.5 Finding NE for Optimal Resource Allocation 10.5.1 Introduction 10.5.2 Basic Assumptions 10.5.3 Pseudo-gradient Projection Method 10.5.4 Extra Pseudo-gradient Method for Finding NE 10.5.5 Convergence Rate 10.5.6 Bound for the Lipschitz Constant 10.5.7 Finding NE as a Pricing Mechanizm 10.6 Finding Nonlinear Input–Output Equilibrium 10.6.1 Introduction 10.6.2 Basic Assumptions 10.6.3 PGP Method for Finding NIOE 10.6.4 EPG Method for Finding NIOE 10.6.5 Convergence Rate and Complexity of the EPG Method 10.6.6 Lipschitz Constant 10.7 Finding J. Nash Equilibrium in n-Person Concave Game 10.7.1 Projection Onto Probability Simplex 10.7.2 Algorithm for Projection onto PS 11 Applications and Numerical Results 11.0 Introduction 11.1 Truss Topology Design 11.2 Intensity-Modulated Radiation Therapy Planning 11.3 QP and Its Applications 11.3.1 Non-negative Least Squares 11.3.2 Support Vector Machines 11.3.3 Fast Gradient Projection for Dual QP. Numerical Results 11.4 Finding Nonlinear Equilibrium 11.5 The ``Hot'' Start Phenomenon Concluding Remarks Appendix References