経済学で出る数学
ワークブックでじっくり攻める：応用問題
十分条件としてのＫＫＴ条件〜凸計画問題〜（作成：2017.3.29）
【問】 $f, g_1, \ldots , g_m$ を微分可能な凸関数とする．最適化問題：
\[
\begin{align}
最小化 & f(x)\\[2ex]
条件 & g_i(x)\leq 0, i=1,\ldots , m\\
\end{align}
\]
に対しＫＫＴ条件
\[
\begin{align}
\nabla f(\bar{x})+\sum_{i=1}^{m}\bar{\lambda}_i\nabla g_i(\bar{x})=0&\tag{1} \\
\bar{\lambda}_i\geq 0, g_i(\bar{x})\leq 0,
\bar{\lambda}_ig_i(\bar{x})=0,& i=1,\ldots , m\tag{2}\\
\end{align}
\]
が成り立つならば，$\bar{x}$ は 最適解であることを示しなさい．
【解答】
関数 $x\mapsto f(x)+\sum_{i=1}^{m}\bar{\lambda}_i\nabla g_i(x)$ は微分可能な凸関数であるので，
\[
f(x)+\sum_{i=1}^{m}\bar{\lambda}_i g_i(x)-
\Bigl(f(\bar{x})+\sum_{i=1}^{m}\bar{\lambda}_i g_i(\bar{x})\Bigr)
\geq
\langle
\nabla f(\bar{x})+\sum_{i=1}^{m}\bar{\lambda}_i\nabla g_i(\bar{x}),
x-\bar{x}=0
\rangle
\]
となり，次式が成立する．
\[
f(x)+\sum_{i=1}^{m}\bar{\lambda}_i g_i(x)
\geq
f(\bar{x})+\sum_{i=1}^{m}\bar{\lambda}_i g_i(\bar{x})=f(\bar{x}).
\]
$g_i(x)\leq 0, i=1,\ldots ,m$ を満たす実行可能解 $x$ に対し，
$\sum_{i=1}^{m}\bar{\lambda}_i g_i(x)\leq 0$なので，$f(x)\geq f(\bar{x})$ となる．
【解答終】
【Further Reading】
福島雅夫『非線形最適化の基礎』朝倉書店（2001）
J.-B. Hiriart-Urruty, ‘Optimisation et analyse convexe’, Press Universitaire de France（1998）
ふろく（２）応用問題 一覧へ