Obviously Awesome

Convex Optimization - book notes

This post is in progress. It will be fleshed out as time permits.

  • Convex Optimization (Boyd, Vandenberghe)

    • Contents
    • Preface

    • Intro

      Math optimization; Linear programming / least squares; Convex optimization; Non-linear optimization; Book outline; Notation

    • Convex Sets

      Affine & convex sets; examples; operations that preserve convexity; inequalities; separating & supporting hyperplanes; dual cones

    • Convex Functions

      Basic properties; operations that preserve convexity; conjugate functions; quasi-convex functions; log-concave & log-convex functions; convexity & generalized inequalities

    • Convex Optimization

      Intro; convex optimization; linear optimization; quadratic optimization; geometric programming; generalized inequality constraints; vector optimization

    • Duality

      Lagrange dual function; Lagrange dual problem; geometric interpretation; saddle-point interpretation; optimality conditions; pertubation & sensitivity analysis; examples; theorems of alternatives; generalized inequalities

    • Approximation & fitting

      Norm approximation; least-norm problems; regularized approximation; robust approximation; function fitting & interpolation

    • Statistical estimation

      Parametric distributions; non-parametric distributions; optimal detector design & hypothesis testing; Chebyshev & Chernoff bounds; experiment design

    • Geometric problems

      Projection on a set; distances between sets; Euclidean distances & angle problems; extremal volume ellipsoids; centering; classification; placement & location; floorplanning

    • Unconstrained optimization

      Problems; descent methods; gradient descent; steepest descent; Newton’s method; self-concordance; implementation

    • Equality-constrained minimization

      Problems; Newton’s method; infeasible-start Newton’s method; implementation

    • Interior-point methods

      Problems; log-barrier function & central path; barrier method; feasibility & phase I methods; complexity analysis; general-inequality problems; primal-dual methods; implementation

    • Appendix: Math

      Norms; analysis; functions; derivatives; linear algebra

    • Appendix: Two-quadratic-function problems

      Single-constraint optimization; S-procedure; symmetric matrix values; strong duality proofs

    • Appendix: Numerical linear algebra

      Matrix structures & algorithm complexity; solving linear equations with factored matrices; LU, Cholesky & LDL factorization; block elimination & Schur complements; solving under-determined linear equations