京都大学 情報学研究科 数理工学専攻 2018年8月実施 オペレーションズ・リサーチ Author Casablanca, 祭音Myyura
Description 大学公表の原題
日本語版
関数 h : R n → R h:\mathbb{R}^n \rightarrow \mathbb{R} h : R n → R g : R → R g:\mathbb{R} \rightarrow \mathbb{R} g : R → R f : R n → R f:\mathbb{R}^n \rightarrow \mathbb{R} f : R n → R
g ( t ) = 2 t , f ( x ) = g ( h ( x ) ) g(t) = 2^t,f(x) = g(h(x)) g ( t ) = 2 t , f ( x ) = g ( h ( x )) ベクトル b i ∈ R n ( i = 1 , … , m ) \boldsymbol{b^i} \in \mathbb{R}^n(i = 1,\dots,m) b i ∈ R n ( i = 1 , … , m ) Δ ⊆ R n , Γ ⊆ R m , Ω ⊆ R n \Delta \subseteq \mathbb{R}^n , \Gamma \subseteq \mathbb{R}^m , \Omega \subseteq \mathbb{R}^n Δ ⊆ R n , Γ ⊆ R m , Ω ⊆ R n
Δ = { b 1 , b 2 , … , b m } Γ = { α ∈ R m ∣ ∑ i = 1 m α i = 1 , α i ≧ 0 ( i = 1 , … , m ) } Ω = { x ∈ R n ∣ x = ∑ i = 1 m α i b i , α ∈ Γ } \begin{aligned}
\Delta &= \{\boldsymbol{b^1},\boldsymbol{b^2},\dots,\boldsymbol{b^m}\} \\
\Gamma &= \bigg\{\alpha \in \mathbb{R}^m \bigg|\sum_{i=1}^m \alpha_i = 1,\alpha_i \geqq 0 (i = 1,\dots,m)\bigg\} \\
\Omega &= \bigg\{\boldsymbol{x} \in \mathbb{R}^n \bigg| \boldsymbol{x} = \sum_{i = 1}^m \alpha_i \boldsymbol{b}^i , \alpha \in \Gamma\bigg\}
\end{aligned} Δ Γ Ω = { b 1 , b 2 , … , b m } = { α ∈ R m i = 1 ∑ m α i = 1 , α i ≧ 0 ( i = 1 , … , m ) } = { x ∈ R n x = i = 1 ∑ m α i b i , α ∈ Γ } 次の非線形計画問題 ( P ) (P) ( P )
( P ) : Maximize f ( x ) subject to x ∈ Ω \begin{aligned}
(P): &\text{Maximize} \quad f(\boldsymbol{x}) \\
&\text{subject to} \quad \boldsymbol{x} \in \Omega \\
\end{aligned} ( P ) : Maximize f ( x ) subject to x ∈ Ω 以下の問いに答えよ。
(i) 任意の α ∈ Γ \alpha \in \Gamma α ∈ Γ
h ( ∑ i = 1 m α i b i ) ≦ ∑ i = 1 m α i h ( b i ) h\bigg(\sum_{i = 1}^m\alpha_i\boldsymbol{b^i}\bigg) \leqq \sum_{i = 1}^m\alpha_i h(\boldsymbol{b^i}) h ( i = 1 ∑ m α i b i ) ≦ i = 1 ∑ m α i h ( b i ) (ii) 関数 g g g f f f
(iii) 次の線形計画問題のカルーシュ ⋅ \cdot ⋅
Maximize ∑ i = 1 m f ( b i ) α i subject to ∑ i = 1 m α i = 1 α i ≧ 0 ( i = 1 , … , m ) \begin{aligned}
&\text{Maximize} \quad \sum_{i = 1}^m f(\boldsymbol{b^i})\alpha_i \\
&\text{subject to} \quad \sum_{i = 1}^m \alpha_i = 1 \\
&\qquad \qquad \quad \alpha_i \geqq 0 (i = 1,\dots,m)
\end{aligned} Maximize i = 1 ∑ m f ( b i ) α i subject to i = 1 ∑ m α i = 1 α i ≧ 0 ( i = 1 , … , m ) ただし, 決定変数は α i ( i = 1 , … , m ) \alpha_i (i = 1,\dots,m) α i ( i = 1 , … , m )
(iv) 問題 ( P ) (P) ( P ) X ∗ X^* X ∗ X ∗ ∩ Δ ≠ ∅ X^* \cap \Delta \neq \emptyset X ∗ ∩ Δ = ∅
English Version
题目描述
设 h : R n → R h:\mathbb{R}^n\to\mathbb{R} h : R n → R
g ( t ) = 2 t , f ( x ) = g ( h ( x ) ) . g(t)=2^t,\qquad
f(\boldsymbol{x})=g\!\left(h(\boldsymbol{x})\right). g ( t ) = 2 t , f ( x ) = g ( h ( x ) ) . 给定向量 b i ∈ R n \boldsymbol{b}^i\in\mathbb{R}^n b i ∈ R n i = 1 , … , m i=1,\ldots,m i = 1 , … , m
Δ = { b 1 , b 2 , … , b m } , Γ = { α ∈ R m | ∑ i = 1 m α i = 1 , α i ≧ 0 ( i = 1 , … , m ) } , Ω = { x ∈ R n | x = ∑ i = 1 m α i b i , α ∈ Γ } . \begin{aligned}
\Delta
&=\{\boldsymbol{b}^1,\boldsymbol{b}^2,\ldots,\boldsymbol{b}^m\},\\
\Gamma
&=\left\{\boldsymbol{\alpha}\in\mathbb{R}^m\ \middle|\
\sum_{i=1}^m\alpha_i=1,\quad
\alpha_i\geqq0\ (i=1,\ldots,m)\right\},\\
\Omega
&=\left\{\boldsymbol{x}\in\mathbb{R}^n\ \middle|\
\boldsymbol{x}=\sum_{i=1}^m\alpha_i\boldsymbol{b}^i,\quad
\boldsymbol{\alpha}\in\Gamma\right\}.
\end{aligned} Δ Γ Ω = { b 1 , b 2 , … , b m } , = { α ∈ R m i = 1 ∑ m α i = 1 , α i ≧ 0 ( i = 1 , … , m ) } , = { x ∈ R n x = i = 1 ∑ m α i b i , α ∈ Γ } . 在这些给定点的凸包 Ω \Omega Ω
( P ) : 最大化 f ( x ) 约束于 x ∈ Ω . \begin{aligned}
(P):\quad
&\text{最大化}\quad f(\boldsymbol{x})\\
&\text{约束于}\quad \boldsymbol{x}\in\Omega.
\end{aligned} ( P ) : 最大化 f ( x ) 约束于 x ∈ Ω. 回答下列问题：
证明对任意 α ∈ Γ \boldsymbol{\alpha}\in\Gamma α ∈ Γ
h ( ∑ i = 1 m α i b i ) ≦ ∑ i = 1 m α i h ( b i ) . h\!\left(\sum_{i=1}^m\alpha_i\boldsymbol{b}^i\right)
\leqq
\sum_{i=1}^m\alpha_i h(\boldsymbol{b}^i). h ( i = 1 ∑ m α i b i ) ≦ i = 1 ∑ m α i h ( b i ) .
证明函数 g g g f f f
对下列以 α i \alpha_i α i i = 1 , … , m i=1,\ldots,m i = 1 , … , m
最大化 ∑ i = 1 m f ( b i ) α i 满足 ∑ i = 1 m α i = 1 , α i ≧ 0 ( i = 1 , … , m ) . \begin{aligned}
&\text{最大化}\quad
\sum_{i=1}^m f(\boldsymbol{b}^i)\alpha_i\\
&\text{满足}\quad
\sum_{i=1}^m\alpha_i=1,\qquad
\alpha_i\geqq0\ (i=1,\ldots,m).
\end{aligned} 最大化 i = 1 ∑ m f ( b i ) α i 满足 i = 1 ∑ m α i = 1 , α i ≧ 0 ( i = 1 , … , m ) .
记问题 ( P ) (P) ( P ) X ∗ X^* X ∗ X ∗ ∩ Δ ≠ ∅ X^*\cap\Delta\ne\varnothing X ∗ ∩ Δ = ∅ b i \boldsymbol{b}^i b i ( P ) (P) ( P )
Kai (i)
Use induction on m m m m = 1 m=1 m = 1 β = ∑ i = 1 m − 1 α i \beta=\sum_{i=1}^{m-1}\alpha_i β = ∑ i = 1 m − 1 α i β = 0 \beta=0 β = 0
h ( ∑ i = 1 m α i b i ) = h ( β ∑ i = 1 m − 1 α i β b i + α m b m ) ≤ β h ( ∑ i = 1 m − 1 α i β b i ) + α m h ( b m ) ≤ ∑ i = 1 m α i h ( b i ) . \begin{aligned}
h\!\left(\sum_{i=1}^{m}\alpha_i b^i\right)
&=h\!\left(\beta\sum_{i=1}^{m-1}\frac{\alpha_i}{\beta}b^i+\alpha_m b^m\right)\\
&\le \beta h\!\left(\sum_{i=1}^{m-1}\frac{\alpha_i}{\beta}b^i\right)+\alpha_mh(b^m)\\
&\le\sum_{i=1}^{m}\alpha_i h(b^i).
\end{aligned} h ( i = 1 ∑ m α i b i ) = h ( β i = 1 ∑ m − 1 β α i b i + α m b m ) ≤ β h ( i = 1 ∑ m − 1 β α i b i ) + α m h ( b m ) ≤ i = 1 ∑ m α i h ( b i ) . (ii)
Since g ′ ′ ( t ) = ( ln 2 ) 2 2 t > 0 g''(t)=(\ln2)^2 2^t>0 g ′′ ( t ) = ( ln 2 ) 2 2 t > 0 g g g 0 ≤ θ ≤ 1 0\le\theta\le1 0 ≤ θ ≤ 1
θ f ( x 1 ) + ( 1 − θ ) f ( x 2 ) ≥ g ( θ h ( x 1 ) + ( 1 − θ ) h ( x 2 ) ) ≥ g ( h ( θ x 1 + ( 1 − θ ) x 2 ) ) , \begin{aligned}
\theta f(x_1)+(1-\theta)f(x_2)
&\ge g\!\left(\theta h(x_1)+(1-\theta)h(x_2)\right)\\
&\ge g\!\left(h(\theta x_1+(1-\theta)x_2)\right),
\end{aligned} θ f ( x 1 ) + ( 1 − θ ) f ( x 2 ) ≥ g ( θ h ( x 1 ) + ( 1 − θ ) h ( x 2 ) ) ≥ g ( h ( θ x 1 + ( 1 − θ ) x 2 ) ) , so f f f
(iii)
Lagrangian
L ( α , λ , μ ) = − ∑ i = 1 m f ( b i ) α i + λ ( 1 ⊤ α − 1 ) − μ ⊤ α . L(\alpha,\lambda,\mu)
=-\sum_{i=1}^m f(b^i)\alpha_i
+\lambda(\boldsymbol1^\top\alpha-1)-\mu^\top\alpha. L ( α , λ , μ ) = − i = 1 ∑ m f ( b i ) α i + λ ( 1 ⊤ α − 1 ) − μ ⊤ α . KKT conditions { − f ( b i ) + λ − μ i = 0 ( i = 1 , … , m ) , 1 ⊤ α = 1 , α i ≥ 0 , μ i ≥ 0 , μ i α i = 0 ( i = 1 , … , m ) . \text{KKT conditions}\quad\left\{
\begin{aligned}
-f(b^i)+\lambda-\mu_i&=0 &&(i=1,\ldots,m),\\
\boldsymbol1^\top\alpha&=1,\qquad \alpha_i\ge0,\\
\mu_i&\ge0,\qquad \mu_i\alpha_i=0 &&(i=1,\ldots,m).
\end{aligned}
\right. KKT conditions ⎩ ⎨ ⎧ − f ( b i ) + λ − μ i 1 ⊤ α μ i = 0 = 1 , α i ≥ 0 , ≥ 0 , μ i α i = 0 ( i = 1 , … , m ) , ( i = 1 , … , m ) . (iv)
For any x = ∑ i = 1 m α i b i ∈ Ω x=\sum_{i=1}^m\alpha_i b^i\in\Omega x = ∑ i = 1 m α i b i ∈ Ω f f f
f ( x ) ≤ ∑ i = 1 m α i f ( b i ) ≤ max 1 ≤ i ≤ m f ( b i ) . f(x)\le\sum_{i=1}^m\alpha_i f(b^i)
\le\max_{1\le i\le m}f(b^i). f ( x ) ≤ i = 1 ∑ m α i f ( b i ) ≤ 1 ≤ i ≤ m max f ( b i ) . Choose j j j b j ∈ Ω b^j\in\Omega b j ∈ Ω ( P ) (P) ( P ) b j ∈ X ∗ ∩ Δ b^j\in X^*\cap\Delta b j ∈ X ∗ ∩ Δ