跳到主要内容

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

标签：

Author​

Casablanca

Description​

日本語版​

関数 f:Rn→Rf: \mathbb{R}^n \to \mathbb{R} を連続的微分可能な凸関数とし、 S={x∈Rn∣a⊤x=b}S = \{\boldsymbol{x} \in \mathbb{R}^n \mid \boldsymbol{a}^{\top} \boldsymbol{x} = b \} とする。 ただし， a\boldsymbol{a} は 0\boldsymbol{0} でない nn 次元ベクトル、 bb はスカラーであり、 ⊤\top はベクトルの転置を表す。

次の凸計画問題を考える。

(P):Minimize  f(x)subject to  x∈S\begin{aligned} \text{(P)}: \text{Minimize } \ &f(\boldsymbol{x}) \\ \text{subject to } \ &\boldsymbol{x} \in S \end{aligned}

さらにパラメータ z∈Rn\boldsymbol{z} \in \mathbb{R}^n を含む次の凸 2 次計画問題を考える。

P(z):Minimize  ∇f(z)⊤y+12(y−z)⊤(y−z)subject to  y∈S\begin{aligned} \text{P}(\boldsymbol{z}): \text{Minimize } \ &\nabla f(\boldsymbol{z})^{\top} \boldsymbol{y} + \frac{1}{2} (\boldsymbol{y} - \boldsymbol{z})^{\top} (\boldsymbol{y} - \boldsymbol{z}) \\ \text{subject to } \ &\boldsymbol{y} \in S \end{aligned}

ここで、決定変数は y\boldsymbol{y} である。 任意の z∈Rn\boldsymbol{z} \in \mathbb{R}^n に対して問題 P(z)\text{P}(\boldsymbol{z}) は唯一の最適解 yˉ(z)\bar{\boldsymbol{y}}(\boldsymbol{z}) をもつ.

以下の問いに答えよ。

(i) z∈S\boldsymbol{z} \in S とする。問題 P(z)\text{P}(\boldsymbol{z}) のカルーシュ・キューン・タッカー (Karush-Kuhn-Tucker) 条件を用いて yˉ(z)\bar{\boldsymbol{y}}(\boldsymbol{z}) を求めよ。

(ii) x∈S\boldsymbol{x} \in S かつ yˉ(x)=x\bar{\boldsymbol{y}}(\boldsymbol{x}) = \boldsymbol{x} であるとき、 x\boldsymbol{x} は問題 (P) の最適解であることを示せ。

(iii) x∈S\boldsymbol{x} \in S かつ yˉ(x)≠x\bar{\boldsymbol{y}}(\boldsymbol{x}) \neq \boldsymbol{x} であるとき，

∇f(x)⊤(yˉ(x)−x)<0,a⊤(yˉ(x)−x)=0\nabla f(\boldsymbol{x})^{\top} (\bar{\boldsymbol{y}}(\boldsymbol{x}) - \boldsymbol{x}) < 0, \quad \boldsymbol{a}^{\top} (\bar{\boldsymbol{y}}(\boldsymbol{x}) - \boldsymbol{x}) = 0

であることを示せ。

(iv) yˉ(x)≠x\bar{\boldsymbol{y}}(\boldsymbol{x}) \neq \boldsymbol{x} であるとき， x\boldsymbol{x} は問題 (P) の最適解でないことを示せ。

English Version​

题目描述​

设 f:Rn→Rf:\mathbb R^n\to\mathbb R 是连续可微凸函数，并定义仿射集合

S={x∈Rn∣a⊤x=b},S=\{\boldsymbol x\in\mathbb R^n\mid\boldsymbol a^\top\boldsymbol x=b\},

其中 a≠0\boldsymbol a\neq\boldsymbol0 是 nn 维向量，bb 是标量，上标 ⊤\top 表示转置。考虑凸规划

(P):min⁡xf(x)s.t.x∈S.\begin{aligned} (\mathrm P):\quad \min_{\boldsymbol x}\quad &f(\boldsymbol x)\\ \text{s.t.}\quad &\boldsymbol x\in S. \end{aligned}

再对参数 z∈Rn\boldsymbol z\in\mathbb R^n 考虑以 y\boldsymbol y 为决策变量的凸二次规划

P(z):min⁡y∇f(z)⊤y+12(y−z)⊤(y−z)s.t.y∈S.\begin{aligned} \mathrm P(\boldsymbol z):\quad \min_{\boldsymbol y}\quad &\nabla f(\boldsymbol z)^\top\boldsymbol y +\frac12(\boldsymbol y-\boldsymbol z)^\top(\boldsymbol y-\boldsymbol z)\\ \text{s.t.}\quad &\boldsymbol y\in S. \end{aligned}

已知对任意 z∈Rn\boldsymbol z\in\mathbb R^n，问题 P(z)\mathrm P(\boldsymbol z) 都有唯一最优解 yˉ(z)\bar{\boldsymbol y}(\boldsymbol z)。完成以下各问：

  1. 设 z∈S\boldsymbol z\in S。利用问题 P(z)\mathrm P(\boldsymbol z) 的 Karush–Kuhn–Tucker（KKT）条件求出 yˉ(z)\bar{\boldsymbol y}(\boldsymbol z)。
  2. 若 x∈S\boldsymbol x\in S 且 yˉ(x)=x\bar{\boldsymbol y}(\boldsymbol x)=\boldsymbol x，证明 x\boldsymbol x 是问题 (P)(\mathrm P) 的最优解。
  3. 若 x∈S\boldsymbol x\in S 且 yˉ(x)≠x\bar{\boldsymbol y}(\boldsymbol x)\neq\boldsymbol x，证明
    ∇f(x)⊤(yˉ(x)−x)<0,a⊤(yˉ(x)−x)=0.\nabla f(\boldsymbol x)^\top \bigl(\bar{\boldsymbol y}(\boldsymbol x)-\boldsymbol x\bigr)<0, \qquad \boldsymbol a^\top \bigl(\bar{\boldsymbol y}(\boldsymbol x)-\boldsymbol x\bigr)=0.
  4. 当 yˉ(x)≠x\bar{\boldsymbol y}(\boldsymbol x)\neq\boldsymbol x 时，证明 x\boldsymbol x 不是问题 (P)(\mathrm P) 的最优解。

Kai​

(i)​

P(z):Minimize∇f(z)⊤y+12(y−z)⊤(y−z)Subject toa⊤y=b\begin{aligned} \text{P}(z): & \text{Minimize} \quad \nabla f(z)^\top y + \frac 12 (y-z)^\top (y-z) \\ &\text{Subject to} \quad a^\top y = b \end{aligned}

Lagrangian:

L(y,μ)=∇f(z)⊤y+12(y−z)⊤(y−z)+μ(a⊤−b)L(y,\mu) = \nabla f(z)^\top y + \frac 12 (y-z)^\top(y-z) + \mu (a^\top - b)
 KKT-conditions{∇f(x)+(yˉ(z)−z)+μa=0a⊤yˉ(z)=b\text{ KKT-conditions} \left\{ \begin{aligned} \nabla f(x) + (\bar{y}(z) - z) + \mu a & = \boldsymbol{0} \\ a^\top \bar{y}(z) &= b \end{aligned} \right.

thus

μ=−b−∇f(z)⊤a+a⊤za⊤a,yˉ(z)=ba⊤aa\mu = \frac{-b - \nabla f(z)^\top a + a^\top z}{a^\top a}, \quad \bar{y}(z) = \frac{b}{a^\top a}a

(ii)​

From (i) we know that ba⊤aa\frac{b}{a^\top a} a minimizes P(ba⊤aa)P(\frac{b}{a^\top a}a) .

S={x∣a⊤(x−ba⊤a)=0}={ba⊤a+td∣a⊤d=0,t∈R}S = \{x | a^\top (x - \frac{b}{a^\top a}) = 0 \} = \{\frac{b}{a^\top a} + td|a^\top d = 0, t\in R \}

Let g(t)=∇f(ba⊤aa)(ba⊤aa+td)+12t2d⊤dg(t) = \nabla f(\frac{b}{a^\top a}a) (\frac{b}{a^\top a}a + td) + \frac 12 t^2 d^\top d . Since

argmin g(t)=0\text{argmin } g(t) = 0

then

∇f(ba⊤aa)⊤d=0\nabla f(\frac{b}{a^\top a}a)^\top d = 0

thus

∀y∈S,f(y)−f(ba⊤aa)≥∇f(ba⊤aa)⊤(y−ba⊤aa)=0\forall y \in S, f(y) - f(\frac{b}{a^\top a}a) \geq \nabla f(\frac{b}{a^\top a }a)^\top (y - \frac{b}{a^\top a}a) = 0

Therefore ba⊤aa\frac{b}{a^\top a}a minnimize f(x)f(x) .

(iii)​

Since

a⊤yˉ(x)=b,a⊤x=ba^\top \bar{y}(x) = b, a^\top x = b

we obtain

a⊤(yˉ(x)−x)=0a^\top (\bar{y}(x) - x) = 0
x=yˉ(x)+td,a⊤d=0,t∈R,t≠0x = \bar{y}(x) + td , a^\top d = 0, t\in R, t\neq 0
∇f(x)⊤yˉ(x)+12(yˉ(x)−x)⊤(yˉ(x)−x)≤∇f(x)⊤x\nabla f(x)^\top \bar{y}(x) + \frac 12 (\bar{y}(x) - x)^\top(\bar{y}(x) - x) \leq \nabla f(x)^\top x

Then

∇f(x)⊤(yˉ(x)−x)<0\nabla f(x)^\top (\bar{y}(x) - x) < 0

(iv)​

Let g(t)=f(x+t(yˉ(x)−x)),t≥0g(t) = f(x + t(\bar{y}(x) - x)), t \geq 0 . g′(0)=∇f(x)⊤(yˉ(x)−x)g'(0) = \nabla f(x)^\top (\bar{y}(x) - x) .

ff is continuously differentiable, and so is gg .

f(c)=g(0)+g′(θ)c, θ∈(0,c)f(c) = g(0) + g'(\theta)c, \ \theta \in (0,c) , thus

g(c)<g(0)g(c) < g(0)

then

f(x+c(yˉ(x)−x))<f(x)f(x + c(\bar{y}(x) - x)) < f(x)

thus xx is not an optimal solution.

本页目录