跳到主要内容

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

标签：

Author​

Casablanca, 祭音Myyura

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​

题目描述​

设 A\boldsymbol A 是 n×nn\times n 正定对称矩阵。定义

f(x,z)=−x⊤x+z⊤Ax,g(x,z)=x⊤x+z⊤Ax+z⊤z,h(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):max⁡x∈Rnf(x,z)s.t.x⊤x≤1,P2(z):min⁡x∈Rng(x,z),P3(z):min⁡(x,y)∈Rn×Rnh(x,y)s.t.x+y=z.\begin{aligned} \mathrm{P1}(\boldsymbol z):\quad \max_{\boldsymbol x\in\mathbb R^n}\quad &f(\boldsymbol x,\boldsymbol z) &&\text{s.t.}\quad \boldsymbol x^\top\boldsymbol x\leq1,\\ \mathrm{P2}(\boldsymbol z):\quad \min_{\boldsymbol x\in\mathbb R^n}\quad &g(\boldsymbol x,\boldsymbol z),\\ \mathrm{P3}(\boldsymbol z):\quad \min_{(\boldsymbol x,\boldsymbol y)\in\mathbb R^n\times\mathbb R^n}\quad &h(\boldsymbol x,\boldsymbol y) &&\text{s.t.}\quad \boldsymbol x+\boldsymbol y=\boldsymbol z. \end{aligned}

已知对任意 z∈Rn\boldsymbol z\in\mathbb R^n，三个问题都各有唯一最优解，依次记为

x1(z),x2(z),(x3(z),y3(z)).\boldsymbol x^1(\boldsymbol z),\qquad \boldsymbol x^2(\boldsymbol z),\qquad \bigl(\boldsymbol x^3(\boldsymbol z),\boldsymbol y^3(\boldsymbol z)\bigr).

完成以下各问：

  1. 在

    z⊤A⊤Az≤4\boldsymbol z^\top\boldsymbol A^\top\boldsymbol A\boldsymbol z\leq4

    的条件下，利用 Karush–Kuhn–Tucker（KKT）条件求 P1(z)\mathrm{P1}(\boldsymbol z) 的最优解 x1(z)\boldsymbol x^1(\boldsymbol z)；注意该问题是最大化问题。

  2. 利用 KKT 条件求 P3(z)\mathrm{P3}(\boldsymbol z) 的最优解

    (x3(z),y3(z)).\bigl(\boldsymbol x^3(\boldsymbol z),\boldsymbol y^3(\boldsymbol z)\bigr).

  3. 分别判断下列命题的真伪；若为真则证明，若为假则给出反例：

    1. 令

      p(z)=f(x1(z),z),p(\boldsymbol z)=f\bigl(\boldsymbol x^1(\boldsymbol z),\boldsymbol z\bigr),

      则 p:Rn→Rp:\mathbb R^n\to\mathbb R 是凸函数。

    2. 令

      q(z)=g(x2(z),z),q(\boldsymbol z)=g\bigl(\boldsymbol x^2(\boldsymbol z),\boldsymbol z\bigr),

      则 q:Rn→Rq:\mathbb R^n\to\mathbb R 是凸函数。

    3. 令

      r(z)=h(x3(z),y3(z)),r(\boldsymbol z) =h\bigl(\boldsymbol x^3(\boldsymbol z),\boldsymbol y^3(\boldsymbol z)\bigr),

      则 r:Rn→Rr:\mathbb R^n\to\mathbb R 是凸函数。

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: {2(1+λ)x∗−A⊤z=0,λ≥0,(x∗)⊤x∗−1≤0,λ((x∗)⊤x∗−1)=0.\text{KKT-conditions: } \left\{ \begin{aligned} 2(1+\lambda)x^* -A^\top z &= 0, \\ \lambda &\geq 0, \\ (x^*)^\top x^* - 1 &\leq 0, \\ \lambda ((x^*)^\top x^* - 1) &= 0. \end{aligned} \right.

Since ∥A⊤z∥2=z⊤AA⊤z=z⊤A⊤Az≤4\|A^\top z\|^2=z^\top AA^\top z=z^\top A^\top Az\leq4, x∗=A⊤z/2x^*=A^\top z/2 is feasible and, with λ=0\lambda=0, satisfies the 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^\top (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,μ=−zx^* = y^* = \frac{1}{2} z , \mu = -z satisfies the KKT conditions, and the minimum is 12z⊤z\frac{1}{2} z^\top z.

(iii)​

(a)​

The statement is true. For each feasible xx, −x⊤x+z⊤Ax-x^\top x+z^\top Ax is affine in zz. Therefore,

p(z)=max⁡x⊤x≤1{−x⊤x+z⊤Ax}p(z)=\max_{x^\top x\leq1}\{-x^\top x+z^\top Ax\}

is the pointwise supremum of affine functions and hence is convex.

(b)​

The statement is false. We have x2(z)=−12A⊤zx^2(z) = -\frac{1}{2} A^\top z, and hence

q(z)=−14z⊤AA⊤z+z⊤z.q(z) = -\frac{1}{4} z^\top AA^\top z + z^\top z.

For example, A=3IA=3I is positive definite and gives q(z)=−54z⊤zq(z)=-\frac54 z^\top z, which is not convex.

(c)(c)​

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

本页目录