跳到主要内容

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

标签：

Author​

Casablanca, 祭音Myyura

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

thus

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

(ii)​

Since yˉ(x)=x\bar y(x)=x, the KKT conditions in (i) give a scalar μ\mu such that

∇f(x)+μa=0.\nabla f(x)+\mu a=0.

For every y∈Sy\in S, convexity gives

f(y)≥f(x)+∇f(x)⊤(y−x)=f(x)−μa⊤(y−x)=f(x).f(y)\geq f(x)+\nabla f(x)^\top(y-x) =f(x)-\mu a^\top(y-x)=f(x).

Therefore, xx is an optimal solution of P.

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

If x∉Sx\notin S, it is infeasible and therefore cannot be optimal. Now assume x∈Sx\in S. Let g(t)=f(x+t(yˉ(x)−x)),t≥0g(t) = f(x + t(\bar{y}(x) - x)), t \geq 0. Then g′(0)=∇f(x)⊤(yˉ(x)−x)<0g'(0) = \nabla f(x)^\top (\bar{y}(x) - x)<0 by (iii).

Since g′g' is continuous, there is an ε>0\varepsilon>0 such that g′(t)<0g'(t)<0 for 0≤t≤ε0\leq t\leq\varepsilon. For 0<c≤ε0<c\leq\varepsilon, the mean value theorem gives

g(c)=g(0)+g′(θ)c<g(0),θ∈(0,c).g(c)=g(0)+g'(\theta)c<g(0),\qquad \theta\in(0,c).

Moreover, x+c(yˉ(x)−x)∈Sx+c(\bar y(x)-x)\in S. Thus

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

and xx is not an optimal solution.

本页目录