Convex optimization Created 2026-09-24 Updated 2026-10-13
Convex optimization is a minimization problem with a convex function as its objective function and a convex set of feasible points. For a finite-valued , the problem is to find with for every . The displayed infimum describes its value even when no minimizing point exists. The two convexity requirements concern different objects: the allowed decisions and the scores assigned to them.
A convex set contains the whole line segment between any two of its points:
A convex function lies below the interpolation of its endpoint values:
Thus mixing two allowed decisions preserves feasibility, and the mixed score is no worse than the same mixture of endpoint scores. The objective function may have flat regions or corners. For a strictly convex function, the second inequality is strict when and .
A useful constraint representation is
where are convex functions on a common convex set , and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: allows and but excludes their midpoint . See Boyd and Vandenberghe, Convex Optimization (2004), §4.2.1 for the standard problem form.
Why local information can certify a global answer. Every local minimum of a convex optimization problem is a global minimum, including minima on the boundary. If a feasible point had , points would remain feasible and have value strictly below for every . Taking arbitrarily small contradicts a local minimum at . This argument explains the special power of convexity: a better distant decision would reveal an improving direction immediately nearby.
If a minimizer exists and the objective function is strictly convex on , it is unique. Two distinct minimizers of value would have a feasible midpoint with value strictly below . Existence is a separate question: the exponential function is strictly convex on , but its infimum is approached only as . Even a bounded convex set need not suffice: on also has unattained infimum . A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.
Nor does strict convexity imply differentiability. For , the squared term gives the strict inequality while the triangle inequality gives the weak inequality for the absolute value. At zero the left and right derivatives are and , so no derivative exists there, although zero is the unique minimizer. Such objectives require subgradients or proximal operators rather than an ordinary gradient at every point.
For a differentiable convex function on an open convex set containing , the constrained first-order condition is
Indeed, the subgradient inequality makes this sufficient; taking the one-sided derivative along feasible line segments makes it necessary. At an interior minimizer, both directions are feasible and the gradient must vanish. At a boundary minimizer it can be nonzero: it only needs to make every feasible direction nondecreasing. See Boyd and Vandenberghe, §§3.1.3 and 4.2.3.
A fully computed nearest-point problem. Project onto the half-space by minimizing half the squared Euclidean distance:
The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer violates the inequality. With the convention , the optimization Lagrangian is , where the Lagrange multiplier satisfies . Its Karush-Kuhn-Tucker conditions are
The last two equations give , . The choice is infeasible, so complementary slackness forces . Consequently , giving , and . The Euclidean distance is , rather than the objective function value . The gradient at the answer balances ; the displacement from to is a normal vector to the boundary.
Figure 1.
The nearest feasible point is where an objective contour first touches the half-space boundary
. Details.
There is an exact certificate independent of numerical search. Completing squares gives
For every feasible point, implies . Thus every feasible objective is at least , and attains this bound. More generally the Lagrangian dual problem has objective for . Its maximum is also , illustrating strong duality through matching computed bounds. This makes the example a model for Euclidean projection onto a convex set and the projection step in projected gradient descent.
What the multiplier conditions require. For differentiable convex functions on an open convex set and equalities defined by affine functions, the KKT conditions combine feasibility, , complementary slackness , and stationarity
with unrestricted equality Lagrange multipliers . They suffice to certify a global minimum without an additional regularity assumption: the optimization Lagrangian is convex, stationarity minimizes it, and feasibility with complementary slackness gives the same certificate as above. To guarantee their necessity at an attained finite optimum, a regularity hypothesis suffices: Slater's condition requires some with and . The projection example has the strictly feasible point . See Boyd and Vandenberghe, §§5.2.3 and 5.5.3. This hypothesis guarantees suitable multipliers, not existence of a primal minimizer.
Without regularity, necessity can fail even for convex functions: minimize subject to . The sole feasible point is optimal, but stationarity would require . No Lagrange multiplier works. There is no strictly feasible point, and the gradient of the constraint vanishes at the answer.
The nonconvex contrast. The polynomial has derivative and second derivative . Numerically solving the cubic gives stationary points , , and . Their objective values are respectively , , and , with second derivatives , , and . Hence both outer points are local minima, and the middle point is a local maximum. Since at both ends, its global minimum exists and must be one of the stationary minima: it is the left one. A method stopping at the right local minimum misses a better value by approximately .
Figure 2.
A strictly convex quadratic has one minimum; a tilted quartic has two local minima with different values
. Details.
The practical appeal of convex optimization is the ability to check an answer globally using geometry and matching Lagrangian duality bounds. The projection certificate certifies every feasible alternative at once; the tilted quartic shows why a zero gradient alone cannot do that for general nonlinear optimization.
Historically, an early landmark is Kuhn and Tucker's [ref]. Its §3 explicitly states a regularity hypothesis for inequality-constrained Lagrange multipliers; its discussion of saddle points explains how concave functions support global conclusions for maximization. This documents an early formulation of the multiplier approach; it does not establish sole discovery of today's KKT conditions or of convex optimization as a whole.
Let with one global dual ball. Its support function is , and the proximal operator of a support function gives . The removed component is the convex projection, while the reconstructed image signal is its residual. Projected gradient descent on , , converges for .
Nonexpansiveness of metric projection Created 2026-09-29 Updated 2026-11-05
For a nonempty closed convex set in a Hilbert space, its metric projection onto a closed convex set obeys
This stronger inequality implies nonexpansiveness of metric projection, , by the Cauchy-Schwarz inequality.
Put and . The variational characterization of convex projection gives and . Adding the corresponding inequalities in the common direction yields , which is the displayed estimate.
Thus projection cannot magnify errors in the input, a useful stability property for projected gradient descent and projections onto convex sets. It need not be a strict contraction: projecting two points already in leaves both unchanged. The closedness, convexity and inner-product geometry are essential to this nearest-point theorem.
Interpret the printed Euclidean norm literally on the full vector array . It is a single global norm, not the sum of pixelwise gradient lengths in discrete isotropic total variation. Set and let be its exact adjoint operator for the chosen difference and boundary conventions. The closed dual ball and its image signal are
The set is nonempty, convex and compact, hence closed, because it is a linear image signal of a compact ball in finite dimensions. Euclidean norm duality gives
the support function of .
The metric projection onto a closed convex set uniquely minimizes over . Its variational characterization of convex projection says
Put . This inequality says precisely that . For any , the primal energy satisfies
Completing the square shows that the right side is uniquely minimized by . At that point the inequality is equality, so
This also follows from the proximal operator of a support function and Moreau decomposition: the convex conjugate of is the indicator functional of a constraint set for . The squared fidelity is strictly convex and coercive, so the primal minimizer exists and is unique.
The convex projection in this formula is the removed component , not generally itself. A metric convex projection onto one fixed closed convex set is idempotent. On a right singular vector direction with positive singular value of any nonzero , this denoising map reduces to soft thresholding with a positive threshold, and applying it twice shrinks again. It therefore cannot be such a convex projection for all data. This qualifies the printed convex projection wording while giving the required global gradient-norm projection residual.
Compute by solving the convex dual least-squares problem
Its gradient is and has Lipschitz constant . Projected gradient descent gives
For fixed , the finite-dimensional projected-gradient convergence theorem ensures that converges to a dual minimizer. Reconstruct ; its limit is the unique primal solution even if dual minimizers are nonunique. If , the primal solution is simply and no iteration is needed. For unit-grid forward differences with periodic or zero-difference boundaries, , so is sufficient. Grid-spacing factors or other boundary stencils change this bound.
The normalization here is global. If a pixelwise sum of gradient lengths had instead been intended, the dual feasible set would be a product of pixelwise balls and convex projection would normalize each block separately; it is a different regularizer and should not be silently substituted.
For the discrete Hessian-norm denoising variant, write and use
This is again a compact convex image signal of a Euclidean ball, now under the second-difference adjoint. In suitable conventions is a discrete double divergence, but its exact boundary adjoint is what defines the set. It lies in , so components in are preserved by denoising. Interior second derivatives annihilate affine image signals; whether all such image signals remain in the kernel depends on the boundary convention. With a pixelwise Hessian norm, the corresponding balls would instead be four-component blocks.
Computing is equivalent to minimizing over , since ranges over precisely . Differentiating with the adjoint operator gives , whose Lipschitz constant is . Starting with any , for example zero, the projected-gradient dual total variation algorithm is
The block formula is the Euclidean projection onto a convex set , since it clips each two-dimensional block to a Euclidean ball of radius . Both components must be clipped together for the isotropic block mixed norm.
For the unscaled forward differences, and likewise in the other direction, so . More exactly, for the one-dimensional path difference has eigenvalues , , and the square-grid operator sums two such spectra. Thus . Finite-dimensional projected gradient descent for a convex objective with an -Lipschitz gradient converges from every feasible starting point to a dual minimizer for fixed . The theorem assumes a nonempty closed convex set, a convex differentiable objective with globally Lipschitz gradient, and a nonempty minimizer set. All hold here: is compact and convex, and is a continuous convex quadratic. Finite-dimensional convergence is of the full sequence, rather than only its objective values.
Consequently any fixed step with is safe on this grid; the more conservative is also safe. The dual minimizer need not be unique because has a null space, but and uniquely. For , the gradient penalty vanishes and , so no positive- step restriction is needed.
Let . Since , projected gradient ascent on the nonnegative orthant is
where the positive part is componentwise and one may take .
For , primal projected gradient descent is
Projection onto is itself a constrained quadratic program. The dual method only projects componentwise onto and uses the fixed matrix , so its iterations can be substantially cheaper, especially when can be prefactored and the number of constraints is moderate.
Using the harmless normalization , the squared-loss empirical risk for linear prediction is
with explicit gradient
Starting from any , projected gradient descent with step sizes is
For a fully explicit update, write and . The projection from part (e) is
Every iterate therefore lies in the prescribed hypothesis class, and any convergent run under the standard convex-optimization step-size conditions targets its empirical-risk minimizer.
The hypothesis class and margin loss are
and
Thus this is a positive semidefinite quadratic-form classifier with logistic loss. Its empirical risk, viewed as a function of the matrix parameter, is
Differentiating under the sum shows that
Hence the displayed is exactly , and the algorithm is projected gradient descent on the positive semidefinite trace ball.
The scalar factor multiplying each lies in . Since
we have the uniform gradient bound
Let parametrize the empirical minimizer . Positive semidefiniteness gives
Thus the initial distance from to is at most , while the gradient bound is .
The averaged projected-gradient bound, in its slightly looser form
applies because is convex. Choose
Substitution gives
Projected gradient descent Created 2026-09-24 Updated 2026-11-05
Let be a nonempty closed convex set in a real finite-dimensional Euclidean space, and let be a differentiable convex function. A projected gradient descent step is
The Euclidean projection onto a convex set is single-valued under these assumptions and restores feasibility after the unconstrained gradient descent step. Closedness matters: the nearest point to zero in the convex set does not exist.
This is the proximal gradient method with nonsmooth term equal to the indicator functional of a constraint set, whose proximal operator is . If is -Lipschitz continuous, a standard choice gives the usual convex objective-error bound relative to an existing minimizer.[ref]
For , . Minimizing from with gives , the constrained optimum.
Minimize over using
The pointwise Euclidean projection onto a convex set sends a block to . The gradient of has Lipschitz constant , so finite-dimensional projected gradient descent converges for . On an unscaled square grid with , is safe. Reconstruct ; unused dual directions may make the minimizing nonunique while the primal minimizer is unique.