京都大学 情報学研究科 数理工学専攻 2022年8月実施 線形計画 Author Casablanca, 祭音Myyura
Description 大学公表の原題
日本語版
A ∈ R m × n , b ∈ R m , c ∈ R n \boldsymbol{A} \in \mathbb{R}^{m \times n},\boldsymbol{b} \in \mathbb{R}^m,\boldsymbol{c} \in \mathbb{R}^n A ∈ R m × n , b ∈ R m , c ∈ R n
P : Minimize c ⊤ x subject to A x = b x ≧ 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} P : Minimize c ⊤ x subject to Ax = b x ≧ 0 ただし, 問題 P P P x ∈ R n \boldsymbol{x} \in \mathbb{R}^n x ∈ R n ⊤ \top ⊤ A y = b \boldsymbol{Ay} = \boldsymbol{b} Ay = b y i > 0 ( i = 1 , … , n ) y_i > 0(i = 1,\dots,n) y i > 0 ( i = 1 , … , n ) y = ( y 1 , … , y n ) ⊤ ∈ R n \boldsymbol{y} = (y_1,\dots,y_n)^{\top} \in \mathbb{R}^n y = ( y 1 , … , y n ) ⊤ ∈ R n
以下の問いに答えよ。
(i) 問題 P P P D D D r ∗ ∈ R m \boldsymbol{r^*} \in \mathbb{R}^m r ∗ ∈ R m D D D ε > 0 \varepsilon > 0 ε > 0 c ⊤ y − b ⊤ r < ε \boldsymbol{c}^{\top}\boldsymbol{y} - \boldsymbol{b}^{\top}r < \varepsilon c ⊤ y − b ⊤ r < ε D D D r ∈ R m \boldsymbol{r} \in \mathbb{R}^m r ∈ 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^*} b ⊤ r ∗ − ε < b ⊤ r ≦ b ⊤ r ∗ が成立することを示せ。
(ii) Y ∈ R n × n \boldsymbol{Y} \in \mathbb{R}^{n \times n} Y ∈ R n × n ( i , i ) (i,i) ( i , i ) y i y_i y i A Y 2 A ⊤ \boldsymbol{AY}^2\boldsymbol{A}^{\top} AY 2 A ⊤
Q : Minimize c ⊤ d subject to A d = 0 ∣ ∣ Y − 1 d ∣ ∣ ≦ 1 2 \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} Q : Minimize c ⊤ d subject to Ad = 0 ∣∣ Y − 1 d ∣∣ ≦ 2 1 ここで, 問題 Q Q Q d ∈ R n \boldsymbol{d} \in \mathbb{R}^n d ∈ R n ∣ ∣ ⋅ ∣ ∣ ||\cdot|| ∣∣ ⋅ ∣∣ z z z ∣ ∣ z ∣ ∣ = z ⊤ z ||z|| = \sqrt{z^{\top}z} ∣∣ z ∣∣ = z ⊤ z p = ( A Y 2 A ⊤ ) − 1 A Y 2 c \boldsymbol{p} = (\boldsymbol{AY^2A}^{\top})^{-1}\boldsymbol{AY^2c} p = ( A Y 2 A ⊤ ) − 1 A Y 2 c c − A ⊤ p ≠ 0 \boldsymbol{c - A^{\top}p \neq 0} c − A ⊤ p = 0
d ∗ = − Y 2 ( 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)}||} d ∗ = − 2∣∣ Y ( c − A ⊤ p ) ∣∣ Y 2 ( c − A ⊤ p ) 以下の問 (a) , (b) , ( c ) (c) ( c )
(a) c ⊤ d ∗ = − ∣ ∣ Y ( c − A ⊤ p ) ∣ ∣ 2 \boldsymbol{c^{\top}d^*} = - \frac{||\boldsymbol{Y(c - A^{\top}p)}||}{2} c ⊤ d ∗ = − 2 ∣∣ Y ( c − A ⊤ p ) ∣∣
(b) d ∗ \boldsymbol{d^*} d ∗ Q Q Q
( c ) (c) ( c ) x ~ = y + d ∗ \boldsymbol{\tilde{x} = y + d^*} x ~ = y + d ∗ x ~ \boldsymbol{\tilde{x}} x ~ P P P c ⊤ x ~ < c ⊤ y \boldsymbol{c^{\top}\tilde{x}} < \boldsymbol{c^{\top}y} c ⊤ x ~ < c ⊤ y
English Version
题目描述
给定
A ∈ R m × n \boldsymbol A\in\mathbb R^{m\times n} A ∈ R m × n b ∈ R m \boldsymbol b\in\mathbb R^m b ∈ R m c ∈ R n \boldsymbol c\in\mathbb R^n c ∈ R n
P : 最小化 c ⊤ x 满足 A x = 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} P : 最小化 c ⊤ x 满足 A x = b , x ≧ 0. 假设存在严格正的可行向量
y = ( y 1 , … , y n ) ⊤ \boldsymbol y=(y_1,\ldots,y_n)^\top y = ( y 1 , … , y n ) ⊤ A y = b \boldsymbol A\boldsymbol y=\boldsymbol b A y = b y i > 0 y_i>0 y i > 0
令 D 为 P 的对偶问题。假设 r ∗ \boldsymbol r^* r ∗ ε > 0 \varepsilon>0 ε > 0 r \boldsymbol r r c ⊤ y − b ⊤ r < ε \boldsymbol c^\top\boldsymbol y-\boldsymbol b^\top\boldsymbol r<\varepsilon c ⊤ y − b ⊤ r < ε
b ⊤ r ∗ − ε < b ⊤ r ≦ b ⊤ r ∗ . \boldsymbol b^\top\boldsymbol r^*-\varepsilon
<\boldsymbol b^\top\boldsymbol r
\leqq\boldsymbol b^\top\boldsymbol r^*. b ⊤ r ∗ − ε < b ⊤ r ≦ b ⊤ r ∗ .
令 Y = diag ( y 1 , … , y n ) \boldsymbol Y=\operatorname{diag}(y_1,\ldots,y_n) Y = diag ( y 1 , … , y n ) A Y 2 A ⊤ \boldsymbol A\boldsymbol Y^2\boldsymbol A^\top A Y 2 A ⊤
Q : 最小化 c ⊤ d 满足 A d = 0 , ∥ Y − 1 d ∥ ≦ 1 2 , \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} Q : 最小化 c ⊤ d 满足 A d = 0 , ∥ Y − 1 d ∥ ≦ 2 1 , 其中 ∥ z ∥ = z ⊤ z \|\boldsymbol z\|=\sqrt{\boldsymbol z^\top\boldsymbol z} ∥ z ∥ = z ⊤ z
p = ( A Y 2 A ⊤ ) − 1 A Y 2 c , \boldsymbol p=
(\boldsymbol A\boldsymbol Y^2\boldsymbol A^\top)^{-1}
\boldsymbol A\boldsymbol Y^2\boldsymbol c, p = ( A Y 2 A ⊤ ) − 1 A Y 2 c , 并假设 c − A ⊤ p ≠ 0 \boldsymbol c-\boldsymbol A^\top\boldsymbol p\ne\boldsymbol0 c − A ⊤ p = 0
d ∗ = − Y 2 ( 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)\|}. d ∗ = − 2∥ Y ( c − A ⊤ p ) ∥ Y 2 ( c − A ⊤ p ) .
证明 c ⊤ d ∗ = − 1 2 ∥ Y ( c − A ⊤ p ) ∥ \boldsymbol c^\top\boldsymbol d^*=-\frac12\|\boldsymbol Y(\boldsymbol c-\boldsymbol A^\top\boldsymbol p)\| c ⊤ d ∗ = − 2 1 ∥ Y ( c − A ⊤ p ) ∥
证明 d ∗ \boldsymbol d^* d ∗
令 x ~ = y + d ∗ \tilde{\boldsymbol x}=\boldsymbol y+\boldsymbol d^* x ~ = y + d ∗ x ~ \tilde{\boldsymbol x} x ~ c ⊤ x ~ < c ⊤ y \boldsymbol c^\top\tilde{\boldsymbol x}<\boldsymbol c^\top\boldsymbol y c ⊤ x ~ < c ⊤ y
Kai (i)
Lagrangian:
L ( x , μ ) = c ⊤ x + μ ⊤ ( b − A x ) L(x,\mu) = c^\top x + \mu^\top(b-Ax) L ( x , μ ) = c ⊤ x + μ ⊤ ( b − A x ) Lagrange dual function:
g ( μ ) = inf x ⪰ 0 { ( c ⊤ − μ ⊤ A ) x + μ ⊤ b } = b ⊤ μ , c − A ⊤ μ ⪰ 0 \begin{aligned}
g(\mu)=& \inf_{x\succeq0} \{ (c^\top - \mu^\top A )x + \mu^\top b \} \\
=&b^\top \mu,\qquad c-A^\top\mu \succeq \mathbf{0}
\end{aligned} g ( μ ) = = x ⪰ 0 inf {( c ⊤ − μ ⊤ A ) x + μ ⊤ b } b ⊤ μ , c − A ⊤ μ ⪰ 0 If any component of c − A ⊤ μ c-A^\top\mu c − A ⊤ μ g ( μ ) = − ∞ g(\mu)=-\infty g ( μ ) = − ∞
dual problem
D : Maximize b ⊤ μ subject to c − A ⊤ μ ⪰ 0 \begin{aligned}
D:&\text{Maximize} & b^\top \mu \\
&\text{subject to} & c - A^\top\mu \succeq \mathbf{0}
\end{aligned} D : Maximize subject to b ⊤ μ c − A ⊤ μ ⪰ 0 thus
b ⊤ r ≤ b ⊤ r ∗ , A y = b b^\top r \leq b^\top r^*, \qquad Ay = b b ⊤ r ≤ b ⊤ r ∗ , A y = b since
c ⊤ y < b ⊤ r + ϵ c^\top y < b^\top r + \epsilon c ⊤ y < b ⊤ r + ϵ and from duality we know
c ⊤ y ≥ b ⊤ r ∗ c^\top y \geq b^\top r^* c ⊤ y ≥ b ⊤ r ∗ thus
b ⊤ r ∗ < b ⊤ r + ϵ b^\top r^* < b^\top r + \epsilon b ⊤ r ∗ < b ⊤ r + ϵ then
b ⊤ r ∗ − ϵ < b ⊤ r ≤ b ⊤ r ∗ b^\top r^* - \epsilon < b^\top r \leq b^\top r^* b ⊤ r ∗ − ϵ < b ⊤ r ≤ b ⊤ r ∗ (ii)
(a)
c ⊤ d ∗ = − c ⊤ Y 2 ( 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)||} c ⊤ d ∗ = − 2∣∣ Y ( c − A ⊤ p ) ∣∣ c ⊤ Y 2 ( c − A ⊤ p ) ( Y ( c − A ⊤ p ) ) ⊤ ( Y ( c − A ⊤ p ) ) = ( c ⊤ − p ⊤ A ) Y Y ( c − A ⊤ p ) = c ⊤ Y 2 c − c ⊤ Y 2 A ⊤ p − p ⊤ A Y 2 c + p ⊤ A Y 2 A ⊤ p = c ⊤ Y 2 c − c ⊤ Y 2 A ⊤ p − p ⊤ A Y 2 c + p ⊤ A Y 2 c = c ⊤ Y 2 ( 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} ( Y ( c − A ⊤ p ) ) ⊤ ( Y ( c − A ⊤ p )) = = = = ( c ⊤ − p ⊤ A ) YY ( c − A ⊤ p ) c ⊤ Y 2 c − c ⊤ Y 2 A ⊤ p − p ⊤ A Y 2 c + p ⊤ A Y 2 A ⊤ p c ⊤ Y 2 c − c ⊤ Y 2 A ⊤ p − p ⊤ A Y 2 c + p ⊤ A Y 2 c c ⊤ Y 2 ( c − A ⊤ p ) thus
c ⊤ d ∗ = − c ⊤ Y 2 ( c − A ⊤ p ) 2 ∥ Y ( c − A ⊤ p ) ∥ = − ∥ Y ( c − A ⊤ p ) ∥ 2 2 ∥ Y ( c − A ⊤ p ) ∥ = − ∥ Y ( c − A ⊤ p ) ∥ 2 c^\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} c ⊤ d ∗ = − 2∥ Y ( c − A ⊤ p ) ∥ c ⊤ Y 2 ( c − A ⊤ p ) = − 2∥ Y ( c − A ⊤ p ) ∥ ∥ Y ( c − A ⊤ p ) ∥ 2 = − 2 ∥ Y ( c − A ⊤ p ) ∥ (b)
Write Q as:
Q : Minimize c ⊤ d subject to A d = 0 d ⊤ ( Y − 1 ) 2 d − 1 4 ≤ 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} Q : Minimize subject to c ⊤ d A d d ⊤ ( Y − 1 ) 2 d − 4 1 = 0 ≤ 0 Lagrangian:
L ( d , λ , μ ) = c ⊤ d + λ ( d ⊤ ( Y − 1 ) 2 d − 1 4 ) + μ ⊤ A d L(d,\lambda, \mu) = c^\top d + \lambda (d^\top (Y^{-1})^2 d - \frac 14) + \mu^\top Ad L ( d , λ , μ ) = c ⊤ d + λ ( d ⊤ ( Y − 1 ) 2 d − 4 1 ) + μ ⊤ A d We get KKT_conditions:
{ c + 2 λ ( Y − 1 ) 2 d ^ + A ⊤ μ = 0 λ ≥ 0 A d ^ = 0 , d ^ ⊤ ( Y − 1 ) 2 d ^ ≤ 1 4 λ ( d ^ ⊤ ( Y − 1 ) 2 d ^ − 1 4 ) = 0 \text{ } \left\{
\begin{aligned}
c + 2\lambda (Y^{-1})^2 \widehat{d} + A^\top\mu & = & 0 \\
\lambda & \geq &0 \\
A \widehat{d} = 0,\quad \widehat{d}^\top (Y^{-1})^2 \widehat{d} & \leq &\frac 14\\
\lambda\left(\widehat{d}^\top (Y^{-1})^2 \widehat{d}-\frac14\right)&=&0
\end{aligned}
\right. ⎩ ⎨ ⎧ c + 2 λ ( Y − 1 ) 2 d + A ⊤ μ λ A d = 0 , d ⊤ ( Y − 1 ) 2 d λ ( d ⊤ ( Y − 1 ) 2 d − 4 1 ) = ≥ ≤ = 0 0 4 1 0 A d ∗ = − A Y 2 c − A Y 2 A ⊤ p 2 ∥ Y ( c − A ⊤ p ) ∥ = 0 , ∥ Y − 1 d ∗ ∥ = ∥ Y ( c − A ⊤ p ) 2 ∥ Y ( c − A ⊤ p ) ∥ ∥ = 1 2 , c + 2 λ ∗ ( Y − 1 ) 2 d ∗ + A ⊤ μ ∗ = 0. \begin{align}
&Ad^* = - \frac{AY^2c - AY^2A^\top p}{2\|Y(c-A^\top p)\|}=0, \tag{1} \\
&\|Y^{-1}d^*\| = \left\|\frac{Y(c - A^\top p)}{2 \|Y(c-A^\top p) \|}\right\| = \frac 12, \tag{2} \\
&c+2\lambda^*(Y^{-1})^2d^*+A^\top\mu^*=0. \tag{3}
\end{align} A d ∗ = − 2∥ Y ( c − A ⊤ p ) ∥ A Y 2 c − A Y 2 A ⊤ p = 0 , ∥ Y − 1 d ∗ ∥ = 2∥ Y ( c − A ⊤ p ) ∥ Y ( c − A ⊤ p ) = 2 1 , c + 2 λ ∗ ( Y − 1 ) 2 d ∗ + A ⊤ μ ∗ = 0. ( 1 ) ( 2 ) ( 3 ) Indeed, (3) holds for
λ ∗ = ∥ Y ( c − A ⊤ p ) ∥ , μ ∗ = − p . \lambda^*=\|Y(c-A^\top p)\|,\qquad \mu^*=-p. λ ∗ = ∥ Y ( c − A ⊤ p ) ∥ , μ ∗ = − p . Thus d ∗ , λ ∗ , μ ∗ d^*,\lambda^*,\mu^* d ∗ , λ ∗ , μ ∗ d = 0 d=0 d = 0 d ∗ d^* d ∗
( c ) (c) ( c ) A ( y + d ∗ ) = b A(y+d^*) = b A ( y + d ∗ ) = b d ∗ = − Y 2 Y ( c − A ⊤ p ) ∥ Y ( c − A ⊤ p ) ∥ d^* = - \frac{Y}{2} \frac{Y(c-A^\top p)}{ \|Y(c-A^\top p)\|} d ∗ = − 2 Y ∥ Y ( c − A ⊤ p ) ∥ Y ( c − A ⊤ p ) d ∗ = − 1 2 Y n ⃗ , n ⃗ = Y ( c − A ⊤ p ) ∥ Y ( c − A ⊤ p ) ∥ , ∥ n ⃗ ∥ = 1. d^* = -\frac{1}{2} Y \vec{n},\qquad
\vec n=\frac{Y(c-A^\top p)}{\|Y(c-A^\top p)\|},\qquad \|\vec n\|=1. d ∗ = − 2 1 Y n , n = ∥ Y ( c − A ⊤ p ) ∥ Y ( c − A ⊤ p ) , ∥ n ∥ = 1. Therefore, ∣ d i ∗ ∣ ≤ y i / 2 |d_i^*|\leq y_i/2 ∣ d i ∗ ∣ ≤ y i /2
y i + d i ∗ ≥ y i 2 > 0 ( i = 1 , … , n ) . y_i+d_i^*\geq\frac{y_i}{2}>0\qquad(i=1,\ldots,n). y i + d i ∗ ≥ 2 y i > 0 ( i = 1 , … , n ) . Thus x ~ \widetilde{x} x
c ⊤ x ~ = c ⊤ y + c ⊤ d ∗ = c ⊤ y − ∥ Y ( c − A ⊤ p ) ∥ 2 < c ⊤ y c^\top \widetilde{x} = c^\top y + c^\top d^* = c^\top y - \frac{\|Y(c-A^\top p)\|}{2} < c^\top y c ⊤ x = c ⊤ y + c ⊤ d ∗ = c ⊤ y − 2 ∥ Y ( c − A ⊤ p ) ∥ < c ⊤ y