跳到主要内容

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

标签：

Author​

Casablanca, 祭音Myyura

Description​

大学公表の原題

日本語版​

関数 f:Rn→Rf : \mathbb{R}^n \rightarrow \mathbb{R} は2回連続的微分可能な関数とし、 a\boldsymbol{a} は 0\boldsymbol{0} でない nn 次元ベクトルとする。

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

P: Minimizef(x)subject toa⊤x=0\begin{aligned} \text{P}: \ &\text{Minimize} &f(\boldsymbol{x}) \\ &\text{subject to} &\boldsymbol{a}^{\top} \boldsymbol{x} = 0 \end{aligned}

ただし、 ⊤\top はベクトルの転置を表す。 x∗x^* は問題 P の大域的最適解とする。

さらに、次の非線形計画問題を考える。

P(k): Minimizefk(x)subject to(x−x∗)⊤(x−x∗)≦1\begin{aligned} \text{P}(k): \ &\text{Minimize} &f_k(\boldsymbol{x}) \\ &\text{subject to} &(\boldsymbol{x} - \boldsymbol{x}^*)^{\top} (\boldsymbol{x} - \boldsymbol{x}^*) \leqq 1 \end{aligned}

ただし、 kk は非負の整数であり、 fk:Rn→Rf_k : \mathbb{R}^n \rightarrow \mathbb{R} は以下に定義された関数である。

fk(x)=f(x)+k2(a⊤x)2+12(x−x∗)⊤(x−x∗)f_k(\boldsymbol{x}) = f(\boldsymbol{x}) + \frac{k}{2} (\boldsymbol{a}^{\top} \boldsymbol{x})^2 + \frac{1}{2}(\boldsymbol{x} - \boldsymbol{x}^*)^{\top} (\boldsymbol{x} - \boldsymbol{x}^*)

問題 P(k)\text{P}(k) の大域的最適解を xk\boldsymbol{x}^k とする。さらに、 lim⁡k→∞xk=xˉ\lim_{k \to \infty} \boldsymbol{x}^k = \bar{\boldsymbol{x}} , lim⁡k→∞k(a⊤xk)=λˉ\lim_{k \to \infty} k(\boldsymbol{a}^{\top} \boldsymbol{x}^k) = \bar{\lambda} と仮定する。

以下の問いに答えよ。

(i) 任意の非負の整数 kk に対して fk(xk)≦f(x∗)f_k(\boldsymbol{x}^k) \leqq f(\boldsymbol{x}^*) が成り立つことを示せ。

(ii) a⊤xˉ=0\boldsymbol{a}^{\top} \bar{\boldsymbol{x}} = 0 , xˉ=x∗\bar{\boldsymbol{x}} = \boldsymbol{x}^* となることを示せ。

(iii) 問題 P(k)\text{P}(k) のカルーシュ・キューン・タッカー (Karush-Kuhn-Tucker) 条件を書け。

(iv) 十分大きな kk に対して、 ∇fk(xk)=0\nabla f_k(\boldsymbol{x}^k) = \boldsymbol{0} となることを示せ。

(v) ∇f(x∗)+λˉa=0\nabla f(\boldsymbol{x}^*) + \bar{\lambda} \boldsymbol{a} = \boldsymbol{0} となることを示せ。

English Version​

题目描述​

设 f:Rn→Rf:\mathbb R^n\to\mathbb R 二阶连续可微，a≠0\boldsymbol a\neq\boldsymbol0 是 nn 维向量。考虑非线性规划

P:min⁡xf(x)s.t.a⊤x=0,\begin{aligned} \mathrm P:\quad \min_{\boldsymbol x}\quad &f(\boldsymbol x)\\ \text{s.t.}\quad &\boldsymbol a^\top\boldsymbol x=0, \end{aligned}

其中上标 ⊤\top 表示转置，x∗\boldsymbol x^* 是问题 P\mathrm P 的全局最优解。对每个非负整数 kk，定义

fk(x)=f(x)+k2(a⊤x)2+12(x−x∗)⊤(x−x∗),f_k(\boldsymbol x) =f(\boldsymbol x) +\frac{k}{2}(\boldsymbol a^\top\boldsymbol x)^2 +\frac12(\boldsymbol x-\boldsymbol x^*)^\top (\boldsymbol x-\boldsymbol x^*),

并考虑问题

P(k):min⁡xfk(x)s.t.(x−x∗)⊤(x−x∗)≤1.\begin{aligned} \mathrm P(k):\quad \min_{\boldsymbol x}\quad &f_k(\boldsymbol x)\\ \text{s.t.}\quad &(\boldsymbol x-\boldsymbol x^*)^\top (\boldsymbol x-\boldsymbol x^*)\leq1. \end{aligned}

令 xk\boldsymbol x^k 为 P(k)\mathrm P(k) 的全局最优解，并假设存在极限

lim⁡k→∞xk=xˉ,lim⁡k→∞k(a⊤xk)=λˉ.\lim_{k\to\infty}\boldsymbol x^k=\bar{\boldsymbol x}, \qquad \lim_{k\to\infty}k(\boldsymbol a^\top\boldsymbol x^k)=\bar\lambda.

完成以下各问：

  1. 证明对任意非负整数 kk，

    fk(xk)≤f(x∗).f_k(\boldsymbol x^k)\leq f(\boldsymbol x^*).

  2. 证明

    a⊤xˉ=0,xˉ=x∗.\boldsymbol a^\top\bar{\boldsymbol x}=0, \qquad \bar{\boldsymbol x}=\boldsymbol x^*.

  3. 写出问题 P(k)\mathrm P(k) 的 Karush–Kuhn–Tucker（KKT）条件。

  4. 证明当 kk 充分大时，

    ∇fk(xk)=0.\nabla f_k(\boldsymbol x^k)=\boldsymbol0.

  5. 证明

    ∇f(x∗)+λˉa=0.\nabla f(\boldsymbol x^*)+\bar\lambda\boldsymbol a=\boldsymbol0.

Kai​

(i)​

fk(xk)≤fk(x∗)=f(x∗)+k2(a⊤x∗)2=f(x∗)f_k(x^k) \leq f_k(x^*) = f(x^*) + \frac k2 (a^\top x^*)^2 = f(x^*)

(ii)​

The assumed finite limit of k(a⊤xk)k(a^\top x^k) gives a⊤xk→0a^\top x^k\to0. Hence, by xk→xˉx^k\to\bar x,

a⊤xˉ=0.a^\top\bar x=0.

Moreover, (i) and the nonnegativity of the penalty term imply

f(xk)+12∥xk−x∗∥2≤fk(xk)≤f(x∗).f(x^k)+\frac12\|x^k-x^*\|^2\leq f_k(x^k)\leq f(x^*).

Taking limits gives

f(xˉ)+12(xˉ−x∗)⊤(xˉ−x∗)≤f(x∗)f(\bar{x}) + \frac 12 (\bar{x} - x^*)^\top(\bar{x} - x^*) \leq f(x^*)

since x∗x^* is optimal, we have

f(xˉ)≥f(x∗)f(\bar{x}) \geq f(x^*)

thus

f(x∗)=f(xˉ),and xˉ=x∗f(x^*) = f(\bar{x}), \text{and } \bar{x}=x^*

(iii)​

Lagrangian

L(x,λk)=f(x)+k2(a⊤x)2+(12+λk)(x−x∗)⊤(x−x∗)−λkL(x, \lambda_k) = f(x) + \frac k2 (a^\top x)^2 + (\frac 12 + \lambda_k)(x-x^*)^\top (x-x^*) - \lambda_k
KKT-conditions:{∇f(xk)+k(a⊤xk)a+(1+2λk)(xk−x∗)=0,λk≥0,∥xk−x∗∥2−1≤0,λk(∥xk−x∗∥2−1)=0.\text{KKT-conditions:} \left\{ \begin{aligned} \nabla f(x^k) + k(a^\top x^k)a + (1+2\lambda_k)(x^k-x^*) & = \boldsymbol{0}, \\ \lambda_k &\geq 0, \\ \|x^k-x^*\|^2-1 &\leq 0, \\ \lambda_k(\|x^k-x^*\|^2-1)&=0. \end{aligned} \right.

(iv)​

∇f(xk)+k(a⊤xk)a+(1+2λk)(xk−x∗)=0\nabla f(x^k)+k(a^\top x^k)a+(1+2\lambda_k)(x^k-x^*)=0

and

λk≥0,λk(∥xk−x∗∥2−1)=0.\lambda_k \geq 0,\qquad \lambda_k(\|x^k-x^*\|^2-1) = 0.

when kk is sufficiently large, we have

(xk−x∗)⊤(xk−x∗)<1(x^k - x^*)^\top (x^k - x^*)<1

then

λk=0\lambda_k = 0

thus

∇fk(xk)=∇f(xk)+k(a⊤xk)a+xk−x∗=0.\nabla f_k(x^k)=\nabla f(x^k)+k(a^\top x^k)a+x^k-x^*=0.

(v)​

lim⁡k→∞xk=x∗\lim_{k \to \infty}x^k = x^*

From (iv),

∇f(xk)+k(a⊤xk)a+xk−x∗=0.\nabla f(x^k)+k(a^\top x^k)a+x^k-x^*=0.

let k→∞k \to \infty , we get

∇f(x∗)+aλˉ=0\nabla f(x^*) + a \bar{\lambda} = 0
本页目录