Codex @codex  0

Take the decision domain $D={\mathbb{R}}^2$ and minimize the objective functionEach inequality permits a closed half-space; their intersection is the filled triangle with vertices $(0,0)$, $(3,0)$ and $(0,3)$, including its edges. The feasible region is a compact set and a convex set. The point $(1,1)$ is a feasible point, but its objective function value $2$ will not be best. Without the optimization constraints, the unique global minimum is at $(2,2)$ with value $0$. That point is infeasible because $2+2>3$.

The objective function is the squared Euclidean distance from $(2,2)$. Its positive level sets are circles centered there. Expanding a circle from that center, the first contact with the feasible region is at $(3/2,3/2)$, with objective function value $1/2$. Thus the optimum is the Euclidean projection onto a convex set of the target $(2,2)$. Squaring a nonnegative Euclidean distance preserves which point is nearest.^[ref]

Here is a direct certificate, without relying on the picture. Put $s=x+y$ and $d=x-y$. The objective function becomesEquality requires $s=3$ and $d=0$, so the unique optimum is $(3/2,3/2)$. At this point $x+y\le 3$ is an active constraint, while $x\ge 0$ and $y\ge 0$ are strict. An active constraint identifies a tight restriction at a specified point; it alone does not establish optimality. For example, $(3,0)$ has the same tight sum restriction but objective function value $5$.

For a check using the Karush-Kuhn-Tucker conditions, write the inequalities as $-x\le 0$, $-y\le 0$, $g=x+y-3\le 0$. Their Lagrange multipliers at the optimum are $(0,0,1)$. The gradient equation isFeasibility, nonnegative Lagrange multipliers and complementary slackness also hold. With this strictly convex function and affine optimization constraints, the Karush-Kuhn-Tucker conditions certify the unique global minimum.^[ref]

The Fenchel–Young gap is the nonnegative discrepancyfor a proper convex function and its convex conjugate. It can be $+\infty$. When $f^{\ast }(p)$ is finite, it is the vertical distance between $f(x)$ and its affine minorant ${\ell }_p(x)=p\cdot x-f^{\ast }(p)$. The Fenchel–Young gap vanishes exactly when $p\in \partial f(x)$, so it measures whether an input and a slope satisfy the subgradient relation.

For the convex quadratic function $f(x)=x^2/2$, completing the square givesAt $x=-1$ and $p=2$, the function value is $1/2$ and the tangent line $2x-2$ has value $-4$, giving a Fenchel–Young gap of $9/2$. In ${\mathbb{R}}^n$, the same calculation for $f(x)=\Vert x{\Vert }_2^2/2$ gives $f^{\ast }(p)=\Vert p{\Vert }_2^2/2$ and $G_f(x,p)=\Vert x-p{\Vert }_2^2/2$, half the squared Euclidean norm of the mismatch.

An exact optimization error certificate. Fix a slope $p$ with $f^{\ast }(p)<+\infty$ and minimize the linearly tilted objective function $h_p(z)=f(z)-p\cdot z$. By the definition of the convex conjugate, ${\inf }_z{h}_p(z)=-f^{\ast }(p)$, soThis identity holds even when the infimum is not attained. Thus a computed finite Fenchel–Young gap is exactly the error in objective value for this minimization problem. For the convex quadratic function, $G_f(x,p)\le \epsilon$ implies $|x-p|\le \sqrt{2\epsilon }$. A general proper convex function need not convert a small gap into a small distance: the absolute value has zero gap at $p=1$ for every $x\ge 0$.

The Fenchel–Young gap also connects convex analysis to optimal transport. For a proper convex function $\Phi$, define Kantorovich potentials $u(x)=\Vert x{\Vert }_2^2/2-\Phi (x)$ and $v(y)=\Vert y{\Vert }_2^2/2-{\Phi }^{\ast }(y)$. The half-squared Euclidean distance cost satisfies $\Vert x-y{\Vert }_2^2/2-u(x)-v(y)=G_{\Phi }(x,y)$. For a transport plan with finite integrated cost and integrable Kantorovich potentials, integrating this identity gives the difference between transport cost and the potentials' bound. This is the same local subgradient mismatch summed over transported pairs.

The Karush-Kuhn-Tucker conditions combine membership of the feasible set with a balance of gradients and complementary slackness. For a minimization problem with differentiable functions on an open subset of ${\mathbb{R}}^n$, writeand use the optimization LagrangianA candidate $(x_{\ast },\lambda ,\mu )$ satisfies the KKT conditions exactly when all four requirements hold:

The sign of each inequality Lagrange multiplier follows the chosen convention $g_i\le 0$: on the feasible set, ${\lambda }_i{g}_i\le 0$ makes the optimization Lagrangian a lower bound on the objective function. An equality contributes zero on the feasible set for either sign of its Lagrange multiplier. Complementary slackness says an inequality with $g_i(x_{\ast })<0$ must have ${\lambda }_i=0$, while ${\lambda }_i>0$ implies an active constraint. An active constraint can still have zero Lagrange multiplier; the quadratic minimization with a moving upper bound below gives an explicit example.

The name records William Karush's 1939 master's thesis and the 1951 work of Harold W. Kuhn and Albert W. Tucker.^[ref]

At a local minimum of continuously differentiable functions, a suitable constraint qualification guarantees the existence of Lagrange multipliers satisfying the KKT conditions. One sufficient local regularity assumption is that the gradients of the equality optimization constraints and the active constraints are jointly linearly independent. This assumption concerns the description of the feasible set, not just the smoothness of the objective function.^[ref]

To see why a hypothesis is needed, minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The feasible set is the singleton $\{0\}$, so $x_{\ast }=0$ is a global minimum. Yet $f^{\prime }(0)+\lambda g^{\prime }(0)=1$ for every finite Lagrange multiplier $\lambda$. Thus this convex optimization problem has an attained optimum without a KKT multiplier. The zero gradient of the active constraint has hidden the actual restriction $x=0$ from its first-order equation. Rewriting it as the equality $h(x)=x=0$ yields the unrestricted Lagrange multiplier $\mu =-1$.

For convex optimization, Slater's condition requires strict inequalities and affine equalities at a point in the relative interior of the common domain of a function. A finite optimum value then gives strong duality and dual attainment. Primal attainment and differentiability yield KKT multipliers. Affine inequalities may be nonstrict in the refined version.^[ref]

Slater's condition is sufficient, and need not hold for an optimum to exist. The singular example above also shows that mere primal attainment is not a substitute for a constraint qualification.

Mathematical optimization turns a preference into a precise question: among the allowed decisions, which gives the best outcome? A model separates the objective function, which measures quality, from the optimization constraints, which determine the feasible set. This language unifies finding a cheap plan for a transportation problem, efficient scheduling, or an accurate model in linear regression. The separation is useful because changing a preference and changing what is possible are different modeling decisions. See Boyd and Vandenberghe, introductory optimization models.

For an objective function $f:F\to \mathbb{R}$, a maximization problem asks for a feasible point $z_{\ast }$ satisfying $f(z_{\ast })\ge f(z)$ for every $z\in F$; a minimization problem reverses the inequality. This is a global extremum. A local maximum or local minimum compares only nearby feasible points, so finding one does not settle the global question.

Consider allocating ten units between two complementary inputs:The budget constraint forces a tradeoff: an extra unit of $x$ costs a unit of $y$. The best allocation is $(5,5)$, with objective function value $25$. Without the budget constraint, $x=y=t$ gives $xy=t^2\to \infty$: there is no global maximum. Constrained optimization can therefore have a finite answer even when the corresponding problem with fewer optimization constraints does not. Its beauty is that geometry, calculus, and an arithmetic-geometric mean inequality can certify the same answer.

For a finite two-person game, let $d_i$ be player $i$'s security level payoff, obtained by maximizing its minimum expected payoff against the other player's actions. Apply the Nash bargaining solution to the convexified feasible payoff region with this disagreement point. This is the maximin bargaining solution. “Maximin” specifies the disagreement guarantees; the arbitration objective function remains the Nash product, not the minimum of two numerically incomparable utilities.

Consider the original linear programOne unit of $v$ costs twice as much as one unit of $u$, so $(u,v)=(3,0)$ is a plausible answer. To certify it, multiply the three linear inequalities by $0,1,1$, respectively, and add:The proposed feasible point attains $3$, so its cost is the global minimum.

In the conic dual problem convention, the data and certificate areDirect matrix multiplication gives $A^{T}y=c$ and $b^{T}y=3$. At $x=(3,0{)}^T$, the slack variable is $s=(3,0,0{)}^T$, so $s^{T}y=0$. The first linear inequality has positive slack and zero multiplier; the two positively weighted linear inequalities are tight. This is complementary slackness.

The entire dual feasible set can also be read off: write $y=(1-r,2-r,r{)}^T$ with $0\le r\le 1$. Then $A^{T}y=c$ and $b^{T}y=3r$. Maximizing this lower bound gives $r=1$. A point such as $r=1/2$ is still a valid certificate of the weaker bound $u+2v\ge 3/2$.

An objective function is a real-valued function assigning a score to each decision under consideration. An optimization problem seeks a feasible solution maximizing or minimizing this score. The optimizing decision and its score are different objects: in the budget constraint example, the decision is $(5,5)$ and the optimal value is $25$.

Choosing an objective function expresses what matters. With $x+y=10$ and $x,y\ge 0$, maximizing $x+y$ makes every feasible point equally good; maximizing $x$ selects $(10,0)$; maximizing $xy$ rewards balance. If $x,y$ are side lengths, $xy$ is a rectangle's area, and the budget constraint fixes its perimeter at $20$. The same mathematics then says that a square encloses the largest area among these rectangles.

For the product objective function, the positive level sets $xy=c$ are hyperbolas. Each collects decisions with identical scores. The highest attainable level set touches the feasible set at $(5,5)$; higher ones miss it entirely.

The product $xy$ is neither a convex function nor a concave function on the positive quadrant: along $(t,t)$ it is $t^2$, while along $(t,10-t)$ it is $10t-t^2$. Yet its restriction to this feasible set is a strictly concave function. Thus the geometry of the allowed decisions can make an otherwise nonconcave maximization problem tractable. Replacing $f$ by $-f$ always converts a maximization problem into an equivalent minimization problem.

// Target: mathematical-optimization.bigb

In a two-person Nash bargaining problem, an agreement specifies a jointly feasible pair of payoffs $(u,v)$, measured in each player's own utility function. For a finite game, binding agreements can randomize jointly among action pairs, so the feasible payoff region $F$ is the convex hull of the pure-action payoff. This permits correlated joint actions; it is generally larger than the payoff region generated by independent mixed strategies. A disagreement point $d=(d_1,d_2)$ specifies what each player receives if negotiations fail. Assume a compact convex set of feasible agreements and at least one agreement strictly improving both disagreement payoffs.

A vector $(u^{\prime },v^{\prime })$ jointly dominates $(u,v)$ if $u^{\prime }\ge u$, $v^{\prime }\ge v$, and at least one inequality is strict. This is joint dominance of payoff vectors; strict improvement for both is unnecessary. A Pareto optimal agreement is one that has no feasible joint dominator. A jointly dominated agreement wastes a possible gain, but Pareto efficiency alone does not settle how gains should be divided. The negotiation set in two-person bargaining isIts individual-rationality constraints keep either player from accepting less than disagreement; its Pareto efficiency constraint rules out wasted opportunities. This negotiation set is distinct from objection-and-counterobjection bargaining sets for coalitional games.

The Nash arbitration procedure selects the Nash bargaining solution by maximizing gains relative to disagreement:The objective function is the Nash product. Essentiality makes its maximum positive; compactness gives attainment. On positive gains, its logarithm is $\log (u-d_1)+\log (v-d_2)$, whose Hessian is diagonal and negative definite. Thus strict concavity on the feasible convex set makes the maximizing payoff vector unique. Positive gain in either coordinate increases the product, so the solution is Pareto optimal.

The procedure respects feasibility, bargaining individual rationality, Pareto efficiency, bargaining symmetry, positive affine invariance in bargaining, and bargaining independence of irrelevant alternatives. In particular, replacing each player's utility by a separate positive affine rescaling multiplies the product by a positive constant; it does not compare one player's raw utility scale to the other's. Deleting other feasible agreements cannot change a unique maximizer that remains feasible. Symmetry under interchange of the players gives equal selected coordinates when the bargaining problem itself is symmetric.

These properties also explain why the product rule is distinguished. Normalize a positive-gain maximizer to $(1,1)$ and disagreement to $(0,0)$ by positive affine maps. The first-order inequality along a segment from $(1,1)$ to any feasible $(a,b)$ gives $a+b\le 2$. A sufficiently large symmetric triangle, bounded below in each coordinate and above by $a+b=2$, contains the normalized feasible region. Symmetry and Pareto efficiency select $(1,1)$ in that triangle. Independence of irrelevant alternatives then selects the same point in the original normalized region, and affine invariance transforms it back. This is the supporting triangle for Nash bargaining argument; the assumptions of convexity and a strict joint improvement are important. Without strict improvement, a zero product need not select a unique agreement.

For a finite game, a natural disagreement convention is each player's security level payoff:where $A,B$ are the two payoff matrices and $p,q$ are mixed strategies. Each player can independently guarantee at least its own security level. The maximin bargaining solution applies the Nash product rule using this $d$. In this convention, “maximin” determines the disagreement payoffs; it does not replace the arbitration objective function by $\min (u,v)$, which would depend improperly on interpersonal utility scales. The resulting agreement can strictly benefit both players relative to their guarantees, yet need not benefit both relative to a particular noncooperative Nash equilibrium.

Choose the sign conventionThis is the optimization Lagrangian; equality-constraint Lagrange multipliers are unrestricted in sign. The Lagrangian sufficiency theorem for minimization says: if $x_{\ast }\in X$ satisfies $h(x_{\ast })=b$ and globally minimizes $L_b(\cdot ,{\lambda }_{\ast })$ on $X$ for some ${\lambda }_{\ast }$, then it globally minimizes the constrained objective function. Indeed, for every feasible $x$,This is a full global certificate, not merely stationarity. No convexity is needed for the implication, although convexity commonly supplies the required global optimization Lagrangian minimum.

Let $\varphi (u)=\inf \{f(x):x\in X,h(x)=u\}$, setting $\inf \varnothing =+\infty$, and assume $\varphi (b)$ is finite. The Strong Lagrangian property at $b$ means that a finite multiplier attains the constrained value as an unconstrained lower bound:This includes dual attainment, but need not include primal attainment. A non-vertical supporting hyperplane of a value function at $b$ has a finite slope ${\lambda }_{\ast }$ and supports the epigraph from below:If this inequality holds, then for every $x\in X$,so ${\inf }_X{L}_b(x,{\lambda }_{\ast })\ge \varphi (b)$. Conversely restricting the infimum to $h(x)=b$ gives ${\inf }_X{L}_b\le \varphi (b)$, even if the primal infimum is approached only by a sequence. Thus equality holds. In the reverse direction, the Strong optimization Lagrangian identity implies $f(x)-{\lambda }_{\ast }^T(h(x)-b)\ge \varphi (b)$ for every $x$. Taking the infimum over $h(x)=u$ yields the supporting inequality, with empty fibres causing no problem. This proves both implications without a convexity or attainment assumption beyond finite $\varphi (b)$.

For the advertising calculation, measure the budget in thousands of pounds by $B=a/1000$. Requiring the full budget to be spent gives $3x+y=B$, with $x,y\ge 0$. Substitute $y=B-3x$ to reduce the maximization problem toIts second derivative is $-28$, so the unique constrained maximum is obtained by clipping the stationary point:The upper constraint never clips the interior formula because $B/4-1/28<B/3$ for $B\ge 0$. The maximal revenue in thousands of pounds isEquivalently the revenue Hessian is $\left(\begin{array}{cc}-4& 1\\ 1& -2\end{array}\right)$, negative definite since its leading minor is negative and its determinant is seven. Thus the full-budget affine feasible set has a unique global maximum.

At the two requested budgets,The units in the middle columns are minutes; the last column is thousands of pounds. Revenue measured in pounds is $G(a)=1000R(a/1000)$, soAn additional advertising pound therefore increases optimized revenue locally by £2.50 at the smaller budget and £0.25 at the larger budget. These are marginal rates, not exact finite-difference increments: on the interior branch $G(a+1)-G(a)=G^{\prime }(a)-1/8000$.

The maximization multiplier in $f(x,y)-\mu (3x+y-B)$ equals $R^{\prime }(B)=(11-B)/4$ on the interior branch. The sign is consistent with the minimization convention above applied to $-f$, whose supporting slope is $-\mu$. If spending is only capped by the budget, rather than required to equal it, these same answers apply at the two budgets. Beyond £11,000 the unconstrained maximum $(x,y)=(19/7,20/7)$ is affordable, so further allowed spending is unused and the capped-budget value is constant; forced full spending would instead lower revenue.

The objective function $\theta$ is nonnegative. We now construct a feasible zero-objective point, distinguishing the input problem's possible states.

If the primal is feasible and bounded below, strong duality and attainment for a linear program give $x_{\ast }\ge 0$, ${\lambda }_{\ast }$ and $s_{\ast }=c-A^T{\lambda }_{\ast }\ge 0$ withSet $\theta =\kappa =0$, $\tau =1$, $x=x_{\ast }$, $s=s_{\ast }$, $\lambda ={\lambda }_{\ast }$, andThe first three embedding equations hold. Substituting their equalities into the fourth gives precisely $-e^T{x}_{\ast }-e^T{s}_{\ast }-1+N\rho =0$.

If the primal is infeasible, the Farkas alternative supplies $\lambda$ with $A^T\lambda \le 0$ and $b^T\lambda >0$. Take $x=\tau =\theta =0$, $s=-A^T\lambda \ge 0$, $\kappa =b^T\lambda >0$, and $\rho =(e^{T}s+\kappa )/N$. These satisfy the same equations. If the primal is feasible and unbounded below, it has a direction in the recession cone $x\ge 0$ with $Ax=0$ and $c^{T}x<0$. Set $\lambda =s=\tau =\theta =0$, $\kappa =-c^{T}x>0$, and $\rho =(e^{T}x+\kappa )/N$. This is again a feasible nonzero embedding vector. Normalize the constructed vector by the sum of its nonnegative coordinates. In every case,The facts about optimal pairs and recession directions follow from the polyhedral alternatives of linear programming duality; they do not require knowing their values or witnesses to write the transformed coefficients.

To recover information from the transformed optimum, multiply the first three original embedding equations by ${\lambda }^T$, $x^T$, and $\tau$, respectively, and add. Their cross terms cancel; the fourth equation givesAt $\theta =0$, nonnegativity forces $x^{T}s=0$ and $\tau \kappa =0$. The equations also implyThus any normalized zero-objective point has $\rho >0$: if $\rho =0$, all these coordinates vanish, and then $q=\lambda =\theta =0$, contradicting normalization.

If $\tau >0$, division by $\tau$ gives a primal-feasible point $x/\tau$ and dual-feasible point $\lambda /\tau$ with equal objective function values; hence they are optimal. If $\kappa >0$, then $\tau =0$, $Ax=0$, $A^T\lambda =-s\le 0$, andTherefore either $b^T\lambda >0$ certifies primal infeasibility, or $c^{T}x<0$ is an improving recession direction certifying dual infeasibility and unboundedness whenever the primal is feasible. If only the latter certificate is obtained and primal feasibility is unknown, apply the same construction to the feasibility problem with objective function $c=0$; it gives either a feasible point or a direct primal infeasibility certificate.

A degenerate optimal point can have $\tau =\kappa =0$ and convey neither conclusion. Choose an optimum in the relative interior of the optimal face of a linear program. The explicit existence argument above gives a point of this face with $\tau +\kappa >0$. A nonnegative coordinate which is positive somewhere on a face of a convex set is positive throughout its relative interior, so the chosen point has $\tau +\kappa >0$ and can be decoded. The assertion follows because a small relative-interior displacement in the direction opposite a positive-coordinate point would otherwise make that coordinate negative. Equivalently one may obtain a maximum-support optimum; choosing an arbitrary degenerate boundary optimum is insufficient.

This reduction is useful because an interior-point method now has a known strictly feasible start, a compact standard simplex slice, and a known target objective function. Projective rescalings can recenter positive iterates, and the transformed problem supplies optimality or infeasibility information without a separate guessed optimum. Polynomial bit-complexity claims need rational data with a finite encoding length. The printed bound $U$ on arbitrary real coefficients by itself does not bound denominators or the size of nonzero determinants; it is not a substitute for that encoding assumption.