跳到主要内容

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

标签：

Author​

Casablanca, 祭音Myyura

Description​

大学公表の原題

日本語版​

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

∇f(x)=(∂f(x)∂x1,…,∂f(x)∂xn)⊤\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 を考える。

P:Minimize∇f(xˉ)⊤xsubject toA(xˉ+x)≦b\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}

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

以下の問いに答えよ。

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

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

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

English Version​

题目描述​

设 f:Rn→Rf:\mathbb R^n\to\mathbb R 为连续可微凸函数，并定义梯度

∇f(x)=(∂f(x)∂x1,…,∂f(x)∂xn)⊤,\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:最小化∇f(xˉ)⊤x满足A(xˉ+x)≦b,\begin{aligned} \mathrm P:\quad &\text{最小化}\quad \nabla f(\bar{\boldsymbol x})^\top\boldsymbol x\\ &\text{满足}\quad \boldsymbol A(\bar{\boldsymbol x}+\boldsymbol x)\leqq\boldsymbol b, \end{aligned}

其中 A\boldsymbol A 是 m×nm\times n 常数矩阵，b\boldsymbol b 是 mm 维常向量，xˉ\bar{\boldsymbol x} 是 nn 维常向量，x\boldsymbol x 是 nn 维变量向量，并假设 P 有最优解。回答：

  1. 证明对任意满足 ∇f(xˉ)⊤d≧0\nabla f(\bar{\boldsymbol x})^\top\boldsymbol d\geqq0 的 d∈Rn\boldsymbol d\in\mathbb R^n，都有 f(xˉ+d)≧f(xˉ)f(\bar{\boldsymbol x}+\boldsymbol d)\geqq f(\bar{\boldsymbol x})。
  2. 写出 P 的对偶问题。
  3. 假设 Axˉ≧b\boldsymbol A\bar{\boldsymbol x}\geqq\boldsymbol b。证明对任意满足 Az≦b\boldsymbol A\boldsymbol z\leqq\boldsymbol b 的 z∈Rn\boldsymbol z\in\mathbb R^n，都有 f(z)≧f(xˉ)f(\boldsymbol z)\geqq f(\bar{\boldsymbol x})。

Kai​

(i)​

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

f(xˉ+d)≥f(xˉ)+∇f(xˉ)⊤d≥f(xˉ)f(\bar{x} + d) \geq f(\bar{x}) + \nabla f(\bar{x})^\top d \geq f(\bar{x})

(ii)​

Lagrangian:

L(x,λ)=∇f(xˉ)⊤x+λ⊤(A(xˉ+x)−b)L(x, \lambda) = \nabla f(\bar{x})^\top x + \lambda^\top (A(\bar{x} + x) - b)

Lagrange dual function

g(λ)=inf⁡x∈RnL(x,λ)={λ⊤(Axˉ−b),∇f(xˉ)+A⊤λ=0,−∞,otherwise.g(\lambda)=\inf_{x\in\mathbb R^n}L(x,\lambda)= \begin{cases} \lambda^\top(A\bar x-b),&\nabla f(\bar x)+A^\top\lambda=0,\\ -\infty,&\text{otherwise}. \end{cases}

Dual problem:

(D):Maximizeλ⊤(Axˉ−b)Subject to∇f(xˉ)+A⊤λ=0 λ⪰0\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−xˉ+xˉ)⪯bAz = A(z-\bar{x} + \bar{x}) \preceq b and z−xˉz-\bar{x} is in domain of P, let v(p)v(p) denote P's optimal value, then

f(z)−f(xˉ)≥∇f(xˉ)⊤(z−xˉ)≥v(p)f(z) - f(\bar{x}) \geq \nabla f(\bar{x})^\top (z- \bar{x}) \geq v(p)

Since P has an optimal solution, strong duality gives an optimal dual solution λ∗\lambda^* and

v(p)=(λ∗)⊤(Axˉ−b)≥0,v(p)=(\lambda^*)^\top(A\bar{x}-b)\geq0,

because Axˉ⪰bA\bar{x}\succeq b and λ∗⪰0\lambda^*\succeq0. Therefore,

f(z)≥f(xˉ)f(z) \geq f(\bar{x})
本页目录