跳到主要内容

京都大学 情報学研究科 数理工学専攻 2010年8月実施 オペレーションズ・リサーチ

标签：

Author​

思齐塾, 祭音Myyura

Description​

大学公表の原題

R+n={x∈Rn∣xi≥0 (i=1,…,n)},R++n={x∈Rn∣xi>0 (i=1,…,n)}.\mathbb{R}^n_{+} = \{ x \in \mathbb{R}^n \mid x_i \ge 0 \ (i=1,\ldots,n) \}, \quad \mathbb{R}^n_{++} = \{ x \in \mathbb{R}^n \mid x_i > 0 \ (i=1,\ldots,n) \}.

関数 ψ:R+n→R\psi : \mathbb{R}^n_{+} \rightarrow \mathbb{R} を

ψ(x)=∑i=1nxiln⁡xi\psi(x) = \sum_{i=1}^n x_i \ln x_i

と定義する。ただし、 ln⁡\ln は自然対数を表し、 0ln⁡0=00\ln 0 = 0 とする。さらに、関数 Bψ:R+n×R++n→RB_\psi: \mathbb{R}^n_{+} \times \mathbb{R}^n_{++} \rightarrow \mathbb{R} を次のように定義する。

Bψ(x,y)=ψ(x)−ψ(y)−∇ψ(y)T(x−y)B_\psi(x, y) = \psi(x) - \psi(y) - \nabla \psi(y)^T (x - y)

ただし、 TT は転置記号である。

次に、パラメータ t∈Rt \in R を含む非線形計画問題 P(t)P(t) を考える。

P(t)minimizetcTx+Bψ(x,y)P(t) \quad \text{minimize} \quad tc^T x + B_\psi(x, y)
subject to∑i=1nxi=1\text{subject to} \quad \sum_{i=1}^n x_i = 1
xi≥0(i=1,...,n)x_i \geq 0 \quad (i = 1,...,n)

ここで、決定変数は xx であり、 c∈Rnc \in R^n と y∈R++ny \in R^n_{++} は定数ベクトルである。問題 P(t)P(t) には唯一の解 x(t)x(t) が存在し、 xi(t)>0(i=1,...,n)x_i(t) > 0 \quad (i = 1,...,n) が成り立つことが知られている。以下の問 (i)-(iv) に答えよ。

(i) 任意の x,y∈R++nx, y \in R^n_{++} に対して、 Bψ(x,y)≥0B_\psi(x, y) \geq 0 となることを示せ。

(ii) 問題 P(t)P(t) のカルーシュ・キューン・タッカー条件 (Karush-Kuhn-Tucker 条件) を書け。

(iii) x(t)x(t) を求めよ。

(iv) ベクトル cc の成分 c1,c2,...,cnc_1, c_2, ..., c_n に対して c1>c2>...>cnc_1 > c_2 > ... > c_n が成り立つとする。

lim⁡t→∞x(t)=(0,...,0,1)T\lim_{t \rightarrow \infty} x(t) = (0, ..., 0, 1)^T

となることを示せ。

题目描述​

记

R+n={x∈Rn∣xi≥0 (i=1,…,n)},R++n={x∈Rn∣xi>0 (i=1,…,n)}.\mathbb R_+^n=\{x\in\mathbb R^n\mid x_i\geq0\ (i=1,\ldots,n)\},\qquad \mathbb R_{++}^n=\{x\in\mathbb R^n\mid x_i>0\ (i=1,\ldots,n)\}.

在 R+n\mathbb R_{+}^n 上定义

ψ(x)=∑i=1nxiln⁡xi,\psi(x)=\sum_{i=1}^n x_i\ln x_i,

其中 ln⁡\ln 为自然对数，并约定 0ln⁡0=00\ln0=0。对 x∈R+nx\in\mathbb R_{+}^n、y∈R++ny\in\mathbb R_{++}^n，定义

Bψ(x,y)=ψ(x)−ψ(y)−∇ψ(y)T(x−y),B_\psi(x,y) =\psi(x)-\psi(y)-\nabla\psi(y)^T(x-y),

其中上标 TT 表示转置。

给定参数 t∈Rt\in\mathbb R，考虑以 xx 为决策变量的非线性规划问题

P(t):min⁡xtcTx+Bψ(x,y)s.t.∑i=1nxi=1,xi≥0(i=1,…,n),\begin{aligned} P(t):\quad \min_x\quad &tc^Tx+B_\psi(x,y)\\ \text{s.t.}\quad &\sum_{i=1}^n x_i=1,\\ &x_i\geq0\qquad(i=1,\ldots,n), \end{aligned}

其中 c∈Rnc\in\mathbb R^n、y∈R++ny\in\mathbb R_{++}^n 为给定常向量。已知 P(t)P(t) 存在唯一解 x(t)x(t)，且其每个分量都严格为正，即 xi(t)>0 (i=1,…,n)x_i(t)>0\ (i=1,\ldots,n)。

完成以下各问：

  1. 证明对任意 x,y∈R++nx,y\in\mathbb R_{++}^n，都有

    Bψ(x,y)≥0.B_\psi(x,y)\geq0.

  2. 写出问题 P(t)P(t) 的 Karush–Kuhn–Tucker（KKT）条件。

  3. 求出唯一最优解 x(t)x(t)。

  4. 若 c1>c2>⋯>cnc_1>c_2>\cdots>c_n，证明

    lim⁡t→∞x(t)=(0,…,0,1)T.\lim_{t\to\infty}x(t)=(0,\ldots,0,1)^T.

Kai​

(i) ∇ψ(y)=(log⁡y1+1,…,log⁡yn+1)T\nabla\psi(y)=(\log y_1+1,\ldots,\log y_n+1)^T なので

Bψ(x,y)=∑i=1n[xilog⁡xiyi−xi+yi].B_\psi(x,y) =\sum_{i=1}^n\left[ x_i\log\frac{x_i}{y_i}-x_i+y_i \right].

r>0r>0 に対して ϕ(r)=rlog⁡r−r+1\phi(r)=r\log r-r+1 とおくと

ϕ′(r)=log⁡r,ϕ′′(r)=1r>0.\phi'(r)=\log r,\qquad \phi''(r)=\frac1r>0.

従って ϕ\phi は r=1r=1 で唯一の最小値 ϕ(1)=0\phi(1)=0 を取る。各項は

xilog⁡xiyi−xi+yi=yiϕ(xiyi)≥0x_i\log\frac{x_i}{y_i}-x_i+y_i =y_i\phi\left(\frac{x_i}{y_i}\right)\geq0

であるから

Bψ(x,y)≥0.\boxed{B_\psi(x,y)\geq0}.

この証明は、一般の x,y∈R++nx,y\in\mathbb R_{++}^n に対して成り立ち、成分和が1であることを仮定しない。

(ii) 問題文で最適解の全成分が正であると与えられているので、その内点での微分を用いる。等式制約の乗数 λ\lambda は符号自由である。

Lagrangian:

L(x,λ,μ)=tcTx+ψ(x)−ψ(y)−∇ψ(y)T(x−y)−λ(∑i=1nxi−1)−∑i=1nμixiL(x, \lambda, \mu) = tc^Tx + \psi(x) - \psi(y) - \nabla \psi(y)^T(x - y) - \lambda(\sum_{i=1}^n x_i - 1) - \sum_{i=1}^n \mu_i x_i

KKT Conditions:

∂L∂xi=tci+ln⁡xi+1−(ln⁡yi+1)−λ−μi=0\frac{\partial L}{\partial x_i} = tc_i + \ln x_i + 1 - (\ln y_i + 1) - \lambda - \mu_i = 0
∑i=1nxi=1\sum_{i=1}^n x_i = 1
xi≥0,μi≥0,μixi=0x_i \geq 0, \mu_i \geq 0, \mu_i x_i = 0
  ⟹  tci+ln⁡xi−ln⁡yi−λ−μi=0\implies tc_i + \ln x_i - \ln y_i - \lambda - \mu_i = 0

(iii) From the KKT conditions:

ln⁡xi=ln⁡yi−tci+λ+μi\ln x_i = \ln y_i - tc_i + \lambda + \mu_i
xi=yie−tci+λ+μix_i = y_i e^{-tc_i + \lambda + \mu_i}

If xi>0x_i > 0 , then μi=0\mu_i = 0 .

xi=yie−tci+λx_i = y_i e^{-tc_i + \lambda}
∑i=1nxi=∑i=1nyie−tci+λ=1\sum_{i=1}^n x_i = \sum_{i=1}^n y_i e^{-tc_i + \lambda} = 1
eλ=1∑i=1nyie−tcie^{\lambda} = \frac{1}{\sum_{i=1}^n y_i e^{-tc_i}}
xi=yie−tci∑j=1nyje−tcjx_i = \frac{y_i e^{-tc_i}}{\sum_{j=1}^n y_j e^{-tc_j}}

(iv) Since c1>c2>...>cnc_1 > c_2 > ... > c_n ,

lim⁡t→∞xi(t)=lim⁡t→∞yie−tci∑j=1nyje−tcj\lim_{t \rightarrow \infty} x_i(t) = \lim_{t \rightarrow \infty} \frac{y_i e^{-tc_i}}{\sum_{j=1}^n y_j e^{-tc_j}}
=lim⁡t→∞yie−t(ci−cn)∑j=1nyje−t(cj−cn)= \lim_{t \rightarrow \infty} \frac{y_i e^{-t(c_i - c_n)}}{\sum_{j=1}^n y_j e^{-t(c_j - c_n)}}

For i<n,ci−cn>0i < n, c_i - c_n > 0 , so lim⁡t→∞e−t(ci−cn)=0\lim_{t \rightarrow \infty} e^{-t(c_i - c_n)} = 0 . For i=n,cn−cn=0i = n, c_n - c_n = 0 , so lim⁡t→∞e−t(cn−cn)=1\lim_{t \rightarrow \infty} e^{-t(c_n - c_n)} = 1 .

lim⁡t→∞xi(t)=0yn=0\lim_{t \rightarrow \infty} x_i(t) = \frac{0}{y_n} = 0
lim⁡t→∞xn(t)=yn∑j=1nyje−t(cj−cn)=ynyn=1\lim_{t \rightarrow \infty} x_n(t) = \frac{y_n}{\sum_{j=1}^n y_j e^{-t(c_j - c_n)}} = \frac{y_n}{y_n} = 1

Thus, lim⁡t→∞x(t)=(0,...,0,1)T\lim_{t \rightarrow \infty} x(t) = (0, ..., 0, 1)^T .

本页目录