Htykuut

In Boyd's Convex Optimisation, the following optimisation problem is considered
$$
begin{align}
minquad & f_0(x)\
text{s.t.}quad & f_i(x)le 0,quad i=1:m,quad minBbb Z_{ge 0}\
& h_i(x) = 0,quad j=1:p,quad pinBbb Z_{ge 0}
end{align}tag{P}
$$
For they time being the functions $f_0,f_{1:m},h_{1:p}:Bbb R^ntoBbb 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:Dtimes Bbb R^mtimesBbb R^pni(x,lambda,mu)mapsto f_0(x)+lambda^T f(x) + mu^T h(x)inBbb 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^mtimes Bbb R^pni(lambda,mu)mapsto inf_{xin D}L(x,lambda,mu)inBbb R.$$
We then formulate the dual problem (as opposed to the primal (P)) as
$$
begin{align}
maxquad & g(lambda, mu)\
text{s.t.}quad & lambda inBbb R_{ge 0}^m\
quad & muinBbb R^p
end{align}tag{D}
$$
Now, suppose $bar x$ and $(barlambda,barmu)$ 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(barlambda,barmu)=inf_{xin color{red}{D}}L(x,barlambda,barmu)le L(bar x, barlambda,barmu)le f_0(bar x)implies bar x=operatorname*{argmin}_{xincolor{red}{D}}L(x,barlambda,barmu).$$
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,barlambda, barmu)=0$. WHY is this true?

Note that Fermat's lemma may not apply: $bar x$ just minimises $L(cdot,barlambda,barmu)$ 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.

$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.

By the way, one way to motivate the Lagrangian intuitively is that we are attempting to replace the hard constraints (which are difficult to handle) with linear penalty terms in the objective function (which are hopefully easy to handle). By introducing the Lagrangian, we hope to solve an unconstrained minimization problem rather than a constrained problem. (But, this strategy requires us to figure out the correct values of the Lagrangian multipliers -- which leads us to solving the dual problem.)