京都大学 情報学研究科 数理工学専攻 2013年8月実施 オペレーションズ・リサーチ

标签：

• Kyoto-University
• Convex-Optimization

Author

find #01058

Description

集合 $I$ を $I=\{1, \ldots, m\}$ とし，関数 $f:\mathbb{R}^n\to\mathbb{R}$ を以下のように定義する．

$$\displaystyle f(\boldsymbol{x})=\frac{1}{2}\boldsymbol{x}^{\mathsf T}M\boldsymbol{x}+\boldsymbol{q}^{\mathsf T}\boldsymbol{x}$$

ただし，$M$ は $n\times n$ 対称行列，$\boldsymbol{q}$ は $n$ 次元ベクトルであり，$\mathsf T$ は転置記号を表す．

次の非線形計画問題 $(\text P)$ を考える．

$$\displaystyle (\mathrm P):\quad \begin{array}{ll}\text{Minimize} & f(\boldsymbol{x})\\ \text{subject to} & (\boldsymbol{a}^{i})^{\mathsf T}\boldsymbol{x}\le b_i\quad(i\in I)\end{array}$$

ここで，$\boldsymbol{a}^{i}\ (i\in I)$ は $n$ 次元定数ベクトルであり，$b_i\ (i\in I)$ は定数である．

問題 $(\text P)$ に対して，次のカルーシュ・キューン・タッカー条件（$\text{Karush-Kuhn-Tucker}$ 条件）をみたすベクトル $\boldsymbol{x}^{*}\in\mathbb{R}^n$ と $\boldsymbol{\lambda}^{*}=(\lambda_1^{*}, \ldots, \lambda_m^{*})^{\mathsf T}\in\mathbb{R}^m$ が存在すると仮定する．

$$\displaystyle \left\{\begin{array}{l}\nabla f(\boldsymbol{x}^{*})+ \displaystyle\sum_{i=1}^{m}\lambda_i^{*}\boldsymbol{a}^{i}=\boldsymbol{0}\\ (\boldsymbol{a}^{i})^{\mathsf T}\boldsymbol{x}^{*}\le b_i, \ \lambda_i^{*}\ge 0, \ \bigl((\boldsymbol{a}^{i})^{\mathsf T}\boldsymbol{x}^{*}-b_i\bigr)\lambda_i^{*}=0\quad(i\in I)\end{array}\right.$$

さらに，$J=\{i\in I\mid(\boldsymbol{a}^{i})^{\mathsf T}\boldsymbol{x}^{*}=b_i\}$，$C=\{\boldsymbol{d}\in\mathbb{R}^n\mid(\boldsymbol{a}^{i})^{\mathsf T}\boldsymbol{d}\le 0\ (i\in J)\}$，$C^0=\{\boldsymbol{d}\in\mathbb{R}^n\mid(\boldsymbol{a}^{i})^{\mathsf T}\boldsymbol{d}=0\ (i\in J)\}$ とする．

以下の問 $(\rm i)$-$(\rm v)$ に答えよ．

$(\rm{i})$ 任意の $\boldsymbol{d}\in\mathbb{R}^n$ に対して，$\displaystyle f(\boldsymbol{x}+\boldsymbol{d})-f(\boldsymbol{x})=\frac{1}{2}\boldsymbol{d}^{\mathsf T}M\boldsymbol{d}+\nabla f(\boldsymbol{x})^{\mathsf T}\boldsymbol{d}$ となることを示せ．

$(\rm{ii})$ 任意の $\boldsymbol{d}\in C$ に対して，$\displaystyle \nabla f(\boldsymbol{x}^{*})^{\mathsf T}\boldsymbol{d}\ge 0$ となることを示せ．

$(\rm{iii})$ 問題 $(\text P)$ の任意の実行可能解 $\boldsymbol{x}$ に対して，$\boldsymbol{x}-\boldsymbol{x}^{*}\in C$ となることを示せ．

$(\rm{iv})$ 任意の $\boldsymbol{d}\in C$ に対して，$\displaystyle \boldsymbol{d}^{\mathsf T}M\boldsymbol{d}\ge 0$ が成り立つとする．このとき，$\boldsymbol{x}^{*}$ は問題 $(\text P)$ の大域的最適解となることを示せ．

$(\rm{v})$ $\boldsymbol{x}^{*}$ が問題 $(\text P)$ の局所的最適解であれば，任意の $\boldsymbol{d}\in C^0$ に対して，$\displaystyle \boldsymbol{d}^{\mathsf T}M\boldsymbol{d}\ge 0$ が成り立つことを示せ．

Kai

$(\rm i)$

由于 $M$ 为对称矩阵，即 $M^{\mathsf T}=M$，有

$$\displaystyle \nabla f(\boldsymbol{x}) = \frac12(M+M^{\mathsf T})\boldsymbol{x} +\boldsymbol{q} = M\boldsymbol{x}+\boldsymbol{q}$$

于是，对于任意 $\boldsymbol{d}\in\mathbb{R}^n$,

$$\displaystyle \begin{aligned} f(\boldsymbol{x}+\boldsymbol{d})-f(\boldsymbol{x}) &= \frac12(\boldsymbol{x}+\boldsymbol{d})^{\mathsf T} M(\boldsymbol{x}+\boldsymbol{d}) +\boldsymbol{q}^{\mathsf T}(\boldsymbol{x}+\boldsymbol{d}) -\frac12\boldsymbol{x}^{\mathsf T}M\boldsymbol{x} -\boldsymbol{q}^{\mathsf T}\boldsymbol{x} \\ &= \frac12\boldsymbol{d}^{\mathsf T}M\boldsymbol{d} +\frac12\boldsymbol{x}^{\mathsf T}M\boldsymbol{d} +\frac12\boldsymbol{d}^{\mathsf T}M\boldsymbol{x} +\boldsymbol{q}^{\mathsf T}\boldsymbol{d} \\ &= \frac12\boldsymbol{d}^{\mathsf T}M\boldsymbol{d} +\boldsymbol{x}^{\mathsf T}M\boldsymbol{d} +\boldsymbol{q}^{\mathsf T}\boldsymbol{d} \\ &= \frac12\boldsymbol{d}^{\mathsf T}M\boldsymbol{d} +(M\boldsymbol{x}+\boldsymbol{q})^{\mathsf T}\boldsymbol{d} \\ &= \frac12\boldsymbol{d}^{\mathsf T}M\boldsymbol{d} +\nabla f(\boldsymbol{x})^{\mathsf T}\boldsymbol{d} \end{aligned}$$

上面第三个等式利用了 $\boldsymbol{x}^{\mathsf T}M\boldsymbol{d}=\boldsymbol{d}^{\mathsf T}M\boldsymbol{x}$，第四个等式利用了 $M=M^{\mathsf T}$.

因此

$$\displaystyle f(\boldsymbol{x}+\boldsymbol{d})-f(\boldsymbol{x}) = \frac12\boldsymbol{d}^{\mathsf T}M\boldsymbol{d} +\nabla f(\boldsymbol{x})^{\mathsf T}\boldsymbol{d} \quad (\forall \boldsymbol{d}\in\mathbb{R}^n) \qquad \Box$$

$(\rm ii)$

由 KKT 条件

$$\displaystyle \begin{aligned} \nabla f(\boldsymbol{x}^*)^{\mathsf T}\boldsymbol{d} &= -\sum_{i=1}^{m}\lambda_i^*(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d} \\ &= -\sum_{i\in J}\lambda_i^*(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d} -\sum_{i\in I\setminus J}\lambda_i^*(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d} \quad (\forall \boldsymbol{d}\in C) \end{aligned}$$

乘子约束为 $\lambda_i^*\ge0\ (i\in I)$. 当 $i\in J$ 时，由 $\boldsymbol{d}\in C$, 有 $\displaystyle (\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d}\le0$. 从而 $\displaystyle -\sum_{i\in J}\lambda_i^*(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d}\ge0$

另一方面，当 $i\in I\setminus J$ 时，由 $\boldsymbol{x}^*$ 的可行性以及 $i\notin J$，有$\displaystyle(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{x}^*\le b_i$ 和 $(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{x}^*\ne b_i$ 成立, 因此 $\displaystyle(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{x}^*<b_i.$

再由KKT条件中的互补松弛条件 $\displaystyle \left((\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{x}^*-b_i\right)\lambda_i^*=0$, 可得 $\lambda_i^*=0$，从而 $\displaystyle -\sum_{i\in I\setminus J}\lambda_i^*(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d}=0.$

综上所述

$$\displaystyle \nabla f(\boldsymbol{x}^*)^{\mathsf T}\boldsymbol{d}\ge0 \quad (\forall\boldsymbol{d}\in C). \qquad \Box$$

$(\rm iii)$

令 $\displaystyle\boldsymbol{d}:=\boldsymbol{x}-\boldsymbol{x}^*$. 由于 $\boldsymbol{x}$ 是问题 $(\text P)$ 的可行解，$\displaystyle(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{x}\le b_i\quad(i\in J\subseteq I).$

又由 $J$ 的定义，$\displaystyle(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{x}^*=b_i\quad(i\in J).$

因此，对于任意 $i\in J$,

$$\displaystyle \begin{aligned} (\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d} &= (\boldsymbol{a}^i)^{\mathsf T}(\boldsymbol{x}-\boldsymbol{x}^*) \\ &= (\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{x} -(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{x}^* \\ &\le0 \end{aligned}$$

故 $\displaystyle\boldsymbol{d}=\boldsymbol{x}-\boldsymbol{x}^*\in C.\qquad \Box$

$(\rm iv)$

任取问题 $(\text P)$ 的一个可行解 $\boldsymbol{x}$。由 $(\rm iii)$，有 $\displaystyle\boldsymbol{d}=\boldsymbol{x}-\boldsymbol{x}^*\in C.$

由 $(\rm i)$

$$\displaystyle \begin{aligned} f(\boldsymbol{x}^*+\boldsymbol{d})-f(\boldsymbol{x}^*) &= \frac12\boldsymbol{d}^{\mathsf T}M\boldsymbol{d} +\nabla f(\boldsymbol{x}^*)^{\mathsf T}\boldsymbol{d} \\ &\ge \nabla f(\boldsymbol{x}^*)^{\mathsf T}\boldsymbol{d} \qquad (\boldsymbol{d}^{\mathsf T}M\boldsymbol{d}\ge0) \\ &\ge0 \end{aligned}$$

其中最后一个不等式由 $(\rm ii)$ 得到.

因此

$$\displaystyle f(\boldsymbol{x}^*) \le f(\boldsymbol{x}^*+\boldsymbol{d}) = f(\boldsymbol{x}).$$

又因为 $\boldsymbol{x}^*$ 是问题 $(\text P)$ 的可行解，所以 $\boldsymbol{x}^*$ 是问题 $(\text P)$ 的全局最优解。$\qquad \Box$

$(\rm v)$

设问题 $(\text P)$ 的可行域为 $\displaystyle X:=\left\{\boldsymbol{x}\in\mathbb{R}^n\ \middle|\ (\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{x}\le b_i, \ i\in I\right\}.$

对 $\boldsymbol{x}^*\in X$，定义其 $\varepsilon$-邻域为 $\displaystyle B_{\varepsilon}(\boldsymbol{x}^*) :=\left\{\boldsymbol{x}\in\mathbb{R}^n\ \middle|\ \ ||\boldsymbol{x}-\boldsymbol{x}^*\|<\varepsilon\right\}.$

由于 $\boldsymbol{x}^*$ 是问题 $(\text P)$ 的局部最优解，因此存在 $\varepsilon>0$，使得 $\displaystyle f(\boldsymbol{x}^*)\le f(\boldsymbol{x})$ 成立 $\quad (\forall\boldsymbol{x}\in B_{\varepsilon}(\boldsymbol{x}^*)\cap X)$

任取 $\boldsymbol{d}\in C^0$. 当 $i\in J$ 时，有 $\displaystyle(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d}=0$, 从而 $(\boldsymbol{a}^i)^{\mathsf T}(\boldsymbol{x}^*+k\boldsymbol{d})=b_i.$

另一方面, 当 $i\in I\setminus J$ 时，有 $\displaystyle (\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{x}^*<b_i.$ 因此存在充分小的 $k>0$，使得 $\displaystyle (\boldsymbol{a}^i)^{\mathsf T}(\boldsymbol{x}^*+k\boldsymbol{d})<b_i$ 成立.

再令 $k\|\boldsymbol{d}\|<\varepsilon$，则 $\displaystyle \boldsymbol{x}^*+k\boldsymbol{d} \in B_{\varepsilon}(\boldsymbol{x}^*)\cap X.$

设 $\boldsymbol{x}:=\boldsymbol{x}^*+k\boldsymbol{d}$。由 $\boldsymbol{x}^*$ 的局部最优性以及 $(\rm i)$, 有

$$\displaystyle \begin{aligned} f(\boldsymbol{x}^*+k\boldsymbol{d})-f(\boldsymbol{x}^*) &= \frac12(k\boldsymbol{d})^{\mathsf T}M(k\boldsymbol{d}) +\nabla f(\boldsymbol{x}^*)^{\mathsf T}(k\boldsymbol{d})\ge0. \end{aligned}$$

即

$$\displaystyle \frac{k^2}{2}\boldsymbol{d}^{\mathsf T}M\boldsymbol{d} +k\nabla f(\boldsymbol{x}^*)^{\mathsf T}\boldsymbol{d} \ge0. \qquad (*)$$

由于局部最优解 $\boldsymbol{x}^*$ 满足 KKT 条件，

$$\displaystyle \begin{aligned} \nabla f(\boldsymbol{x}^*)^{\mathsf T}\boldsymbol{d} &= -\sum_{i=1}^{m}\lambda_i^*(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d} \\ &= -\sum_{i\in J}\lambda_i^*(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d} -\sum_{i\in I\setminus J}\lambda_i^*(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d} \end{aligned}$$

当 $i\in J$ 时，由 $\boldsymbol{d}\in C^0$，$\displaystyle (\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d}=0$. 因此 $\displaystyle -\sum_{i\in J}\lambda_i^*(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d}=0.$

当 $i\in I\setminus J$ 时，和 $(\rm ii)$ 同理，有 $\lambda_i^*=0$. 因此 $\displaystyle-\sum_{i\in I\setminus J}\lambda_i^*(\boldsymbol{a}^i)^{\mathsf T}\boldsymbol{d}=0.$

从而 $\displaystyle k\nabla f(\boldsymbol{x}^*)^{\mathsf T}\boldsymbol{d}=0.$ 代入 $(*)$，有 $\displaystyle\frac{k^2}{2}\boldsymbol{d}^{\mathsf T}M\boldsymbol{d}\ge0.$ 又由 $k>0$，得到 $\displaystyle\boldsymbol{d}^{\mathsf T}M\boldsymbol{d}\ge0\quad(\forall\boldsymbol{d}\in C^0)\qquad \Box$