跳到主要内容

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

标签：

Author​

Casablanca

Description​

日本語版​

関数 f:Rn→Rf : \mathbb{R}^n \rightarrow \mathbb{R} は2回連続的微分可能な関数とし、a\boldsymbol{a} は 0\boldsymbol{0} でない nn 次元ベクトルとする。

次の非線形計画問題を考える。

P: Minimizef(x)subject toa⊤x=0\begin{aligned} \text{P}: \ &\text{Minimize} &f(\boldsymbol{x}) \\ &\text{subject to} &\boldsymbol{a}^{\top} \boldsymbol{x} = 0 \end{aligned}

ただし、⊤\top はベクトルの転置を表す。x∗x^* は問題 P の大域的最適解とする。

さらに、次の非線形計画問題を考える。

P(k): Minimizefk(x)subject to(x−x∗)⊤(x−x∗)≦1\begin{aligned} \text{P}(k): \ &\text{Minimize} &f_k(\boldsymbol{x}) \\ &\text{subject to} &(\boldsymbol{x} - \boldsymbol{x}^*)^{\top} (\boldsymbol{x} - \boldsymbol{x}^*) \leqq 1 \end{aligned}

ただし、kk は非負の整数であり、 fk:Rn→Rf_k : \mathbb{R}^n \rightarrow \mathbb{R} は以下に定義された関数である。

fk(x)=f(x)+k2(a⊤x)2+12(x−x∗)⊤(x−x∗)f_k(\boldsymbol{x}) = f(\boldsymbol{x}) + \frac{k}{2} (\boldsymbol{a}^{\top} \boldsymbol{x})^2 + \frac{1}{2}(\boldsymbol{x} - \boldsymbol{x}^*)^{\top} (\boldsymbol{x} - \boldsymbol{x}^*)

問題 P(k)\text{P}(k) の大域的最適解を xk\boldsymbol{x}^k とする。さらに、lim⁡k→∞xk=xˉ\lim_{k \to \infty} \boldsymbol{x}^k = \bar{\boldsymbol{x}}, lim⁡k→∞k(a⊤xk)=λˉ\lim_{k \to \infty} k(\boldsymbol{a}^{\top} \boldsymbol{x}^k) = \bar{\lambda} と仮定する。

以下の問いに答えよ。

(i) 任意の非負の整数 kk に対して fk(xk)≦f(x∗)f_k(\boldsymbol{x}^k) \leqq f(\boldsymbol{x}^*) が成り立つことを示せ。

(ii) a⊤xˉ=0\boldsymbol{a}^{\top} \bar{\boldsymbol{x}} = 0, xˉ=x∗\bar{\boldsymbol{x}} = \boldsymbol{x}^* となることを示せ。

(iii) 問題 P(k)\text{P}(k) のカルーシュ・キューン・タッカー (Karush-Kuhn-Tucker) 条件を書け。

(iv) 十分大きな kk に対して、∇fk(xk)=0\nabla f_k(\boldsymbol{x}^k) = \boldsymbol{0} となることを示せ。

(v) ∇f(x∗)+λˉa=0\nabla f(\boldsymbol{x}^*) + \bar{\lambda} \boldsymbol{a} = \boldsymbol{0} となることを示せ。

English Version​

Kai​

(i)​

fk(xk)≤fk(x∗)=f(x∗)+k2(a⊤x∗)2=f(x∗)f_k(x^k) \leq f_k(x^*) = f(x^*) + \frac k2 (a^\top x^*)^2 = f(x^*)

(ii)​

By (i) we have

lim⁡k→∞fk(xk)=lim⁡k→∞(f(xk)+k2(a⊤xk)2+12(xk−x∗)⊤(xk−x∗))=f(xˉ)+lim⁡k→∞k22(a⊤xˉ)2+12(xˉ−x∗)⊤(xˉ−x∗)≤f(x∗)\begin{aligned} \lim_{k \to \infty} f_k(x^k) &= \lim_{k\rightarrow\infty} (f(x^k) + \frac k2 (a^\top x^k)^2 + \frac12 (x^k - x^*)^\top (x^k - x^*)) \\ &= f(\bar{x}) + \lim_{k\rightarrow \infty} \frac{k^2}{2}(a^\top \bar{x})^2 + \frac 12 (\bar{x} - x^*)^\top (\bar{x} - x^*) \\ & \leq f(x^*) \end{aligned}

which implies that

a⊤xˉ=0a^\top \bar{x} = 0

and then we have

f(xˉ)+12(xˉ−x∗)⊤(xˉ−x∗)≤f(x∗)f(\bar{x}) + \frac 12 (\bar{x} - x^*)^\top(\bar{x} - x^*) \leq f(x^*)

since x∗x^* is optimal, we have

f(xˉ)≥f(x∗)f(\bar{x}) \geq f(x^*)

thus

f(x∗)=f(xˉ),and xˉ=x∗f(x^*) = f(\bar{x}), \text{and } \bar{x}=x^*

(iii)​

Lagrangian

L(x,λ)=f(x)+k2(a⊤x)2+(12+λ)(x−x∗)⊤(x−x∗)−λL(x, \lambda) = f(x) + \frac k2 (a^\top x)^2 + (\frac 12 + \lambda)(x-x^*)^\top (x-x^*) - \lambda
KKT-conditions:{∇f(x)+kaa⊤x+(1+2λ)(x−x∗)⊤(x−x∗)=0λ⪰0,λ((x−x∗)⊤(x−x∗)−1)=0(x−x∗)⊤(x−x∗)−1≤0\text{KKT-conditions:} \left\{ \begin{aligned} \nabla f(x) + k aa^\top x + (1+2\lambda)(x-x^*)^\top (x-x^*) & = \boldsymbol{0} \\ \lambda \succeq \boldsymbol{0}, \lambda ((x-x^*)^\top (x-x^*) - 1) &= 0 \\ (x-x^*)^\top (x-x^*)-1 &\leq 0 \end{aligned} \right.

(iv)​

∇f(xk)+ka⊤axk+(x−xk)(1+2λ)=0\nabla f(x^k) + k a^\top a x^k + (x-x^k)(1+2\lambda) = 0

and

λ≥0,λ((xk−x∗)⊤(xk−x∗)−1)=0\lambda \geq 0, \lambda ((x^k - x^*)^\top(x^k - x^*)-1) = 0

when kk is sufficiently large, we have

(xk−x∗)⊤(xk−x∗)<1(x^k - x^*)^\top (x^k - x^*)<1

then

λ=0\lambda = 0

thus

∇fk(xk)+ka⊤ax∗+xk−x∗=0\nabla f_k(x^k) + ka^\top a x^* + x^k - x^* = 0

therefore

∇fk(xk)=∇f(xk)+ka⊤ax∗+xk−x∗=0\nabla f_k(x^k) = \nabla f(x^k) + ka^\top a x^* + x^k - x^* = 0

(v)​

lim⁡k→∞xk=x∗\lim_{k \to \infty}x^k = x^*

from KKT-conditions:

∇f(xk)+aka⊤xk+(1+2λ)(xk−x∗)=0\nabla f(x^k) + aka^\top x^k + (1+2\lambda)(x^k - x^*) = 0

let k→∞k \to \infty, we get

∇f(x∗)+aλˉ=0\nabla f(x^*) + a \bar{\lambda} = 0
本页目录