跳到主要内容

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

标签：

Author​

Casablanca, 祭音Myyura

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​

题目描述​

定义箱集

Ω={x∈Rn | 0≦xi≦1, i=1,…,n}.\Omega=\left\{\boldsymbol{x}\in\mathbb{R}^n\ \middle|\ 0\leqq x_i\leqq1,\ i=1,\ldots,n\right\}.

设 f:Rn→Rf:\mathbb{R}^n\to\mathbb{R} 连续可微，并且对任意 x,y∈Rn\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^n 和 α∈[0,1]\alpha\in[0,1] 都有

α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\!\left(\alpha\boldsymbol{x}+(1-\alpha)\boldsymbol{y}\right) +\alpha(1-\alpha)(\boldsymbol{x}-\boldsymbol{y})^\top (\boldsymbol{x}-\boldsymbol{y}),

其中 ⊤\top 表示转置。考虑非线性规划

P:最小化−f(x)约束于x∈Ω,\begin{aligned} P:\quad &\text{最小化}\quad -f(\boldsymbol{x})\\ &\text{约束于}\quad \boldsymbol{x}\in\Omega, \end{aligned}

以及以 z∈Ω\boldsymbol{z}\in\Omega 为参数、以 x∈Rn\boldsymbol{x}\in\mathbb{R}^n 为决策变量的凸二次规划

Q(z):最小化−∇f(z)⊤x+12(x−z)⊤(x−z)约束于x∈Ω.\begin{aligned} Q(\boldsymbol{z}):\quad &\text{最小化}\quad -\nabla f(\boldsymbol{z})^\top\boldsymbol{x} +\frac12(\boldsymbol{x}-\boldsymbol{z})^\top (\boldsymbol{x}-\boldsymbol{z})\\ &\text{约束于}\quad \boldsymbol{x}\in\Omega. \end{aligned}

已知对每个 z∈Ω\boldsymbol{z}\in\Omega，Q(z)Q(\boldsymbol{z}) 都有唯一最优解，记为 xˉ(z)\bar{\boldsymbol{x}}(\boldsymbol{z})。回答下列问题：

  1. 证明对任意 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}-\boldsymbol{y}) +(\boldsymbol{x}-\boldsymbol{y})^\top(\boldsymbol{x}-\boldsymbol{y}).
  1. 写出问题 Q(z)Q(\boldsymbol{z}) 的 Karush–Kuhn–Tucker（KKT）条件。
  2. 证明对任意 z∈Ω\boldsymbol{z}\in\Omega，
f(z)−f ⁣(xˉ(z))≦−(xˉ(z)−z)⊤(xˉ(z)−z).f(\boldsymbol{z})-f\!\left(\bar{\boldsymbol{x}}(\boldsymbol{z})\right) \leqq -\left(\bar{\boldsymbol{x}}(\boldsymbol{z})-\boldsymbol{z}\right)^\top \left(\bar{\boldsymbol{x}}(\boldsymbol{z})-\boldsymbol{z}\right).
  1. 判断命题（A）是否成立：若 z∈Ω\boldsymbol{z}\in\Omega 且 xˉ(z)=z\bar{\boldsymbol{x}}(\boldsymbol{z})=\boldsymbol{z}，则 z\boldsymbol{z} 是问题 PP 的局部最优解。若成立，请证明；若不成立，请给出反例。

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, \lambda, \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,λi(xi∗−1)=0(i=1,…,n)x∗⪯1,νixi∗=0(i=1,…,n)\text{ KKT-conditions} \left\lbrace \begin{aligned} -\nabla f(z) + x^* - z + \lambda-\nu & = 0 \\ \lambda \succeq \boldsymbol{0}, \nu &\succeq \boldsymbol{0} \\ x^* \succeq \boldsymbol{0}, \lambda_i(x_i^* - 1) &= 0\quad(i=1,\ldots,n) \\ x^* \preceq \boldsymbol{1}, \nu_i x_i^* &= 0\quad(i=1,\ldots,n) \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∥2+λ⊤(xˉ(z)−z)−ν⊤(xˉ(z)−z)≥0,\nabla f(z)^\top(\bar{x}(z) - z) = \|\bar{x}(z)-z\|^2+\lambda^\top(\bar{x}(z)-z)-\nu^\top(\bar{x}(z)-z) \geq 0,

because complementary slackness gives λ⊤(xˉ−z)=λ⊤(1−z)≥0\lambda^\top(\bar x-z)=\lambda^\top(\boldsymbol1-z)\geq0 and −ν⊤(xˉ−z)=ν⊤z≥0-\nu^\top(\bar x-z)=\nu^\top z\geq0.

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)​

The statement is false. Let n=1n=1, Ω=[0,1]\Omega=[0,1], and f(x)=x2f(x)=x^2. The assumed inequality holds with equality. At z=0z=0,

Q(0):min⁡0≤x≤112x2Q(0):\quad \min_{0\leq x\leq1}\frac12x^2

has xˉ(0)=0\bar x(0)=0. However, −f(x)=−x2<−f(0)-f(x)=-x^2<-f(0) for every sufficiently small x>0x>0, so z=0z=0 is not a local minimizer of P.

本页目录