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

标签：

• Kyoto-University
• Linear-Programming-Duality
• Convex-First-Order-Optimality

Author

Casablanca

Description

日本語版

関数 $f : \mathbb{R}^n \rightarrow \mathbb{R}$ を連続的微分可能な凸関数とする。 さらに、$\nabla f(\boldsymbol{x})$ を次式で定義される関数 $f$ の $\boldsymbol{x} \in \mathbb{R}^n$ における勾配とする。

$$\nabla f(\boldsymbol{x}) = \left( \frac{\partial f(\boldsymbol{x})}{\partial x_1}, \ldots, \frac{\partial f(\boldsymbol{x})}{\partial x_n} \right)^\top$$

ただし、$\top$ は転置記号を表す。

次の線形計画問題 P を考える。

$$\begin{aligned} \text{P} : &\text{Minimize} &\nabla f(\bar{\boldsymbol{x}})^\top \boldsymbol{x} \\ &\text{subject to} &\boldsymbol{A}(\bar{\boldsymbol{x}} + \boldsymbol{x}) \leqq \boldsymbol{b} \end{aligned}$$

ただし、$\boldsymbol{A}$ は $m \times n$ 定数行列、$\boldsymbol{b}$ は $m$ 次元定数ベクトル、$\bar{\boldsymbol{x}}$ は $n$ 次元定数ベクトル、$\boldsymbol{x}$ は $n$ 次元変数ベクトルである。 問題 P は最適解を持つとする。

以下の問いに答えよ。

(i) $\nabla f(\bar{\boldsymbol{x}})^\top \boldsymbol{d} \geqq 0$ である任意の $\boldsymbol{d} \in \mathbb{R}^n$ に対して $f(\bar{\boldsymbol{x}} + \boldsymbol{d}) \geqq f(\bar{\boldsymbol{x}})$ となることを示せ。

(ii) 問題 P の双対問題を書け。

(iii) $\boldsymbol{A}\bar{\boldsymbol{x}} \geqq \boldsymbol{b}$ とする。このとき、$\boldsymbol{A} \boldsymbol{z} \leqq \boldsymbol{b}$ である任意の $z \in \mathbb{R}^n$ に対して、$f(\boldsymbol{z}) \geqq f(\bar{\boldsymbol{x}})$ であることを示せ。

English Version

Kai

(i)

Since $\nabla f(\bar{x})^\top d \geqq 0$, from first order condition we have

$$f(\bar{x} + d) \geq f(\bar{x}) + \nabla f(\bar{x})^\top d \geq f(\bar{x})$$

(ii)

Lagrangian:

$$L(x, \lambda) = \nabla f(\bar{x})^\top x + \lambda^\top (A(\bar{x} + x) - b)$$

Lagrange dual function

$$g(\lambda) = \lambda ^\top A \bar{x} - \lambda^\top b$$

Dual problem:

$$\begin{aligned} (D): &\text{Maximize} &\lambda^\top (A\bar{x} - b) \\ &\text{Subject to} &\nabla f(\bar{x}) + A^\top \lambda = \boldsymbol{0} \\ &\text{ } &\lambda \succeq \boldsymbol{0} \\ \end{aligned}$$

(iii)

Since $Az = A(z-\bar{x} + \bar{x}) \preceq b$ and $z-\bar{x}$ is in domain of P, let $v(p)$ denote P's optimal value, then

$$f(z) - f(\bar{x}) \geq \nabla f(\bar{x})^\top (z- \bar{x}) \geq v(p)$$

Since

$$A\bar{x} \succeq b, \lambda ^\top (A\bar{x}-b) \geq 0$$

thus

$$v(p) \geq 0$$

therefore

$$f(z) \geq f(\bar{x})$$