= Solution
Use the <optimization Lagrangian> with the sensitivity sign convention
$$
\boxed{L_b(x,\lambda)=f(x)-\lambda^T(h(x)-b),\qquad \lambda\in\mathbb R^m.}
$$
For equality constraints the <Lagrange multipliers> have unrestricted signs. The <Lagrangian sufficiency theorem> says that if $h(x^*)=b$ and, for some $\lambda^*$, $x^*$ globally minimizes $L_b(\cdot,\lambda^*)$ over $X$, then $x^*$ globally minimizes $f$ subject to the constraint. Indeed every feasible $x$ satisfies
$$
f(x)=L_b(x,\lambda^*)\geq L_b(x^*,\lambda^*)=f(x^*).
$$
This 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 $\phi(u)=\inf\{f(x):x\in X,h(x)=u\}$, with value $+\infty$ when the feasible set is empty, and suppose $\phi(b)$ is finite. The problem has the <Strong Lagrangian property> if a finite multiplier $\lambda$ satisfies
$$
\boxed{\inf_{x\in X}L_b(x,\lambda)=\phi(b).}
$$
This 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_XL_b(x,\lambda)\leq\phi(b)$, the relevant <weak duality>. A <non-vertical supporting hyperplane of a value function> is a plane
$$
r=\phi(b)+\lambda^T(u-b)
$$
with $\phi(u)\geq\phi(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_iv_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 bound
$$
A^2=\left(\sum_i\sqrt{v_i/x_i}\sqrt{a_ix_i}\right)^2\leq\left(\sum_i\frac{v_i}{x_i}\right)\left(\sum_i a_ix_i\right)\leq b\sum_i\frac{v_i}{x_i}.
$$
Equality requires $v_i/x_i$ to be proportional to $a_ix_i$. The budget then determines the unique allocation:
$$
\boxed{x_i^*(b)=\frac bA\sqrt{\frac{v_i}{a_i}},\qquad \phi(b)=\frac{A^2}{b}.}
$$
This is the <optimal cost-constrained stratified sampling allocation>.
For an inequality $\sum_i a_ix_i\leq b$, our sign convention uses $\lambda\leq0$, so $L_b=f-\lambda(\sum_i a_ix_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 gives
$$
\boxed{\lambda^*(b)=-\frac{A^2}{b^2}.}
$$
The function $v_i/x_i+(-\lambda^*)a_ix_i$ has a strict global minimum at $x_i^*$: 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$,
$$
\phi(b+\delta b)-\phi(b)=-\frac{A^2\delta b}{b(b+\delta b)}=\lambda^*(b)\,\delta b+O((\delta b)^2).
$$
Hence \b[the first-order change in minimal variance is $\boxed{\lambda^*\delta b}$]. Increased resources decrease the variance. With the alternative convention $L=f+\mu(\sum_i a_ix_i-b)$, the multiplier is $\mu=-\lambda^*>0$ and the sensitivity is $-\mu\delta b$.
Back to article page
