| |
| |
| |
| Introduction | |
| |
| |
| |
| Problem Statement and Basic Definitions | |
| |
| |
| |
| Illustrative Examples | |
| |
| |
| |
| Guidelines for Model Construction | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Convex Analysis | |
| |
| |
| |
| Convex Sets | |
| |
| |
| |
| Convex Hulls | |
| |
| |
| |
| Closure and Interior of a Set | |
| |
| |
| |
| Weierstrass's Theorem | |
| |
| |
| |
| Separation and Support of Sets | |
| |
| |
| |
| Convex Cones and Polarity | |
| |
| |
| |
| Polyhedral Sets, Extreme Points, and Extreme Directions | |
| |
| |
| |
| Linear Programming and the Simplex Method | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Convex Functions and Generalizations | |
| |
| |
| |
| Definitions and Basic Properties | |
| |
| |
| |
| Subgradients of Convex Functions | |
| |
| |
| |
| Differentiable Convex Functions | |
| |
| |
| |
| Minima and Maxima of Convex Functions | |
| |
| |
| |
| Generalizations of Convex Functions | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Optimality Conditions and Duality | |
| |
| |
| |
| The Fritz John and Karush-Kuhn-Tucker Optimality Conditions | |
| |
| |
| |
| Unconstrained Problems | |
| |
| |
| |
| Problems Having Inequality Constraints | |
| |
| |
| |
| Problems Having Inequality and Equality Constraints | |
| |
| |
| |
| Second-Order Necessary and Sufficient Optimality Conditions for Constrained Problems | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Constraint Qualification | |
| |
| |
| |
| Cone of Tangents | |
| |
| |
| |
| Other Constraint Qualifications | |
| |
| |
| |
| Problems Having Inequality and Equality Constraints | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Lagrangian Duality and Saddle Point Optimality Conditions | |
| |
| |
| |
| Lagrangian Dual Problem | |
| |
| |
| |
| Duality Theorems and Saddle Point Optimality Conditions | |
| |
| |
| |
| Properties of the Dual Function | |
| |
| |
| |
| Formulating and Solving the Dual Problem | |
| |
| |
| |
| Getting the Primal Solution | |
| |
| |
| |
| Linear and Quadratic Programs | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Algorithms and Their Convergence | |
| |
| |
| |
| The Concept of an Algorithm | |
| |
| |
| |
| Algorithms and Algorithmic Maps | |
| |
| |
| |
| Closed Maps and Convergence | |
| |
| |
| |
| Composition of Mappings | |
| |
| |
| |
| Comparison Among Algorithms | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Unconstrained Optimization | |
| |
| |
| |
| Line Search Without Using Derivatives | |
| |
| |
| |
| Line Search Using Derivatives | |
| |
| |
| |
| Some Practical Line Search Methods | |
| |
| |
| |
| Closedness of the Line Search Algorithmic Map | |
| |
| |
| |
| Multidimensional Search Without Using Derivatives | |
| |
| |
| |
| Multidimensional Search Using Derivatives | |
| |
| |
| |
| Modification of Newton's Method: Levenberg-Marquardt and Trust Region Methods | |
| |
| |
| |
| Methods Using Conjugate Directions: Quasi-Newton and Conjugate Gradient Methods | |
| |
| |
| |
| Subgradient Optimization Methods | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Penalty and Barrier Functions | |
| |
| |
| |
| Concept of Penalty Functions | |
| |
| |
| |
| Exterior Penalty Function Methods | |
| |
| |
| |
| Exact Absolute Value and Augmented Lagrangian Penalty Methods | |
| |
| |
| |
| Barrier Function Methods | |
| |
| |
| |
| Polynomial-Time Interior Point Algorithms for Linear Programming Based on a Barrier Function | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Methods of Feasible Directions | |
| |
| |
| |
| Method of Zoutendijk | |
| |
| |
| |
| Convergence Analysis of the Method of Zoutendijk | |
| |
| |
| |
| Successive Linear Programming Approach | |
| |
| |
| |
| Successive Quadratic Programming or Projected Lagrangian Approach | |
| |
| |
| |
| Gradient Projection Method of Rosen | |
| |
| |
| |
| Reduced Gradient Method of Wolfe and Generalized Reduced Gradient Method | |
| |
| |
| |
| Convex-Simplex Method of Zangwill | |
| |
| |
| |
| Effective First- and Second-Order Variants of the Reduced Gradient Method | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Linear Complementary Problem, and Quadratic, Separable, Fractional, and Geometric Programming | |
| |
| |
| |
| Linear Complementary Problem | |
| |
| |
| |
| Convex and Nonconvex Quadratic Programming: Global Optimization Approaches | |
| |
| |
| |
| Separable Programming | |
| |
| |
| |
| Linear Fractional Programming | |
| |
| |
| |
| Geometric Programming | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Mathematical Review | |
| |
| |
| |
| Summary of Convexity, Optimality Conditions, and Duality | |
| |
| |
| Bibliography | |
| |
| |
| Index | |