You are previewing Convex Optimization.
O'Reilly logo
Convex Optimization

Book Description

Convex optimization problems arise frequently in many different fields. This book provides a comprehensive introduction to the subject, and shows in detail how such problems can be solved numerically with great efficiency. The book begins with the basic elements of convex sets and functions, and then describes various classes of convex optimization problems. Duality and approximation techniques are then covered, as are statistical estimation techniques. Various geometrical problems are then presented, and there is detailed discussion of unconstrained and constrained minimization problems, and interior-point methods. The focus of the book is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. It contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance and economics.

Table of Contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright
  5. Dedication
  6. Contents
  7. Preface
  8. 1. Introduction
    1. 1.1 Mathematical optimization
    2. 1.2 Least-squares and linear programming
    3. 1.3 Convex optimization
    4. 1.4 Nonlinear optimization
    5. 1.5 Outline
    6. 1.6 Notation
    7. Bibliography
  9. I: Theory
    1. 2. Convex sets
      1. 2.1 Affine and convex sets
      2. 2.2 Some important examples
      3. 2.3 Operations that preserve convexity
      4. 2.4 Generalized inequalities
      5. 2.5 Separating and supporting hyperplanes
      6. 2.6 Dual cones and generalized inequalities
      7. Bibliography
      8. Exercises
    2. 3. Convex functions
      1. 3.1 Basic properties and examples
      2. 3.2 Operations that preserve convexity
      3. 3.3 The conjugate function
      4. 3.4 Quasiconvex functions
      5. 3.5 Log-concave and log-convex functions
      6. 3.6 Convexity with respect to generalized inequalities
      7. Bibliography
      8. Exercises
    3. 4. Convex optimization problems
      1. 4.1 Optimization problems
      2. 4.2 Convex optimization
      3. 4.3 Linear optimization problems
      4. 4.4 Quadratic optimization problems
      5. 4.5 Geometric programming
      6. 4.6 Generalized inequality constraints
      7. 4.7 Vector optimization
      8. Bibliography
      9. Exercises
    4. 5. Duality
      1. 5.1 The Lagrange dual function
      2. 5.2 The Lagrange dual problem
      3. 5.3 Geometric interpretation
      4. 5.4 Saddle-point interpretation
      5. 5.5 Optimality conditions
      6. 5.6 Perturbation and sensitivity analysis
      7. 5.7 Examples
      8. 5.8 Theorems of alternatives
      9. 5.9 Generalized inequalities
      10. Bibliography
      11. Exercises
  10. II: Applications
    1. 6. Approximation and fitting
      1. 6.1 Norm approximation
      2. 6.2 Least-norm problems
      3. 6.3 Regularized approximation
      4. 6.4 Robust approximation
      5. 6.5 Function fitting and interpolation
      6. Bibliography
      7. Exercises
    2. 7. Statistical estimation
      1. 7.1 Parametric distribution estimation
      2. 7.2 Nonparametric distribution estimation
      3. 7.3 Optimal detector design and hypothesis testing
      4. 7.4 Chebyshev and Chernoff bounds
      5. 7.5 Experiment design
      6. Bibliography
      7. Exercises
    3. 8. Geometric problems
      1. 8.1 Projection on a set
      2. 8.2 Distance between sets
      3. 8.3 Euclidean distance and angle problems
      4. 8.4 Extremal volume ellipsoids
      5. 8.5 Centering
      6. 8.6 Classification
      7. 8.7 Placement and location
      8. 8.8 Floor planning
      9. Bibliography
      10. Exercises
  11. III: Algorithms
    1. 9. Unconstrained minimization
      1. 9.1 Unconstrained minimization problems
      2. 9.2 Descent methods
      3. 9.3 Gradient descent method
      4. 9.4 Steepest descent method
      5. 9.5 Newton’s method
      6. 9.6 Self-concordance
      7. 9.7 Implementation
      8. Bibliography
      9. Exercises
    2. 10. Equality constrained minimization
      1. 10.1 Equality constrained minimization problems
      2. 10.2 Newton’s method with equality constraints
      3. 10.3 Infeasible start Newton method
      4. 10.4 Implementation
      5. Bibliography
      6. Exercises
    3. 11. Interior-point methods
      1. 11.1 Inequality constrained minimization problems
      2. 11.2 Logarithmic barrier function and central path
      3. 11.3 The barrier method
      4. 11.4 Feasibility and phase I methods
      5. 11.5 Complexity analysis via self-concordance
      6. 11.6 Problems with generalized inequalities
      7. 11.7 Primal-dual interior-point methods
      8. 11.8 Implementation
      9. Bibliography
      10. Exercises
  12. Appendices
    1. A. Mathematical background
      1. A.1 Norms
      2. A.2 Analysis
      3. A.3 Functions
      4. A.4 Derivatives
      5. A.5 Linear algebra
      6. Bibliography
    2. B. Problems involving two quadratic functions
      1. B.1 Single constraint quadratic optimization
      2. B.2 The S-procedure
      3. B.3 The field of values of two symmetric matrices
      4. B.4 Proofs of the strong duality results
      5. Bibliography
    3. C. Numerical linear algebra background
      1. C.1 Matrix structure and algorithm complexity
      2. C.2 Solving linear equations with factored matrices
      3. C.3 LU, Cholesky, and LDLT factorization
      4. C.4 Block elimination and Schur complements
      5. C.5 Solving underdetermined linear equations
      6. Bibliography
  13. References
  14. Notation
  15. Index