Introduction to continuous optimization / / Roman A. Polyak

• Record Nr.: UNINA9910484600303321
• Autore: Polyak Roman A.
• Pubbl/distr/stampa: Cham, Switzerland : , : Springer, , [2021]; ©2021
• ISBN: 3-030-68713-9
• Descrizione fisica: 1 online resource (552 pages)
• Collana: Springer optimization and its applications ; ; 172
• Disciplina: 519.3
• Soggetti: Mathematical optimization; Optimització matemàtica; Llibres electrònics
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Nota di bibliografia: Includes bibliographical references.
• Nota di contenuto: Intro -- 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.