Mathematical optimization

A constraint imposed with a specified probability when data or demands are random. Distributional assumptions can turn it into a deterministic condition on decision variables. The choice of strict versus non-strict event matters when the distribution has atoms, as in the deterministic boundary in an upper-tail chance constraint.

Deterministic boundary in an upper-tail chance constraint ( $X = m, P (X \geq C) \leq ε < 1 ⟺ C > m$ )

A deterministic demand has probability one of meeting or exceeding its mean. Thus replacing a positive-variance Gaussian chance constraint by its naive zero-variance limit with a non-strict capacity inequality loses the boundary condition. The example

X = 0

C = 0

ε = e^{- 1}

satisfies

m + ϕ v \leq C

for finite

ϕ

, but violates the chance requirement.

Exact Gaussian chance constraint ( $m + Φ^{- 1} (1 - ε) v \leq C$ )

For

X \sim N (m, v)

with

v > 0

and

0 < ε < 1

P (X \geq C) \leq ε

is equivalent to the displayed chance constraint, because the standard normal distribution function is continuous and strictly increasing. The coefficient is a standard normal quantile, which can be negative. If

v = 0

, equality is an atom and the exact condition becomes

C > m

instead.

Variational inequality ( $F (x^{}) \cdot (x - x^{}) \geq 0 (x \in K)$ )

For a feasible set

K

and a vector field

F

, a variational inequality asks for

x^{*} \in K

satisfying the displayed inequality for every feasible

x

. If

K

is convex and

F

is the gradient of a differentiable convex function, it is the necessary and sufficient first-order condition for minimizing that function. It also describes Wardrop equilibria when no scalar objective has the route-cost vector as its gradient.

First-order optimality condition ( $\nabla f (x_{*}) = 0$ )

At an interior local extremum of a differentiable function, its gradient is zero: restricting the function to every line through the point shows that all directional derivatives vanish. This is only a necessary condition in general. For a strictly concave function, an interior stationary point is the unique global maximizer on its convex domain. Constrained or boundary optima instead need conditions adapted to their feasible directions.

Lagrangian duality ( $sup_{λ \geq 0, μ} in f_{u} L (u, λ, μ)$ )

For a minimization problem, the infimum of the optimization Lagrangian over its primal variables gives a lower bound for each allowable multiplier. Maximizing these lower bounds is the Lagrangian dual problem. Weak duality always holds; strong duality requires further hypotheses and holds for feasible bounded linear programs.

Primal problem ( $in f_{x} φ (x)$ )

The original mathematical optimization problem relative to a chosen Lagrangian dual problem. In convex perturbation duality, its objective is

φ (x) = f (x, 0)

and its value is

p (0)

. Strong duality concerns optimal values; primal attainment additionally requires an actual minimizing point.

Maximization problem ( $sup_{u \in F} f (u)$ )

A maximization problem seeks a feasible point with largest objective value. Its supremum can fail to be attained or be infinite. Negating the objective gives a minimization problem. A global extremum of an optimization Lagrangian can certify a feasible optimum by the Lagrangian sufficiency theorem.

Minimization problem ( $in f_{u \in F} f (u)$ )

A minimization problem seeks a feasible point with smallest objective value. Its infimum can be finite without being attained, or equal to

- \infty

when unbounded below. Negating the objective converts it to a maximization problem.

Parametric optimization

A parametric optimization problem has objective or constraints depending on input data. Its optimizer set is a solution map of a parametric optimization problem. Sensitivity analysis asks how this map changes as the data vary.

Solution map of a parametric optimization problem ( $S (a) = argmin_{x} F_{a} (x)$ )

The solution map sends a data parameter

a

to the set of minimizers of the associated objective,

S (a) = argmin_{x} F_{a} (x)

. Existence, uniqueness and local stability are distinct questions. Strong convexity gives uniqueness when a minimizer exists; the Aubin property gives a perturbation bound.

Variational analysis

Variational analysis studies optimization, perturbation stability and generalized differentiation through functions, sets and set-valued mappings. Convex analysis is a foundational special case; limiting normal constructions also handle nonconvex geometry.

Normal cone ( $N_{C} (z)$ )

Normal cones describe generalized supporting directions to sets. For a convex set, the normal condition is

⟨ w, z^{'} - z ⟩ \leq 0

for every

z^{'}

in the set. For nonconvex sets, the Fréchet normal cone and the limiting normal cone distinguish local regular support from limits of such supports.

Limiting normal cone ( $N_{C} (z) = lim sup_{z^{'} \to z} N_{C} (z^{'})$ )

The limiting normal cone consists of limits

w_{k} \to w

of vectors from the Fréchet normal cone

w_{k} \in N_{C} (z_{k})

with

z_{k} \to z

C

. It need not be convex. Including normals from nearby graph pieces is essential to the Mordukhovich criterion.

Fréchet normal cone ( $N_{C} (z)$ )

A vector

w

is a regular normal at

z \in C

when

lim sup_{z^{'} \to z, z^{'} \in C ∖ {z}} ⟨ w, z^{'} - z ⟩ /∥ z^{'} - z ∥ \leq 0

. At an isolated point all vectors satisfy this condition. It is the local first-order supporting cone.

Set-valued analysis

Set-valued analysis studies relations whose output at one input is a set. Solution maps, subdifferentials and generalized normal mappings are important examples. Graph geometry provides definitions of continuity, local stability and differentiation.

Set-valued mapping ( $S : X ⇉ Y$ )

A mapping

S : X ⇉ Y

assigns a subset

S (u) \subset Y

to each

u

. Empty and multiple values are allowed. The graph of a set-valued mapping records the relation as a subset of

X \times Y

Aubin property ( $S (u) \cap V \subset S (u^{'}) + κ ∥ u - u^{'} ∥ B$ )

Near

(\overset{u}{ˉ}, \overset{v}{ˉ})

in a graph, this property requires neighborhoods

U, V

and a finite

κ

such that

S (u) \cap V \subset S (u^{'}) + κ ∥ u - u^{'} ∥ B

for all

u, u^{'} \in U

. Nearby solutions can be matched under nearby perturbations with linear displacement control. Single-valued maps reduce to local Lipschitz continuity.

Mordukhovich criterion ( $D^{*} S (\overset{u}{ˉ} ∣ \overset{v}{ˉ}) (0) = {0}$ )

In finite dimensions, if the graph is locally closed at

(\overset{u}{ˉ}, \overset{v}{ˉ})

, the Aubin property holds exactly when

D^{*} S (\overset{u}{ˉ} ∣ \overset{v}{ˉ}) (0) = {0}

. Thus no nonzero horizontal vector in the limiting normal cone may occur. The exact local Lipschitz modulus is the outer norm of this coderivative.

Graph of a set-valued mapping ( $gph S = {(u, v) : v \in S (u)}$ )

The graph is

gph S = {(u, v) : v \in S (u)}

. Local graph normals encode the Mordukhovich coderivative and hence the Aubin property. Graph closedness is a local hypothesis in the sensitivity criterion.

Limiting coderivative ( $D^{*} S (\overset{u}{ˉ} ∣ \overset{v}{ˉ})$ )

The limiting coderivative is

D^{*} S (\overset{u}{ˉ} ∣ \overset{v}{ˉ}) (v^{*}) = {u^{*} : (u^{*}, - v^{*}) \in N_{gph S} (\overset{u}{ˉ}, \overset{v}{ˉ})}

. The negative sign on the output dual is essential. For a smooth single-valued function it gives the transpose Jacobian acting on

v^{*}

Pareto efficiency

An outcome is Pareto efficient when no feasible alternative weakly improves every agent's utility and strictly improves at least one. For strict preference orders over distinct alternatives, an outcome unanimously ranked below another is inefficient. Onto strategyproof social choice functions on an unrestricted domain are Pareto efficient: rank-raising monotonicity and unanimity rule out selecting a unanimously dominated alternative.

Pareto frontier

The Pareto frontier consists of feasible payoff vectors that no other feasible vector weakly improves in every coordinate and strictly improves in at least one. A Nash bargaining solution with positive gains lies on this frontier, because increasing either gain without decreasing the other raises its Nash product.

Approximation algorithm

An approximation algorithm efficiently returns a feasible solution with a proved performance guarantee relative to the optimum. The guarantee must specify whether the problem is a maximization or minimization problem.

Approximation ratio ( $α$ )

For maximization, an approximation ratio

α \in (0, 1]

means the returned feasible value is at least

α

times the optimal value on every permitted instance. Some conventions instead report its reciprocal; specify the convention.

Integer programming

An integer program optimizes an objective under constraints with some or all variables restricted to integers. Its continuous relaxation removes those integrality restrictions; a relaxed optimum bounds the integer optimum in the appropriate direction.

Branch and bound

A branch-and-bound search partitions a feasible set, maintains a feasible incumbent, and prunes subproblems using bounds that cannot improve that incumbent. For a quadratic knapsack problem, fixing a selected set

S

adds its exact quadratic value as a constant and replaces remaining profits by

v_{i} + 2 \sum_{j \in S} p_{ij}

under the ordered-pair convention. Residual fractional row bounds for quadratic knapsack and a Lagrangian knapsack bound can then be recomputed. Worst-case search remains exponential.

Knapsack problem

The knapsack problem selects items of prescribed weights and profits under a total-weight capacity. The 0-1 knapsack problem permits each item at most once; bounded and unbounded multiplicity variants use different integer restrictions. Nonnegative weights and capacity are assumed here.

Quadratic knapsack problem ( $max {v^{T} x + \sum_{i \neq = j} p_{ij} x_{i} x_{j} : w^{T} x \leq B, x \in {0, 1}^{n}}$ )

The quadratic knapsack problem includes pairwise interactions between selected items. For symmetric

p_{ij}

, a sum over all ordered pairs counts each unordered interaction twice; an alternative convention sums only over

i < j

. The objective convention must be kept consistent when bounding or fixing variables.

Fractional row bound for quadratic knapsack ( $q_{i} = max {\sum_{j \neq = i} p_{ij} y_{j} : \sum_{j \neq = i} w_{j} y_{j} \leq B - w_{i}, 0 \leq y_{j} \leq 1}$ )

Conditioning on selecting item

i

leaves capacity

B - w_{i}

. Its fractional knapsack problem bounds that item's total interaction with the other selected items. Thus the ordered-pair quadratic objective is at most

\sum_{i} (v_{i} + q_{i}) x_{i}

. Remove overweight items before defining their residual-capacity problems.

Fractional knapsack problem ( $0 \leq x_{i} \leq 1$ )

This linear programming relaxation allows a fraction of each item. With positive weights, sort decreasing profit-to-weight ratios and fill capacity in that order, using at most one fractional item. An exchange argument proves optimality. Negative-profit items are omitted and positive-profit zero-weight items are included for free.

0-1 knapsack problem ( $max {v^{T} x : w^{T} x \leq B, x \in {0, 1}^{n}}$ )

This binary integer program selects each item at most once. Exact optimization is NP-hard; the fractional knapsack problem gives an upper bound and supports a half-approximation algorithm for knapsack.

Half-approximation algorithm for knapsack ( $ALG \geq \frac{1}{2} OPT$ )

After removing overweight items and handling free items, compare the feasible density-sorted prefix with the best feasible singleton. The fractional knapsack problem optimum is at most the sum of their profits, so the better solution has approximation ratio

1/2

Cutting-plane method

A cutting-plane method repeatedly adds valid inequalities that exclude a current relaxed solution while preserving all feasible integer solutions. Gomory fractional cuts provide such inequalities from a fractional simplex dictionary.

Gomory fractional cut ( $\sum_{j} {a_{j}} x_{j} \geq {b}$ )

For an all-integer dictionary row

x_{B} + \sum_{j} a_{j} x_{j} = b

with nonnegative variables, this cut follows because

x_{B} + \sum_{j} ⌊ a_{j} ⌋ x_{j}

is an integer and

\sum_{j} {a_{j}} x_{j} \geq 0

. Consequently that integer is at most

⌊ b ⌋

. Negative coefficients use the usual fractional part

u - ⌊ u ⌋

, so

{- 1/5} = 4/5

. Normalize a resulting inequality sensibly before introducing a new integer-valued slack variable.

Gomory infeasibility certificate from a fractional slack row

For a nonnegative all-integer row

x_{B} + \sum_{j} a_{j} x_{j} = b

with

a_{j} > 0

, the Gomory fractional cut requires

\sum_{j} {a_{j}} x_{j} \geq {b}

. The original row gives

\sum_{j} a_{j} x_{j} \leq b

. If a constant

κ

satisfies

{a_{j}} \leq κ a_{j}

for every

j

and

κb < {b}

, these inequalities contradict the cut. A single row therefore certifies integer infeasibility. Slacks may be used as integer variables when the original constraint coefficients and right sides are integral and the decision variables are integral.

Travelling salesman problem

Given finitely many locations and pairwise travel costs, find a cyclic visiting order minimizing the sum of its costs. For Euclidean distance this becomes the Euclidean travelling salesman tour problem.

Metric travelling salesman problem

This is the travelling salesman problem on a complete graph with nonnegative symmetric distances satisfying the triangle inequality. Repeated visits can be shortcut without increasing cost. Assigning distance one to edges of an input graph and two to its nonedges creates a metric instance with a tour of cost at most the number of vertices exactly when the graph has a Hamiltonian cycle. Thus the metric problem remains NP-hard.

Christofides algorithm ( $ALG \leq \frac{3}{2} OPT$ )

Compute a minimum spanning tree, then a minimum-weight perfect matching on its odd-degree vertices. Their multiset union is connected with even degrees, so it has an Euler circuit. Shortcut repeated vertices to obtain a metric tour. The tree costs at most the optimal tour, and shortcutting the optimal tour to its odd-degree subset gives a cyclic order whose alternating matchings show that the added matching costs at most half the optimum. The result is a polynomial-time

3/2

-approximation algorithm for symmetric metric instances.

Euclidean travelling salesman tour ( $TS (X)$ )

A closed polygonal tour through a finite point set, measured using Euclidean distance. Write

TS (X)

for the minimum length over cyclic visiting orders. A two-point tour traverses its segment twice; a one-point tour has length zero. The triangle inequality allows repeated visits to be shortcut when estimating this minimum.

Weighted mismatch bound for Euclidean tours ( $TS (x) - TS (y) \leq \sum_{i : x_{i} \neq = y_{i}} a_{i} (x)$ )

For every configuration

x

in the unit square there are nonnegative weights

a_{i} (x)

such that

\sum_{i} a_{i} (x)^{2} \leq 16

and

TS (x) - TS (y) \leq \sum_{i : x_{i} \neq = y_{i}} a_{i} (x) for every y .

Use the sums of the two incident edge lengths in a tour from the squared edge bound for tours in the unit square. Runs of missing vertices can be added by the cheaper of two out-and-back detours. This connects Euclidean travelling salesman tours to Talagrand's convex distance inequality.

Squared edge bound for tours in the unit square ( $\sum_{i} ∥ x_{i + 1} - x_{i} ∥^{2} \leq 4$ )

Every finite point set in the unit square admits a cyclic visiting order with

\sum_{i} ∥ x_{i + 1} - x_{i} ∥^{2} \leq 4

. Split the square into two right triangles, apply the quadratic path bound in a right triangle, and remove auxiliary corners using the law of cosines. The Cauchy-Schwarz inequality then gives

TS (X) \leq 2 ∣ X ∣

. The tour minimizing ordinary length need not minimize the sum of squared lengths.

Quadratic path bound in a right triangle ( $\sum_{e \in P} ∣ e ∣^{2} \leq ∣ a - b ∣^{2}$ )

Given finitely many points in a right triangle with hypotenuse endpoints

a, b

, there is a path from

a

b

visiting them all with sum of squared edge lengths at most

∥ a - b ∥^{2}

. Repeated altitude subdivision reduces to cells containing one point. Joining the child paths preserves the squared-cost bound by the Pythagorean theorem; deleting an auxiliary right-angle vertex preserves it by the law of cosines.

Randomized rounding

A method turning a solution of a continuous optimization relaxation into a random feasible solution of a discrete problem. An expected objective bound can give an approximation guarantee. Gaussian hyperplane rounding and Rademacher rounding for a semidefinite relaxation are different examples.

Gaussian hyperplane rounding

Given a real unit-vector Gram matrix

Y_{ij} = ⟨ v_{i}, v_{j} ⟩

, draw a standard Gaussian random vector

Z

and set

y_{i} = sign ⟨ v_{i}, Z ⟩

. Each coordinate is almost surely a sign; zero projections have probability zero. The same random separating hyperplane is used for every coordinate, so the signs need not be independent. Their pair expectations follow the Gaussian sign-correlation identity.

Krivine rounding scheme

For a bipartite elliptope matrix

X

, put

t = lo g (1 + 2)

and apply

sinh (t x)

within the two diagonal blocks and

sin (t x)

across them. Matching absolute power series coefficients give a positive semidefinite matrix by coefficient-dominated entrywise positivity, while

sinh t = 1

gives unit diagonal. Gaussian hyperplane rounding then turns each cross-block correlation coefficient into

(2/ π) arcsin (sin (t X_{ij})) = (2 t / π) X_{ij}

because

t < π /2

. The zero diagonal blocks of the bipartite objective eliminate every other contribution.

Bipartite sign rounding bound

For bipartite binary quadratic optimization, if

v^{*}

is the sign optimum and

p_{SDP}^{*}

its semidefinite relaxation of binary quadratic optimization value, then

c_{K} p_{SDP}^{*} \leq v^{*} \leq p_{SDP}^{*}

. The upper bound follows from rank-one lifting. For the lower bound, Krivine rounding scheme preprocessing followed by Gaussian hyperplane rounding has expected objective exactly

c_{K} p_{SDP}^{*}

, and every rounded vector is feasible. Some outcome reaches at least this expectation. No independence of rounded coordinates or positive semidefiniteness of the original bipartite objective is needed.

Krivine rounding constant ( $c_{K} = \frac{2}{π} lo g (1 + 2)$ )

The Krivine rounding scheme yields

c_{K} = 0.56109985 \dots

as its guaranteed objective factor. It is obtained by normalizing

sinh t = 1

, so

t = arsinh (1)

and

c_{K} = 2 t / π

. This proof gives a valid universal factor for the bipartite sign problem, not a proof that it is optimal.

Quadratic optimization

Optimization of a quadratic form or quadratic-plus-linear objective over specified constraints. Convexity depends on the matrix and feasible domain; discrete restrictions lead to binary quadratic optimization.

Binary quadratic optimization

Optimization of a quadratic form over binary choices, here using signs

x_{i} \in {- 1, 1}

. Lifting

x x^{T}

turns the objective into a matrix trace; dropping the rank-one condition gives a semidefinite relaxation of binary quadratic optimization.

Bipartite binary quadratic optimization

For a real rectangular matrix

S

, maximize

p^{T} Sq

over separate sign choices for

p

and

q

. With

x = (p, q)

, the symmetric block matrix

A = \frac{1}{2} (0 S^{T} S 0)

satisfies

x^{T} A x = p^{T} Sq

. Its zero diagonal blocks allow the Krivine rounding scheme to linearize the cross-block expected objective.

Optimal transport

Optimal transport minimizes the cost of moving one probability measure to another. The Monge optimal transport problem uses a transport map; the Kantorovich optimal transport problem allows a transport plan that can split mass.

c-cyclical monotonicity ( $\sum_{i} c (x_{i}, y_{i}) \leq \sum_{i} c (x_{i + 1}, y_{i})$ )

A set of source-destination pairs has this property if every finite cyclic reassignment of destinations cannot lower its total cost. A transport plan has the property if it is concentrated on such a set. For a general cost, this is stronger than a two-point monotonicity test.

Finite-cost optimal transport converse

An optimal transport plan of finite cost for a finite continuous cost function is c-cyclically monotone. A strict violation at finitely many support points persists in small product neighborhoods; subtracting small normalized pieces and inserting cyclically re-paired product measures preserves both marginals and strictly improves the finite cost. The finite-value hypothesis matters: if every competitor has infinite cost, a nonmonotone plan may still be an extended-value minimizer.

Strong c-monotonicity ( $u (x) + v (y) \leq c (x, y), u + v = c π -a.e.$ )

A transport plan is strongly c-monotone if Borel Kantorovich potentials satisfy the displayed feasible inequality everywhere and equality almost everywhere for the plan. Extended values

- \infty

away from the full marginal-measure sets may be permitted. This is a potential certificate, not a strict version of every cyclic inequality. A finite continuous cost allows the transport potential path construction.

Symmetric clipping proof of transport optimality ( $u_{n} = max (- n, min (u, n)), v_{n} = max (- n, min (v, n))$ )

For a nonnegative cost, simultaneous symmetric clipping preserves feasibility of a pair of Kantorovich potentials. On their equality set the clipped sums are nonnegative and increase to the cost. Their bounded integrals are fixed by the marginals, so monotone convergence theorem proves optimality without subtracting undefined infinite marginal integrals.

Transport potential path construction

Anchor a countable dense subset of a closed c-cyclically monotone support. Take the infimum of accumulated differences

c (x_{j + 1}, y_{j}) - c (x_{j}, y_{j})

along chains ending at a variable point. Cyclical monotonicity bounds this potential below on the support projection. Its cost transform gives the other potential, with equality on the support. Continuity makes both potentials upper semicontinuous and thus Borel.

Monotone rearrangement

For an atomless measure

μ

R

with cumulative distribution function

F

, the monotone transport to a target with quantile function

G^{- 1}

T = G^{- 1} \circ F

, defined

μ

-almost everywhere. It minimizes well-defined costs

d (x - y)

for convex continuous

d

. With atoms in the source, the common-quantile transport plan

(F^{- 1}, G^{- 1})_{#} U (0, 1)

remains available but need not be induced by a map.

One-dimensional quadratic transport uniqueness criterion ( $π {x \leq a, y \leq b} = min {F (a), G (b)}$ )

For atomless source and target probabilities with continuous strictly increasing cumulative distributions, the squared-distance optimal coupling is unique. Two-point optimality forbids crossed support pairs. This makes every pair of source and target lower-tail events nested up to null sets and forces the displayed joint distribution, which is the common-quantile coupling and is induced by

G^{- 1} F

Knott–Smith optimality criterion

For probability measures on

R^{d}

with finite second moments, a transport plan minimizes the quadratic cost exactly when it is concentrated on the graph of the subdifferential of a sequentially lower semicontinuous proper convex function.

Brenier theorem

For probability measures on

R^{d}

with finite second moments and a source satisfying absolute continuity of measures with respect to Lebesgue measure, the quadratic Kantorovich optimal transport problem has a unique optimal transport plan. It is induced by the gradient of a convex function, which also uniquely solves the Monge optimal transport problem up to a source-null set.

Kantorovich optimal transport problem

The Kantorovich problem minimizes

\int c (x, y) d π (x, y)

over transport plans

π

with marginal distributions

μ, ν

. It relaxes the Monge optimal transport problem by allowing source mass to split among destinations.

Transport cost function ( $c : X \times Y \to [0, \infty]$ )

The transport cost function assigns a cost to a unit of mass moved from

x

y

. A transport plan has total cost

\int c d π

. Costs separating as

a (x) + b (y)

have the same well-defined total for every coupling of fixed marginals.

Kantorovich duality theorem

For probability measures defined as Borel measures on Polish spaces and a nonnegative sequentially lower semicontinuous cost, the minimum cost over transport plans equals the supremum of

\int u d μ + \int v d ν

over integrable Kantorovich potentials satisfying

u (x) + v (y) \leq c (x, y)

. The primal minimum is attained; a dual maximum needs additional assumptions. Compact metric spaces and a finite continuous cost suffice for attainment of both extrema.

Kantorovich duality by positive extension

For compact metric spaces and a continuous cost, define the marginal functional

ℓ (f (x) + g (y)) = \int f d P + \int g d Q

. Its majorant envelope

p (h) = in f_{s \geq h} ℓ (s)

is finite and sublinear. The dual value is

- p (- c)

. Assign that value to the cost direction and use the dominated Hahn-Banach theorem to obtain a positive linear functional on all continuous functions of two variables. The Riesz-Markov-Kakutani representation theorem turns it into an optimal transport plan with the prescribed marginals.

Kantorovich potential

Kantorovich potentials are the functions in the dual of the Kantorovich optimal transport problem. A feasible pair satisfies

u (x) + v (y) \leq c (x, y)

and provides a lower bound

\int u d μ + \int v d ν

for every transport plan. An optimal pair attaining the dual value provides an optimality certificate.

Transport plan ( $π \in Π (μ, ν)$ )

A transport plan is a coupling of probability distributions

μ, ν

, that is, a probability measure on the product space with those marginal distributions. Unlike a transport map, it need not be concentrated on the graph of a function.

Monge optimal transport problem

Given a cost

c

and probability measures

μ, ν

, the Monge problem minimizes

\int c (x, T (x)) d μ (x)

over measurable transport maps with pushforward measure

T_{#} μ = ν

. The feasible set may be empty because a map cannot split an atom of a measure.

Transport map ( $T$ )

A transport map from

μ

ν

is a measurable function

T

satisfying

T_{#} μ = ν

. Its graph defines the transport plan

(Id, T)_{#} μ

Measure-preserving parametrization of one-dimensional transport maps ( $T = G^{- 1} \circ S \circ F$ )

When source and target have continuous strictly increasing cumulative distributions, all transport maps are obtained by choosing a Lebesgue-measure-preserving map

S

on the unit interval. The maps

F

and

G

turn the two measures into uniform measure. The choice

S = id

gives the monotone rearrangement.

Lagrange sufficiency theorem

For maximizing

f

subject to

g_{i} (x) \geq 0

and

h_{j} (x) = 0

, suppose a feasible

x^{*}

and multipliers

λ_{i} \geq 0, μ_{j}

satisfy complementary slackness and

x^{*}

globally maximizes

L (x) = f (x) + \sum_{i} λ_{i} g_{i} (x) + \sum_{j} μ_{j} h_{j} (x) .

Then

x^{*}

globally maximizes

f

on the feasible set. Convexity or concavity hypotheses are commonly used to prove the required global extremum of the Lagrangian from first-order conditions.

Scalar multiplier certificate for a quadratic equality constraint ( $∥ c ∥^{2} / (4 λ^{2}) - λ / (2 γ) = R$ )

For

γ > 0

and

c \neq = 0

, minimize

c^{T} u + γ z^{2}

subject to

∥ u ∥^{2} + z = R

. Adding a positive Lagrange multiplier times the constraint gives a positive-definite quadratic optimization Lagrangian, whose minimizer is

u = - c / (2 λ)

and

z = - λ / (2 γ)

. Feasibility is the displayed scalar equation. Its left side strictly decreases from positive infinity to negative infinity on

λ > 0

, so it has a unique root for every real

R

. The Lagrangian sufficiency theorem certifies a unique global optimum on the possibly nonconvex equality surface.

Dynamic programming

 2  0

Dynamic programming solves a multistage optimization problem backwards by expressing each remaining-horizon value in terms of the next-stage value.

Retirement threshold with multiplicative capture risk

If a successful step in action

i

has expected reward

a_{i} \geq 0

and survival probability

q_{i} = 1 - p_{i}

, a finite-horizon retirement problem with zero wealth after capture has threshold

max_{i} a_{i} q_{i} / p_{i}

. Above it, induction makes retirement optimal; below it, a single further step already beats retirement. The threshold does not depend on the remaining positive horizon.

Bellman equation

A Bellman equation is the recursive optimality relation for the value function of a dynamic programming problem.

Bellman comparison with nonnegative rewards and superunit discount ( $β \geq 1, r \geq 0$ )

For nonnegative rewards, a nonnegative value satisfying the maximizing Bellman equation dominates every competing policy, even for

β \geq 1

. Iterate the one-step inequality, discard the nonnegative terminal value, then apply the monotone convergence theorem to the accumulated reward.

Hamilton-Jacobi-Bellman equation

The Hamilton--Jacobi--Bellman equation is the continuous-time Bellman equation. For state dynamics

\overset{x}{˙} = f (x, u, t)

, running cost

L (x, u, t)

and terminal cost

Φ (x)

, a smooth value function satisfies

V_{t} + in f_{u} {L + \nabla V \cdot f} = 0, V (x, h) = Φ (x) .

Linear-quadratic optimal control

A linear-quadratic optimal-control problem has linear state dynamics and running and terminal costs defined by quadratic forms. Its value function is quadratic in the state, the optimal feedback is linear, and its coefficient obeys a Riccati equation.

Discrete Riccati recurrence

A backward scalar or matrix recurrence for the quadratic coefficients in a value function for a linear-quadratic optimal control problem. It results from completing the control square in the Bellman equation. Multiplicative noise modifies the quadratic coefficients through its second moments.

Value function

 2  0

A value function assigns each state and time the best objective attainable from that state over the remaining decisions.

Bayesian box search problem

A hidden object lies in box

i

with posterior probability

p_{i}

. Searching box

i

costs

c_{i}

and, conditional on the object being there, detects it with probability

α_{i}

. After an unsuccessful search of box

i

, Bayes theorem updates the probabilities to

p_{i}^{(i)} = \frac{( 1 - α _{i} ) p _{i}}{1 - α _{i} p _{i}}, p_{j}^{(i)} = \frac{p _{j}}{1 - α _{i} p _{i}} (j \neq = i) .

Optimal index for Bayesian box search ( $α_{i} p_{i} / c_{i}$ )

When search continues until discovery, expected search cost is minimized by searching at each step a box maximizing

α_{i} p_{i} / c_{i}

. An adjacent-interchange argument compares two searches: placing

i

before

j

costs less exactly when

α_{i} p_{i} / c_{i} \geq α_{j} p_{j} / c_{j}

Rewarded Bayesian box search Bellman equation

If discovery in box

i

earns reward

R_{i}

and stopping earns zero, the Bellman equation is

V (p) = max {0, max_{i} [- c_{i} + α_{i} p_{i} R_{i} + (1 - α_{i} p_{i}) V (p^{(i)})]} .

\sum_{i} c_{i} / (α_{i} R_{i}) < 1

, every posterior state has some

i

with

α_{i} p_{i} R_{i} > c_{i}

, so stopping is never optimal.

Newton method

Newton's method for minimizing a twice differentiable function uses

x_{k + 1} = x_{k} - [\nabla^{2} f (x_{k})]^{- 1} \nabla f (x_{k}) .

Quadratic convergence bound for Newton's method

\nabla^{2} f ⪰ m I

and the Hessian is

M

-Lipschitz near a minimizer

x^{*}

, then

∥ x_{k + 1} - x^{*} ∥ \leq \frac{M}{2 m} ∥ x_{k} - x^{*} ∥^{2} .

Thus a sufficiently close initial point has an error exponent that doubles at each iteration.

Karush-Kuhn-Tucker conditions

For differentiable inequality constraints

g_{i} (x) \leq 0

, a regular local minimum has multipliers

λ_{i} \geq 0

satisfying

\nabla f + \sum_{i} λ_{i} \nabla g_{i} = 0, λ_{i} g_{i} = 0.

For a convex problem under a suitable constraint qualification, these conditions are sufficient for global optimality.

Active-set transition in capped resource allocation

In a convex resource-allocation problem, tightening an upper bound can change its multiplier from zero to positive. The optimum then moves from a point where only the total-resource constraint is active to the intersection where both constraints are active.

Convex optimization

Convex optimization minimizes a convex objective over a convex feasible set.

Chambolle–Pock algorithm

For a saddle point problem

min_{u} max_{v} {F (u) + ⟨ D u, v ⟩ - G (v)}

, one update ordering is

u^{k + 1} = prox_{τ F} (u^{k} - τ D^{*} v^{k}), v^{k + 1} = prox_{σ G} (v^{k} + σ D (2 u^{k + 1} - u^{k})) .

The proximal operators treat both nonsmooth convex terms, while the extrapolation

2 u^{k + 1} - u^{k}

couples the primal and dual variables. The primal objective is

F (u) + G^{*} (D u)

, with

G^{*}

the convex conjugate. A dual-first ordering is obtained by exchanging roles; consistent indexing is needed when comparing the formulas.

Convergence of primal-dual hybrid gradient ( $τ σ ∥ D ∥^{2} < 1$ )

For proper lower semicontinuous convex functions on finite-dimensional Hilbert spaces, a nonempty saddle point set, and constant positive steps satisfying the displayed inequality, the primal-dual hybrid gradient method with extrapolation parameter one converges to a saddle point. The strict condition controls the bilinear coupling by the operator norm. It does not remove the need for existence of a saddle point. The fixed-step theorem and assumptions are recalled in Malitsky and Pock, A first-order primal-dual algorithm with linesearch, Section 1.

Convex positively one-homogeneous functional ( $J (t u) = t J (u) (t \geq 0)$ )

This is a proper convex function that has degree-one positive homogeneity, with

J (0) = 0

. It need not be even or nonnegative; linear functionals are examples. Its subdifferential satisfies

p \in \partial J (u) ⟺ ⟨ p, u ⟩ = J (u) and ⟨ p, z ⟩ \leq J (z) for every z .

The two tests

z = 0

and

z = 2 u

prove equality; the subgradient inequality then gives the global upper bound. Conversely that bound and equality prove the subgradient condition. Hence a subgradient at

u

also supports every nonnegative multiple of

u

. Requiring

J (- u) = J (u)

gives an absolutely one-homogeneous functional.

Generalized eigenfunction in the forward-operator metric ( $λ K^{*} K u \in \partial J (u)$ )

A nonzero

u

satisfying this relation, with

K u \neq = 0

, generalizes the eigenfunction of an absolutely one-homogeneous functional to the quadratic geometry induced by the forward map. Pairing with

u

yields

λ = J (u) /∥ K u ∥^{2}

. With unit data norm it is a generalized singular vector. If

λ > 0

0 \leq α λ \leq 1

and the exact data are

K u

, the vector

(1 - α λ) u

minimizes the quadratic variational regularization objective. Substitute its raywise subgradient into the subgradient optimality condition. Every minimizing branch has the same predicted data, and injectivity of

K

gives equality of vectors. The Bregman distance along this ray is zero even though the reconstruction is shrunk. For nonnegative

J

the branch continues as

(1 - α λ)_{+} u

; nonnegativity supplies

0 \in \partial J (0)

for the threshold argument.

Background on these generalized singular vectors: Benning and Burger, Ground States and Singular Vectors of Convex Variational Regularization Methods.

Conic optimization

Optimization of a linear function subject to affine constraints and membership in a closed convex cone. Choosing the positive semidefinite cone gives semidefinite programming; other choices include copositive optimization and completely positive optimization. Dual cones produce scalar-product bounds on feasible objectives.

Farkas lemma ( $A z = b, z \geq 0 or A^{T} y \geq 0, b^{T} y < 0$ )

Exactly one of the two displayed systems is feasible. Closedness of finitely generated cones and the Fenchel-Moreau theorem applied to a cone's indicator functional provide a proof through its polar cone. It yields a nonnegative multiplier certificate when a finite system of linear inequalities is inconsistent.

Farkas certificate for linear inequalities ( $C^{T} y = 0, y \geq 0, d^{T} y < 0$ )

Such a vector certifies that

C x \leq d

has no solution: the nonnegative weighted sum of the constraints would give

0 \leq d^{T} y < 0

. Conversely, Farkas lemma supplies one whenever the system is inconsistent.

Interior-point method

An interior-point method solves constrained mathematical optimization problems by maintaining variables in the interiors of their feasible cones or inequality domains. Barrier derivatives are defined there, and damped Newton methods keep subsequent iterates in their domains. A central path gives a family of barrier-regularized optima whose duality gap approaches zero; a conic phase-I problem can supply a strict feasible starting point.

Conic phase-I problem

An auxiliary conic optimization problem searches for strict feasibility before following a central path. Given

e \in int K

, minimizing

t

subject to

A x - b + t e \in K

and

t \geq - 1

has a strict feasible start for sufficiently large

t

. Any feasible solution with

t < 0

certifies

A x - b \in int K

. If the original problem is strictly feasible, a small negative

t

is feasible. Equality constraints and dual feasibility require their corresponding auxiliary procedures.

Self-concordant barrier ( $F, ν$ )

A convex three-times differentiable barrier

F

is self-concordant when

∣ D^{3} F (x) [h, h, h] ∣ \leq 2 (D^{2} F (x) [h, h])^{3/2} .

A barrier of parameter

ν

additionally satisfies

∣ D F (x) [h] ∣ \leq ν D^{2} F (x) [h, h]

and diverges at the domain boundary. Logarithmically homogeneous cone barriers satisfy

F (t x) = F (x) - ν lo g t

. The orthant barrier

- \sum_{i} lo g x_{i}

has parameter equal to the dimension, while the Lorentz-cone barrier

- lo g (t^{2} - ∥ z ∥^{2})

t > ∥ z ∥

has parameter two. Their Hessians define Dikin ellipsoids and control interior Newton steps.

Logarithmically homogeneous barrier ( $F (t s) = F (s) - ν lo g t$ )