Convex Optimization

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.

Type

Book

Intellectual base

Review or monograph

Year

2004

DOI

10.1017/cbo9780511804441

ISBN

9780521833783

Link

https://doi.org/10.1017/CBO9780511804441

Cited from

cognitive_science, computer_science, mathematics

Cited by

13 citations across 13 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.

• 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.

• 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.

• Navigation
  • In optimization, gradient descent, evolutionary search, and simulated annealing navigate a configuration space under a locality constraint toward a goal, and "getting stuck in a local minimum" is a navigation failure where the local picture says no neighbor is better while the global goal stays unreachable.

    This sourceStandard reference on gradient descent and line search: local-gradient steps with a fixed step size, the locality constraint distinguishing iterative descent from global search, and local minima as the characteristic failure.

• 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.

• 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.

• 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.

• 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.

Domain-specific

• Linear separability
  • There exist a weight vector and threshold whose signed affine score is strictly positive for every point of one class and strictly negative for every point of the other, with weak conventions handling boundary points.
• Proper Convex Function
  • Boyd and Vandenberghe's extended-value convention shows how positive infinity records points outside an ordinary function's domain; the convention alone does not supply properness or lower semicontinuity.
• Quasiconvex Function
  • Thus no point between two domain points rises above both endpoint values.
• Strong duality
  • A theorem may additionally guarantee primal or dual attainment, but equality of extended optimal values and existence of optimizers are logically distinct claims.

Mechanisms

• Shadow Pricing
  • In optimization it is rigorous: the shadow price of a binding constraint is a genuine marginal value, not a guess.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Links previously used in the corpus

Before the registry existed this work was also linked 2 other ways.

• https://web.stanford.edu/~boyd/cvxbook/ ×5
• https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf ×3

Registry ID ref:5b300aaaa7d3 · see in the full table