跳到主要内容

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

标签：

Author​

Casablanca

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

(zi)⊤zi(z^i)^\top z^i is convex, y⊤yy^\top y is convex, then the objective function is convex.

(iii)​

By (i) we have

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

and

∑i=1n(zi)⊤zi+y⊤y+x⊤Cx=(1+x⊤x)y⊤y+x⊤Cx=(Ax−b)⊤(Ax−b)1+x⊤x+x⊤Xx=f(x)\begin{aligned} \sum_{i=1}^{n} (z^i)^\top z^i + y^\top y + x^\top C x &= (1+x^\top x)\\ y^\top y + x^\top C x &= \frac{(Ax - b)^\top (Ax - b)}{ 1 + x^\top x} + x^\top X x = f(x) \end{aligned}
f(x∗)≤f(0)f(x^*) \leq f(0)
b⊤b≥(Ax∗−b)⊤(AX∗−b)1+(x∗)2b^\top b \geq \frac{(Ax^* - b)^\top(AX^* - b)}{1+(x^*)^2}

since CC is symmetric positive difinete, CC can be decomposited as C=P−1ΛPC = P^{-1} \Lambda P , and P−1=P⊤P^{-1} = P^\top

(x∗)⊤Cx∗=(Px∗)⊤ΛPx∗≥λmin(C)∣∣(Px∗)⊤∣∣∗∣∣Px∗∣∣=λmin(C)(x∗)⊤x∗\begin{aligned} (x^*)^\top C x^* &= (Px^*)^\top \Lambda Px^* \\ &\geq \lambda_{min}(C)||(Px^*)^\top|| *||Px^*|| \\ &=\lambda_{min}(C) (x^*)^\top x^* \end{aligned}

Thus (x∗)⊤x∗≤b⊤bλmin(C)(x^*)^\top x^* \leq \frac{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⊤x−α≤0\text{KKT-conditions } \left\{ \begin{aligned} (C^\top + C)x + 2\rho x &= \mathbf{0} \\ \rho (x^\top x - \alpha) &= 0 \\ \rho \geq 0, x^\top x^\top x - \alpha &\leq 0 \\ \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 \widetilde{x}^\top C \widetilde{x} = -2\rho \widetilde{x}^\top \widetilde{x}

If ρ≠0\rho \neq 0, then x^2=x~2=α,x^⊤Cx^=−ρα=x~⊤Cx~\hat{x}^2 = \widetilde{x}^2 = \alpha ,\hat{x}^\top C \hat{x} = -\rho \alpha = \widetilde{x}^\top C \widetilde{x}.

If ρ=0\rho = 0, then x^⊤Cx^=0=x~⊤Cx~\hat{x}^\top C \hat{x} = 0 = \widetilde{x}^\top C \widetilde{x}.

本页目录