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

标签：

• Kyoto-University
• Linear-Programming-Duality
• Complementary-Slackness

Author

Casablanca

Description

日本語版

$\boldsymbol{a}^i \ (i = 1, \ldots, n)$ と $\boldsymbol{b}$ を $m$ 次元ベクトル，$\boldsymbol{c} = (c_1, c_2, \ldots, c_n)^{\top}$ を $n$ 次元ベクトルする． ただし $\top$ は転置記号を表す．さらに，$\boldsymbol{A}$ を第 $i$ 列が $\boldsymbol{a}^i$ となる $m \times n$ 行列，つまり $\boldsymbol{A} = [\boldsymbol{a}^1 \ \boldsymbol{a}^2 \ \cdots \ \boldsymbol{a}^n]$ とする．

次の線形計画問題 (P) とその双対問題 (D) を考える．

$$\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}$$

$$\begin{aligned} \text{(D)}\ &\text{Maximize} &\boldsymbol{b}^{\top} \boldsymbol{w} \\ &\text{subject to} &\boldsymbol{A}^{\top} \boldsymbol{w} \leqq \boldsymbol{c} \end{aligned}$$

ただし，(P) の決定変数は $\boldsymbol{x} \in \mathbb{R}^n$，(D) の決定変数は $\boldsymbol{w} \in \mathbb{R}^m$ である．

問題 (P) は $x_1^* = 0$ となる唯一の最適解 $\boldsymbol{x}^* = (x_1^*, x_2^*, \ldots, x_n^*)^{\top}$ を持つとする．このとき，次の線形計画問題 (Q) を考える．

$$\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}$$

ただし，決定変数は $\boldsymbol{u} \in \mathbb{R}^m$ と $v \in \mathbb{R}$ である．

以下の問いに答えよ．

(i) 問題 (Q) の双対問題を書け．

(ii) 問題 (Q) が最適解を持つことを示せ．

(iii) 問題 (Q) の最適値が $0$ となることを示せ．

(iv) 問題 (Q) は $v^* > 0$ となる最適解 $(\boldsymbol{u}^*, v^*)$ を持つとする．$\boldsymbol{w}^* = \frac{\boldsymbol{u}^*}{v^*}$ とする．このとき，$\boldsymbol{w}^*$ は双対問題 (D) の最適解であることを示せ．

(v) 問題 (Q) は $v^* = 0$ となる最適解 $(\boldsymbol{u}^*, v^*)$ を持つとする．このとき，$(\boldsymbol{a}^1)^{\top} \boldsymbol{w}^* < c_1$ となる (D) の最適解 $\boldsymbol{w}^*$ が存在することを示せ．

English Version

题目描述

令 $\boldsymbol a^i$（$i=1,\ldots,n$）和 $\boldsymbol b$ 为 $m$ 维向量，$\boldsymbol c=(c_1,\ldots,c_n)^\top$ 为 $n$ 维向量，$\boldsymbol A=[\boldsymbol a^1\ \cdots\ \boldsymbol a^n]$。考虑互为原、对偶的线性规划

$$\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}$$

其中 $\boldsymbol x\in\mathbb R^n$、$\boldsymbol w\in\mathbb R^m$。假设 P 有唯一最优解 $\boldsymbol x^*=(x_1^*,\ldots,x_n^*)^\top$，且 $x_1^*=0$。再考虑以 $\boldsymbol u\in\mathbb R^m$、$v\in\mathbb R$ 为变量的

$$\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}$$

回答：

1. 写出 Q 的对偶问题。
2. 证明 Q 有最优解。
3. 证明 Q 的最优值为 $0$。
4. 若 Q 有一个满足 $v^*>0$ 的最优解 $(\boldsymbol u^*,v^*)$，令 $\boldsymbol w^*=\boldsymbol u^*/v^*$。证明 $\boldsymbol w^*$ 是 D 的最优解。
5. 若 Q 有一个满足 $v^*=0$ 的最优解 $(\boldsymbol u^*,v^*)$，证明存在 D 的最优解 $\boldsymbol w^*$ 满足 $(\boldsymbol a^1)^\top\boldsymbol w^*<c_1$。

考点

• 线性规划对偶：为辅助问题 Q 构造对偶，并结合强对偶分析最优值与解的存在性。
• 互补松弛与严格松弛：利用原问题唯一最优解中 $x_1^*=0$，证明可找到对该变量约束严格松弛的对偶最优解。
• 齐次缩放论证：按辅助变量 $v^*$ 是否为正分别归一化或处理退化情形，从 Q 的最优解恢复 D 的最优解。

Kai

(i)

Lagrangian:

$$L(u,v,\lambda, \kappa) = (c^\top x^*)v - b^\top u + \lambda ^\top (A^\top u - vc - d) - \kappa v$$

Lagrange dual function:

$$d(\lambda, \kappa) = -\lambda ^\top d$$

$$\begin{aligned} (D): \text{Minimize } \ &d^\top \lambda \\ \text{Subject to } \ &c^\top x^* - c^\top \lambda - \kappa = 0 \\ &\kappa \geq 0, \lambda \succeq \boldsymbol{0}\\ \end{aligned}$$

where $d = [-1,0,0,\ldots, 0]^\top$

(ii)

For (D), $\kappa = 0$, $\lambda = x^*$ is feasible , hence (Q) has optimal value $v(\text{Q}) \leq d^\top x^* = 0$.

Hence (Q) is bounded, and therefore has an optimal value.

(iii)

For $w^*$, we have $c^\top x^* = b^\top w^*$. Since duality gap is zero, for $(Q)$, when $u = w^*$ and $v = 1$, $0$ is attained.

(iv)

we know

$$b^\top u^* - v^* (c^\top x^*) = 0$$

then

$$b^\top \frac{u^*}{v^*} = c^\top x^*$$

since

$$A^\top \frac{u^*}{v^*} \leq c+d \leq c,$$

$\frac{u^*}{v^*}$ is an optimal solution to $(D)$

(v)

we have

$$b^\top u^* = 0, A^\top u^* \leq d$$

(D) has optimal solution $\widetilde{w}$, let $w^* = \widetilde{w} + tu^*$, $t > 0$, then we have

$$Aw^* \leq c+ td, \quad (a^1)\top w^* < c_1$$

$$b^\top w^* = b^\top \widetilde{w}$$

i.e., $w^*$ is such an optimal solution