跳到主要内容

京都大学 情報学研究科 数理工学専攻 2022年8月実施 線形計画

标签：

Author​

Casablanca

Description​

日本語版​

A∈Rm×n,b∈Rm,c∈Rn\boldsymbol{A} \in \mathbb{R}^{m \times n},\boldsymbol{b} \in \mathbb{R}^m,\boldsymbol{c} \in \mathbb{R}^n とする。次の線形計画問題を考える。

P:Minimizec⊤xsubject toAx=bx≧0\begin{aligned} \text{P}: &\text{Minimize} \quad \boldsymbol{c}^{\top}\boldsymbol{x} \\ &\text{subject to} \quad \boldsymbol{Ax} = \boldsymbol{b} \\ &\qquad \qquad \quad \boldsymbol{x} \geqq 0 \end{aligned}

ただし, 問題 PP の決定変数は x∈Rn\boldsymbol{x} \in \mathbb{R}^n であり, ⊤\top は転置記号を表す。また, Ay=b\boldsymbol{Ay} = \boldsymbol{b} と yi>0(i=1,…,n)y_i > 0(i = 1,\dots,n) を満たすベクトル y=(y1,…,yn)⊤∈Rn\boldsymbol{y} = (y_1,\dots,y_n)^{\top} \in \mathbb{R}^n が存在するとする。

以下の問いに答えよ。

(i) 問題 PP の双対問題を DD とする。r∗∈Rm\boldsymbol{r^*} \in \mathbb{R}^m が問題 DD の最適解であり, ある実数 ε>0\varepsilon > 0 に対して, c⊤y−b⊤r<ε\boldsymbol{c}^{\top}\boldsymbol{y} - \boldsymbol{b}^{\top}r < \varepsilon を満たす問題 DD の実行可能解 r∈Rm\boldsymbol{r} \in \mathbb{R}^m が存在すると仮定する。そのとき,

b⊤r∗−ε<b⊤r≦b⊤r∗\boldsymbol{b}^{\top}\boldsymbol{r^*} - \varepsilon < \boldsymbol{b}^{\top}\boldsymbol{r} \leqq \boldsymbol{b}^{\top}\boldsymbol{r^*}

が成立することを示せ。

(ii) Y∈Rn×n\boldsymbol{Y} \in \mathbb{R}^{n \times n} は第 (i,i)(i,i) 成分を yiy_i とする　対角行列と定義し, AY2A⊤\boldsymbol{AY}^2\boldsymbol{A}^{\top} は正則行列と仮定する。さらに, 以下の最適化問題を考える。

Q:Minimizec⊤dsubject toAd=0∣∣Y−1d∣∣≦12\begin{aligned} \text{Q}: &\text{Minimize} \quad \boldsymbol{c}^{\top}\boldsymbol{d} \\ &\text{subject to} \quad \boldsymbol{Ad} = \boldsymbol{0} \\ &\qquad \qquad \quad \boldsymbol{||Y^{-1}d||} \leqq \frac{1}{2} \end{aligned}

ここで, 問題 QQ の決定変数は d∈Rn\boldsymbol{d} \in \mathbb{R}^n であり, ∣∣⋅∣∣||\cdot|| はユークリッドノルマ表す (すなわち, 任意のベクトル zz に対して, ∣∣z∣∣=z⊤z||z|| = \sqrt{z^{\top}z}). また, p=(AY2A⊤)−1AY2c\boldsymbol{p} = (\boldsymbol{AY^2A}^{\top})^{-1}\boldsymbol{AY^2c} と定義し, c−A⊤p≠0\boldsymbol{c - A^{\top}p \neq 0} と仮定する。さらに, 以下のベクトルを定義する。

d∗=−Y2(c−A⊤p)2∣∣Y(c−A⊤p)∣∣\boldsymbol{d^*} = -\frac{\boldsymbol{Y^2(c - A^{\top}p)}}{2||\boldsymbol{Y(c - A^{\top}p)}||}

以下の問 (a) , (b) , (c)(c) に答えよ。

(a) c⊤d∗=−∣∣Y(c−A⊤p)∣∣2\boldsymbol{c^{\top}d^*} = - \frac{||\boldsymbol{Y(c - A^{\top}p)}||}{2} であることを示せ。

(b) d∗\boldsymbol{d^*} が問題 QQ の最適解であることを示せ。

(c)(c) x~=y+d∗\boldsymbol{\tilde{x} = y + d^*} とする。そのとき, x~\boldsymbol{\tilde{x}}が問題 PP の実行可能解であることと, c⊤x~<c⊤y\boldsymbol{c^{\top}\tilde{x}} < \boldsymbol{c^{\top}y} を満たすことを示せ。

English Version​

题目描述​

给定 A∈Rm×n\boldsymbol A\in\mathbb R^{m\times n}、 b∈Rm\boldsymbol b\in\mathbb R^m、 c∈Rn\boldsymbol c\in\mathbb R^n，考虑

P:最小化c⊤x满足Ax=b,x≧0.\begin{aligned} \mathrm P:\quad &\text{最小化}\quad\boldsymbol c^\top\boldsymbol x\\ &\text{满足}\quad\boldsymbol A\boldsymbol x=\boldsymbol b,\qquad \boldsymbol x\geqq0. \end{aligned}

假设存在严格正的可行向量 y=(y1,…,yn)⊤\boldsymbol y=(y_1,\ldots,y_n)^\top，即 Ay=b\boldsymbol A\boldsymbol y=\boldsymbol b 且每个 yi>0y_i>0。回答：

  1. 令 D 为 P 的对偶问题。假设 r∗\boldsymbol r^* 是 D 的最优解，且对某个 ε>0\varepsilon>0 存在 D 的可行解 r\boldsymbol r 满足 c⊤y−b⊤r<ε\boldsymbol c^\top\boldsymbol y-\boldsymbol b^\top\boldsymbol r<\varepsilon。证明
    b⊤r∗−ε<b⊤r≦b⊤r∗.\boldsymbol b^\top\boldsymbol r^*-\varepsilon <\boldsymbol b^\top\boldsymbol r \leqq\boldsymbol b^\top\boldsymbol r^*.
  2. 令 Y=diag⁡(y1,…,yn)\boldsymbol Y=\operatorname{diag}(y_1,\ldots,y_n)，假设 AY2A⊤\boldsymbol A\boldsymbol Y^2\boldsymbol A^\top 可逆。考虑
    Q:最小化c⊤d满足Ad=0,∥Y−1d∥≦12,\begin{aligned} \mathrm Q:\quad &\text{最小化}\quad\boldsymbol c^\top\boldsymbol d\\ &\text{满足}\quad\boldsymbol A\boldsymbol d=\boldsymbol0,\qquad \|\boldsymbol Y^{-1}\boldsymbol d\|\leqq\frac12, \end{aligned}
    其中 ∥z∥=z⊤z\|\boldsymbol z\|=\sqrt{\boldsymbol z^\top\boldsymbol z}。定义
    p=(AY2A⊤)−1AY2c,\boldsymbol p= (\boldsymbol A\boldsymbol Y^2\boldsymbol A^\top)^{-1} \boldsymbol A\boldsymbol Y^2\boldsymbol c,
    并假设 c−A⊤p≠0\boldsymbol c-\boldsymbol A^\top\boldsymbol p\ne\boldsymbol0，再令
    d∗=−Y2(c−A⊤p)2∥Y(c−A⊤p)∥.\boldsymbol d^*= -\frac{\boldsymbol Y^2(\boldsymbol c-\boldsymbol A^\top\boldsymbol p)} {2\|\boldsymbol Y(\boldsymbol c-\boldsymbol A^\top\boldsymbol p)\|}.
    1. 证明 c⊤d∗=−12∥Y(c−A⊤p)∥\boldsymbol c^\top\boldsymbol d^* =-\frac12\|\boldsymbol Y(\boldsymbol c-\boldsymbol A^\top\boldsymbol p)\|。
    2. 证明 d∗\boldsymbol d^* 是 Q 的最优解。
    3. 令 x~=y+d∗\tilde{\boldsymbol x}=\boldsymbol y+\boldsymbol d^*。证明 x~\tilde{\boldsymbol x} 是 P 的可行解，且 c⊤x~<c⊤y\boldsymbol c^\top\tilde{\boldsymbol x} <\boldsymbol c^\top\boldsymbol y。

考点​

  • 线性规划对偶间隙：利用严格可行原点与近似对偶解，把可行对偶目标夹在最优值附近。
  • 仿射尺度方向：在椭球信赖域与零空间约束中投影目标梯度，验证给定 d∗\boldsymbol d^* 的可行性和最优性。
  • 内点可行步：由缩放范数上界保证 y+d∗\boldsymbol y+\boldsymbol d^* 保持非负，并证明目标严格下降。

Kai​

(i)​

Lagrangian:

L(x,μ)=c⊤x+μ⊤(b−Ax)L(x,\mu) = c^\top x + \mu^\top(b-Ax)

Lagrange dual function:

g(μ)=inf⁡x{(c⊤−μ⊤A)x+μ⊤b}=b⊤μ,c+Aμ⪰0\begin{aligned} g(\mu)=& \inf_{x} \{ (c^\top - \mu^\top A )x + \mu^\top b \} \\ =&b^\top \mu, c + A\mu \succeq \mathbf{0} \end{aligned}

dual problem

D:Maximizeb⊤μsubject toc−Aμ⪰0\begin{aligned} D:&\text{Maximize} & b^\top \mu \\ &\text{subject to} & c - A\mu \succeq \mathbf{0} \end{aligned}

thus

b⊤r≥b⊤r∗,Ay=bb^\top r \geq b^\top r^*, Ay = b

since

c⊤y≤b⊤r+ϵc^\top y \leq b^\top r + \epsilon

and from duality we know

c⊤y≥b⊤r∗c^\top y \geq b^\top r^*

thus

b⊤r∗<b⊤r+ϵb^\top r^* < b^\top r + \epsilon

then

b⊤r∗−ϵ<b⊤r≤b⊤r∗b^\top r^* - \epsilon < b^\top r \leq b^\top r^*

(ii)​

(a)​

c⊤d∗=−c⊤Y2(c−A⊤p)2∣∣Y(c−A⊤p)∣∣c^\top d^* = - \frac{c^\top Y^2 (c-A^\top p)}{2||Y(c- A^\top p)||}
(Y(c−A⊤p))⊤(Y(c−A⊤p))=(c⊤−p⊤A)YY(c−A⊤p)=c⊤Y2c−c⊤Y2A⊤p−p⊤AY2c+p⊤AY2A⊤p=c⊤Y2c−c⊤Y2A⊤p−p⊤AY2c+p⊤AY2c=c⊤Y2(c−A⊤p)\begin{aligned} (Y(c- A^\top p))^\top (Y(c-A^\top p)) =& (c^\top - p^\top A)YY(c-A^\top p)\\ =& c^\top Y^2 c - c^\top Y^2 A^\top p - p^\top AY^2 c + p^\top A Y^2 A^\top p\\ = & c^\top Y^2 c - c^\top Y^2 A^\top p - p^\top AY^2 c + p^\top AY^2 c\\ = & c^\top Y^2 (c - A^\top p)\\ \end{aligned}

thus

c⊤d∗=−c⊤Y2(c−A⊤p)2∣∣Y(c−A⊤p)∣∣=(Y(c−A⊤p))2−2∣∣Y(c−A⊤p)∣∣=−∣∣Y(c−A⊤p)∣∣2c^\top d^* = -\frac{c^\top Y^2(c-A^\top p)}{2||Y(c- A^\top p)||} = \frac{(Y(c-A^\top p)) ^ 2}{-2||Y(c-A^\top p)||} = - \frac{||Y(c-A^\top p)||}{2}

(b)​

Write Q as:

Q:Minimizec⊤dsubject toAd=0 d⊤(Y−1)2d−14≤0\begin{aligned} Q:&\text{Minimize} & c^\top d \\ &\text{subject to} & Ad & = \mathbf{0} \\ &\text{ } &d^\top (Y^{-1})^2d - \frac 14 & \leq 0 \end{aligned}

Lagrangian:

L(d,λ,μ)=c⊤d+λ(d⊤(Y−1)2d−14)+μ(Ad)L(d,\lambda, \mu) = c^\top d + \lambda (d^\top (Y^{-1})^2 d - \frac 14) + \mu (Ad)

We get KKT_conditions:

 {λ(Y−1)2d^+c+Aμ=0λ≥0Ad^=0,d^⊤(Y−1)2d^≤14\text{ } \left\{ \begin{aligned} \lambda (Y^{-1})^2 \widehat{d} + c + A \mu & = & 0 \\ \lambda & \geq &0 \\ A \widehat{d} = 0, \widehat{d}^\top (Y^{-1})^2 \widehat{d} & \leq &\frac 14 \end{aligned} \right.
Ad∗=−AY2c−AY2A⊤pconstant=−AY2C−AY2Cconstant=0∥Y−1d∥=∥Y(c−A⊤p)2∥Y(c−A⊤p)∥∥=12λ∗(−c−A⊤p2∥Y(c−A⊤p)∥)+c⊤+Aμ∗=0\begin{align} &Ad^* = - \frac{AY^2c - AY^2A^\top p}{constant} = - \frac{AY^2C - AY^2C}{constant} = 0 \tag{1} \\ &\|Y^{-1}d\| = \|\frac{Y(c - A^\top p)}{2 \|Y(c-A^\top p) \|} \| = \frac 12 \tag{2} \\ &\lambda ^* (- \frac{c - A^\top p}{2 \|Y(c-A^\top p)\|}) + c^\top + A \mu^* = 0 \tag{3} \end{align}

d∗,λ∗,μ∗d^*, \lambda^* , \mu^* satisfies KKT-conditions for λ∗=2∥Y(c−A⊤p)∥,μ∗=−p\lambda ^* = 2\|Y(c-A^\top p)\|, \mu^* = -p

(c)(c)​

A(y+d∗)=bA(y+d^*) = b
d∗=−Y2Y(c−A⊤p)∥Y(c−A⊤p)∥d^* = - \frac{Y}{2} \frac{Y(c-A^\top p)}{ \|Y(c-A^\top p)\|}
d∗=−12Yn⃗,∣di∣<12yid^* = -\frac{1}{2} Y \vec{n}, |d_i| < \frac{1}{2} y_i

and easy to see:

−1⊤Y2≤d∗≤1⊤Y2-\mathbf{1}^\top \frac{Y}{2} \leq d^* \leq \mathbf{1}^\top \frac{Y}{2}

thus

y+d∗⪰0y + d^* \succeq \mathbf{0}

thus x~\widetilde{x} is feasible, and we get:

c⊤x~=c⊤y+c⊤d∗=c⊤y−∥Y(c−A⊤p)∥2<c⊤yc^\top \widetilde{x} = c^\top y + c^\top d^* = c^\top y - \frac{\|Y(c-A^\top p)\|}{2} < c^\top y
本页目录