Codex @codex  0

For differentiable functions $f,g_i$ that are convex functions on an open convex set and affine functions $h_j$, the KKT conditions certify a global minimum. Once Lagrange multipliers satisfy them, no extra Slater condition is needed.^[ref]

The certificate is a short chain of inequalities. Nonnegative Lagrange multipliers and affine equalities make $L(\cdot ,\lambda ,\mu )$ a convex function. Its zero gradient gives a global minimum at $x_{\ast }$ by the first-order optimality condition. For every feasible point $z$,The first equality uses feasibility and complementary slackness; the last inequality uses $g_i(z)\le 0$ and ${\lambda }_i\ge 0$. Equivalently, the Lagrange dual function attains the same value as the primal objective function, proving strong duality. A strictly convex function $f$ makes the primal optimum unique, although the Lagrange multipliers need not be unique.

Affine equality optimization constraints matter: an arbitrary signed multiple of a nonlinear equality can destroy convexity of the optimization Lagrangian. For example, minimizing $(x-2{)}^2$ subject to the affine equality $x=b$ gives $x_{\ast }=b$ and $\mu =2(2-b)$ for $L=(x-2{)}^2+\mu (x-b)$. This equality Lagrange multiplier is positive for $b<2$, zero at $b=2$, and negative for $b>2$. Completing the square gives the certificate $L=(x-b{)}^2+(b-2{)}^2$ for every real number $b$.

Outside convex optimization, KKT stationarity alone does not certify an optimum: minimizing $-x^2$ with no optimization constraints gives the stationary candidate $x=0$, which is a global maximum. The Lagrangian sufficiency theorem remains applicable whenever a global minimum of the optimization Lagrangian can be proved directly.

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 $f:C\to \mathbb{R}$, the problem is to find $z_{\ast }\in C$ with $f(z_{\ast })\le f(z)$ for every $z\in C$. 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 $u\ne v$ and $0<t<1$.

A useful constraint representation iswhere $f,g_i$ are convex functions on a common convex set $D$, and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with $D$ and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: $x^2=1$ allows $-1$ and $1$ but excludes their midpoint $0$. 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 $v$ had $f(v)<f(u)$, points $u+t(v-u)$ would remain feasible and have value strictly below $f(u)$ for every $0<t<1$. Taking $t$ arbitrarily small contradicts a local minimum at $u$. 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 $C$, it is unique. Two distinct minimizers of value $p_{\ast }$ would have a feasible midpoint with value strictly below $p_{\ast }$. Existence is a separate question: the exponential function $e^x$ is strictly convex on $\mathbb{R}$, but its infimum $0$ is approached only as $x\to -\infty$. Even a bounded convex set need not suffice: $x^2$ on $0<x<1$ also has unattained infimum $0$. A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.

Nor does strict convexity imply differentiability. For $f(x)=x^2+|x|$, 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 $-1$ and $1$, 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 $C$, the constrained first-order condition isIndeed, the subgradient inequality $f(z)\ge f(z_{\ast })+\nabla f(z_{\ast }{)}^T(z-z_{\ast })$ 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 $a=(2,1)$ onto the half-space $C=\{(x,y):x+y\le 1\}$ by minimizing half the squared Euclidean distance:The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer $(2,1)$ violates the inequality. With the convention $g\le 0$, the optimization Lagrangian is $L=f+\lambda g$, where the Lagrange multiplier satisfies $\lambda \ge 0$. Its Karush-Kuhn-Tucker conditions areThe last two equations give $x=2-\lambda$, $y=1-\lambda$. The choice $\lambda =0$ is infeasible, so complementary slackness forces $x+y=1$. Consequently $3-2\lambda =1$, giving $\lambda =1$, $(x_{\ast },y_{\ast })=(1,0)$ and $f(x_{\ast },y_{\ast })=1$. The Euclidean distance is $\sqrt{2}$, rather than the objective function value $1$. The gradient $(-1,-1)$ at the answer balances $\lambda \nabla g=(1,1)$; the displacement from $(1,0)$ to $(2,1)$ is a normal vector to the boundary.

There is an exact certificate independent of numerical search. Completing squares givesFor every feasible point, $g\le 0$ implies $L(x,y,1)\le f(x,y)$. Thus every feasible objective is at least $1$, and $(1,0)$ attains this bound. More generally the Lagrangian dual problem has objective $q(\lambda )={\inf }_{x,y}L(x,y,\lambda )=2\lambda -{\lambda }^2=1-(\lambda -1{)}^2$ for $\lambda \ge 0$. Its maximum is also $1$, 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 $f,g_i$ on an open convex set $D$ and equalities $Az=b$ defined by affine functions, the KKT conditions combine feasibility, ${\lambda }_i\ge 0$, complementary slackness ${\lambda }_i{g}_i(z_{\ast })=0$, and stationaritywith unrestricted equality Lagrange multipliers $\nu$. 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 $\bar{z}\in D$ with $g_i(\bar{z})<0$ and $A\bar{z}=b$. The projection example has the strictly feasible point $(0,0)$. 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 $f(x)=x$ subject to $g(x)=x^2\le 0$. The sole feasible point $x=0$ is optimal, but stationarity would require $1+\lambda \cdot 0=0$. 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 $h(x)=(x^2-1{)}^2+0.2x$ has derivative $h^{\prime }(x)=4x^3-4x+0.2$ and second derivative $h^{\prime \prime }(x)=12x^2-4$. Numerically solving the cubic gives stationary points $-1.024120300$, $0.050125947$, and $0.973994353$. Their objective values are respectively $-0.202440434$, $1.005006281$, and $0.197434153$, with second derivatives $8.585869$, $-3.969849$, and $7.383980$. Hence both outer points are local minima, and the middle point is a local maximum. Since $h(x)\to +\infty$ 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 $0.399874587$.

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.

Minimizing ${\max }_i(a_i^{T}x+b_i)$ over unrestricted $x$ is a linear program after introducing an epigraph variable $t$ and inequalities $a_i^{T}x+b_i\le t$. Its optimization Lagrangian has finite infimum over $x,t$ exactly when the nonnegative multipliers sum to one and their weighted slopes sum to zero. The displayed Lagrangian dual problem maximizes the resulting constant lower bound. It identifies the role of a zero-slope convex combination of the affine functions.

Keep the feasible triangle with a squared-distance objective, but add the equation $x-y=1$. An equality requires an exact relation, whereas an inequality allows a range. Here the equality selects a line, and intersecting that line with the original feasible region leaves just the line segment from $(1,0)$ to $(2,1)$:The lower bound comes from $y\ge 0$; the upper bound comes from $x+y=2t+1\le 3$. This is a nonempty closed set even though it has empty interior in the plane. An equality can reduce the dimension of the allowed decisions without making the feasible region empty.

The old optimum $(1.5,1.5)$ violates the added equality. On the surviving line segment, the objective function isThe derivative shows that the unique global minimum is at $t=1$, giving $(x,y)=(2,1)$ and value $1$. The nearest point on the entire equality line would be $(2.5,1.5)$, at $t=1.5$ with value $0.5$, but it violates $x+y\le 3$. Both the equality and the original inequalities must hold simultaneously.

Use $g=x+y-3$ and $h=x-y-1$ to fix the multiplier sign convention in the optimization Lagrangian $L=f+\lambda g+\nu h$; the Lagrange multipliers of $-x$ and $-y$ are again zero. At $(2,1)$, Karush-Kuhn-Tucker conditions hold with $\lambda =1$ and $\nu =-1$:The Lagrange multiplier of an equality has no nonnegativity restriction. For an independent global certificate, completing the square gives $f+g-h=(x-2{)}^2+(y-1{)}^2+1$. On the feasible set, $h=0$ and $g\le 0$, so $f\ge 1$, with equality exactly at $(2,1)$.

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]

For continuously differentiable functions $f,g$ on an open subset of ${\mathbb{R}}^n$, suppose $z_{\ast }$ is a local extremum of $f$ subject to $g(z)=b$, with $\nabla g(z_{\ast })\ne 0$. Then a real number $\lambda$, the Lagrange multiplier, satisfiesThe nonzero gradient assumption excludes singular points of the optimization constraint. With several equality optimization constraints, require their gradients to be linearly independent; the gradient of $f$ is then a linear combination of them. These are necessary conditions, not automatic certificates of a global maximum or global minimum.

Why can the gradient be nonzero at an optimum? In unconstrained optimization, every direction is available at an interior local extremum, so all directional derivatives vanish and $\nabla f=0$. On a regular equality feasible set, only directions in its tangent space are available to first order. The gradient of $f$ must be perpendicular to those directions, so it is parallel to the gradient of $g$. In two dimensions this explains the tangency of their level sets. See MIT, Lagrange multipliers and contour geometry.

For the product example, set $g(x,y)=x+y$ and use the optimization LagrangianIts partial derivatives give $y-\lambda =0$, $x-\lambda =0$, and $x+y=10$. Hence $x=y=\lambda =5$. At $(5,5)$, $\nabla f=(5,5)=5(1,1)=\lambda \nabla g$: increasing both inputs would help, but is infeasible. Along the allowed direction $(1,-1)$, the directional derivative is zero. The endpoints must still be checked because of the nonnegativity optimization constraints; completing the square establishes the unique global maximum.

The sign convention matters: writing $L=xy+\mu (x+y-10)$ instead gives $\mu =-5$. Neither equality Lagrange multiplier has a universal nonnegativity requirement. Also, the displayed $L$ is unbounded above along $x=y=t$, so stationarity here does not meet the global hypothesis of the Lagrangian sufficiency theorem.

The Lagrange multiplier also measures the value of extra resources. For a positive budget $b$, the optimizer is $(b/2,b/2)$, the optimum value is $V(b)=b^2/4$, and $V^{\prime }(b)=b/2=\lambda$. At $b=10$, an extra $0.1$ units predicts a gain of $0.5$; the exact gain is $V(10.1)-V(10)=0.5025$. This is the envelope theorem in a computed sensitivity analysis: the multiplier translates a binding budget constraint into a marginal benefit.

The chosen quadratic objective function above gives more than an optimal allocation: its Lagrange multiplier predicts how much the best cost changes when the required total changes. For this example,This is an explicit derivative of a constrained value function and an instance of the envelope theorem. At $c=3$, one extra small unit of required output costs approximately $4$ units per unit of output, in the chosen normalized model. Increasing $c$ makes this equality-constrained minimization problem more expensive; it is not a gain from relaxing an upper resource limit. The sign and meaning depend on how the optimization constraint and optimization Lagrangian are written.^[ref]

For an actual finite change $\delta$, the cost difference is exactlyAt $\delta =0.1$, the linear approximation predicts $0.4$, while the exact increase is $61/150\approx 0.406667$. The extra $1/150$ comes from the squared term in this polynomial, rather than numerical error. A Lagrange multiplier gives a local sensitivity analysis; treating it as a constant price over a large change generally loses the change in the optimum itself.

For a smooth optimizer $z(c)$ of an equality problem $g(z)=c$, the short chain rule calculation explains the result: $\nabla g(z(c))\cdot z^{\prime }(c)=1$ and $\nabla f(z(c))=\lambda (c)\nabla g(z(c))$ imply $df(z(c))/dc=\lambda (c)$. The differentiability and stationarity assumptions matter: an optimizer can fail to be unique or vary smoothly. The envelope theorem records when this interpretation is justified.

Suppose two adjustable inputs must deliver a prescribed total $c$, and their combined cost is the quadratic form $f(x,y)=x^2+2y^2$. These are chosen, dimensionless quantities; the coefficient $2$ makes concentrating an input in $y$ more expensive. Initially allow all real numbers $x,y$, with the equality optimization constraint $g(x,y)=x+y=c$. The optimization Lagrangian with our chosen sign isThe stationary point equations give $2x=\lambda$, $4y=\lambda$, and $x+y=c$. ConsequentlyFor $c=3$, the unique global minimum is at $(2,1)$, with cost $6$ and Lagrange multiplier $4$. Equal allocation would cost $6.75$; assigning everything to $x$ would cost $9$. At the optimum, the two marginal costs agree: ${\partial }_{x}f={\partial }_{y}f=4$. Moving a little input from one component to the other therefore has zero first-order effect on cost. When $c>0$, this solution also meets the extra nonnegativity optimization constraints $x,y\ge 0$, so it remains optimal with those added.

Here the Lagrange multiplier equations locate a candidate, and a short independent check certifies it. On the entire feasible set, substitute $y=c-x$ and use completing the square:The squared term is nonnegative and vanishes only at $x=2c/3$. Thus the candidate is the unique global minimum; there is no global maximum on this unbounded feasible set, a line. This separates finding a stationary point from proving optimality. The geometric beauty is that equal marginal costs, parallel gradients, tangency of level sets, and completing the square identify the same allocation.

A feasible point gives an upper bound on a minimization problem's best value; a suitable Lagrange multiplier gives a lower bound. Lagrangian duality searches for the strongest bound obtainable this way. Matching bounds certify a global minimum.

Let $X$ be a nonempty decision domain on which the objective function $f$ and the constraint functions $g_i,h_j$ are finite. Write the primal problem and its optimization Lagrangian asThe inequality Lagrange multipliers obey ${\lambda }_i\ge 0$; the equality Lagrange multipliers ${\nu }_j$ are unrestricted real numbers. Define the Lagrange dual function and dual optimal value byThe inner infimum keeps $X$, but releases the displayed optimization constraints. It can be $-\infty$, giving an uninformative lower bound. A different domain changes the bound.^[ref]

Here is the entire weak duality argument. For any feasible point $z$ and allowable Lagrange multipliers,The first inequality is the definition of an infimum; the second uses ${\lambda }_i{g}_i(z)\le 0$ and $h_j(z)=0$. Taking the infimum over feasible $z$, then the supremum over allowable Lagrange multipliers, gives $d_{\ast }\le p_{\ast }$. No convexity is used.

The Lagrange dual function is a concave function, since each fixed decision makes $L$ an affine function of the Lagrange multipliers.^[ref] Explicitly, write $y=(\lambda ,\nu )$ and choose two points where $q$ is finite. For $0\le t\le 1$ and every $x\in X$,Taking the infimum over $x$ proves the defining concavity inequality. Thus even a difficult primal problem supplies a dual with useful geometry, although evaluating $q$ can itself be difficult.

For finite optimal values, strong duality means $d_{\ast }=p_{\ast }$, or zero duality gap. It need not imply dual attainment. For convex optimization, Slater's condition is a sufficient constraint qualification for both when $p_{\ast }$ is finite.^[ref] The Strong Lagrangian property requires an actual finite Lagrange multiplier achieving equality. Convex perturbation duality interprets such a bound as a supporting slope of the perturbed value function.

Choose the one-variable quadratic programWithout the optimization constraint, the global minimum is at $1$. On the feasible set $[4,\infty )$, write $x=4+s$ with $s\ge 0$: then $f(x)=11+6s+s^2\ge 11$. Hence $x_{\ast }=4$ is the unique primal optimizer and $p_{\ast }=11$.

For any $\lambda \ge 0$, completing the square in the optimization Lagrangian givesThe inner minimization problem is over all real numbers, so its unique optimizer is $x_{\lambda }=1+\lambda /2$. ThereforeThe best lower bound is $d_{\ast }=11$, attained at ${\lambda }_{\ast }=6$. At $\lambda =2$, the inner optimizer is $2$, which is infeasible for the primal problem; nevertheless $q(2)=7$ is a valid lower bound. At $\lambda =9$, the inner optimizer is $5.5$, which is feasible, but $q(9)=8.75$ is weaker than $11$. Feasibility of an inner optimizer alone does not make the bound exact.

At $(x_{\ast },{\lambda }_{\ast })=(4,6)$, the Karush-Kuhn-Tucker conditions reduce toThe last equality is complementary slackness. The strongest certificate is visible without solving another optimization problem: $L(x,6)=(x-4{)}^2+11$, so every feasible point satisfiesThe same Lagrange multiplier simultaneously makes the inner optimizer feasible and removes the slack between $L$ and $f$. This is a convex KKT optimality certificate; $x=5$ also verifies Slater's condition.

The domain in the inner infimum is essential. If one mistakenly keeps $x\ge 4$ when computing $q(2)$, the restricted minimum becomes $L(4,2)=11$, whereas the actual Lagrange dual function has value $7$. Constraints deliberately retained in $X$ are allowed in a Lagrangian relaxation, but that is a different choice of which restrictions to dualize.

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.

For real $a_i$ not all equal, let $S_1={\sum }_i{a}_i$, $S_2={\sum }_i{a}_i^2$ and $\Delta =n{S}_2-S_1^2>0$. The unique minimizer of ${\sum }_i{x}_i^2$ under ${\sum }_i{x}_i=1$, ${\sum }_i{a}_i{x}_i=0$ is $x_i^{\ast }=(S_2-S_1{a}_i)/\Delta$, with minimum $S_2/\Delta$. To prove sufficiency, the optimization Lagrangian with multipliers $\lambda =S_2/\Delta$, $\mu =-S_1/\Delta$ is a sum of squares in $x_i-\lambda -\mu a_i$ plus a constant. Equivalently every feasible $x$ satisfies ${\sum }_i{x}_i^2-{\sum }_i(x_i^{\ast }{)}^2={\sum }_i(x_i-x_i^{\ast }{)}^2$.

Suppose the variance is ${\sum }_i{v}_i/x_i$ and the sampling cost is ${\sum }_i{a}_i{x}_i\le b$, with positive costs, variance coefficients and budget. The Cauchy-Schwarz inequality gives $A^2\le ({\sum }_i{v}_i/x_i)({\sum }_i{a}_i{x}_i)\le b{\sum }_i{v}_i/x_i$. Equality forces $x_i$ proportional to $\sqrt{v_i/a_i}$ and a tight budget, proving the displayed unique optimum. The minimal variance is $A^2/b$. For the optimization Lagrangian $f-\lambda ({\sum }_i{a}_i{x}_i-b)$, the multiplier and budget derivative both equal $-A^2/b^2$. Therefore a small resource change $\delta b$ changes the optimum by $\lambda \delta b+O((\delta b{)}^2)$. This is a continuous allocation; integer sample-size restrictions define a separate optimization problem.

Taking the natural logarithm of the positive product constraint gives $h(x)={\sum }_i{a}_i\log x_i=0$. Its gradient has entries $a_i/x_i>0$, so the equality constraint qualification holds everywhere on the feasible set. Use the optimization LagrangianStationarity requires $a_i-\lambda a_i/x_i=0$, so every $x_i=\lambda$. Substitution into the constraint, using ${\sum }_i{a}_i=1$, gives $\lambda =1$. Thus the only candidate for a local minimum is $x=(1,\dots ,1)$.

To prove global minimality without assuming the inequality to be established, set $u_i=\log x_i$. The constraint becomes the affine hyperplane ${\sum }_i{a}_i{u}_i=0$, and the objective function becomes $F(u)={\sum }_i{a}_i{e}^{u_i}$. Its Hessian matrix $\mathrm{diag}(a_i{e}^{u_i})$ is positive-definite, so $F$ is strictly convex. The elementary tangent inequality $e^t\ge 1+t$, with equality only at zero, givesEquality forces every $u_i=0$. ThereforeThis point is the unique global minimizer and the only local minimizer. The logarithm change of variables also explains why a multiplicative constraint leads to a convex optimization argument.

With inequalities written as $c_i\ge 0$, use the optimization Lagrangian $L(x,\lambda )=f(x)-{\sum }_i{\lambda }_i{c}_i(x)$. The Karush-Kuhn-Tucker conditions at $(x_{\ast },{\lambda }_{\ast })$ areFor any feasible point $z$, the first-order inequalities for a convex function and a concave function giveThe last equality uses complementary slackness. Thus $x_{\ast }$ is a global minimizer. Slater's condition is useful for necessity and existence of Lagrange multipliers, but is not required for this sufficiency argument once a KKT point is supplied.

The equality-constrained Lagrangian sufficiency theorem says: if $x^{\ast }$ is feasible and, for some fixed multipliers, it globally minimizes the optimization Lagrangian over all $x$, then it globally minimizes the objective over feasible $x$. On the feasible set the constraint terms vanish, so the two minimizations agree. No convexity assumption is needed for this version once global minimization of the optimization Lagrangian has been established.

Let $S_1={\sum }_i{a}_i$, $S_2={\sum }_i{a}_i^2$, and $\Delta =n{S}_2-S_1^2$. Sincethe two constraints are independent. For the squared Euclidean norm objective in the original PDF, takeCompleting the square shows that its unique global minimizer has $x_i=\lambda +\mu a_i$. The constraints become $n\lambda +S_1\mu =1$, $S_1\lambda +S_2\mu =0$, giving $\lambda =S_2/\Delta$, $\mu =-S_1/\Delta$. The Lagrangian sufficiency theorem therefore givesFor the value, use ${\sum }_i(x_i^{\ast }{)}^2=\lambda {\sum }_i{x}_i^{\ast }+\mu {\sum }_i{a}_i{x}_i^{\ast }=\lambda$. Uniqueness also follows directly: for every feasible $x$, the cross term in ${\sum }_i(x_i-x_i^{\ast }{)}^2$ vanishes, so the difference of objectives equals that strictly positive sum unless $x=x^{\ast }$. This is the minimum squared norm under two affine constraints.

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.

First take $s_i>0$, the hypothesis required for the printed ratios and their optimization formula to be well-defined. Since $\sum p_i=1$,The maximizing and minimizing problems therefore have exactly the same solutions.

Let $\tau >0$ and minimize the separable optimization LagrangianEach summand is convex, and its derivative is $-p_i{s}_i/(s_i+x_i{)}^2+\tau$. Its minimizer is $x_i(\tau )=(\sqrt{p_i{s}_i/\tau }-s_i{)}^{+}$. The sum of these coordinates is continuous in $\tau$, decreases from infinity to zero, and is strictly decreasing wherever positive. Thus there is a unique $\tau$ for which the sum is $b$. For every feasible $y$, coordinatewise minimization gives $L(y,\tau )\ge L(x(\tau ),\tau )$; both constraint terms vanish. The Lagrangian sufficiency theorem proves global optimality, not just a necessary stationary condition.

Put $r_i=p_i/s_i$ in decreasing order. A positive bet occurs exactly when $r_i>\tau$. Hence the positive bets form an initial block. To interpret the maximal index in the question, one may include any subsequent indices tied at $r_i=\tau$: their bets are zero but their marginal-return equality still holds. Take $k=\max \{i:r_i\ge \tau \}$. ThenFor this block, $\sqrt{\tau }=({\sum }_{i\le k}\sqrt{p_i{s}_i})/(b+{\sum }_{i\le k}{s}_i)$, with the threshold inequalities determining $k$. Zero-probability horses receive zero bets.

Let $H$ be the set attaining $\rho =\max r_i$, and write $S_H={\sum }_{i\in H}{s}_i$, $P_H={\sum }_{i\in H}{p}_i=\rho S_H$. For sufficiently small $b$, the solution uses only $H$, with $x_i=b{s}_i/S_H$ there and $\tau =\rho [S_H/(S_H+b){]}^2$. If the next ratio is $r_{\ast }<\rho$, this remains valid when $b\le S_H(\sqrt{\rho /r_{\ast }}-1)$; if all outside ratios are zero there is no finite threshold. Put $S={\sum }_i{s}_i$. The fixed pool is $S+b$, so the expected gross payout and net gain areTied best horses receive bets proportional to their existing stakes; betting all on one tied horse is not generally optimal for finite $b$. This is pari-mutuel expected-return allocation.

The literal allowance $s_i=0$ needs qualification. At $s_i=x_i=0$ the printed objective contains $0/0$ and the ordered ratios are undefined. Even defining an unbacked horse's payout to be zero does not always yield an attained optimum. For example, take $b=1$, $p_1=p_2=1/2$, $s_1=0$, $s_2=1$. For $x_1>0$, the normalized expected payout is $1/2+(1/2)(1-x_1)/(2-x_1)$, tending to $3/4$ as $x_1\downarrow 0$ but never attaining it; at $x_1=0$ that zero-payout convention gives $1/4$. Thus the proved allocation formula requires positive existing stakes, or an explicitly modified market model. The zero-stake case cannot be justified by silently dividing by zero.

For maximization of $f(x)$ subject to $g_j(x)\le 0$ and $h_k(x)=0$, the Lagrangian sufficiency theorem says: if a feasible $x^{\ast }$ globally maximizes $L(x)=f(x)-{\sum }_j{\lambda }_j{g}_j(x)+{\sum }_k{\nu }_k{h}_k(x)$, where ${\lambda }_j\ge 0$, and ${\lambda }_j{g}_j(x^{\ast })=0$, then $x^{\ast }$ globally maximizes $f$ over the feasible set. Indeed, at every feasible $x$,This requires a global maximum of the optimization Lagrangian; a stationary point alone is not sufficient without additional concavity or another justification.

Put $q=p/(p-1)$ and $C=({\sum }_i|a_i{|}^q{)}^{1/q}$. If every $a_i=0$, the maximum is zero and every feasible vector is optimal. Otherwise setSince $p(q-1)=q$, ${\sum }_i|x_i^{\ast }{|}^p=1$. For $g(x)={\sum }_i|x_i{|}^p-1$, the optimization Lagrangian is $L(x)={\sum }_i{a}_i{x}_i-\lambda g(x)$. Its gradient vanishes at $x^{\ast }$ becauseThe function ${\sum }_i|x_i{|}^p$ is a strictly convex function for $p>1$, so $L$ is a strictly concave function. Its supporting-hyperplane inequality proves that this stationary point is its global maximum. Complementary slackness and feasibility hold, so the sufficiency theorem applies. Substitution givesThe maximizing vector is unique when $a\ne 0$. It is the norming vector for Holder inequality, and the value is the corresponding dual norm.