Convex Optimization¶
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Cited by¶
22 citations across 22 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Convexity
- From this single algebraic shape an unusually large number of well-behaved properties follow — local minima coincide with global minima, separating hyperplanes always exist, certificates of optimality become checkable by inspection, and aggregation across many decision-makers behaves predictably — which is why a property that looks like a piece of geometry turns out to govern tractability across many substrates.
This sourceStandard reference establishing that convex sets and convex objectives make optimization tractable (local optimum = global), with duality, separating-hyperplane certificates, and the convex quadratic program.
Supported in partVerified against the work's full text
The text shows a zero gradient of a convex function is a global minimiser and that disjoint convex sets have a separating hyperplane; checkable optimality certificates and aggregation are not shown.
“if ∇f (x) = 0, then for all y ∈ domf ,f (y) ≥f (x), i.e.,x is a global minimizer”
- From this single algebraic shape an unusually large number of well-behaved properties follow — local minima coincide with global minima, separating hyperplanes always exist, certificates of optimality become checkable by inspection, and aggregation across many decision-makers behaves predictably — which is why a property that looks like a piece of geometry turns out to govern tractability across many substrates.
- Intersection
- The simultaneous-membership (AND) test is the defining move: a point $x$ is feasible only if it lies in every half-space at once, so the feasible region is the intersection $\bigcap_i \{x : a_i \cdot x \le b_i\}$ — a convex polytope.
This sourceEstablishes that the feasible region of a linear program is the intersection of half-spaces (a convex polyhedron), monotonically shrinking as constraints are added.
SupportedVerified against the work's full text
The book treats a polyhedron as the solution set of a system of linear inequalities, states that polyhedra are convex sets, and presents a polyhedron as the intersection of five halfspaces with outward normal vectors. A point satisfies such a system only by lying in every halfspace at once, which is the feasible-region structure the sentence describes; the book also records that a bounded polyhedron is sometimes called a polytope. The simultaneous-membership (AND) test is the article's phrasing rather than the work's, and the work notes that authors differ over whether polytope is reserved for bounded polyhedra.
“A polyhedron is thus the intersection of a ... polyhe dra are convex sets.”
- The simultaneous-membership (AND) test is the defining move: a point $x$ is feasible only if it lies in every half-space at once, so the feasible region is the intersection $\bigcap_i \{x : a_i \cdot x \le b_i\}$ — a convex polytope.
- Local Optimum
- In mathematical optimisation it is the canonical home: gradient ascent on a non-convex function halts at a local maximum, and the structural difficulty of non-convex optimisation just is the local-optimum problem.
This sourceTreats local versus global optima and the structural difficulty of non-convex optimization where gradient methods halt at local maxima.
Supported in partVerified against the work's full text
Boyd and Vandenberghe define local optimization as settling for a locally optimal point with no global guarantee; the gradient-ascent halting claim and "just is" framing are not in the text held.
“Instead w e seek a point that is only locally optimal, which means that it minimizes the obje ctive function among feasible points that are near it, but is not guaranteed to hav e a lower objective value than all other feasible points.”
- In mathematical optimisation it is the canonical home: gradient ascent on a non-convex function halts at a local maximum, and the structural difficulty of non-convex optimisation just is the local-optimum problem.
- Optimization
- In mathematics and operations research, optimization spans linear programming (Dantzig's simplex method, 1947 — already FACT-resolved as part of constraint #22 in DP-03), integer programming, convex optimization
This sourceCanonical modern textbook on convex analysis: defines convex functions via the second-order curvature condition (positive semidefinite Hessian) and develops state-dependent marginal effects as the structural fingerprint of convexity.
- In mathematics and operations research, optimization spans linear programming (Dantzig's simplex method, 1947 — already FACT-resolved as part of constraint #22 in DP-03), integer programming, convex optimization
- Projection
- The projected-gradient pattern — do an unconstrained move, then project back to the feasible set — transfers to any setting with hard constraints, recurring as clipping in machine learning, snapping to spec in engineering, and proposal-then-statutory-revision in policy.
This sourceDevelops projection onto convex sets and projected-gradient methods for constrained optimization.
- The projected-gradient pattern — do an unconstrained move, then project back to the feasible set — transfers to any setting with hard constraints, recurring as clipping in machine learning, snapping to spec in engineering, and proposal-then-statutory-revision in policy.
- Subadditivity
- Together with a norm's absolute homogeneity, the triangle inequality makes every norm ball convex; by itself it also turns local component bounds into a bound on a vector sum.
This sourceAuthor-hosted text stating the norm triangle inequality \(f(x+y)\leq f(x)+f(y)\) and its role in norm geometry.
- Together with a norm's absolute homogeneity, the triangle inequality makes every norm ball convex; by itself it also turns local component bounds into a bound on a vector sum.
- Termination Condition
- In optimization and control, convergence criteria for nonlinear solvers, early stopping in training, and branch-and-bound termination on the bound gap all instantiate the pattern.
This sourceStandard reference for stopping/convergence criteria in iterative optimization solvers.
- In optimization and control, convergence criteria for nonlinear solvers, early stopping in training, and branch-and-bound termination on the bound gap all instantiate the pattern.
Domain-specific¶
- Feasible Region
- When the feasible region is convex (as in linear and convex programmes), every local optimum is a global optimum, and gradient-based algorithms converge to the global solution without being trapped in inferior local minima
This sourceThe fundamental property of convex optimization that any locally optimal point is also globally optimal.
Supported in partVerified against the work's full text
“A fundamental property of convex optimization problems is that any locally optimal point is also (globally) optimal.”
- When the feasible region is convex (as in linear and convex programmes), every local optimum is a global optimum, and gradient-based algorithms converge to the global solution without being trapped in inferior local minima
- Indicator function (convex analysis)
- Linear separability
- Proper Convex Function
- Quasiconvex Function
- Strong duality
- Supporting hyperplane
Mechanisms¶
- Constraint Relaxation Probe
- This mirrors the logic of a shadow price, the value revealed by relaxing a binding constraint by one unit: constraints with a high shadow price are the ones worth attacking.
This sourceDefines the shadow-price sensitivity of an active constraint as the marginal change in optimal value produced by relaxing its bound.
- This mirrors the logic of a shadow price, the value revealed by relaxing a binding constraint by one unit: constraints with a high shadow price are the ones worth attacking.
- Linear-Combination Membership Test
- Had the chemist tested membership in the full span (allowing negative coefficients), the target would have looked reachable — and the recipe would have been physically impossible.
This sourceDistinguishes membership in a linear span with unrestricted coefficients from physically suggestive nonnegative (conic) combinations.
- Had the chemist tested membership in the full span (allowing negative coefficients), the target would have looked reachable — and the recipe would have been physically impossible.
- Minimum Service Floor
- As a constraint rather than a target, it lets the system optimize freely above the line while guaranteeing no protected case falls below it — the standard shape of a minimum service standard or an SLA floor.
This sourceSeparates an optimization objective from feasibility constraints, requiring every candidate solution to satisfy each bound.
- As a constraint rather than a target, it lets the system optimize freely above the line while guaranteeing no protected case falls below it — the standard shape of a minimum service standard or an SLA floor.
- Shadow Price Analysis
- The theorem underneath it, complementary slackness, is precise about binding status but says nothing about how far the price extends.
This sourceDerives complementary slackness for binding constraints and interprets optimal multipliers as local shadow prices.
- The theorem underneath it, complementary slackness, is precise about binding status but says nothing about how far the price extends.
- Shadow Price Probe
- The concept of a shadow price is borrowed honestly from optimization, where it is the value of relaxing a binding constraint by one unit — but a shadow price read off human patience conflates willingness to wait with ability to wait, so the well-resourced look like they value the good more.
This sourceDocuments the value of relaxing a binding constraint by one unit.
- The concept of a shadow price is borrowed honestly from optimization, where it is the value of relaxing a binding constraint by one unit — but a shadow price read off human patience conflates willingness to wait with ability to wait, so the well-resourced look like they value the good more.
- Shadow Pricing
- Vector-Space Specification Sheet
- The classic misuse is drafting a sheet for the probability simplex — the set of distributions over outcomes — as though it were a vector space, then adding two distributions and getting a vector that sums to two and is no longer a distribution.
This sourceDefines the probability simplex as nonnegative vectors summing to one, so ordinary addition of two distributions produces a vector summing to two and outside the simplex.
- The classic misuse is drafting a sheet for the probability simplex — the set of distributions over outcomes — as though it were a vector space, then adding two distributions and getting a vector that sums to two and is no longer a distribution.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 5 of 22 citations: 1 supported, 4 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 3 other ways.
- https://web.stanford.edu/~boyd/cvxbook/ ×6
- https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf ×3
- https://www.seas.ucla.edu/~vandenbe/cvxbook.html ×1
Registry ID ref:5b300aaaa7d3 · see in the full table