[proofplan] We first prove necessity by separating the convex set of attainable objective and inequality-constraint levels from the strictly improving infeasible orthant. Slater's condition forces the separating functional to have positive weight on the objective coordinate, so normalization produces nonnegative inequality multipliers. The separation inequality then says that the Lagrangian is minimized on the affine equality set at $x^*$, and the finite-dimensional convex optimality rule for affine constraints gives stationarity. The converse is direct: stationarity makes $x^*$ minimize the Lagrangian, while primal feasibility, dual feasibility, and [complementary slackness](/theorems/2559) identify the Lagrangian value with the primal objective value. [/proofplan] [step:Separate attainable levels from strict objective improvement] Let $x^* \in \mathbb{R}^n$ denote the primal optimal point in the theorem statement, and let $p^* = f_0(x^*)$ denote the primal optimal value. Define the convex set \begin{align*} C := \{(u,t) \in \mathbb{R}^m \times \mathbb{R} : \text{there exists } x \in \mathbb{R}^n \text{ with } Ax=b,\ f_i(x) \leq u_i \text{ for all } i,\ f_0(x)-p^* \leq t\}. \end{align*} The set $C$ is nonempty because it contains $(f_1(x^*),\dots,f_m(x^*),0)$, and convexity of $C$ follows from convexity of $f_0,\dots,f_m$ and linearity of the constraint $Ax=b$. Define the open convex set \begin{align*} D := (-\infty,0)^m \times (-\infty,0) \subset \mathbb{R}^m \times \mathbb{R}. \end{align*} The sets $C$ and $D$ are disjoint: if $(u,t) \in C \cap D$, then some $x \in \mathbb{R}^n$ satisfies $Ax=b$, $f_i(x)<0$ for all $i$, and $f_0(x)<p^*$, contradicting the definition of $p^*$. Thus $C$ is a nonempty convex set, while $D$ is an open convex set disjoint from $C$. We use the finite-dimensional strict separating hyperplane theorem in the following explicit form: if $C_1 \subset \mathbb{R}^k$ is nonempty and convex, $C_2 \subset \mathbb{R}^k$ is open and convex, and $C_1 \cap C_2=\varnothing$, then there exist a nonzero vector $a \in \mathbb{R}^k$ and a scalar $\gamma \in \mathbb{R}$ such that $a \cdot z_1 \geq \gamma \geq a \cdot z_2$ for all $z_1 \in C_1$ and $z_2 \in C_2$. Applying this theorem with $k=m+1$, $C_1=C$, and $C_2=D$, there exist $(\nu,\mu) \in \mathbb{R}^m \times \mathbb{R}$, not both zero, and $\gamma \in \mathbb{R}$ such that \begin{align*} \nu \cdot u + \mu t \geq \gamma \geq \nu \cdot v + \mu s \end{align*} for every $(u,t) \in C$ and every $(v,s) \in D$. Since $v_i$ and $s$ may tend independently to $-\infty$ inside $D$, the inequality on $D$ forces \begin{align*} \nu_i \geq 0 \text{ for } i=1,\dots,m. \end{align*} and \begin{align*} \mu \geq 0. \end{align*} Also, taking $(v,s) \to (0,0)$ with $(v,s) \in D$ gives $\gamma \geq 0$. Because $x^*$ is feasible and optimal, the point \begin{align*} (f_1(x^*),\dots,f_m(x^*),0) \end{align*} belongs to $C$. Hence \begin{align*} \sum_{i=1}^m \nu_i f_i(x^*) \geq \gamma \geq 0. \end{align*} On the other hand, $\nu_i \geq 0$ and $f_i(x^*) \leq 0$ for each $i$, so \begin{align*} \sum_{i=1}^m \nu_i f_i(x^*) \leq 0. \end{align*} Therefore \begin{align*} \gamma = 0,\qquad \sum_{i=1}^m \nu_i f_i(x^*) = 0. \end{align*} Since each summand $\nu_i f_i(x^*)$ is nonpositive, this implies \begin{align*} \nu_i f_i(x^*) = 0 \text{ for every } i=1,\dots,m. \end{align*} It remains in this step to show $\mu>0$. Suppose instead that $\mu=0$. Since $(\nu,\mu)$ is nonzero, $\nu \neq 0$. Let $\bar{x}$ be the Slater point. Then \begin{align*} (f_1(\bar{x}),\dots,f_m(\bar{x}),f_0(\bar{x})-p^*) \in C, \end{align*} so separation gives \begin{align*} \sum_{i=1}^m \nu_i f_i(\bar{x}) \geq 0. \end{align*} But $\nu \in \mathbb{R}^m_+ \setminus \{0\}$ and $f_i(\bar{x})<0$ for every $i$, so \begin{align*} \sum_{i=1}^m \nu_i f_i(\bar{x}) < 0, \end{align*} a contradiction. Thus $\mu>0$. Define $\nu^* \in \mathbb{R}^m_+$ by \begin{align*} \nu_i^* := \frac{\nu_i}{\mu} \text{ for } i=1,\dots,m. \end{align*} For every $x \in \mathbb{R}^n$ with $Ax=b$, the point \begin{align*} (f_1(x),\dots,f_m(x),f_0(x)-p^*) \end{align*} belongs to $C$, so \begin{align*} f_0(x)+\sum_{i=1}^m \nu_i^* f_i(x) \geq p^*. \end{align*} At $x=x^*$, complementary slackness gives equality. [guided] The separating set records exactly the data that matter for optimality: the inequality values and the amount by which the objective exceeds $p^*$. We define \begin{align*} C := \{(u,t) \in \mathbb{R}^m \times \mathbb{R} : \text{there exists } x \in \mathbb{R}^n \text{ with } Ax=b,\ f_i(x) \leq u_i \text{ for all } i,\ f_0(x)-p^* \leq t\}. \end{align*} This set is convex because if two points in $C$ are witnessed by $x_0$ and $x_1$, then the convex combination is witnessed by $(1-\theta)x_0+\theta x_1$ for $0 \leq \theta \leq 1$: the equality constraint is preserved by linearity of $A$, and the inequalities are preserved by convexity of the functions $f_i$. Now define \begin{align*} D := (-\infty,0)^m \times (-\infty,0). \end{align*} A point of $D$ would mean all inequality constraints are strictly satisfied and the objective is strictly below $p^*$. Thus $C \cap D = \varnothing$, since a point in the intersection would be witnessed by some $x \in \mathbb{R}^n$ with $Ax=b$, $f_i(x)<0$ for every $i$, and $f_0(x)<p^*$, contradicting the definition of $p^*$ as the optimal value. The set $C$ is nonempty because it contains $(f_1(x^*),\dots,f_m(x^*),0)$, it is convex by the preceding convex-combination argument, and $D$ is open and convex by its definition as a product of open intervals. We have also proved $C \cap D=\varnothing$. Therefore we may apply the finite-dimensional strict separating hyperplane theorem in the following form: if $C_1 \subset \mathbb{R}^k$ is nonempty and convex, $C_2 \subset \mathbb{R}^k$ is open and convex, and $C_1 \cap C_2=\varnothing$, then there exist a nonzero vector $a \in \mathbb{R}^k$ and a scalar $\gamma \in \mathbb{R}$ such that $a \cdot z_1 \geq \gamma \geq a \cdot z_2$ for all $z_1 \in C_1$ and $z_2 \in C_2$. Applying this theorem with $k=m+1$, $C_1=C$, and $C_2=D$, it gives a nonzero vector $(\nu,\mu) \in \mathbb{R}^m \times \mathbb{R}$ and a scalar $\gamma \in \mathbb{R}$ such that \begin{align*} \nu \cdot u + \mu t \geq \gamma \geq \nu \cdot v + \mu s \end{align*} for every $(u,t) \in C$ and every $(v,s) \in D$. The signs of the coefficients are forced by the fact that $D$ extends infinitely far in the negative coordinate directions. If some $\nu_i<0$, then taking $v_i \to -\infty$ while keeping the other coordinates fixed would make $\nu \cdot v+\mu s$ tend to $+\infty$, contradicting the upper bound by $\gamma$. Hence $\nu_i \geq 0$ for each $i$. The same argument with $s \to -\infty$ gives $\mu \geq 0$. Since points of $D$ can approach $(0,0)$ from below, we also get $\gamma \geq 0$. Because $x^*$ is feasible and $f_0(x^*)=p^*$, the point \begin{align*} (f_1(x^*),\dots,f_m(x^*),0) \end{align*} lies in $C$. The separation inequality therefore gives \begin{align*} \sum_{i=1}^m \nu_i f_i(x^*) \geq \gamma \geq 0. \end{align*} But each term $\nu_i f_i(x^*)$ is nonpositive, because $\nu_i \geq 0$ and $f_i(x^*) \leq 0$. Therefore \begin{align*} \sum_{i=1}^m \nu_i f_i(x^*) = 0. \end{align*} A sum of nonpositive terms can equal zero only when every term is zero, so \begin{align*} \nu_i f_i(x^*) = 0 \text{ for every } i=1,\dots,m. \end{align*} The key role of Slater's condition is to rule out the possibility that the separating hyperplane ignores the objective coordinate. Suppose $\mu=0$. Then $\nu \neq 0$, since $(\nu,\mu)$ is nonzero. Let $\bar{x}$ be the Slater point, so $A\bar{x}=b$ and $f_i(\bar{x})<0$ for every $i$. The point \begin{align*} (f_1(\bar{x}),\dots,f_m(\bar{x}),f_0(\bar{x})-p^*) \end{align*} belongs to $C$, so separation gives \begin{align*} \sum_{i=1}^m \nu_i f_i(\bar{x}) \geq 0. \end{align*} This is impossible because $\nu \in \mathbb{R}^m_+ \setminus \{0\}$ and every $f_i(\bar{x})$ is strictly negative. Hence $\mu>0$. We may therefore normalize by $\mu$. Define $\nu^* \in \mathbb{R}^m_+$ by \begin{align*} \nu_i^* := \frac{\nu_i}{\mu} \text{ for } i=1,\dots,m. \end{align*} For any $x \in \mathbb{R}^n$ satisfying $Ax=b$, the point \begin{align*} (f_1(x),\dots,f_m(x),f_0(x)-p^*) \end{align*} belongs to $C$. Dividing the separation inequality by $\mu$ gives \begin{align*} f_0(x)+\sum_{i=1}^m \nu_i^* f_i(x) \geq p^*. \end{align*} At $x=x^*$, the complementary slackness already proved gives equality. [/guided] [/step] [step:Convert affine constrained minimality into stationarity] Define the convex function \begin{align*} \phi: \mathbb{R}^n \to \mathbb{R} \end{align*} by \begin{align*} \phi(x) := f_0(x)+\sum_{i=1}^m \nu_i^* f_i(x). \end{align*} Because $\nu_i^* \geq 0$ for every $i$ and each $f_i$ is finite-valued and convex, $\phi$ is a finite-valued convex function on $\mathbb{R}^n$; the sum rule also permits the coefficients $\nu_i^*$ to be zero. The previous step shows that $x^*$ minimizes $\phi$ over the affine set \begin{align*} S := \{x \in \mathbb{R}^n : Ax=b\}. \end{align*} The set $S$ is a nonempty affine subspace because $x^* \in S$ and it is defined by the affine equation $Ax=b$. The set $S$ is closed because it is the inverse image of the closed singleton $\{b\}$ under the continuous [linear map](/page/Linear%20Map) $A: \mathbb{R}^n \to \mathbb{R}^p$. By the finite-dimensional convex Fermat rule for a convex function minimized over a closed affine set, $0 \in \partial \phi(x^*)+N_S(x^*)$, where $N_S(x^*)$ denotes the convex normal cone to $S$ at $x^*$. For the affine set $S=\{x\in\mathbb{R}^n:Ax=b\}$, its direction space is $\ker A$, and its normal cone is the orthogonal complement $(\ker A)^\perp=\operatorname{range}(A^\top)$. Hence there exists $\rho^* \in \mathbb{R}^p$ such that \begin{align*} 0 \in \partial \phi(x^*) + A^\top \rho^*. \end{align*} Since each $f_i$ is finite-valued and convex on all of $\mathbb{R}^n$, each $f_i$ is continuous on $\mathbb{R}^n$, so the finite-dimensional [Moreau-Rockafellar subdifferential sum rule](/theorems/6695) for finite convex functions applies to the finite sum defining $\phi$. Hence there exist \begin{align*} g_i^* \in \partial f_i(x^*) \text{ for } i=0,1,\dots,m \end{align*} such that \begin{align*} g_0^*+\sum_{i=1}^m \nu_i^* g_i^*+A^\top \rho^* = 0. \end{align*} Together with primal feasibility, dual feasibility, and complementary slackness from the previous step, this proves the KKT conditions. [guided] The previous step constructed the multiplier vector $\nu^* \in \mathbb{R}^m_+$ and proved that $x^*$ minimizes the weighted objective over the equality constraint. Define \begin{align*} \phi: \mathbb{R}^n \to \mathbb{R} \end{align*} by \begin{align*} \phi(x) := f_0(x)+\sum_{i=1}^m \nu_i^* f_i(x). \end{align*} Since every coefficient $\nu_i^*$ is nonnegative and each $f_i$ is finite-valued and convex on $\mathbb{R}^n$, the function $\phi$ is finite-valued and convex on $\mathbb{R}^n$. Zero coefficients cause no difficulty in the subdifferential sum rule, because the zero multiple contributes the singleton subdifferential $\{0\}$. Let \begin{align*} S := \{x \in \mathbb{R}^n : Ax=b\}. \end{align*} This set is nonempty because $x^* \in S$, and it is affine because it is the solution set of the affine equation $Ax=b$. It is also closed, since $S=A^{-1}(\{b\})$ and $A: \mathbb{R}^n \to \mathbb{R}^p$ is continuous. The inequality from the separation step says that $\phi(x) \geq \phi(x^*)$ for every $x \in S$, so $x^*$ minimizes $\phi$ over $S$. We now apply the finite-dimensional convex Fermat rule for a convex function minimized over a closed affine set. Its hypotheses are satisfied: $\phi$ is finite convex, $S$ is a nonempty closed affine set, and $x^* \in S$ is a minimizer. The rule gives \begin{align*} 0 \in \partial \phi(x^*)+N_S(x^*), \end{align*} where $N_S(x^*)$ denotes the convex normal cone to $S$ at $x^*$. For this particular affine set, the normal cone has the required multiplier form. The direction space of $S=\{x\in\mathbb{R}^n:Ax=b\}$ is $\ker A$: if $x^*+h\in S$, then $Ah=0$, and every $h\in\ker A$ is an admissible tangent direction. Therefore \begin{align*} N_S(x^*)=(\ker A)^\perp=\operatorname{range}(A^\top). \end{align*} The equality $(\ker A)^\perp=\operatorname{range}(A^\top)$ is the finite-dimensional fundamental theorem of linear algebra applied to the matrix $A$. Hence there exists $\rho^* \in \mathbb{R}^p$ such that \begin{align*} 0 \in \partial \phi(x^*) + A^\top \rho^*. \end{align*} Because the functions $f_i$ are finite-valued convex functions on all of $\mathbb{R}^n$, they are continuous on $\mathbb{R}^n$. Hence the finite-dimensional Moreau-Rockafellar subdifferential sum rule for finite convex functions applies to the finite sum defining $\phi$, including the possibly zero coefficients $\nu_i^*$. Thus there exist \begin{align*} g_i^* \in \partial f_i(x^*) \text{ for } i=0,1,\dots,m \end{align*} such that \begin{align*} g_0^*+\sum_{i=1}^m \nu_i^* g_i^*+A^\top \rho^* = 0. \end{align*} Together with $Ax^*=b$, $f_i(x^*)\leq 0$, $\nu^*\in\mathbb{R}^m_+$, and $\nu_i^*f_i(x^*)=0$ from the separation step, this is exactly the KKT system. [/guided] [/step] [step:Use the KKT conditions to prove primal and dual optimality] Assume conversely that $x^* \in \mathbb{R}^n$, $\nu^* \in \mathbb{R}^m_+$, and $\rho^* \in \mathbb{R}^p$ satisfy the KKT conditions. Define the Lagrangian \begin{align*} L: \mathbb{R}^n \times \mathbb{R}^m_+ \times \mathbb{R}^p \to \mathbb{R} \end{align*} by \begin{align*} L(x,\nu,\rho) := f_0(x)+\sum_{i=1}^m \nu_i f_i(x)+\rho \cdot (Ax-b). \end{align*} For fixed $(\nu^*,\rho^*)$, the map \begin{align*} x \mapsto L(x,\nu^*,\rho^*) \end{align*} is finite-valued and convex, because it is the sum of $f_0$, the nonnegative convex terms $\nu_i^* f_i$, and the affine function $x \mapsto \rho^* \cdot (Ax-b)$. The finite-dimensional Moreau-Rockafellar subdifferential sum rule applies to this finite sum, so the KKT stationarity condition is exactly \begin{align*} 0 \in \partial_x L(x^*,\nu^*,\rho^*). \end{align*} By the subgradient optimality condition for finite convex functions, this inclusion implies that $x^*$ minimizes $x \mapsto L(x,\nu^*,\rho^*)$ over $\mathbb{R}^n$. Therefore the dual function \begin{align*} g: \mathbb{R}^m_+ \times \mathbb{R}^p \to \mathbb{R} \cup \{-\infty\} \end{align*} by \begin{align*} g(\nu,\rho) := \inf_{x \in \mathbb{R}^n} L(x,\nu,\rho) \end{align*} satisfies \begin{align*} g(\nu^*,\rho^*) = L(x^*,\nu^*,\rho^*). \end{align*} Using primal feasibility and complementary slackness, \begin{align*} L(x^*,\nu^*,\rho^*) = f_0(x^*)+\sum_{i=1}^m \nu_i^* f_i(x^*)+\rho^* \cdot (Ax^*-b) = f_0(x^*). \end{align*} Now let $y \in \mathbb{R}^n$ be any primal feasible point. Since $\nu_i^* \geq 0$ and $f_i(y) \leq 0$ for every $i$, and since $Ay=b$, we have \begin{align*} L(y,\nu^*,\rho^*) = f_0(y)+\sum_{i=1}^m \nu_i^* f_i(y) \leq f_0(y). \end{align*} Because $x^*$ minimizes the Lagrangian, \begin{align*} f_0(x^*) = L(x^*,\nu^*,\rho^*) \leq L(y,\nu^*,\rho^*) \leq f_0(y). \end{align*} Thus $x^*$ is primal optimal. Finally, [weak duality](/theorems/2549) follows directly from the same inequality: for every dual feasible pair $(\nu,\rho) \in \mathbb{R}^m_+ \times \mathbb{R}^p$ and every primal feasible $y$, \begin{align*} g(\nu,\rho) \leq L(y,\nu,\rho) \leq f_0(y). \end{align*} Taking the infimum over primal feasible $y$ gives $g(\nu,\rho) \leq p_{\mathrm{opt}}$, where $p_{\mathrm{opt}}$ denotes the primal optimal value. Since the preceding paragraph proved that $x^*$ is primal optimal, $p_{\mathrm{opt}}=f_0(x^*)$. Therefore \begin{align*} g(\nu^*,\rho^*) = f_0(x^*) = p_{\mathrm{opt}}, \end{align*} so the pair $(\nu^*,\rho^*)$ is dual optimal. This completes the proof. [guided] Assume now that $x^* \in \mathbb{R}^n$, $\nu^* \in \mathbb{R}^m_+$, and $\rho^* \in \mathbb{R}^p$ satisfy the KKT conditions. Define the Lagrangian \begin{align*} L: \mathbb{R}^n \times \mathbb{R}^m_+ \times \mathbb{R}^p \to \mathbb{R} \end{align*} by \begin{align*} L(x,\nu,\rho) := f_0(x)+\sum_{i=1}^m \nu_i f_i(x)+\rho \cdot (Ax-b). \end{align*} For fixed $(\nu^*,\rho^*)$, the map $x \mapsto L(x,\nu^*,\rho^*)$ is finite-valued and convex because it is a finite nonnegative linear combination of convex functions plus an affine function. To identify KKT stationarity with a subgradient condition for the full Lagrangian, we use the finite-dimensional Moreau-Rockafellar subdifferential sum rule for finite convex functions, together with the fact that the affine term $x \mapsto \rho^* \cdot (Ax-b)$ has gradient $A^\top\rho^*$. Thus the KKT stationarity condition states exactly that \begin{align*} 0 \in \partial_x L(x^*,\nu^*,\rho^*). \end{align*} By the subgradient optimality condition for finite convex functions, this inclusion implies that $x^*$ minimizes $x \mapsto L(x,\nu^*,\rho^*)$ over $\mathbb{R}^n$. Define the dual function \begin{align*} g: \mathbb{R}^m_+ \times \mathbb{R}^p \to \mathbb{R} \cup \{-\infty\} \end{align*} by \begin{align*} g(\nu,\rho) := \inf_{x \in \mathbb{R}^n} L(x,\nu,\rho). \end{align*} Since $x^*$ minimizes the Lagrangian with multipliers $(\nu^*,\rho^*)$, \begin{align*} g(\nu^*,\rho^*) = L(x^*,\nu^*,\rho^*). \end{align*} Primal feasibility gives $Ax^*=b$, and complementary slackness gives $\sum_{i=1}^m \nu_i^* f_i(x^*)=0$, so \begin{align*} L(x^*,\nu^*,\rho^*) = f_0(x^*). \end{align*} Let $y \in \mathbb{R}^n$ be any primal feasible point. Then $Ay=b$, $f_i(y)\leq 0$, and $\nu_i^*\geq 0$ for every $i$, so \begin{align*} L(y,\nu^*,\rho^*) \leq f_0(y). \end{align*} Because $x^*$ minimizes the Lagrangian, \begin{align*} f_0(x^*) = L(x^*,\nu^*,\rho^*) \leq L(y,\nu^*,\rho^*) \leq f_0(y). \end{align*} Thus $x^*$ is primal optimal. For any dual feasible pair $(\nu,\rho) \in \mathbb{R}^m_+ \times \mathbb{R}^p$ and any primal feasible $y$, the same feasibility argument gives \begin{align*} g(\nu,\rho) \leq L(y,\nu,\rho) \leq f_0(y). \end{align*} Taking the infimum over primal feasible $y$ yields $g(\nu,\rho) \leq p_{\mathrm{opt}}$, where $p_{\mathrm{opt}}$ denotes the primal optimal value. We have already proved in this converse direction that $x^*$ is primal optimal, so $p_{\mathrm{opt}}=f_0(x^*)$. Since $g(\nu^*,\rho^*)=f_0(x^*)=p_{\mathrm{opt}}$, the pair $(\nu^*,\rho^*)$ is dual optimal. This proves primal-dual optimality. [/guided] [/step]