product iamge

Linear and Nonlinear Programming

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

The 5th edition of this classic textbook covers the central concepts of practical optimization techniques, with an emphasis on methods that are both state-of-the-art and popular. One major insight is the connection between the purely analytical character of an optimization problem and the behavior of algorithms used to solve that problem. End-of-chapter exercises are provided for all chapters.

 The material is organized into three separate parts. Part I offers a self-contained introduction to linear programming. The presentation in this part is fairly conventional, covering the main elements of the underlying theory of linear programming, many of the most effective numerical algorithms, and many of its important special applications. Part II, which is independent of Part I, covers the theory of unconstrained optimization, including both derivations of the appropriate optimality conditions and an introduction to basic algorithms. This part of the book explores the general properties of algorithms and defines various notions of convergence. In turn, Part III extends the concepts developed in the second part to constrained optimization problems. Except for a few isolated sections, this part is also independent of Part I. As such, Parts II and III can easily be used without reading Part I and, in fact, the book has been used in this way at many universities.

 New to this edition are popular topics in data science and machine learning, such as the Markov Decision Process, Farkas’ lemma, convergence speed analysis, duality theories and applications, various first-order methods, stochastic gradient method, mirror-descent method, Frank-Wolf method, ALM/ADMM method, interior trust-region method for non-convex optimization, distributionally robust optimization, online linear programming, semidefinite programming for sensor-network localization, and infeasibility detection for nonlinear optimization.

Author(s): David G. Luenberger, Yinyu Ye
Series: International Series in Operations Research & Management Science, 228
Edition: 5
Publisher: Springer
Year: 2021

Language: English
Pages: 624

Preface
Contents
1 Introduction
1.1 Optimization
1.2 Types of Problems
Linear Programming
Conic Linear Programming
Unconstrained Problems
Constrained Problems
1.3 Complexity of Problems
1.4 Iterative Algorithms and Convergence
Part I Linear Programming
2 Basic Properties of Linear Programs
2.1 Introduction
2.2 Examples of Linear Programming Problems
2.3 Basic Feasible Solutions
2.4 The Fundamental Theorem of Linear Programming
2.5 Relations to Convex Geometry
2.6 Farkas' Lemma and Alternative Systems
2.7 Summary
2.8 Exercises
References
3 Duality and Complementarity
3.1 Dual Linear Programs and Interpretations
3.2 The Duality Theorem
3.3 Geometric and Economic Interpretations
Dual Multipliers—Shadow Prices
3.4 Sensitivity and Complementary Slackness
Sensitivity
Complementary Slackness
3.5 Selected Applications of the Duality
Robust and Distributionally Robust Optimization
Online Linear Programming
3.6 Max Flow–Min Cut Theorem
Max Flow Augmenting Algorithm
Max Flow–Min Cut Theorem
Relation to Duality
3.7 Summary
3.8 Exercises
References
4 The Simplex Method
4.1 Adjacent Basic Feasible Solutions (Extreme Points)
Nondegeneracy Assumption
Determination of Vector to Leave Basis
Conic Combination Interpretations
4.2 The Primal Simplex Method
Determining an Optimal Feasible Solution
The Simplex Procedure
Finding an Initial Basic Feasible Solution
4.3 The Dual Simplex Method
The Primal–Dual Algorithm
4.4 The Simplex Tableau Method
Decomposition
4.5 The Simplex Method for Transportation Problems
Finding a Basic Feasible Solution
The Northwest Corner Rule
Basis Triangularity
The Transportation Simplex Method
Simplex Multipliers
Cycle of Change
The Transportation Simplex Algorithm
4.6 Efficiency Analysis of the Simplex Method
4.7 Summary
4.8 Exercises
References
5 Interior-Point Methods
5.1 Elements of Complexity Theory
5.2 The Simplex Method Is Not Polynomial-Time
5.3 The Ellipsoid Method
Cutting Plane and New Containing Ellipsoid
Convergence
Ellipsoid Method for Usual Form of LP
5.4 The Analytic Center
Cutting Plane and Analytic Volume of Reduction
5.5 The Central Path
Dual Central Path
Primal–Dual Central Path
Duality Gap
5.6 Solution Strategies
Primal Barrier Method
Primal–Dual Path-Following
Primal–Dual Potential Reduction Algorithm
Iteration Complexity
5.7 Termination and Initialization
Termination
Initialization
The HSD Algorithm
5.8 Summary
5.9 Exercises
References
6 Conic Linear Programming
6.1 Convex Cones
6.2 Conic Linear Programming Problem
6.3 Farkas' Lemma for Conic Linear Programming
6.4 Conic Linear Programming Duality
6.5 Complementarity and Solution Rank of SDP
Null-Space Rank Reduction
Gaussian Projection Rank Reduction
Randomized Binary Rank Reduction
Objective-Guide Rank Reduction
6.6 Interior-Point Algorithms for Conic Linear Programming
Initialization: The HSD Algorithm
6.7 Summary
6.8 Exercises
References
Part II Unconstrained Problems
7 Basic Properties of Solutions and Algorithms
7.1 First-Order Necessary Conditions
Feasible and Descent Directions
7.2 Examples of Unconstrained Problems
7.3 Second-Order Conditions
Sufficient Conditions for a Relative Minimum
7.4 Convex and Concave Functions
Properties of Convex Functions
Properties of Differentiable Convex Functions
7.5 Minimization and Maximization of Convex Functions
7.6 Global Convergence of Descent Algorithms
Iterative Algorithms
Descent
Closed Mappings
Global Convergence Theorem
Spacer Steps
7.7 Speed of Convergence
Order of Convergence
Linear Convergence
Arithmetic Convergence
Average Rates
Convergence of Vectors
Complexity
7.8 Summary
7.9 Exercises
References
8 Basic Descent Methods
8.1 Line Search Algorithms
0th-Order Method: Golden Section Search and Curve Fitting
Search by Golden Section
Quadratic Fit
1st-Order Method: Bisection and Curve Fitting Methods
The Bisection Method
Quadratic Fit: Method of False Position
Cubic Fit
2nd-Order Method: Newton's Method
Global Convergence of Curve Fitting
Closedness of Line Search Algorithms
Inaccurate Line Search
Armijo's Rule
8.2 The Method of Steepest Descent: First-Order
The Method
Global Convergence and Convergence Speed
The Quadratic Case
The Nonquadratic Case
8.3 Applications of the Convergence Theory and Preconditioning
Scaling as Preconditioning
8.4 Accelerated Steepest Descent
The Heavy Ball Method
The Method of False Position
8.5 Multiplicative Steepest Descent
Affine-Scaling Method
Mirror-Descent Method
8.6 Newton's Method: Second-Order
Order Two Convergence
Modifications
Newton's Method and Logarithms
Self-concordant Functions
8.7 Sequential Quadratic Optimization Methods
Trust Region Method
A Homotopy or Path-Following Method
8.8 Coordinate and Stochastic Gradient Descent Methods
Global Convergence
Local Convergence Rate
Convergence Speed of a Randomized Coordinate Descent Method
Stochastic Gradient Descent (SGD) Method
8.9 Summary
8.10 Exercises
References
9 Conjugate Direction Methods
9.1 Conjugate Directions
9.2 Descent Properties of the Conjugate Direction Method
9.3 The Conjugate Gradient Method
Conjugate Gradient Algorithm
Verification of the Algorithm
9.4 The C–G Method as an Optimal Process
Bounds on Convergence
9.5 The Partial Conjugate Gradient Method
9.6 Extension to Nonquadratic Problems
Quadratic Approximation
Line Search Methods
Convergence
Preconditioning and Partial Methods
9.7 Parallel Tangents
9.8 Exercises
References
10 Quasi-Newton Methods
10.1 Modified Newton Method
Other Modified Newton's Methods
10.2 Construction of the Inverse
Rank One Correction
10.3 Davidon–Fletcher–Powell Method
Positive Definiteness
Finite Step Convergence
10.4 The Broyden Family
Partial Quasi-Newton Methods
10.5 Convergence Properties
Global Convergence
Local Convergence
10.6 Scaling
Improvement of Eigenvalue Ratio
Scale Factors
A Self-Scaling Quasi-Newton Algorithm
10.7 Memoryless Quasi-Newton Methods
Scaling and Preconditioning
10.8 Combination of Steepest Descent and Newton's Method
10.9 Summary
10.10 Exercises
References
Part III Constrained Optimization
11 Constrained Optimization Conditions
11.1 Constraints and Tangent Plane
Tangent Plane
11.2 First-Order Necessary Conditions (Equality Constraints)
Sensitivity
11.3 Equality Constrained Optimization Examples
Large-Scale Applications
11.4 Second-Order Conditions (Equality Constraints)
Eigenvalues in Tangent Subspace
Projected Hessians
11.5 Inequality Constraints
First-Order Necessary Conditions
The Lagrangian and First-Order Conditions
Second-Order Conditions
Sensitivity
11.6 Mix-Constrained Optimization Examples
11.7 Lagrangian Duality and Zero-Order Conditions
11.8 Rules for Constructing the Lagrangian Dual Explicitly
11.9 Summary
11.10 Exercises
References
12 Primal Methods
12.1 Infeasible Direction and the Steepest Descent Projection Method
12.2 Feasible Direction Methods: Sequential Linear Programming
12.3 The Gradient Projection Method
Linear Constraints
Nonlinear Constraints
12.4 Convergence Rate of the Gradient Projection Method
Geodesic Descent
Geodesics
Lagrangian and Geodesics
Rate of Convergence
Problems with Inequalities
12.5 The Reduced Gradient Method
Linear Constraints
Global Convergence
Nonlinear Constraints
12.6 Convergence Rate of the Reduced Gradient Method
12.7 Sequential Quadratic Optimization Methods
12.8 Active Set Methods
Changes in Working Set
12.9 Summary
12.10 Exercises
References
13 Penalty and Barrier Methods
13.1 Penalty Methods
The Method
Convergence
13.2 Barrier Methods
The Method
Convergence
13.3 Lagrange Multipliers in Penalty and Barrier Methods
Lagrange Multipliers in the Penalty Method
The Hessian Matrix
Lagrange Multipliers in the Barrier Method
13.4 Newton's Method for the Logarithmic Barrier Optimization
The KKT Condition System of the Logarithmic Barrier Function
The KKT System of a ``Shifted'' Barrier
The Interior Ellipsoidal-Trust Region Method with Barrier
13.5 Newton's Method for Equality Constrained Optimization
Normalization of Penalty Functions
Inequalities
13.6 Conjugate Gradients and Penalty Methods
13.7 Penalty Functions and Gradient Projection
Underlying Concept
Implementing the First Step
Inequality Constraints
13.8 Summary
13.9 Exercises
References
14 Local Duality and Dual Methods
14.1 Local Duality and the Lagrangian Method
Inequality Constraints
Partial Duality
The Lagrangian Method: Dual Steepest Ascent
Preconditioning or Scaling
14.2 Separable Problems and Their Duals
Decomposition
14.3 The Augmented Lagrangian and Interpretation
The Penalty Viewpoint
Geometric Interpretation
14.4 The Augmented Lagrangian Method of Multipliers
Inequality Constraints
14.5 The Alternating Direction Method of Multipliers
Convergence Speed Analysis
14.6 The Multi-Block Extension of the Alternating Direction Method of Multipliers
14.7 Cutting Plane Methods
General Form of Algorithm
Kelley's Convex Cutting Plane Algorithm
Convergence
Modifications
Dropping Nonbinding Constraints
14.8 Exercises
References
15 Primal–Dual Methods
15.1 The Standard Problem and Monotone Function
The System of Equations of Monotone Functions
Strategies
15.2 A Simple Merit Function
15.3 Basic Primal–Dual Methods
First-Order Method
Convergence Speed Analysis
Second-Order Method: Newton's Method
Convergence Speed Analysis
A Path-Following Method
15.4 Relation to Sequential Quadratic Optimization
Modified Newton's Method
Absolute-Value Penalty Function
15.5 Primal–Dual Interior-Point (Barrier) Methods
Logarithmic Barrier Function
Interior-Point Method for Convex Quadratic Programming
Potential Function as a Merit Function
15.6 The Monotone Complementarity Problem
The Interior-Point Method for the Complementarity Problem
15.7 Detect Infeasibility in Nonlinear Optimization
15.8 Summary
15.9 Exercises
References
A Mathematical Review
A.1 Sets
Sets of Real Numbers
A.2 Matrix Notation
A.3 Spaces
A.4 Eigenvalues and Quadratic Forms
A.5 Topological Concepts
A.6 Functions
Convex and Concave Functions
Taylor's Theorem
Implicit Function Theorem
o, O Notation
B Convex Sets
B.1 Basic Definitions
B.2 Hyperplanes and Polytopes
B.3 Separating and Supporting Hyperplanes
B.4 Extreme Points
C Gaussian Elimination
C.1 The LU Decomposition
C.2 Pivots
D Basic Network Concepts
D.1 Flows in Networks
D.2 Tree Procedure
D.3 Capacitated Networks
Bibliography
Index