跳到主要内容

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

标签：

Author​

Casablanca

Description​

日本語版​

Ω={x∈Rn∣0≦xi≦1(i=1,…,n)}\Omega = \{\boldsymbol{x} \in \mathbb{R}^n| 0 \leqq x_i \leqq 1(i=1,\dots,n)\} とする。さらに, 関数 f:Rn→Rf:\mathbb{R}^n \rightarrow \mathbb{R} は次の不等式を満たす連続的微分可能な関数とする。

αf(x)+(1−α)f(y)≧f(αx+(1−α)y)+α(1−α)(x−y)⊤(x−y)\alpha f(\boldsymbol{x}) + (1 - \alpha)f(\boldsymbol{y}) \geqq f(\alpha\boldsymbol{x} + (1 - \alpha)\boldsymbol{y}) + \alpha(1 - \alpha)(\boldsymbol{x - y})^{\top}(\boldsymbol{x - y})
∀x,y∈Rn,α∈[0,1]\forall \boldsymbol{x,y} \in \mathbb{R}^n,\alpha \in [0,1]

ただし, ⊤\top は転置記号である。

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

P:Minimize−f(x)subject tox∈Ω\begin{aligned} P: &\text{Minimize} \quad -f(\boldsymbol{x}) \\ &\text{subject to} \quad \boldsymbol{x} \in \Omega \\ \end{aligned}

さらに, パラメータ z∈Ω\boldsymbol{z} \in \Omega をもつ次の凸 22 次計画問題 Q(z)Q(\boldsymbol{z}) を考える。

Q(z):Minimize−∇f(z)⊤x+12(x−z)⊤(x−z)subject tox∈Ω\begin{aligned} Q(\boldsymbol{z}): &\text{Minimize} \quad -\nabla f(\boldsymbol{z})^{\top}\boldsymbol{x} + \frac{1}{2}(\boldsymbol{x - z})^{\top}(\boldsymbol{x - z}) \\ &\text{subject to} \quad \boldsymbol{x} \in \Omega \\ \end{aligned}

ただし, 問題 Q(z)Q(\boldsymbol{z}) の決定変数は x∈Rn\boldsymbol{x} \in \mathbb{R}^n である。任意の z∈Ω\boldsymbol{z} \in \Omega に対して, 問題 Q(z)Q(\boldsymbol{z}) は唯一の最適解 xˉ(z)\bar{\boldsymbol{x}}(\boldsymbol{z}) をもつ。

  以下の問いに答えよ。

(i) 任意の x,y∈Rn\boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^n に対して次の不等式が成り立つことを示せ。

f(x)−f(y)≧∇f(y)⊤(x−y)+(x−y)⊤(x−y)f(\boldsymbol{x}) - f(\boldsymbol{y}) \geqq \nabla f(\boldsymbol{y})^{\top}(\boldsymbol{x - y}) + (\boldsymbol{x - y})^{\top}(\boldsymbol{x - y})

(ii) 問題 Q(z)Q(\boldsymbol{z}) のカルーシュ ⋅\cdot タッカー (Karush-Kuhn-Tucker) 条件を書け。

(iii) 任意の z∈Ω\boldsymbol{z} \in \Omega に対して次の不等式が成り立つことを示せ。

f(z)−f(xˉ(z))≦−(xˉ(z)−z)⊤(xˉ(z)−z)f(\boldsymbol{z}) - f(\bar{\boldsymbol{x}}(\boldsymbol{z})) \leqq -(\bar{\boldsymbol{x}}(\boldsymbol{z}) - \boldsymbol{z})^{\top}(\bar{\boldsymbol{x}}(\boldsymbol{z}) - \boldsymbol{z})

(iv) 次の命題 (A) について, 真であれば証明を, 偽であれば反例を与えよ。

   (A) z∈Ω\boldsymbol{z} \in \Omega かつ xˉ(z)=z\bar{\boldsymbol{x}}(\boldsymbol{z}) = \boldsymbol{z} であれば, z\boldsymbol{z} は問題 PP の局所的最適解である。

English Version​

Kai​

(i)​

αf(x)+(1−α)f(y)≥f(αx+(1−α)y)+α(1−α)(x−y)⊤(x−y)\alpha f(x) + (1-\alpha)f(y) \geq f(\alpha x + (1-\alpha)y) + \alpha (1-\alpha)(x-y)^\top (x-y)

and

f(x)−f(y)≥1α(f(y+α(x−y))−f(y)+α(1−α)(x−y)⊤(x−y))f(x)-f(y)\geq \frac {1}{\alpha}(f(y + \alpha(x-y)) -f(y) + \alpha(1-\alpha)(x-y)^\top(x-y))

Let α→0\alpha \rightarrow 0,

f(x)−f(y)≥∇f(y)⊤(x−y)+(x−y)⊤(x−y)f(x) - f(y) \geq \nabla f(y)^\top (x - y) + (x-y)^\top(x-y)

(ii)​

(Q(z)):Minimize−∇f(z)⊤x+12(x−z)⊤(x−z)Subject tox⪰0 x⪯1\begin{aligned} (\text{Q}(z)): &\text{Minimize} &-\nabla f(z)^\top x + \frac 12 (x-z)^\top(x-z) \\ &\text{Subject to} &x \succeq 0\\ &\text{ } &x \preceq 1 \end{aligned}

Lagrangian:

L(x,μ,ν)=−∇f(z)⊤x+12(x−z)⊤(x−z)+λ⊤(x−1)+ν⊤(−x)L(x, \mu, \nu) = -\nabla f(z)^\top x + \frac 12 (x-z)^\top (x-z) + \lambda^\top (x-\boldsymbol{1}) + \nu^\top (-x)
 KKT-conditions{−∇f(z)+x∗−z+λ=0λ⪰0,ν⪰0x⪰0,λ(x∗−1)=0x⪯1,ν(−x)=0\text{ KKT-conditions} \left\lbrace \begin{aligned} -\nabla f(z) + x^* - z + \lambda & = 0 \\ \lambda \succeq \boldsymbol{0}, \nu &\succeq \boldsymbol{0} \\ x \succeq \boldsymbol{0}, \lambda(x^* - \boldsymbol{1}) &= 0 \\ x \preceq \boldsymbol{1}, \nu (-x) &= 0 \end{aligned} \right.

(iii)​

Solution 1​

Since xˉ(z)\bar{x}(z) minimize Q(z)\text{Q}(z), we obtain

−∇f(z)⊤xˉ(z)+12(xˉ(z)−z)⊤(xˉ(z)−z)≤−∇f(z)⊤z-\nabla f(z)^\top \bar{x}(z) + \frac 12 (\bar{x}(z) - z)^\top (\bar{x}(z) - z) \leq -\nabla f(z)^\top z
−∇f(z)⊤(xˉ(z)−z)≤−12(xˉ(z)−z)⊤(xˉ(z)−z)-\nabla f(z)^\top (\bar{x}(z) -z) \leq -\frac 12 (\bar{x}(z) - z)^\top (\bar{x}(z) -z)

from (i) we have

−∇f(z)⊤(xˉ(z)−z)≥f(z)−f(xˉ(z))+(z−xˉ(z))⊤(z−xˉ(z))-\nabla f(z)^\top (\bar{x}(z) - z) \geq f(z) - f(\bar{x}(z)) + (z-\bar{x}(z))^\top (z-\bar{x}(z))

by subtracting them, we obtain

f(z)−f(xˉ(z))≤−32(xˉ(z)−z)⊤(xˉ(z)−z)≤−(xˉ(z)−z)⊤(xˉ(z)−z)f(z) - f(\bar{x}(z)) \leq -\frac 32 (\bar{x}(z)-z)^\top (\bar{x}(z)-z) \leq - (\bar{x}(z)-z)^\top (\bar{x}(z)-z)

Solution 2​

From (i) we have

f(z)−f(xˉ(z))≤−∇f(z)⊤(xˉ(z)−z)−(z−xˉ(z))⊤(z−xˉ(z))f(z) - f(\bar{x}(z)) \leq -\nabla f(z)^\top (\bar{x}(z) - z) - (z-\bar{x}(z))^\top (z-\bar{x}(z))

by KKT-conditons we have

∇f(z)=xˉ(z)−z+λ−ν\nabla f(z) = \bar{x}(z) - z + \lambda - \nu

then

∇f(z)(xˉ(z)−z)=(xˉ(z)−z)⊤(xˉ(z)−z)+λ(xˉ(z)−z)−ν⊤xˉ(z)+νz≥0\nabla f(z)(\bar{x}(z) - z) = (\bar{x}(z) - z) ^\top (\bar{x}(z)-z) + \lambda (\bar{x}(z)-z) - \nu ^\top \bar{x}(z) + \nu z \geq 0

thus

f(z)−f(xˉ(z))≤0−(xˉ(z)−z)⊤(xˉ(z)−z)f(z) - f(\bar{x}(z)) \leq 0 - (\bar{x}(z)-z)^\top(\bar{x}(z)-z)

(iv)​

本页目录