[proofplan] The proof compares the dual value with the Lagrangian evaluated at the primal optimum. Since $g(\nu^*,\rho^*)$ is the infimum of the Lagrangian over all $x$, it is bounded above by $L(x^*,\nu^*,\rho^*)$. Feasibility of $x^*$ removes the equality-constraint term and makes each inequality-constraint contribution $\nu_i^* f_i(x^*)$ nonpositive. Zero duality gap forces the whole sum of these nonpositive terms to be zero, and therefore each term is zero. [/proofplan] [step:Evaluate the Lagrangian at the primal feasible point] By the definition of primal feasibility for this programme, $x^* \in \mathbb{R}^n$ satisfies $f_i(x^*) \leq 0$ for every $i \in \{1,\dots,m\}$ and $Ax^*=b$. The Lagrangian is the map $L: \mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R}$ defined 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*} Therefore the equality-constraint term vanishes at the primal feasible point: \begin{align*} (\rho^*)^\top(Ax^*-b)=0. \end{align*} Substituting $x=x^*$, $\nu=\nu^*$, and $\rho=\rho^*$ into the definition of $L$ gives \begin{align*} L(x^*,\nu^*,\rho^*)=f_0(x^*)+\sum_{i=1}^m \nu_i^* f_i(x^*). \end{align*} [/step] [step:Use the infimum definition of the dual function] The dual function is the map $g: \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R} \cup \{-\infty\}$ defined by \begin{align*} g(\nu,\rho)=\inf_{x\in\mathbb{R}^n} L(x,\nu,\rho). \end{align*} For the fixed dual feasible multipliers $(\nu^*,\rho^*)$, this gives \begin{align*} g(\nu^*,\rho^*)=\inf_{x\in\mathbb{R}^n} L(x,\nu^*,\rho^*). \end{align*} Since $x^* \in \mathbb{R}^n$ is one of the points over which this infimum is taken, the infimum is bounded above by the value at $x^*$: \begin{align*} g(\nu^*,\rho^*) \leq L(x^*,\nu^*,\rho^*). \end{align*} Using the previous step, this becomes \begin{align*} g(\nu^*,\rho^*) \leq f_0(x^*)+\sum_{i=1}^m \nu_i^* f_i(x^*). \end{align*} [guided] The dual function is built by minimizing the Lagrangian over the primal variable. Formally, $g: \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R} \cup \{-\infty\}$ is defined by \begin{align*} g(\nu,\rho)=\inf_{x\in\mathbb{R}^n} L(x,\nu,\rho). \end{align*} For the fixed dual feasible multipliers $(\nu^*,\rho^*)$, this definition gives \begin{align*} g(\nu^*,\rho^*)=\inf_{x\in\mathbb{R}^n} L(x,\nu^*,\rho^*). \end{align*} An infimum over all $x \in \mathbb{R}^n$ cannot exceed the value of the same function at any particular point. Since $x^* \in \mathbb{R}^n$, we may compare the infimum with the value at $x^*$ and obtain \begin{align*} g(\nu^*,\rho^*) \leq L(x^*,\nu^*,\rho^*). \end{align*} Now we use primal feasibility. The equality constraint gives $Ax^*=b$, so \begin{align*} (\rho^*)^\top(Ax^*-b)=0. \end{align*} Thus the Lagrangian at $x^*$ reduces to \begin{align*} L(x^*,\nu^*,\rho^*)=f_0(x^*)+\sum_{i=1}^m \nu_i^* f_i(x^*). \end{align*} Combining these identities gives \begin{align*} g(\nu^*,\rho^*) \leq f_0(x^*)+\sum_{i=1}^m \nu_i^* f_i(x^*). \end{align*} This is the only place where the infimum defining the dual function is used. [/guided] [/step] [step:Force the total slackness sum to vanish] By the definition of zero duality gap for the primal-dual optimal pair, \begin{align*} g(\nu^*,\rho^*)=f_0(x^*). \end{align*} Combining this equality with the inequality from the previous step gives \begin{align*} f_0(x^*) \leq f_0(x^*)+\sum_{i=1}^m \nu_i^* f_i(x^*). \end{align*} Subtracting $f_0(x^*)$ from both sides yields \begin{align*} 0 \leq \sum_{i=1}^m \nu_i^* f_i(x^*). \end{align*} On the other hand, for each $i \in \{1,\dots,m\}$, primal feasibility gives $f_i(x^*) \leq 0$ and dual feasibility gives $\nu_i^* \geq 0$, so $\nu_i^* f_i(x^*) \leq 0$. Summing these inequalities gives \begin{align*} \sum_{i=1}^m \nu_i^* f_i(x^*) \leq 0. \end{align*} Therefore \begin{align*} \sum_{i=1}^m \nu_i^* f_i(x^*)=0. \end{align*} [/step] [step:Conclude that each complementary slackness product is zero] For each $i \in \{1,\dots,m\}$, define the real number $a_i=\nu_i^* f_i(x^*)$. The previous step proves $\sum_{i=1}^m a_i=0$, and also proves $a_i \leq 0$ for every $i$. If some $a_j<0$, then because all other $a_i$ are nonpositive, the whole sum would satisfy $\sum_{i=1}^m a_i<0$, contradicting $\sum_{i=1}^m a_i=0$. Hence $a_i=0$ for every $i \in \{1,\dots,m\}$. By the definition of $a_i$, this is exactly $\nu_i^* f_i(x^*)=0$ for every $i \in \{1,\dots,m\}$. This proves [complementary slackness](/theorems/2559). [/step]