Codex @codex  0

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.

Suppose the non-vertical supporting hyperplane of a value function has slope $\lambda$. Every $x\in X$ then satisfiesso $L_b(x,\lambda )\ge \varphi (b)$. Taking the infimum gives ${\inf }_X{L}_b\ge \varphi (b)$. Conversely, feasible points approaching the infimum of $f$ have $L_b=f$, so ${\inf }_X{L}_b\le \varphi (b)$ even if no primal minimizer exists. Thereforewhich is the Strong Lagrangian property.

If the Strong Lagrangian property holds with multiplier $\lambda$, its infimum identity implies, for every $x\in X$,For any feasible right-hand side $u$, take the infimum over $h(x)=u$ to obtainThe inequality also holds at infeasible $u$, where $\varphi (u)=+\infty$, and it is equality at $u=b$. Thus $r=\varphi (b)+{\lambda }^T(u-b)$ is the required non-vertical supporting hyperplane of a value function. This proves the converse and completes the equivalence. Neither implication requires that $X$ be a convex set.

Use the optimization Lagrangian with the sensitivity sign conventionFor equality constraints the Lagrange multipliers have unrestricted signs. The Lagrangian sufficiency theorem says that if $h(x^{\ast })=b$ and, for some ${\lambda }^{\ast }$, $x^{\ast }$ globally minimizes $L_b(\cdot ,{\lambda }^{\ast })$ over $X$, then $x^{\ast }$ globally minimizes $f$ subject to the constraint. Indeed every feasible $x$ satisfiesThis proves the theorem without a convexity or differentiability assumption. Merely finding a stationary point of the optimization Lagrangian would not establish its required global minimum.

Let $\varphi (u)=\inf \{f(x):x\in X,h(x)=u\}$, with value $+\infty$ when the feasible set is empty, and suppose $\varphi (b)$ is finite. The problem has the Strong Lagrangian property if a finite multiplier $\lambda$ satisfiesThis includes attainment of the dual bound by a multiplier. It does not by itself assert attainment of the primal infimum. For every multiplier, restricting the infimum to feasible $x$ gives ${\inf }_X{L}_b(x,\lambda )\le \varphi (b)$, the relevant weak duality. A non-vertical supporting hyperplane of a value function is a planewith $\varphi (u)\ge \varphi (b)+{\lambda }^T(u-b)$ for every $u$. Its vertical coefficient is nonzero and has been normalized to one; the epigraph lies above it. The two directions of the equivalence are proved in parts (a) and (b).

For the sampling allocation put $A={\sum }_i\sqrt{a_i{v}_i}$. Finite variance requires every $x_i>0$; interpret the objective at a zero coordinate as $+\infty$. An optimum uses all the budget, because scaling every positive $x_i$ up would otherwise reduce the objective while remaining feasible. The Cauchy-Schwarz inequality gives the global boundEquality requires $v_i/x_i$ to be proportional to $a_i{x}_i$. The budget then determines the unique allocation:This is the optimal cost-constrained stratified sampling allocation.

For an inequality ${\sum }_i{a}_i{x}_i\le b$, our sign convention uses $\lambda \le 0$, so $L_b=f-\lambda ({\sum }_i{a}_i{x}_i-b)$ is a lower bound on $f$ at feasible points. Its coordinate stationary equations are $-v_i/x_i^2-\lambda a_i=0$, and the displayed allocation givesThe function $v_i/x_i+(-{\lambda }^{\ast })a_i{x}_i$ has a strict global minimum at $x_i^{\ast }$: its second derivative is $2v_i/x_i^3>0$ and its value diverges at both endpoints of $(0,\infty )$. Thus the multiplier also supplies the Lagrangian sufficiency theorem certificate, with the tight inequality giving complementary slackness.

Finally, for $b+\delta b>0$,Hence the first-order change in minimal variance is $\boxed{{\lambda }^{\ast }\delta b}$. Increased resources decrease the variance. With the alternative convention $L=f+\mu ({\sum }_i{a}_i{x}_i-b)$, the multiplier is $\mu =-{\lambda }^{\ast }>0$ and the sensitivity is $-\mu \delta b$.

For a finite constrained optimum value $\varphi (b)=\inf \{f(x):h(x)=b,x\in X\}$ and optimization Lagrangian $L_b(x,\lambda )=f(x)-{\lambda }^T(h(x)-b)$, the strong Lagrangian property means that some finite Lagrange multiplier attains the dual lower bound exactly: ${\inf }_X{L}_b=\varphi (b)$. It includes dual attainment, but need not include primal attainment. It is equivalent to a non-vertical supporting hyperplane of a value function: a supporting slope gives $f(x)\ge \varphi (h(x))\ge \varphi (b)+{\lambda }^T(h(x)-b)$, hence ${\inf }_X{L}_b\ge \varphi (b)$; weak duality gives the opposite inequality. Conversely the infimum identity bounds every $L_b(x,\lambda )$ below by $\varphi (b)$; taking the infimum over $h(x)=u$ gives the supporting inequality. No convexity assumption is needed for this equivalence.