跳到主要内容

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

标签：

Author​

Casablanca, 祭音Myyura

Description​

日本語版​

A∈Rm×n,b∈Rm,C∈Rn×n\boldsymbol{A} \in \mathbb{R}^{m \times n}, \boldsymbol{b} \in \mathbb{R}^m, \boldsymbol{C} \in \mathbb{R}^{n \times n} とする。 パラメータ x=(x1,…,xn)⊤∈Rn\boldsymbol{x} = (x_1, \ldots, x_n)^\top \in \mathbb{R}^n をもつ次の非線形計画問題を考える。

P(x):Minimize∑i=1n(zi)⊤zi+y⊤y+x⊤Cxsubject toy−∑i=1nxizi=Ax−b\begin{aligned} \text{P}(\boldsymbol{x}): \quad &\text{Minimize} \quad \sum_{i=1}^n (\boldsymbol{z}^i)^\top \boldsymbol{z}^i + \boldsymbol{y}^\top \boldsymbol{y} + \boldsymbol{x}^\top C \boldsymbol{x} \\ &\text{subject to} \quad \boldsymbol{y} - \sum_{i=1}^n x_i \boldsymbol{z}^i = \boldsymbol{A}\boldsymbol{x} - \boldsymbol{b} \end{aligned}

ここで、P(x)\text{P}(\boldsymbol{x}) の決定変数は y,zi∈Rm (i=1,…,n)\boldsymbol{y}, \boldsymbol{z}^i \in \mathbb{R}^m \ (i = 1, \ldots, n) である。 また、⊤\top は転置記号を表す。さらに、任意の x\boldsymbol{x} に対して、問題 P(x)\text{P}(\boldsymbol{x}) の最適値が定義されているとし、その最適値を f(x)f(\boldsymbol{x}) と表す。

以下の問いに答えよ。

(i) 問題 P(x)\text{P}(\boldsymbol{x}) のカルーシュ・キューン・タッカー条件 (Karush-Kuhn-Tucker 条件) を書け。

(ii) 問題 P(x)\text{P}(\boldsymbol{x}) の目的関数が、y,zi∈Rm (i=1,…,n)\boldsymbol{y}, \boldsymbol{z}^i \in \mathbb{R}^m \ (i = 1, \ldots, n) に対して凸であることを示せ。

(iii) C\boldsymbol{C} を正定値対称行列と仮定し、次の最適化問題を考える。

P1:Minimizef(x)subject tox∈Rn\begin{aligned} \text{P1:} \quad &\text{Minimize} \quad f(\boldsymbol{x}) \\ &\text{subject to} \quad \boldsymbol{x} \in \mathbb{R}^n \end{aligned}

x∗∈Rn\boldsymbol{x}^* \in \mathbb{R}^n を問題 P1 の大域的最適解とするとき、以下の不等式が成り立つことを示せ。

(x∗)⊤x∗≦b⊤bλmin⁡(C)(\boldsymbol{x}^*)^\top \boldsymbol{x}^* \leqq \frac{\boldsymbol{b}^\top \boldsymbol{b}}{\lambda_{\min}(\boldsymbol{C})}

ただし、λmin⁡(C)\lambda_{\min}(\boldsymbol{C}) は C\boldsymbol{C} の最小固有値を表す。

(iv) A\boldsymbol{A} を m×nm \times n 零行列、b\boldsymbol{b} を mm 次元零ベクトルと仮定する。以下の最適化問題を考える。

P2:Minimizef(x)subject tox⊤x≦α\begin{aligned} \text{P2:} \quad &\text{Minimize} \quad f(\boldsymbol{x}) \\ &\text{subject to} \quad \boldsymbol{x}^\top \boldsymbol{x} \leqq \alpha \end{aligned}

ここで、α∈R\alpha \in \mathbb{R} は正の実数である。(x^,ρ),(xˉ,ρ)∈Rn×R(\hat{\boldsymbol{x}}, \rho), (\bar{\boldsymbol{x}}, \rho) \in \mathbb{R}^n \times \mathbb{R} が共に問題 P2 のカルーシュ・キューン・タッカー条件を満たすとき、f(x^)=f(xˉ)f(\hat{\boldsymbol{x}}) = f(\bar{\boldsymbol{x}}) が成り立つことを示せ。

English Version​

题目描述​

给定 A∈Rm×n\boldsymbol A\in\mathbb R^{m\times n}、 b∈Rm\boldsymbol b\in\mathbb R^m、 C∈Rn×n\boldsymbol C\in\mathbb R^{n\times n}。对参数 x=(x1,…,xn)⊤∈Rn\boldsymbol x=(x_1,\ldots,x_n)^\top\in\mathbb R^n，考虑以 y,zi∈Rm\boldsymbol y,\boldsymbol z^i\in\mathbb R^m（i=1,…,ni=1,\ldots,n）为变量的问题

P(x):最小化∑i=1n(zi)⊤zi+y⊤y+x⊤Cx满足y−∑i=1nxizi=Ax−b.\begin{aligned} \mathrm P(\boldsymbol x):\quad &\text{最小化}\quad \sum_{i=1}^n(\boldsymbol z^i)^\top\boldsymbol z^i +\boldsymbol y^\top\boldsymbol y +\boldsymbol x^\top\boldsymbol C\boldsymbol x\\ &\text{满足}\quad \boldsymbol y-\sum_{i=1}^n x_i\boldsymbol z^i =\boldsymbol A\boldsymbol x-\boldsymbol b. \end{aligned}

假设其最优值对任意 x\boldsymbol x 均有定义，记为 f(x)f(\boldsymbol x)。回答：

  1. 写出 P(x)(\boldsymbol x) 的 KKT 条件。

  2. 证明 P(x)(\boldsymbol x) 的目标函数关于决策变量 y,z1,…,zn\boldsymbol y,\boldsymbol z^1,\ldots,\boldsymbol z^n 是凸函数。

  3. 假设 C\boldsymbol C 为正定对称矩阵，考虑 min⁡x∈Rnf(x)\min_{\boldsymbol x\in\mathbb R^n}f(\boldsymbol x)。若 x∗\boldsymbol x^* 是其全局最优解，证明

    (x∗)⊤x∗≦b⊤bλmin⁡(C),(\boldsymbol x^*)^\top\boldsymbol x^* \leqq\frac{\boldsymbol b^\top\boldsymbol b} {\lambda_{\min}(\boldsymbol C)},

    其中 λmin⁡(C)\lambda_{\min}(\boldsymbol C) 为 C\boldsymbol C 的最小特征值。

  4. 假设 A\boldsymbol A、b\boldsymbol b 均为零，并对 α>0\alpha>0 考虑

    min⁡f(x)满足x⊤x≦α.\min f(\boldsymbol x) \quad\text{满足}\quad \boldsymbol x^\top\boldsymbol x\leqq\alpha.

    若 (x^,ρ)(\hat{\boldsymbol x},\rho) 与 (xˉ,ρ)(\bar{\boldsymbol x},\rho) 都满足该问题的 KKT 条件，证明 f(x^)=f(xˉ)f(\hat{\boldsymbol x})=f(\bar{\boldsymbol x})。

Kai​

(i)​

Lagrangian:

L(y,zi,μ)=∑i=1n(zi)⊤zi+y⊤y+x⊤Cx+μ⊤(y−∑i=1nxizi−Ax+b)L(y, z^i, \mu) = \sum_{i=1}^{n}(z^i)^\top z^i + y^\top y + x^\top C x + \mu^\top (y - \sum_{i=1}^{n}x_iz^i - Ax + b)

and we get:

KKT-conditions {2y+μ=02zi−xiμ=0y−∑i=1nxizi−Ax+b=0\text{KKT-conditions } \left\{ \begin{aligned} 2y + \mu & = \mathbf{0} \\ 2z^i - x_i \mu &=0 \\ y - \sum_{i=1}^{n}x_iz^i - Ax + b &= 0\\ \end{aligned} \right.

(ii)​

Each (zi)⊤zi(z^i)^\top z^i and y⊤yy^\top y is convex, while x⊤Cxx^\top Cx is constant with respect to the decision variables. Hence the objective function is convex.

(iii)​

By (i) we have

zi=−xiy,y=Ax−b1+x⊤x,z^i=-x_i y,\qquad y=\frac{Ax-b}{1+x^\top x},

and

f(x)=(Ax−b)⊤(Ax−b)1+x⊤x+x⊤Cx.f(x)=\frac{(Ax-b)^\top(Ax-b)}{1+x^\top x}+x^\top Cx.

Since x∗x^* is globally optimal,

λmin⁡(C)(x∗)⊤x∗≤(x∗)⊤Cx∗≤f(x∗)≤f(0)=b⊤b.\begin{aligned} \lambda_{\min}(C)(x^*)^\top x^* &\le (x^*)^\top Cx^*\\ &\le f(x^*)\\ &\le f(0)=b^\top b. \end{aligned}

Therefore (x∗)⊤x∗≤b⊤b/λmin⁡(C)(x^*)^\top x^*\le b^\top b/\lambda_{\min}(C).

(iv)​

(P2)Minimizex⊤Cxsubject tox⊤x≤α\begin{aligned} (P2) &\text{Minimize} & x^\top Cx \\ &\text{subject to} & x^\top x \leq \alpha \end{aligned}

Lagrangian:

L(x,ρ)=x⊤Cx+ρ(x⊤x−α)L(x,\rho) = x^\top Cx + \rho (x^\top x - \alpha)
KKT-conditions {(C⊤+C)x+2ρx=0ρ(x⊤x−α)=0ρ≥0,x⊤x−α≤0.\text{KKT-conditions } \left\{ \begin{aligned} (C^\top + C)x + 2\rho x &= \mathbf{0} \\ \rho (x^\top x - \alpha) &= 0 \\ \rho&\geq0,\qquad x^\top x-\alpha\leq0. \end{aligned} \right.
2x^⊤Cx^=−2ρx^⊤x^2\hat{x}^\top C \hat{x} = -2\rho \hat{x}^\top \hat{x}
2xˉ⊤Cxˉ=−2ρxˉ⊤xˉ2 \bar{x}^\top C \bar{x} = -2\rho \bar{x}^\top \bar{x}

If ρ≠0\rho\ne0, complementarity gives x^⊤x^=xˉ⊤xˉ=α\hat{x}^\top\hat{x}=\bar{x}^\top\bar{x}=\alpha, and hence

f(x^)=x^⊤Cx^=−ρα=xˉ⊤Cxˉ=f(xˉ).f(\hat{x})=\hat{x}^\top C\hat{x}=-\rho\alpha =\bar{x}^\top C\bar{x}=f(\bar{x}).

If ρ=0\rho=0, the two displayed stationarity identities give f(x^)=f(xˉ)=0f(\hat{x})=f(\bar{x})=0.

本页目录