[proofplan] We use the optimal dual multipliers for the unperturbed problem to produce a global lower bound on the objective. Dual optimality says that the unperturbed optimal value is no larger than the Lagrangian evaluated at any point with multipliers $(\nu^*,\rho^*)$. If a point is feasible for the perturbed problem, then the inequality constraints and nonnegativity of $\nu^*$ bound the multiplier term by $(\nu^*)^\top u$, while the equality constraint turns the linear multiplier term into $(\rho^*)^\top v$. Rearranging gives the lower bound for every perturbed feasible point, and taking the infimum gives the claimed inequality for $p(u,v)$. [/proofplan]

[step:Declare the programme, the perturbation value, and the Lagrangian] Let $n,m,r \in \mathbb{N}$. Let $f_0,f_1,\dots,f_m: \mathbb{R}^n \to \mathbb{R}$ be the objective and inequality-constraint functions of the convex programme, let $A \in \mathbb{R}^{r \times n}$ be the equality-constraint matrix, and let $b \in \mathbb{R}^r$ be the equality-constraint vector. For each perturbation $(u,v) \in \mathbb{R}^m \times \mathbb{R}^r$, define the perturbed feasible set $\mathcal{F}(u,v) \subset \mathbb{R}^n$ by \begin{align*} \mathcal{F}(u,v):=\{x \in \mathbb{R}^n : f_i(x)\leq u_i \text{ for } i=1,\dots,m \text{ and } Ax-b=v\}. \end{align*} Define the perturbation value function $p: \mathbb{R}^m \times \mathbb{R}^r \to \mathbb{R} \cup \{\pm \infty\}$ by \begin{align*} p(u,v):=\inf\{f_0(x):x\in \mathcal{F}(u,v)\}. \end{align*} Define the Lagrangian $L: \mathbb{R}^n \times \mathbb{R}^m_+ \times \mathbb{R}^r \to \mathbb{R}$ by \begin{align*} L(x,\nu,\rho):=f_0(x)+\sum_{i=1}^m \nu_i f_i(x)+\rho^\top(Ax-b). \end{align*} Define the dual objective $g: \mathbb{R}^m_+ \times \mathbb{R}^r \to \mathbb{R} \cup \{-\infty\}$ by \begin{align*} g(\nu,\rho):=\inf_{y \in \mathbb{R}^n} L(y,\nu,\rho). \end{align*} Here $y \in \mathbb{R}^n$ is the optimization variable used in the infimum defining the dual objective. [/step]

[step:Turn dual optimality into a pointwise Lagrangian lower bound] Since $(x^*,\nu^*,\rho^*)$ is primal-dual optimal for the unperturbed problem, the multiplier pair $(\nu^*,\rho^*)$ attains the dual optimum and there is no duality gap between the primal and dual optimal values. Therefore the dual objective value at $(\nu^*,\rho^*)$ equals the unperturbed primal value: \begin{align*} p(0,0)=g(\nu^*,\rho^*)=\inf_{y \in \mathbb{R}^n} L(y,\nu^*,\rho^*). \end{align*} Therefore, for every $x \in \mathbb{R}^n$, \begin{align*} p(0,0)\leq L(x,\nu^*,\rho^*). \end{align*} Using the definition of $L$, this means that for every $x \in \mathbb{R}^n$, \begin{align*} p(0,0)\leq f_0(x)+\sum_{i=1}^m \nu_i^* f_i(x)+(\rho^*)^\top(Ax-b). \end{align*} [/step]

[step:Evaluate the Lagrangian bound on an arbitrary perturbed feasible point]Fix a perturbation $(u,v) \in \mathbb{R}^m \times \mathbb{R}^r$ such that $p(u,v)$ is finite. Let $x \in \mathbb{R}^n$ be feasible for the perturbed problem, so that $f_i(x)\leq u_i$ for each $i=1,\dots,m$ and $Ax-b=v$. Because $\nu^* \in \mathbb{R}^m_+$, each component satisfies $\nu_i^*\geq 0$. Multiplying the inequality $f_i(x)\leq u_i$ by $\nu_i^*$ preserves the inequality: \begin{align*} \nu_i^* f_i(x)\leq \nu_i^* u_i. \end{align*} Summing over $i=1,\dots,m$ gives \begin{align*} \sum_{i=1}^m \nu_i^* f_i(x)\leq \sum_{i=1}^m \nu_i^* u_i=(\nu^*)^\top u. \end{align*} Also, since $Ax-b=v$, \begin{align*} (\rho^*)^\top(Ax-b)=(\rho^*)^\top v. \end{align*} Substituting these two estimates into the pointwise Lagrangian lower bound yields \begin{align*} p(0,0)\leq f_0(x)+(\nu^*)^\top u+(\rho^*)^\top v. \end{align*}[/step]

[guided]Fix a perturbation $(u,v) \in \mathbb{R}^m \times \mathbb{R}^r$ such that $p(u,v)$ is finite, and take an arbitrary feasible point $x \in \mathbb{R}^n$ for the perturbed problem. Before using feasibility, we recall the global bound from dual optimality: since $(x^*,\nu^*,\rho^*)$ is primal-dual optimal for the unperturbed problem, the multiplier pair $(\nu^*,\rho^*)$ attains the dual optimum and there is no duality gap. Hence \begin{align*} p(0,0)=g(\nu^*,\rho^*)=\inf_{y \in \mathbb{R}^n} L(y,\nu^*,\rho^*). \end{align*} Thus every $x \in \mathbb{R}^n$ satisfies \begin{align*} p(0,0)\leq L(x,\nu^*,\rho^*). \end{align*} Expanding the Lagrangian gives \begin{align*} p(0,0)\leq f_0(x)+\sum_{i=1}^m \nu_i^* f_i(x)+(\rho^*)^\top(Ax-b). \end{align*} Feasibility means exactly that the perturbed inequality and equality constraints hold: \begin{align*} f_i(x)\leq u_i \quad \text{for each } i=1,\dots,m. \end{align*} It also means \begin{align*} Ax-b=v. \end{align*} The role of the sign condition $\nu^* \in \mathbb{R}^m_+$ is to let us compare the inequality-constraint term in the Lagrangian with the perturbation vector $u$. Since $\nu_i^*\geq 0$ and $f_i(x)\leq u_i$, multiplying by $\nu_i^*$ preserves the direction of the inequality: \begin{align*} \nu_i^* f_i(x)\leq \nu_i^* u_i. \end{align*} Adding these inequalities for $i=1,\dots,m$ gives \begin{align*} \sum_{i=1}^m \nu_i^* f_i(x)\leq \sum_{i=1}^m \nu_i^* u_i. \end{align*} By the definition of the Euclidean dot product in $\mathbb{R}^m$, the right-hand side is $(\nu^*)^\top u$, so \begin{align*} \sum_{i=1}^m \nu_i^* f_i(x)\leq (\nu^*)^\top u. \end{align*} For the equality constraint, there is no monotonicity issue. Feasibility gives the exact identity $Ax-b=v$, and hence \begin{align*} (\rho^*)^\top(Ax-b)=(\rho^*)^\top v. \end{align*} Now insert these two facts into the global Lagrangian lower bound \begin{align*} p(0,0)\leq f_0(x)+\sum_{i=1}^m \nu_i^* f_i(x)+(\rho^*)^\top(Ax-b). \end{align*} The inequality-constraint term is bounded above by $(\nu^*)^\top u$, and the equality-constraint term equals $(\rho^*)^\top v$, so we obtain \begin{align*} p(0,0)\leq f_0(x)+(\nu^*)^\top u+(\rho^*)^\top v. \end{align*} This is the shadow-price estimate at the level of a single feasible point $x$. It remains to pass from one feasible point to the optimal value. Subtracting $(\nu^*)^\top u+(\rho^*)^\top v$ from both sides gives \begin{align*} f_0(x)\geq p(0,0)-(\nu^*)^\top u-(\rho^*)^\top v. \end{align*} Because the chosen point $x$ was an arbitrary element of $\mathcal{F}(u,v)$, the same lower bound holds for every feasible point of the perturbed problem. Taking the infimum of $f_0(x)$ over $x \in \mathcal{F}(u,v)$, and using the definition of $p(u,v)$, gives \begin{align*} p(u,v)=\inf\{f_0(x):x\in \mathcal{F}(u,v)\}\geq p(0,0)-(\nu^*)^\top u-(\rho^*)^\top v. \end{align*} This proves the shadow price inequality for the fixed perturbation $(u,v)$, and since the perturbation was arbitrary subject to $p(u,v)$ being finite, the theorem follows.[/guided]

[step:Rearrange the pointwise estimate and take the infimum over feasible points] From \begin{align*} p(0,0)\leq f_0(x)+(\nu^*)^\top u+(\rho^*)^\top v \end{align*} we subtract $(\nu^*)^\top u+(\rho^*)^\top v$ from both sides to get \begin{align*} f_0(x)\geq p(0,0)-(\nu^*)^\top u-(\rho^*)^\top v. \end{align*} This holds for every feasible $x \in \mathbb{R}^n$ for the perturbed problem. Taking the infimum of $f_0(x)$ over all such feasible points gives \begin{align*} p(u,v)\geq p(0,0)-(\nu^*)^\top u-(\rho^*)^\top v. \end{align*} This is the desired shadow price inequality. [/step]