跳到主要内容

京都大学 情報学研究科 数理工学専攻 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​

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}.

本页目录