跳到主要内容

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

标签：

Author​

Casablanca

Description​

日本語版​

A\boldsymbol{A} を n×nn \times n の正定値対称行列とする。 さらに、関数 f:Rn×Rn→Rf: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}, g:Rn×Rn→Rg: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}, h:Rn×Rn→Rh: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R} を以下のように定義する。

f(x,z)=−x⊤x+z⊤Axg(x,z)=x⊤x+z⊤Ax+z⊤zh(x,y)=x⊤x+y⊤y\begin{aligned} f(\boldsymbol{x}, \boldsymbol{z}) &= - \boldsymbol{x}^{\top} \boldsymbol{x} + \boldsymbol{z}^{\top} \boldsymbol{A} \boldsymbol{x} \\ g(\boldsymbol{x}, \boldsymbol{z}) &= \boldsymbol{x}^{\top} \boldsymbol{x} + \boldsymbol{z}^{\top} \boldsymbol{A} \boldsymbol{x} + \boldsymbol{z}^{\top} \boldsymbol{z} \\ h(\boldsymbol{x}, \boldsymbol{y}) &= \boldsymbol{x}^{\top} \boldsymbol{x} + \boldsymbol{y}^{\top} \boldsymbol{y} \end{aligned}

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

z∈Rn\boldsymbol{z} \in \mathbb{R}^n をパラメータにもつ次の非線形計画問題を考える。

P1(z):Maximizef(x,z)subject tox⊤x≦1\begin{aligned} \text{P1}(\boldsymbol{z}): &\text{Maximize} &f(\boldsymbol{x}, \boldsymbol{z}) \\ &\text{subject to} &\boldsymbol{x}^{\top} \boldsymbol{x} \leqq 1 \end{aligned}
P2(z):Minimizeg(x,z)subject tox∈Rn\begin{aligned} \text{P2}(\boldsymbol{z}): &\text{Minimize} &g(\boldsymbol{x}, \boldsymbol{z}) \\ &\text{subject to} &\boldsymbol{x} \in \mathbb{R}^n \end{aligned}
P3(z):Minimizeh(x,y)subject tox+y=z\begin{aligned} \text{P3}(\boldsymbol{z}): &\text{Minimize} &h(\boldsymbol{x}, \boldsymbol{y}) \\ &\text{subject to} &\boldsymbol{x} + \boldsymbol{y} = \boldsymbol{z} \end{aligned}

ただし、P1(z)\text{P1}(\boldsymbol{z}) と P2(z)\text{P2}(\boldsymbol{z}) の決定変数は x∈Rn\boldsymbol{x} \in \mathbb{R}^n であり、P3(z)\text{P3}(\boldsymbol{z}) の決定変数は (x,y)∈Rn×Rn(\boldsymbol{x}, \boldsymbol{y}) \in \mathbb{R}^n \times \mathbb{R}^n である。

任意のパラメータ z∈Rn\boldsymbol{z} \in \mathbb{R}^n に対して P1(z)\text{P1}(\boldsymbol{z}), P2(z)\text{P2}(\boldsymbol{z}), P3(z)\text{P3}(\boldsymbol{z}) は唯一の最適解をもつ。 P1(z)\text{P1}(\boldsymbol{z}), P2(z)\text{P2}(\boldsymbol{z}), P3(z)\text{P3}(\boldsymbol{z}) の最適解をそれぞれ x1(z)\boldsymbol{x}^1(\boldsymbol{z}), x2(z)\boldsymbol{x}^2(\boldsymbol{z}), (x3(z),y3(z))(\boldsymbol{x}^3(\boldsymbol{z}), \boldsymbol{y}^3(\boldsymbol{z})) とする。

以下の問いに答えよ。

(i) z⊤A⊤Az≦4\boldsymbol{z}^\top \boldsymbol{A}^{\top} \boldsymbol{A} \boldsymbol{z} \leqq 4 とする。 カルーシュ・キューン・タッカー (Karush-Kuhn-Tucker) 条件を用いて P1(z)\text{P1}(\boldsymbol{z}) の最適解 x1(z)\boldsymbol{x}^1(\boldsymbol{z}) を求めよ。(P1(z)\text{P1}(\boldsymbol{z}) が最大化問題であることに注意すること。)

(ii) カルーシュ・キューン・タッカー条件を用いて P3(z)\text{P3}(\boldsymbol{z}) の最適解 (x3(z),y3(z))(\boldsymbol{x}^3(\boldsymbol{z}), \boldsymbol{y}^3(\boldsymbol{z})) を求めよ。

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

  • (a) 関数 p:Rn→Rp : \mathbb{R}^n \rightarrow \mathbb{R} を p(z)=f(x1(z),z)p(\boldsymbol{z}) = f(\boldsymbol{x}^1(\boldsymbol{z}), \boldsymbol{z}) としたとき、関数 pp は凸関数である。
  • (b) 関数 q:Rn→Rq : \mathbb{R}^n \rightarrow \mathbb{R} を q(z)=g(x2(z),z)q(\boldsymbol{z}) = g(\boldsymbol{x}^2(\boldsymbol{z}), \boldsymbol{z}) としたとき、関数 qq は凸関数である。
  • (c)(c) 関数 r:Rn→Rr : \mathbb{R}^n \rightarrow \mathbb{R} を r(z)=h(x3(z),y3(z))r(\boldsymbol{z}) = h(\boldsymbol{x}^3(\boldsymbol{z}), \boldsymbol{y}^3(\boldsymbol{z})) としたとき、関数 rr は凸関数である。

English Version​

Kai​

(i)​

P1(z)Minimizex⊤x−z⊤Axsubject tox⊤x≤1\begin{aligned} \text{P1}(z) &\text{Minimize} &x^\top x - z^\top Ax\\ &\text{subject to} &x^\top x \leq 1\\ \end{aligned}

Lagrantian:

L(x,λ)=x⊤x−z⊤Ax−λ(x⊤x−1)L(x, \lambda) = x^\top x - z^\top Ax - \lambda (x^\top x -1)
KKT-conditions: {(z+2λ)x∗−z⊤A=0λ⪰0,ν⪰0λ≥0,(x∗)2−1≤0λ((x∗)2−1)=0\text{KKT-conditions: } \left\{ \begin{aligned} (z+2\lambda)x^* -z^\top A &= 0 \\ \lambda \succeq \boldsymbol{0}, \nu &\succeq \boldsymbol{0} \\ \lambda \geq 0, (x^*)^2 - 1 &\leq 0 \\ \lambda ((x^*)^2 - 1) &= 0 \end{aligned} \right.

easy to see x∗⊤=z⊤A2,λ=0x^{*\top} = \frac{z^\top A}{2}, \lambda = 0 satisfies KKT-conditions.

x1(z)=A⊤z2x^1(z) = \frac{A^\top z}{2}

(ii)​

P3(z)Minimizex⊤x+y⊤ysubject tox+y−z=0\begin{aligned} \text{P3}(z) &\text{Minimize} &x^\top x + y^\top y\\ &\text{subject to} &x+y-z =0\\ \end{aligned}

Lagrangian:

L(x,y,μ)=x⊤x+y⊤y+μ(x+y−z)L(x,y,\mu) = x^\top x + y^\top y + \mu (x+y - z)
KKT-conditions: {2x∗+μ=02y∗+μ=0x∗+y∗−z=0\text{KKT-conditions: } \left\{ \begin{aligned} 2x^* + \mu & = \boldsymbol{0} \\ 2y^* + \mu &= \boldsymbol{0} \\ x^* + y^* - z &= \boldsymbol{0} \\ \end{aligned} \right.

x∗=y∗=12z,μ=−12zx^* = y^* = \frac{1}{2} z , \mu = -\frac{1}{2} z satisfies KKT-conditions, and we get minimum 12z⊤z\frac{1}{2} z^\top z

(iii)​

(a)​

Let n=1n = 1 , then easy to see that the function is not conves.

(b)​

Easy to see x2(z)=−12A⊤zx_2(z) = -\frac{1}{2} A^\top z. Then

g(x2(z),z)=−14z⊤AA⊤z+z⊤zg(x_2(z),z) = -\frac{1}{4} z^\top AA^\top z + z^\top z

when −14A⊤A+I≺0-\frac{1}{4} A^\top A + I \prec \boldsymbol{0}, qq is not convex.

(c)(c)​

h=12z⊤zh = \frac{1}{2} z^\top z, obviously, it's convex

本页目录