Mathematical optimization

Mathematical optimization studies extrema under constraints.

For a convex differentiable objective with convex differentiable inequality constraints, a feasible point satisfying the Karush-Kuhn-Tucker conditions with nonnegative multipliers is a global minimizer.

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

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

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

Newton's method for minimizing a twice differentiable function uses

If ${\nabla }^{2}f⪰mI$ and the Hessian is $M$-Lipschitz near a minimizer $x^{\ast }$, thenThus a sufficiently close initial point has an error exponent that doubles at each iteration.

For differentiable inequality constraints $g_i(x)\le 0$, a regular local minimum has multipliers ${\lambda }_i\ge 0$ satisfyingFor a convex problem under a suitable constraint qualification, these conditions are sufficient for global optimality.

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 minimizes a convex objective over a convex feasible set.

For a convex function $f$, the subdifferential at $x$ isThe point $x$ minimizes $f$ exactly when $0\in \partial f(x)$.

For a real matrix $P$, exactly one of the following holds: there is $\varphi$ with $P\varphi \ge 0$ and $P\varphi \ne 0$, or there is $q>0$ with $P^{T}q=0$. Separating $\mathrm{Im}P$ from the standard simplex proves the result; $q$ may then be normalized to sum to one.

For a convex set $C$ and a differentiable convex objective $F$, projected gradient descent uses

If $\Vert \nabla F(x_i)\Vert \le G$ and $\Vert x_1-x_{\ast }\Vert \le D$, thenIt follows by expanding the squared distance after each projected step, using nonexpansiveness of projection, summing the resulting inequalities, and applying convexity.

At a regular constrained extremum of $f$ subject to $g=0$, the gradients satisfy

Forsuppose the optimizer and multiplier vary smoothly and use $L=f-\lambda (g-b)$. Differentiating the optimum value and using stationarity gives

For a topless rectangular box with dimensions $x,y,z$, volume $V$, and weighted face costan interior optimum equalizes the three terms:The same result and global minimality follow from the arithmetic-geometric mean inequality.

For nonnegative $a_1,\dots ,a_n$,with equality exactly when all the $a_i$ are equal.

Linear programming optimizes a linear function subject to finitely many linear equalities and inequalities.

For $Ax=b$, $x\ge 0$, a feasible vector $x$ is basic when the columns $A_i$ indexed by its positive coordinates are linearly independent. Equivalently, enlarge those columns to a basis, set every nonbasic coordinate to zero, and solve the resulting square system.

If a linear program has an optimal solution, it has an optimal basic feasible solution. Choose an optimum with minimal positive support. A dependence among its active columns gives a feasible two-sided perturbation; optimality makes its objective slope zero, and moving until one coordinate vanishes contradicts minimality.

Linear-fractional programming optimizes a ratio $c^{T}x/d^{T}x$ over a polyhedron on which the denominator is positive.

For $d^{T}x>0$, setThen $d^{T}y=1$, and $Ax=b$ becomes $Ay=bt$, turning a linear-fractional program into a linear program with objective $c^{T}y$.

Every linear maximization program has a dual minimization program whose feasible objective values bound the primal values.

For a primal maximization problem $Ax\le b$, $x\ge 0$, the dual minimizes $b^{T}y$ subject to $A^{T}y\ge c$, $y\ge 0$.

The dual pairsatisfies weak duality because $b^{T}y\le y^{T}Ax=x^T{A}^{T}y\le c^{T}x$ for every feasible pair.

Every feasible dual objective value bounds every feasible primal objective value.

At a primal-dual optimum, each positive variable corresponds to a tight dual constraint and conversely for positive dual variables.

The transportation problem minimizes linear shipping cost while matching prescribed row supplies and column demands.

The transportation polytope is the set of nonnegative matrices with fixed row and column sums.

The positive cells of a nondegenerate transportation basis form a spanning tree in the bipartite graph of supply and demand vertices.

The transportation simplex computes row and column potentials, enters a negative-reduced-cost cell, and pivots around its induced alternating cycle.

The northwest-corner method repeatedly allocates the smaller remaining supply and demand in the current top-left cell to construct an initial transportation basis.

For transportation potentials, the reduced cost is ${\bar{c}}_{ij}=c_{ij}-u_i-v_j$; a negative value identifies an improving entering cell.

Adding a nonbasic edge to a transportation tree creates one cycle; alternating equal additions and subtractions around it preserves every row and column sum.

Integer supplies and demands admit an integer optimum because an integer initial basis and every cycle pivot remain integer.

A matrix is totally unimodular when every square subdeterminant is $0$, $1$, or $-1$; linear programs with such a constraint matrix and integer right side have integral vertices.

The simplex method moves between adjacent basic feasible solutions along improving edges of a feasible polytope until no improving pivot remains.

For $0\le x_i\le 1$, $x_1+x_2+x_3\le 5/2$, and objective $x_1+2x_2+4x_3$, the oriented edge graph has eight improving paths from the origin to the unique optimum $(1/2,1,1)$. Their lengths range from three to five pivots.

A convex set contains every line segment joining two of its points.

The nonnegative orthant consists of vectors whose coordinates are all nonnegative. Its interior is the positive orthant, where every coordinate is positive.

A convex combination of points $x_1,\dots ,x_n$ is a sum

If a convex subset of ${\mathbb{R}}^n$ is invariant under cyclic coordinate permutation, averaging the $n$ cyclic images of $x$ shows thatalso belongs to the set.

A closed half-space is a set of the form $\{x:a^{T}x\le b\}$ for a nonzero vector $a$; it is a convex set and is closed.

The line segment joining vectors $x$ and $y$ is

A convex polytope is a bounded intersection of finitely many closed half-spaces, equivalently the convex hull of finitely many points.

An extreme point of a convex set $C$ is a point $x\in C$ for whichimplies $x=y=z$.

For a nonempty closed convex subset $C$ of a finite-dimensional inner-product space, ${\Pi }_C(x)$ is the unique point of $C$ minimizing $\Vert x-z\Vert$.

For $p\in C$,

The second-order cone, also called the Lorentz cone, is

For $x=(u,t)$ and $\rho =\Vert u{\Vert }_2$,

The convex hull of a set is the set of all finite convex combinations of its points, equivalently the smallest convex set containing it.

Every point in the convex hull of a subset of ${\mathbb{R}}^d$ is a convex combination of at most $d+1$ points of that subset.

The positive semidefinite matrices form a convex cone because nonnegative combinations preserve nonnegative quadratic forms.

For a positive semidefinite matrix, a trace bound is a bound on the sum of its nonnegative eigenvalues.

The positive semidefinite trace ball of radius $s$ isIt is closed and convex, and $\Vert Z{\Vert }_F\le \mathrm{tr}Z\le s$ for every $Z\in {\mathcal{S}}_s$.

If $M⪰0$ has eigenpairs $({\mu }_i,v_i)$ and $\mathrm{tr}M>s$, then its Frobenius projection onto ${\mathcal{S}}_s$ iswhere $\rho >0$ is uniquely determined by ${\sum }_i({\mu }_i-\rho {)}_{+}=s$.

Game theory studies strategic interaction among decision makers.

A mixed strategy is a probability distribution over a player's pure strategies.

A bimatrix game is a finite two-player game specified by one payoff matrix for each player.

A Nash equilibrium is a strategy profile in which no player can increase their expected payoff by changing only their own strategy.

Normalize each player's positive pure-strategy payoff improvements to define a continuous self-map of the product of their mixed-strategy simplices. At a Brouwer fixed point every positive improvement must vanish, giving a Nash equilibrium.

In a two-player zero-sum game, one player’s payoff is the other player’s loss.

A matrix game is a finite two-player zero-sum game whose entry $A_{ij}$ is the row player's payoff when the players choose row $i$ and column $j$.

The row player solves

If the column player has an optimal strategy at value $v$ and a row probability vector $p$ satisfies $p^{T}A\ge v{e}^T$, then $p$ is optimal: it guarantees $v$, while the optimal column strategy prevents every row strategy from exceeding $v$.

If a symmetric invertible payoff matrix satisfies $A^{-1}e\ge 0$, both players may useand the game value is $(e^T{A}^{-1}e{)}^{-1}$.

Forboth players optimally choose cards $1,2,3$ with probabilities $41/50,2/25,1/10$, and the row player's expected payoff is $57/25$.

The finite minimax theorem equates the maximizing player’s security level with the minimizing player’s security level.

An optimal mixed strategy guarantees the value of the game against every opposing pure strategy.

A square game with antisymmetric payoff matrix has value zero.

A dominated strategy can be replaced by another strategy that performs at least as well against every opponent action.

Mathematical finance applies probability and optimization to portfolios, prices, and risk.

An arbitrage is a zero-cost self-financing portfolio whose terminal payoff is nonnegative in every state and strictly positive with positive probability.

A portfolio is self-financing when every change in its asset holdings is paid for entirely by selling or buying assets within the portfolio, with no external cash added or removed.

In expected-utility portfolio choice, an increasing utility function prefers greater wealth, while concavity models aversion to risk.

Expected utility maximization chooses an admissible random payoff $X$ to maximize $\mathbb{E}[U(X)]$.

A utility indifference price for a claim is the cash amount at which optimally buying the claim leaves the investor with the same maximal expected utility as trading without it.

Let $\mathcal{X}$ be a vector space of random variables and supposehas an optimizer for every $y$. If $U$ is increasing and concave, then $F$ is increasing and concave. For concavity, combine optimizers at two values using the same convex coefficient as the values themselves.

If $U$ is concave and $\mathbb{E}Z=0$, thenis concave in $s$. By Jensen inequality, $G(s)\le G(0)$; concavity then makes $G$ nonincreasing on $[0,\infty )$.

For independent return innovations ${\xi }_n$ and a predictable process of holdings ${\theta }_n$, wealth obeysThe investor chooses the holdings to maximize expected utility of terminal wealth.

For terminal utility $U$ and independent return innovations,

If terminal utility is increasing and concave and each Bellman supremum is attained, backward induction shows that every remaining-horizon value function is increasing and concave. Concavity follows by combining optimal portfolios for two initial wealths with the same convex coefficient.

An equivalent martingale measure is a probability measure equivalent to the physical measure under which discounted asset prices are martingales. In a finite one-period market, its existence is equivalent to no arbitrage.

At each period a risky asset in a binomial market has one of two returns, while the risk-free asset grows by a fixed factor. When the risk-free return lies strictly between the two stock returns, the market is arbitrage-free and complete.

If the stock factors are $1+a$ and $1+b$ and the risk-free factor is $1+r$, the discounted stock is a martingale under the probabilityof an up move. The probability of a down move is $(b-r)/(b-a)$.

For one-period successor claim values $V_u,V_d$ and stock prices $S_u,S_d$, the replicating stock holding isThe remaining value is placed in the risk-free asset. In a complete binomial market, backward replication determines the unique no-arbitrage claim price.

At each node of a binomial tree, a claim with next-period values $V_u,V_d$ has valuewhere $q$ is the local risk-neutral probability in a binomial market. For an American claim, replace this continuation value by the maximum of continuation and immediate exercise value.

Let $Q$ be the risk-neutral measure in an $N$-period binomial market. The stock-numeraire measure is defined on terminal events byIf the $Q$-probability of an up move is $q$, its up probability under $\hat{Q}$ isThis change of measure converts discounted expectations containing a factor $S_N$ into probabilities under $\hat{Q}$.

In a finite market, absence of arbitrage is equivalent to the existence of an equivalent martingale measure. If that measure is unique, every contingent claim has a unique no-arbitrage price given by its discounted expectation.

Let $P$ be the state-by-asset matrix of discounted gains. There exists $\theta$ with $Y-P\theta \ge 0$ exactly whenfor every $q\ge 0$ satisfying $P^{T}q=0$. This is the finite-dimensional cone-separation, or Farkas-duality, form of superhedging.

A European call with maturity $N$ and strike $K$ pays $(S_N-K{)}^{+}$ at time $N$.

For European calls and puts with the same maturity and strike,

Conditioning on the first binomial move expresses a call with $N+1$ periods as a positive weighted sum of two $N$-period calls with rescaled strikes.

A forward-start call fixes its strike at a future time as a multiple of the stock price then. In a homogeneous binomial model, its time-zero price reduces to that of an ordinary call over the remaining periods.

A European put with maturity $N$ and strike $K$ pays $(K-S_N{)}^{+}$ at time $N$ and can be exercised only at maturity.

An American option may be exercised at any time up to maturity. Its value is the Snell envelope of its discounted exercise payoff.

An American put has exercise payoff $(K-S_n{)}^{+}$. In a finite binomial market, backward option pricing compares that payoff with the discounted risk-neutral continuation value at every node.

Mean-variance optimization balances expected linear return against a positive-definite quadratic variance penalty.

Without a risk-free intercept or constraints, every undominated linear portfolio lies on the nonnegative ray through $V^{-1}b$.

Let $\xi \sim N(b,\Sigma )$, where $b\ne 0$ and $\Sigma$ is positive definite. For any increasing concave objective of $m+{\theta }^T\xi$, every unique optimal portfolio has the formIndeed, the component orthogonal to ${\Sigma }^{-1}b$ in the $\Sigma$ inner product contributes independent mean-zero Gaussian risk without changing the mean. Removing it cannot reduce expected concave utility. A negative coefficient is dominated by the corresponding positive coefficient, which has the same variance and a larger mean.

A portfolio dominates another when it has no smaller mean and no larger variance, with at least one strict improvement.

Projection onto the mean-variance portfolio $V^{-1}b$ leaves residual covariance $V-b{b}^T/(b^T{V}^{-1}b)$.

A linear functional minus one half of a positive-definite quadratic has the unique maximizer obtained by solving its linear first-order equation.

A positive-definite matrix $V$ defines the inner product $x^{T}Vy$, allowing decomposition into a chosen direction and its $V$-orthogonal complement.