京都大学 情報学研究科 数理工学専攻 2019年8月実施 線形計画 Author Casablanca, 祭音Myyura
Description 日本語版
a i ( i = 1 , … , n ) \boldsymbol{a}^i \ (i = 1, \ldots, n) a i ( i = 1 , … , n ) b \boldsymbol{b} b m m m c = ( c 1 , c 2 , … , c n ) ⊤ \boldsymbol{c} = (c_1, c_2, \ldots, c_n)^{\top} c = ( c 1 , c 2 , … , c n ) ⊤ n n n ⊤ \top ⊤ A \boldsymbol{A} A i i i a i \boldsymbol{a}^i a i m × n m \times n m × n A = [ a 1 a 2 ⋯ a n ] \boldsymbol{A} = [\boldsymbol{a}^1 \ \boldsymbol{a}^2 \ \cdots \ \boldsymbol{a}^n] A = [ a 1 a 2 ⋯ a n ]
次の線形計画問題 (P) とその双対問題 (D) を考える．
(P) Minimize c ⊤ x subject to A x = b x ≧ 0 \begin{aligned}
\text{(P)}\ &\text{Minimize} &\boldsymbol{c}^{\top} \boldsymbol{x} \\
&\text{subject to} &\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b} \\
&\text{ } &\boldsymbol{x} \geqq \boldsymbol{0}
\end{aligned} (P) Minimize subject to c ⊤ x A x = b x ≧ 0 (D) Maximize b ⊤ w subject to A ⊤ w ≦ c \begin{aligned}
\text{(D)}\ &\text{Maximize} &\boldsymbol{b}^{\top} \boldsymbol{w} \\
&\text{subject to} &\boldsymbol{A}^{\top} \boldsymbol{w} \leqq \boldsymbol{c}
\end{aligned} (D) Maximize subject to b ⊤ w A ⊤ w ≦ c ただし，(P) の決定変数は x ∈ R n \boldsymbol{x} \in \mathbb{R}^n x ∈ R n w ∈ R m \boldsymbol{w} \in \mathbb{R}^m w ∈ R m
問題 (P) は x 1 ∗ = 0 x_1^* = 0 x 1 ∗ = 0 x ∗ = ( x 1 ∗ , x 2 ∗ , … , x n ∗ ) ⊤ \boldsymbol{x}^* = (x_1^*, x_2^*, \ldots, x_n^*)^{\top} x ∗ = ( x 1 ∗ , x 2 ∗ , … , x n ∗ ) ⊤
(Q) Maximize b ⊤ u − ( c ⊤ x ∗ ) v subject to ( a 1 ) ⊤ u − c 1 v ≦ − 1 ( a i ) ⊤ u − c i v ≦ 0 ( i = 2 , 3 , … , n ) v ≧ 0 \begin{aligned}
\text{(Q)}\ \text{Maximize } \ & \boldsymbol{b}^{\top} \boldsymbol{u} - (\boldsymbol{c}^{\top} \boldsymbol{x}^*) v \\
\text{subject to } \ &(\boldsymbol{a}^1)^{\top} \boldsymbol{u} - c_1 v \leqq -1 \\
\text{ } &(\boldsymbol{a}^i)^{\top} \boldsymbol{u} - c_i v \leqq 0 \ (i = 2, 3, \ldots, n) \\
\text{ } &v \geqq 0
\end{aligned} (Q) Maximize subject to b ⊤ u − ( c ⊤ x ∗ ) v ( a 1 ) ⊤ u − c 1 v ≦ − 1 ( a i ) ⊤ u − c i v ≦ 0 ( i = 2 , 3 , … , n ) v ≧ 0 ただし，決定変数は u ∈ R m \boldsymbol{u} \in \mathbb{R}^m u ∈ R m v ∈ R v \in \mathbb{R} v ∈ R
以下の問いに答えよ．
(i) 問題 (Q) の双対問題を書け．
(ii) 問題 (Q) が最適解を持つことを示せ．
(iii) 問題 (Q) の最適値が 0 0 0
(iv) 問題 (Q) は v ∗ > 0 v^* > 0 v ∗ > 0 ( u ∗ , v ∗ ) (\boldsymbol{u}^*, v^*) ( u ∗ , v ∗ ) w ∗ = u ∗ v ∗ \boldsymbol{w}^* = \frac{\boldsymbol{u}^*}{v^*} w ∗ = v ∗ u ∗ w ∗ \boldsymbol{w}^* w ∗
(v) 問題 (Q) は v ∗ = 0 v^* = 0 v ∗ = 0 ( u ∗ , v ∗ ) (\boldsymbol{u}^*, v^*) ( u ∗ , v ∗ ) ( a 1 ) ⊤ w ∗ < c 1 (\boldsymbol{a}^1)^{\top} \boldsymbol{w}^* < c_1 ( a 1 ) ⊤ w ∗ < c 1 w ∗ \boldsymbol{w}^* w ∗
English Version
题目描述
令 a i \boldsymbol a^i a i i = 1 , … , n i=1,\ldots,n i = 1 , … , n b \boldsymbol b b m m m c = ( c 1 , … , c n ) ⊤ \boldsymbol c=(c_1,\ldots,c_n)^\top c = ( c 1 , … , c n ) ⊤ n n n A = [ a 1 ⋯ a n ] \boldsymbol A=[\boldsymbol a^1\ \cdots\ \boldsymbol a^n] A = [ a 1 ⋯ a n ]
( P ) : min x c ⊤ x A x = b , x ≧ 0 , ( D ) : max w b ⊤ w A ⊤ w ≦ c , \begin{aligned}
(\mathrm P):\quad&\min_{\boldsymbol x}\ \boldsymbol c^\top\boldsymbol x\\
&\boldsymbol A\boldsymbol x=\boldsymbol b,\quad
\boldsymbol x\geqq\boldsymbol0,
\end{aligned}
\qquad
\begin{aligned}
(\mathrm D):\quad&\max_{\boldsymbol w}\ \boldsymbol b^\top\boldsymbol w\\
&\boldsymbol A^\top\boldsymbol w\leqq\boldsymbol c,
\end{aligned} ( P ) : x min c ⊤ x A x = b , x ≧ 0 , ( D ) : w max b ⊤ w A ⊤ w ≦ c , 其中 x ∈ R n \boldsymbol x\in\mathbb R^n x ∈ R n w ∈ R m \boldsymbol w\in\mathbb R^m w ∈ R m x ∗ = ( x 1 ∗ , … , x n ∗ ) ⊤ \boldsymbol x^*=(x_1^*,\ldots,x_n^*)^\top x ∗ = ( x 1 ∗ , … , x n ∗ ) ⊤ x 1 ∗ = 0 x_1^*=0 x 1 ∗ = 0 u ∈ R m \boldsymbol u\in\mathbb R^m u ∈ R m v ∈ R v\in\mathbb R v ∈ R
( Q ) : 最大化 b ⊤ u − ( c ⊤ x ∗ ) v 满足 ( a 1 ) ⊤ u − c 1 v ≦ − 1 , ( a i ) ⊤ u − c i v ≦ 0 ( i = 2 , … , n ) , v ≧ 0. \begin{aligned}
(\mathrm Q):\quad
&\text{最大化}\quad
\boldsymbol b^\top\boldsymbol u-(\boldsymbol c^\top\boldsymbol x^*)v\\
&\text{满足}\quad
(\boldsymbol a^1)^\top\boldsymbol u-c_1v\leqq-1,\\
&\hspace{2.8em}
(\boldsymbol a^i)^\top\boldsymbol u-c_iv\leqq0
\quad(i=2,\ldots,n),\\
&\hspace{2.8em}v\geqq0.
\end{aligned} ( Q ) : 最大化 b ⊤ u − ( c ⊤ x ∗ ) v 满足 ( a 1 ) ⊤ u − c 1 v ≦ − 1 , ( a i ) ⊤ u − c i v ≦ 0 ( i = 2 , … , n ) , v ≧ 0. 回答：
写出 Q 的对偶问题。
证明 Q 有最优解。
证明 Q 的最优值为 0 0 0
若 Q 有一个满足 v ∗ > 0 v^*>0 v ∗ > 0 ( u ∗ , v ∗ ) (\boldsymbol u^*,v^*) ( u ∗ , v ∗ ) w ∗ = u ∗ / v ∗ \boldsymbol w^*=\boldsymbol u^*/v^* w ∗ = u ∗ / v ∗ w ∗ \boldsymbol w^* w ∗
若 Q 有一个满足 v ∗ = 0 v^*=0 v ∗ = 0 ( u ∗ , v ∗ ) (\boldsymbol u^*,v^*) ( u ∗ , v ∗ ) w ∗ \boldsymbol w^* w ∗ ( a 1 ) ⊤ w ∗ < c 1 (\boldsymbol a^1)^\top\boldsymbol w^*<c_1 ( a 1 ) ⊤ w ∗ < c 1
Kai (i)
After replacing the maximization objective by its negative, the Lagrangian is
L ( u , v , λ , κ ) = ( c ⊤ x ∗ ) v − b ⊤ u + λ ⊤ ( A ⊤ u − v c − d ) − κ v L(u,v,\lambda, \kappa) = (c^\top x^*)v - b^\top u + \lambda ^\top (A^\top u - vc - d) - \kappa v L ( u , v , λ , κ ) = ( c ⊤ x ∗ ) v − b ⊤ u + λ ⊤ ( A ⊤ u − v c − d ) − κ v The infimum is finite only if
A λ = b , c ⊤ x ∗ − c ⊤ λ − κ = 0. A\lambda=b,\qquad c^\top x^*-c^\top\lambda-\kappa=0. A λ = b , c ⊤ x ∗ − c ⊤ λ − κ = 0. Negating the resulting dual objective gives the following dual of Q:
( Q D ) : Minimize d ⊤ λ Subject to c ⊤ x ∗ − c ⊤ λ − κ = 0 A λ = b κ ≥ 0 , λ ⪰ 0 \begin{aligned}
(Q_D): \text{Minimize } \ &d^\top \lambda \\
\text{Subject to } \ &c^\top x^* - c^\top \lambda - \kappa = 0 \\
&A\lambda=b\\
&\kappa \geq 0, \lambda \succeq \boldsymbol{0}\\
\end{aligned} ( Q D ) : Minimize Subject to d ⊤ λ c ⊤ x ∗ − c ⊤ λ − κ = 0 A λ = b κ ≥ 0 , λ ⪰ 0 where d = [ − 1 , 0 , 0 , … , 0 ] ⊤ d = [-1,0,0,\ldots, 0]^\top d = [ − 1 , 0 , 0 , … , 0 ] ⊤
(ii)
The point ( λ , κ ) = ( x ∗ , 0 ) (\lambda,\kappa)=(x^*,0) ( λ , κ ) = ( x ∗ , 0 ) Q D Q_D Q D ( λ , κ ) (\lambda,\kappa) ( λ , κ )
A λ = b , λ ⪰ 0 , c ⊤ λ = c ⊤ x ∗ − κ ≤ c ⊤ x ∗ . A\lambda=b,\qquad \lambda\succeq0,\qquad
c^\top\lambda=c^\top x^*-\kappa\leq c^\top x^*. A λ = b , λ ⪰ 0 , c ⊤ λ = c ⊤ x ∗ − κ ≤ c ⊤ x ∗ . Thus λ \lambda λ λ = x ∗ \lambda=x^* λ = x ∗ κ = 0 \kappa=0 κ = 0 Q D Q_D Q D d ⊤ x ∗ = 0 d^\top x^*=0 d ⊤ x ∗ = 0
(iii)
By (ii), the dual problem Q D Q_D Q D
d ⊤ x ∗ = − x 1 ∗ = 0. d^\top x^*=-x_1^*=0. d ⊤ x ∗ = − x 1 ∗ = 0. Strong duality therefore gives v ( Q ) = 0 v(Q)=0 v ( Q ) = 0
(iv)
we know
b ⊤ u ∗ − v ∗ ( c ⊤ x ∗ ) = 0 b^\top u^* - v^* (c^\top x^*) = 0 b ⊤ u ∗ − v ∗ ( c ⊤ x ∗ ) = 0 then
b ⊤ u ∗ v ∗ = c ⊤ x ∗ b^\top \frac{u^*}{v^*} = c^\top x^* b ⊤ v ∗ u ∗ = c ⊤ x ∗ since
A ⊤ u ∗ v ∗ ≤ c + d v ∗ ≤ c , A^\top \frac{u^*}{v^*} \leq c+\frac{d}{v^*} \leq c, A ⊤ v ∗ u ∗ ≤ c + v ∗ d ≤ c , u ∗ v ∗ \frac{u^*}{v^*} v ∗ u ∗ ( D ) (D) ( D )
(v)
we have
b ⊤ u ∗ = 0 , A ⊤ u ∗ ≤ d b^\top u^* = 0, A^\top u^* \leq d b ⊤ u ∗ = 0 , A ⊤ u ∗ ≤ d (D) has optimal solution w ~ \widetilde{w} w w ∗ = w ~ + t u ∗ w^* = \widetilde{w} + tu^* w ∗ = w + t u ∗ t > 0 t > 0 t > 0
A ⊤ w ∗ ≤ c + t d ≤ c , ( a 1 ) ⊤ w ∗ ≤ c 1 − t < c 1 A^\top w^* \leq c+ td \leq c, \qquad (a^1)^\top w^* \leq c_1-t<c_1 A ⊤ w ∗ ≤ c + t d ≤ c , ( a 1 ) ⊤ w ∗ ≤ c 1 − t < c 1 b ⊤ w ∗ = b ⊤ w ~ b^\top w^* = b^\top \widetilde{w} b ⊤ w ∗ = b ⊤ w i.e., w ∗ w^* w ∗