Convex Optimization PDF Download – Boyd & Vandenberghe (2004) MS/BSCS/Engineering

Convex Optimization by Stephen Boyd and Lieven Vandenberghe is the standard reference for the convex optimization course taught in MS programs and in senior-year BSCS and Engineering electives at Pakistani universities. It covers the mathematics of convex sets, convex functions, and duality, then shows how the same theory solves real problems in statistics, estimation, and engineering design. The book assumes a solid background in multivariable calculus and linear algebra, which most MS and final-year BSCS or Engineering students already have from earlier coursework.

For students taking an optimization, machine learning theory, or control systems course, this is where the underlying mathematics actually comes from. The chapter order builds from convex sets and functions to duality, then to applications and finally to the interior-point algorithms that solve these problems in practice, so most exam topics have a direct home in one chapter. Working through the chapter summaries and Important Questions on this page before a quiz or paper is faster than re-reading the full PDF the night before.

Book Overview

Chapter List

Chapter 1: Introduction

Part I: Theory · Difficulty: Easy · Key topics: optimization problem, objective function, constraints, convexity, least-squares, linear programming

Mathematical optimization problems take the form of minimizing an objective function subject to constraints, and this chapter opens by showing why most such problems are hard in general but why convex problems are the major exception. It defines what makes a problem convex — both the objective and every constraint function must satisfy convexity’s defining inequality for weighted averages of points — and argues that convexity, not linearity, is the real dividing line between tractable and intractable optimization. It places two already-solved problem classes, least-squares (solved directly via linear equations) and linear programming (solved via simplex or interior-point methods), as special cases of the broader convex framework the book goes on to build. The chapter’s real point is methodological: once a problem is correctly recognized and formulated as convex, interior-point methods solve it reliably and efficiently, so the hard part of applied optimization is the formulation, not the solving. It closes by laying out the book’s own three-part structure — Theory, Applications, Algorithms.

Key Points:

• A convex optimization problem requires both the objective and every constraint function to satisfy the convexity inequality for weighted averages of any two points.
• Convexity, not linearity, is presented as the real boundary between tractable and intractable optimization problems.
• Least-squares problems are solved directly by linear algebra, with no iterative algorithm needed.
• Linear programming is solved reliably by the simplex method or by interior-point methods.
• Once a problem is correctly formulated as convex, interior-point methods solve it efficiently even at large scale.
• The book’s three parts are Theory, Applications, and Algorithms, taught in that order.

Memory Tip: Remember the chapter’s message as “formulate, don’t fight” — most of the difficulty in using convex optimization is recognizing and writing a problem in convex form, not running the solver afterward.

Common Mistake: Students often assume “convex” means “linear”; the chapter is explicit that convex optimization is a strictly larger class that includes many nonlinear problems.

Important Questions:

• What two conditions make an optimization problem a convex optimization problem? Both the objective function and every constraint function must satisfy the convexity inequality for weighted averages of any two points in the domain.
• Why does the book call least-squares and linear programming special cases of convex optimization? Both minimize a convex function over a convex feasible set, so the general convex theory covers them as particular instances.

Chapter 2: Convex Sets

Part I: Theory · Difficulty: Medium · Key topics: affine sets, convex sets, convex hull, cones, hyperplanes, polyhedra, separating hyperplane

This chapter builds the geometric vocabulary the rest of the book depends on. It separates affine sets (closed under affine combinations, where the coefficients just need to sum to one) from convex sets (closed under convex combinations, where the coefficients must also be nonnegative), and defines the convex hull as the smallest convex set containing a given set of points. It introduces cones and convex cones — sets closed under nonnegative scaling and, for convex cones, under nonnegative (conic) combinations — and works through the standard library of convex sets later chapters reuse: hyperplanes and halfspaces, Euclidean balls and ellipsoids, norm balls and norm cones, and polyhedra formed by intersecting finitely many halfspaces and hyperplanes. It proves that convexity survives intersection and affine mapping, and ends with the separating and supporting hyperplane theorems, which become the geometric foundation for duality in Chapter 5.

Key Points:

• An affine set is closed under affine combinations (coefficients summing to one); a convex set additionally requires nonnegative coefficients.
• The convex hull of a set is the smallest convex set that contains it.
• A convex cone is closed under nonnegative (conic) combinations of its points.
• Polyhedra are intersections of finitely many halfspaces and hyperplanes; simplexes are a special case.
• Intersection and affine images preserve convexity.
• The separating hyperplane theorem: two disjoint convex sets can always be separated by a hyperplane.
• Every boundary point of a convex set has a supporting hyperplane at that point.

Memory Tip: Keep “affine = equality, convex = equality plus nonnegative” as the one-line distinction between the two coefficient rules.

Common Mistake: Students often think any intersection or union of convex sets stays convex — intersection does, union generally does not.

Important Questions:

• What is the difference between an affine combination and a convex combination? An affine combination only requires the coefficients to sum to one (they can be negative); a convex combination additionally requires every coefficient to be nonnegative.
• What does the separating hyperplane theorem guarantee? That any two disjoint convex sets can be separated by at least one hyperplane, with each set lying entirely on one side of it.

Chapter 3: Convex Functions

Part I: Theory · Difficulty: Medium · Key topics: convexity inequality, first-order condition, second-order condition, Hessian, log-sum-exp, quasiconvexity

Chapter 3 moves the same idea from sets to functions. A function is convex when its domain is convex and it satisfies the inequality f(θx+(1−θ)y) ≤ θf(x)+(1−θ)f(y); concave functions reverse the inequality, and strict convexity tightens it for distinct points. For differentiable functions the chapter gives two practical tests: the first-order condition, that the function always lies above its tangent line/plane, and for twice-differentiable functions the second-order condition, that the Hessian is positive semidefinite everywhere. It runs through the standard library of convex examples — exponentials, suitable powers, negative logarithms, norms, the maximum of convex functions, log-sum-exp, the quadratic-over-linear function, geometric mean, and log-determinant — and the operations that preserve convexity: nonnegative weighted sums, composition rules, pointwise maxima and suprema, minimization over a convex set, and the perspective function. It closes by generalizing to quasiconvex functions, log-concave/log-convex functions, and convexity with respect to generalized inequalities defined by a cone.

Key Points:

• A twice-differentiable function is convex exactly when its Hessian is positive semidefinite on its whole domain.
• The first-order condition says a convex function always lies on or above every tangent line/plane.
• log-sum-exp, norms, and the quadratic-over-linear function are standard convex building blocks used throughout the book.
• Nonnegative weighted sums and the pointwise maximum of convex functions are themselves convex.
• Quasiconvex functions generalize convexity: their sublevel sets are convex even though the function itself may not be.
• Composition rules let you check convexity of combined functions without re-deriving the definition each time.

Memory Tip: Picture the Hessian test as “convex = bowl-shaped everywhere” — positive semidefinite curvature at every point, like a bowl that never curves the wrong way.

Common Mistake: Students apply the composition rule for convexity without checking the required monotonicity of the outer function — composing convex with convex is only convex under specific increasing/decreasing conditions, not automatically.

Important Questions:

• What is the second-order condition for convexity of a twice-differentiable function? Its Hessian matrix must be positive semidefinite at every point of its (convex) domain.
• How does a quasiconvex function differ from a convex function? A quasiconvex function only requires every sublevel set to be convex; the function’s graph itself need not satisfy the convexity inequality the way a true convex function’s does.

Chapter 4: Convex Optimization Problems

Part I: Theory · Difficulty: Medium · Key topics: standard form, local vs global optimality, epigraph form, linear/quadratic/SOCP/SDP programs, Pareto optimality

This chapter states the standard-form convex optimization problem — minimize a convex objective subject to convex inequality constraints and affine equality constraints — and proves the property that makes the whole subject useful: every locally optimal point of a convex problem is automatically globally optimal, so a solver never has to worry about getting trapped in a bad local minimum. It gives the first-order optimality condition for differentiable objectives, and covers standard reformulation tricks: eliminating equality constraints by parameterizing their solution set, introducing slack variables, and converting to epigraph form by adding one variable that represents the objective value. It surveys the major named problem classes that fit this mold — linear programming, quadratic programming, quadratically constrained quadratic programming, second-order cone programming, geometric programming, and semidefinite programming — and introduces vector optimization with multiple objectives, where Pareto optimality replaces a single optimal value.

Key Points:

• Any locally optimal point of a convex problem is also globally optimal — this is the single most important consequence of convexity.
• Epigraph form rewrites a problem by adding one variable for the objective value, turning the objective into a constraint.
• Named convex problem classes include LP, QP, QCQP, second-order cone programs (SOCP), geometric programs (GP), and semidefinite programs (SDP).
• Equality constraints can be eliminated entirely by parameterizing the set of points that satisfy them.
• Pareto optimal points replace a single optimum when a problem has multiple competing objectives.

Memory Tip: Remember “local = global” as convex optimization’s single biggest promise — it is the one line that explains why these problems are tractable at all.

Common Mistake: Students sometimes believe SOCP and SDP are unrelated extensions; in fact LP is contained in QP, which is contained in SOCP, which is contained in SDP — a strict hierarchy of increasingly general convex problem classes.

Important Questions:

• Why is local optimality enough to guarantee global optimality in a convex problem? Because the feasible set and the objective’s sublevel sets are convex, so no point elsewhere in the feasible region can beat a point that is already optimal in its own neighborhood.
• What is epigraph form and why is it useful? It rewrites minimizing f₀(x) as minimizing a new variable t subject to f₀(x) ≤ t plus the original constraints, letting every convex problem be treated as minimizing a linear function of the extended variable.

Chapter 5: Duality

Part I: Theory · Difficulty: Hard · Key topics: Lagrangian, dual function, weak/strong duality, Slater’s condition, KKT conditions, complementary slackness

Duality is the chapter where the theory pays off. The Lagrangian folds the constraints into the objective using dual variables (multipliers), and minimizing the Lagrangian over the primal variable produces the Lagrange dual function, which is always concave regardless of whether the original problem was convex. Maximizing the dual function subject to nonnegativity of the inequality multipliers gives the dual problem, whose optimal value never exceeds the primal’s (weak duality); the gap between them is the duality gap. For convex primal problems satisfying Slater’s condition (existence of a strictly feasible point), the gap closes entirely — strong duality — and the chapter derives the Karush-Kuhn-Tucker (KKT) conditions, combining primal feasibility, dual feasibility, and complementary slackness into necessary conditions for optimality that become sufficient once the problem is convex. The chapter closes by using the dual variables as sensitivity measures, showing how the optimal value would change if a constraint were relaxed.

Key Points:

• The Lagrangian combines the objective and constraints into one function using dual variables (multipliers).
• The Lagrange dual function is concave even when the primal problem is not convex.
• Weak duality always holds; strong duality (zero gap) holds for convex problems under Slater’s condition.
• Complementary slackness means a multiplier is nonzero only for a constraint that holds with equality at the optimum.
• The KKT conditions are necessary for optimality in general, and sufficient for optimality when the problem is convex.
• Dual variables double as sensitivity measures, showing the rate of change of the optimal value as a constraint is relaxed.

Memory Tip: Think of the Lagrangian dual as “always a floor” — the dual function’s value never rises above the primal’s true minimum, no matter how nonconvex the original problem is.

Common Mistake: Students assume strong duality always holds for convex problems; it requires a constraint qualification such as Slater’s condition, and without it a nonzero duality gap is possible even in convex problems.

Important Questions:

• What does Slater’s condition guarantee, and why does it matter? It guarantees strong duality (a zero duality gap) for a convex problem, by requiring the existence of a point that strictly satisfies every inequality constraint.
• State complementary slackness in your own words. At an optimal primal-dual pair, whenever an inequality constraint’s multiplier is strictly positive, that constraint must hold with equality; if the constraint is slack, its multiplier must be zero.

Chapter 6: Approximation and Fitting

Part II: Applications · Difficulty: Medium · Key topics: norm approximation, Chebyshev approximation, regularization, robust approximation, function fitting

The applications half of the book opens with approximation: choosing a model from a family to minimize the discrepancy between a target quantity and the model’s prediction, with the choice of norm determining the flavor of the problem. The Euclidean norm gives ordinary least-squares, solvable in closed form; the infinity norm gives Chebyshev approximation, which becomes a linear program. Regularized approximation treats the problem as a bi-criterion trade-off between fit quality and model simplicity, with Tikhonov (ridge) regularization adding a penalty on the squared size of the parameters to control that trade-off and improve robustness against overfitting. Robust approximation extends the framework to handle uncertainty in the problem data itself, either statistically (parameters drawn from a known distribution) or via worst-case, min-max formulations that protect against the most adversarial realization of the uncertain data. The chapter closes with function fitting and interpolation, extending the same machinery to reconstructing a function from noisy or sparse samples.

Key Points:

• Least-squares approximation uses the Euclidean norm and is solvable directly, in closed form.
• Chebyshev approximation minimizes the worst-case (infinity-norm) deviation and reduces to a linear program.
• Tikhonov regularization (ridge regression) adds a penalty on parameter size to trade off fit against overfitting.
• Robust approximation comes in two flavors: stochastic (known distribution over the uncertain data) and worst-case/min-max.
• Regularized approximation is naturally framed as a bi-criterion problem: minimize error and model size simultaneously.

Memory Tip: Picture the norm choice as the whole decision: Euclidean norm gives smooth least-squares, infinity norm gives worst-case Chebyshev — both end up as convex problems either way.

Common Mistake: Students conflate “robust” with simply “regularized” — regularization controls overfitting to given data, while robustness specifically protects against uncertainty or error in that data itself.

Important Questions:

• What kind of problem does Chebyshev approximation become, and why? A linear program, because minimizing the maximum absolute residual can be rewritten as minimizing a single auxiliary variable subject to linear inequality bounds on every residual.
• What is the difference between stochastic and worst-case robust approximation? Stochastic robust approximation assumes the uncertain parameters follow a known probability distribution; worst-case robust approximation optimizes against the single worst possible realization of the uncertainty, with no distributional assumption.

Chapter 7: Statistical Estimation

Part II: Applications · Difficulty: Medium · Key topics: maximum likelihood, MAP estimation, hypothesis testing, Chernoff bound, experiment design

This chapter shows that several classical statistics problems are themselves convex optimization problems in disguise. Maximum likelihood (ML) estimation chooses the parameter that makes the observed data most probable; whenever the negative log-likelihood is convex — true for many exponential-family distributions — the ML problem is a convex program solvable efficiently. Maximum a posteriori (MAP) estimation folds in a prior belief about the parameter, maximizing the log-likelihood plus the log-prior, which stays convex whenever both pieces are. The chapter turns to detection and hypothesis testing, framing the detector’s decision rule as a convex optimization variable, with false-alarm and miss probabilities as convex objectives or constraints, and brings in Chernoff bounds as distribution-free guarantees on how fast detection error probabilities decay. It closes with experiment design, where convex optimization chooses which measurements to take — D-optimal design maximizes the determinant of the Fisher information matrix, while E-optimal design minimizes the largest eigenvalue of the estimation error’s covariance.

Key Points:

• Maximum likelihood estimation is a convex problem whenever the negative log-likelihood is convex, which holds for many exponential-family distributions.
• MAP estimation adds a log-prior term to the log-likelihood and stays convex when both are convex.
• Chernoff bounds give distribution-free bounds on detection error probability decay rates.
• D-optimal experiment design maximizes the determinant of the Fisher information matrix.
• E-optimal experiment design minimizes the largest eigenvalue of the estimation error covariance.

Memory Tip: Remember ML vs MAP as “likelihood alone” vs “likelihood plus a prior” — MAP is just ML with an extra convex penalty term baked in.

Common Mistake: Students assume maximum likelihood is always a convex problem; it only is when the specific negative log-likelihood happens to be convex, which must be checked case by case.

Important Questions:

• Under what condition is maximum likelihood estimation a convex optimization problem? When the negative log-likelihood function of the parameter is convex, as holds for many (but not all) standard exponential-family distributions.
• What does D-optimal experiment design optimize, and what does that achieve? It maximizes the determinant of the Fisher information matrix over the choice of measurements, minimizing the volume of the parameter estimate’s confidence ellipsoid.

Chapter 8: Geometric Problems

Part II: Applications · Difficulty: Medium · Key topics: projection, distance between sets, Löwner-John ellipsoid, Chebyshev center, linear discrimination, support vector classifiers

The last applications chapter turns convex optimization on purely geometric questions. It starts with projecting a point onto a convex set and computing the distance between two convex sets, both themselves convex problems. It then studies extremal-volume ellipsoids: the Löwner-John ellipsoid is the minimum-volume ellipsoid that contains a given convex set, and the maximum-volume inscribed ellipsoid is the largest one that fits inside it. These feed into centering problems, where the Chebyshev center, the analytic center, and the maximum-volume inscribed ellipsoid’s center all give different, useful notions of the “middle” of a convex region. The chapter covers classification: linear discrimination separates two sets of points with a hyperplane, support vector classifiers extend this by maximizing the margin between the classes, and nonlinear discrimination handles cases a straight hyperplane cannot. It ends with placement and location problems, positioning points or components to minimize cost or distance under spatial constraints.

Key Points:

• Projecting a point onto a convex set, and finding the distance between two convex sets, are both convex optimization problems.
• The Löwner-John ellipsoid is the minimum-volume ellipsoid containing a given convex set.
• The Chebyshev center is the point of a region farthest from every constraint boundary.
• Support vector classifiers extend linear discrimination by explicitly maximizing the margin between two classes.
• Placement and location problems minimize cost or distance subject to spatial constraints, using the same convex machinery.

Memory Tip: Group the three “centers” together — Chebyshev, analytic, and max-volume-inscribed-ellipsoid — as three different convex answers to the same informal question, “where is the middle of this region?”

Common Mistake: Students think a support vector classifier always needs the data to be linearly separable; the chapter’s nonlinear discrimination material is exactly the response to that not being the case in practice.

Important Questions:

• What is the Löwner-John ellipsoid? The unique minimum-volume ellipsoid that contains a given convex set.
• How does a support vector classifier differ from simple linear discrimination? It specifically chooses the hyperplane that maximizes the margin to the nearest points of either class, rather than just any separating hyperplane.

Chapter 9: Unconstrained Minimization

Part III: Algorithms · Difficulty: Hard · Key topics: descent methods, line search, gradient descent, Newton’s method, Newton decrement, affine invariance

The algorithms part opens with the simplest setting: minimizing a convex function over all of R^n, where optimality just means the gradient is zero. Every method in the chapter follows the same descent framework — move from the current point in a descent direction, scaled by a step size chosen either by exact line search or backtracking line search — guaranteed to strictly reduce the objective at each step. Gradient descent takes the direction of steepest decrease in the Euclidean norm; steepest descent generalizes this to other norms. The chapter’s centerpiece is Newton’s method, which forms its step from the function’s second-order (quadratic) approximation, giving a step that is affine-invariant — unlike gradient descent, its behavior does not change under linear changes of coordinates. The Newton decrement measures how close the current point is to optimal, and convergence splits into a damped phase (backtracking line search) followed by a quadratically convergent phase once the iterate is close enough to the optimum.

Key Points:

• Optimality in unconstrained minimization just means the gradient is zero at the point.
• Backtracking line search is a cheap, practical alternative to exact line search for choosing the step size.
• Gradient descent moves in the steepest-descent direction under the Euclidean norm.
• Newton's method uses the Hessian to form a step from the function’s quadratic approximation.
• Newton’s method is affine-invariant — its iterates are unaffected by linear changes of coordinates, a property gradient descent lacks.
• Convergence has two phases: a damped phase, then a quadratically convergent phase near the optimum.

Memory Tip: Remember Newton’s method as “fits a bowl, jumps to its bottom” each iteration — it approximates the function by a quadratic and steps straight to that quadratic’s minimum.

Common Mistake: Students expect Newton’s method to always converge faster than gradient descent from any starting point; its fast quadratic convergence only kicks in once the damped phase has brought the iterate close enough to the optimum.

Important Questions:

• Why is Newton’s method called affine-invariant, and why does that matter? Applying a linear change of variables produces exactly the same sequence of iterates (transformed accordingly), unlike gradient descent, whose progress depends heavily on the problem’s scaling.
• What are the two phases of Newton’s method’s convergence? A damped phase using backtracking line search, followed by a quadratically convergent phase where the step size is 1 and the error shrinks roughly as the square of the previous error.

Chapter 10: Equality Constrained Minimization

Part III: Algorithms · Difficulty: Hard · Key topics: KKT system, equality constrained Newton step, infeasible start Newton method, elimination, Schur complement

This chapter extends Newton’s method to problems with affine equality constraints, Ax = b, where optimality is characterized by a KKT system combining the gradient stationarity condition with dual (Lagrange multiplier) variables. Rather than stepping in the unconstrained direction, the equality constrained Newton method solves this structured KKT linear system directly, producing a step that keeps every iterate feasible while still improving the objective. The infeasible start Newton method relaxes the need to begin at a feasible point at all: it solves a related KKT system that drives both the objective’s optimality conditions and the constraint violation toward zero together — a major practical convenience, since finding any feasible starting point can itself be hard. The chapter ends on solving the KKT system efficiently: elimination methods (block elimination, Schur complements) exploit the system’s special structure, and when the Hessian or constraints are sparse, this can cut the cost of each Newton step well below the generic cubic bound.

Key Points:

• The KKT system for equality constrained problems combines the gradient stationarity condition with the constraint Ax = b.
• Standard equality constrained Newton steps keep every iterate exactly feasible.
• The infeasible start Newton method removes the requirement of starting from a feasible point, driving feasibility and optimality to zero together.
• Elimination and Schur complement techniques solve the KKT system by exploiting its block structure.
• Exploiting sparsity in the Hessian or constraint matrix can reduce the per-step cost well below the generic cubic bound.

Memory Tip: Picture the infeasible start method as “fixing two things at once” — it drives both constraint violation and suboptimality to zero in the same iteration, instead of requiring feasibility as a precondition.

Common Mistake: Students assume any linear-equality-constrained Newton step needs a feasible starting point; the infeasible start variant specifically exists because that is often impractical to arrange.

Important Questions:

• What does the KKT system for an equality constrained problem combine? The stationarity condition on the gradient of the Lagrangian together with the equality constraint Ax = b, solved jointly for the primal step and the dual variables.
• Why does exploiting sparsity matter when solving the KKT system? A dense KKT solve costs roughly cubic time in problem size; when the Hessian or constraint matrix is sparse, factorization methods can solve the same system at a small fraction of that cost.

Chapter 11: Interior-Point Methods

Part III: Algorithms · Difficulty: Hard · Key topics: logarithmic barrier, central path, barrier method, phase I, primal-dual methods, semidefinite/SOCP barriers

The book’s final chapter handles inequality constraints by converting them into a sequence of equality-constrained (or unconstrained) subproblems, using a logarithmic barrier function that adds an increasingly severe penalty as a variable approaches a constraint boundary. As the barrier’s weighting parameter is driven toward zero, the sequence of minimizers traces out the central path, which converges to the true optimum under mild conditions. The barrier method implements this directly: starting from a strictly feasible point, it solves a sequence of barrier subproblems with Newton’s method, decreasing the barrier parameter each time, and stops once the duality gap is small enough. When no feasible starting point is known, phase I methods construct one first using an auxiliary optimization problem. The barrier framework generalizes to generalized inequalities, which is exactly what makes it applicable to semidefinite and second-order cone programs. The chapter closes with primal-dual interior-point methods, which update primal and dual variables together rather than strictly tracking the central path, typically needing fewer iterations.

Key Points:

• The logarithmic barrier function penalizes approaching a constraint boundary, replacing explicit inequality constraints.
• The central path is the trajectory of barrier-subproblem minimizers as the barrier parameter decreases to zero.
• The barrier method solves a sequence of barrier subproblems with Newton’s method, decreasing the barrier parameter each time.
• Phase I methods find an initial strictly feasible point when none is known in advance.
• The barrier approach extends to generalized inequalities, covering semidefinite and second-order cone programs.
• Primal-dual interior-point methods update both sets of variables together and usually need fewer iterations than the plain barrier method.

Memory Tip: Picture the barrier as an electric fence around the feasible region — it gets harder to approach the boundary as the barrier parameter shrinks, so the solver stays strictly inside until convergence.

Common Mistake: Students think interior-point methods only apply to linear and quadratic programs; the chapter’s whole point about generalized inequalities is that the same barrier machinery handles semidefinite and second-order cone programs too.

Important Questions:

• What is the central path? The curve traced by the unique minimizers of the logarithmic-barrier-augmented objective as the barrier parameter is driven toward zero, converging to the original problem’s optimal point.
• How do primal-dual interior-point methods differ from the basic barrier method? They update the primal and dual variables simultaneously at each iteration rather than solving a sequence of barrier subproblems to convergence first, letting them take larger, more efficient steps while retaining the same guarantees.

Appendices: Mathematical and Numerical Background

Appendix · Difficulty: Hard · Key topics: norms, gradients/Hessians, S-procedure, LU/Cholesky factorization, Schur complement, sparse linear systems

The three appendices are reference material rather than narrative chapters. Appendix A gathers the mathematical background the main text leans on without re-deriving: norms and their properties, basic analysis (convergence, topology), function and derivative notation including gradients and Hessians, and core linear algebra facts. Appendix B is a narrower, specialized topic: problems involving exactly two quadratic functions, which are not convex in general but remain tractable — it covers the single-constraint case, the S-procedure for turning a quadratic constraint into a linear matrix inequality, the field of values of a symmetric matrix pair, and the proofs behind strong duality results for this specific nonconvex problem class. Appendix C covers the numerical linear algebra that makes the algorithms of Part III practical: how matrix structure (bandedness, sparsity) affects the true cost of solving a linear system, standard factorizations (LU, Cholesky), block elimination and the Schur complement for structured systems, and methods for underdetermined systems.

Key Points:

• Appendix A is a self-contained reference for norms, basic analysis, and gradient/Hessian notation used throughout the book.
• Appendix B covers problems with exactly two quadratic functions, which can be nonconvex yet still solvable via the S-procedure.
• The S-procedure converts certain quadratic constraints into linear matrix inequalities.
• Appendix C explains LU and Cholesky factorization as the standard tools for solving the linear systems that appear in every Newton step.
• Exploiting sparsity and structure via block elimination and the Schur complement is what makes large-scale algorithms in Part III practical.

Memory Tip: Treat the appendices as the book’s own toolbox — skim Appendix A as a refresher before Chapter 2, and come back to Appendix C only once Chapters 9-11’s algorithms need the numerical linear algebra behind them.

Common Mistake: Students skip the appendices entirely and then get stuck mid-algorithm in Part III wondering how a Newton step is actually solved numerically — Appendix C is exactly where that gap gets filled in.

Important Questions:

• What does the S-procedure do, and where is it used? It converts a condition that one quadratic function is nonnegative whenever another is nonnegative into an equivalent linear matrix inequality, used in Appendix B for problems with exactly two quadratic functions.
• Why does the book include a separate numerical linear algebra appendix? Because the practical cost of every algorithm in Part III depends on how efficiently the underlying KKT/Newton linear systems are solved, and exploiting sparsity via factorizations like LU and Cholesky is what makes large-scale convex optimization computationally feasible.

Download Convex Optimization PDF (Free)

The free PDF of Convex Optimization is hosted on Stephen Boyd’s official Stanford page with Cambridge University Press’s permission. Click below to open it directly from the publisher-approved source.

How to Study This Book

Start with Chapters 1-5 (Part I: Theory) in order — this is the one part of the book you cannot skip or reorder, since Chapter 3’s convex functions build on Chapter 2’s convex sets, and Chapter 5’s duality leans on both. Read Appendix A alongside Chapter 2 if your linear algebra and real analysis need a refresher; it is written as a quick reference, not a teaching chapter, so do not try to read it cover to cover first.

Once Part I is solid, Part II (Chapters 6-8) can be read selectively depending on your course. A statistics-heavy optimization course will focus on Chapter 7 (maximum likelihood, MAP, experiment design); a machine learning or computational geometry course will spend more time on Chapter 8 (classification, SVMs, extremal ellipsoids); a signal-processing or data-fitting course leans on Chapter 6. Few courses cover all three applications chapters in one semester, and that is normal.

Part III (Chapters 9-11) is essential for anyone who will implement a solver or take a numerical optimization or machine learning course that builds its own gradient descent, Newton, or interior-point code. Read Chapter 9 (unconstrained minimization) before Chapter 10 (equality constrained minimization) before Chapter 11 (interior-point methods) — each chapter’s algorithm is a direct generalization of the one before it.

If your course is theory-only (recognizing and formulating convex problems, not implementing solvers), Chapters 1-5 plus Chapter 4’s problem-class catalogue may be the entire syllabus, and Part III can be treated as optional background.

Keep Appendix C close while working through Chapters 9-11 — every Newton step in those chapters reduces to solving a linear system, and Appendix C is where the book explains how that solve is actually done efficiently.

Do not try to memorize the book; it is a reference as much as a textbook. Use the Key Points and Important Questions on this page as a fast way to revise a chapter before an exam, and go back to the full chapter only when a Key Point does not make sense on its own.

Used In These Programs

This book is the standard reference for the Optimization / Convex Optimization course in BS Computer Science and MS programs, and in Engineering electives, at Pakistani universities. Browse all Optimization books, all Linear Algebra books (the main prerequisite), or all Mathematics books.

Who Should Read This

This book is written for MS students and senior-year BSCS or Engineering students taking a convex optimization, numerical optimization, machine learning theory, or control systems course, and for anyone doing research that formulates a problem as an optimization and needs to know whether it is convex. It assumes you already have a solid foundation in multivariable calculus and linear algebra — gradients, Hessians, eigenvalues, and matrix norms are used from Chapter 2 onward without re-explanation, so a dedicated calculus or linear algebra refresher is worth doing first if those are rusty. It is not a good first book on optimization for a student who has not yet taken linear algebra, and it is not a programming tutorial — the book’s own software examples (CVX, CVXPY, and similar modeling tools) are mentioned only briefly and are not the point of the text.

Applicable Universities

This book is useful for MS and senior BSCS/Engineering students at Pakistani universities offering a convex optimization, numerical optimization, or optimization theory course, including NUST, LUMS, FAST-NUCES, GIK Institute, UET, COMSATS, and other HEC-recognized institutions running MS programs in Computer Science, Electrical Engineering, or related fields.

FAQs

• Calculus Volume 1 (OpenStax) — the multivariable calculus (gradients, Hessians) this book assumes from Chapter 2 onward.
• Discrete Mathematics: An Open Introduction — the proof-writing background used throughout the Theory chapters.
• Problem Solving with Algorithms and Data Structures using Python — for implementing the gradient descent, Newton, and interior-point algorithms from Part III.
• Active Calculus — an alternative calculus reference if OpenStax’s style is not a fit.

Convex Optimization stays the field’s standard reference because it treats formulation — recognizing a problem as convex in the first place — as seriously as it treats the algorithms that solve it once formulated. Download the free PDF above, work through the Theory chapters in order, and use the chapter summaries on this page to revise before exams. Browse more Mathematics books for the calculus and linear algebra background this book builds on.

Convex Optimization by Stephen Boyd and Lieven Vandenberghe, Cambridge University Press (2004). Copyright is held by Cambridge University Press, who have “kindly agreed to allow us to keep the book available on the web” — a free, copyright-retained posting, not a Creative Commons licence. All rights to the text remain with Cambridge University Press and the authors; this page links only to the authors’ own official copy and hosts no file.