# How to imply the vanishing gradient condition in KKT?

In Boyd's Convex Optimisation, the following optimisation problem is considered \begin{align} \min\quad & f_0(x)\\ \text{s.t.}\quad & f_i(x)\le 0,\quad i=1:m,\quad m\in\Bbb Z_{\ge 0}\\ & h_i(x) = 0,\quad j=1:p,\quad p\in\Bbb Z_{\ge 0} \end{align}\tag{P} For they time being the functions $$f_0,f_{1:m},h_{1:p}:\Bbb R^n\to\Bbb R$$ are assumed $$C^1$$ but not necessarily convex. Let $$D$$ be the the feasible domain specified by the conditions $$f_{1:m}(x)\le 0$$ and $$h_{1:p}(x)=0$$. Then the associated Lagrangian is $$L:D\times \Bbb R^m\times\Bbb R^p\ni(x,\lambda,\mu)\mapsto f_0(x)+\lambda^T f(x) + \mu^T h(x)\in\Bbb R$$ where $$f:=(f_1,\cdots,f_m)^T$$ and $$h:=(h_1,\cdots,h_p)^T$$, and the Lagrange function is thus defined as $$g:\Bbb R^m\times \Bbb R^p\ni(\lambda,\mu)\mapsto \inf_{x\in D}L(x,\lambda,\mu)\in\Bbb R.$$ We then formulate the dual problem (as opposed to the primal (P)) as \begin{align} \max\quad & g(\lambda, \mu)\\ \text{s.t.}\quad & \lambda \in\Bbb R_{\ge 0}^m\\ \quad & \mu\in\Bbb R^p \end{align}\tag{D} Now, suppose $$\bar x$$ and $$(\bar\lambda,\bar\mu)$$ are a dual feasible pair for (P) and (D), and suppose that strong duality holds. Then we can show easily that $$\DeclareMathOperator*{\argmin}{argmin} f_0(\bar x) = g(\bar\lambda,\bar\mu)=\inf_{x\in \color{red}{D}}L(x,\bar\lambda,\bar\mu)\le L(\bar x, \bar\lambda,\bar\mu)\le f_0(\bar x)\implies \bar x=\operatorname*{argmin}_{x\in\color{red}{D}}L(x,\bar\lambda,\bar\mu).$$ But then Boyd claims that, "since $$\bar x$$ minimises $$L$$ over $$x$$, its gradient must vanish at $$\bar x$$", i.e. that $$\nabla_x L(\bar x,\bar\lambda, \bar\mu)=0$$. WHY is this true?

Note that Fermat's lemma may not apply: $$\bar x$$ just minimises $$L(\cdot,\bar\lambda,\bar\mu)$$ within the primal feasible domain $$\color{red}{D}$$, to which $$\bar x$$ is NOT necessarily an interior point, and even $$D$$ itself may not have non-empty interior in $$\Bbb R^n$$. So why can we conclude the gradient w.r.t. $$x$$ vanishes at $$\bar x$$?

Thank you.

As LittleO kindly pointed out, my problem is actually a non-problem that arose from the confusion over the definition of $$D$$: it is NOT the feasible region of $$(P)$$; rather, it is the intersection of domains of $$f$$ and $$h$$ which are assumed open (hence making $$D$$ open too).

• @littleO Sorry I seem to have made a hasty assumption about its definition. Indeed Boyd has defined the dom thing as the domain instead of the feasible region. – Vim Dec 10 '18 at 6:46

$$D$$ is not the set of all points $$x$$ where the constraints are satisfied. Rather, as stated at the beginning of section 5.1, $$D = \cap_i \textbf{dom } f_i \, \cap \, \cap _i \textbf{dom } h_i$$.
At the beginning of section 5.5.3, the book assumes that the functions $$f_i$$ and $$h_i$$ have open domains. It follows that $$D$$ is an open set. Thus, Fermat's lemma does apply.