跳到主要内容

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

标签：

Author​

思齐塾, 祭音Myyura

Description​

つぎの凸2次計画問題を考える。

P: Minimize 12xTAx\text{Minimize } \frac{1}{2}x^T A x subject to aTx=b\text{subject to } a^T x = b

ただし、  A\ A は n×nn \times n 正定値対称行列、 aa は 00 でない nn 次元ベクトル、 bb はスカラーであり、  T\ ^T はベクトルの転置を表す。この問題は唯一の最適解 x∗x^* をもつ。 R+={t∈R∣t≥0}\mathbb{R}_+ = \{ t \in \mathbb{R} \mid t \geq 0 \} とする。パラメータ λ∈R\lambda \in \mathbb{R} と ρ∈R+\rho \in \mathbb{R}_+ を含むつぎの制約なし最小化問題を考える。

P( λ,ρ\lambda, \rho ): Minimize 12xTAx+λ(aTx−b)+ρ(aTx−b)2\text{Minimize } \frac{1}{2}x^T A x + \lambda(a^T x - b) + \rho (a^T x - b)^2 subject to x∈Rn\text{subject to } x \in \mathbb{R}^n

任意の λ∈R\lambda \in \mathbb{R} と ρ∈R+\rho \in \mathbb{R}_+ に対して問題 P( λ,ρ\lambda, \rho ) は唯一の最適解 xˉ(λ,ρ)\bar{x}(\lambda, \rho) をもつ。

以下の問いに答えよ。

(i) 問題 P のカルーシュ・キューン・タッカー (Karush-Kuhn-Tucker) 条件を用いて x∗x^* を求めよ。

(ii) xˉ(λ,ρ)\bar{x}(\lambda, \rho) を求めよ。

(iii) パラメータ λ∗∈R\lambda^* \in \mathbb{R} は Ax∗+λ∗a=0A x^* + \lambda^* a = 0 を満たすとする。このとき任意の ρ∈R+\rho \in \mathbb{R}_+ に対して xˉ(λ∗,ρ)=x∗\bar{x}(\lambda^*, \rho) = x^* となることを示せ。

(iv) 任意の λ∈R\lambda \in \mathbb{R} と ρ∈R+\rho \in \mathbb{R}_+ に対して、次の不等式が成り立つことを示せ。

12(x∗)TAx∗≥12xˉ(λ,ρ)TAxˉ(λ,ρ)+λ(aTxˉ(λ,ρ)−b)+ρ(aTxˉ(λ,ρ)−b)2\frac{1}{2} (x^*)^T A x^* \geq \frac{1}{2} \bar{x}(\lambda, \rho)^T A \bar{x}(\lambda, \rho) + \lambda (a^T \bar{x}(\lambda, \rho) - b) + \rho (a^T \bar{x}(\lambda, \rho) - b)^2

(v) 任意の λ∈R\lambda \in \mathbb{R} に対して, lim⁡ρ→∞xˉ(λ,ρ)\lim_{\rho \to \infty} \bar{x}(\lambda, \rho) は存在することが知られている。パラメータ λ\lambda の値に関わらず, lim⁡ρ→∞xˉ(λ,ρ)=x∗\lim_{\rho \to \infty} \bar{x}(\lambda, \rho) = x^* となることを示せ。

题目描述​

考虑凸二次规划

P:min⁡x12xTAxs.t.aTx=b,\begin{aligned} P:\quad \min_x\quad &\frac12x^TAx\\ \text{s.t.}\quad &a^Tx=b, \end{aligned}

其中 AA 是 n×nn\times n 正定对称矩阵，aa 是非零的 nn 维向量，bb 是标量，上标 TT 表示转置。已知该问题有唯一最优解 x∗x^*。

记 R+={t∈R∣t≥0}\mathbb R_+=\{t\in\mathbb R\mid t\geq0\}。对参数 λ∈R\lambda\in\mathbb R、ρ∈R+\rho\in\mathbb R_+，再考虑无约束最小化问题

P(λ,ρ):min⁡x∈Rn12xTAx+λ(aTx−b)+ρ(aTx−b)2.\begin{aligned} P(\lambda,\rho):\quad \min_{x\in\mathbb R^n}\quad \frac12x^TAx+\lambda(a^Tx-b)+\rho(a^Tx-b)^2. \end{aligned}

已知对任意 λ∈R\lambda\in\mathbb R、ρ≥0\rho\geq0，P(λ,ρ)P(\lambda,\rho) 都有唯一最优解 xˉ(λ,ρ)\bar x(\lambda,\rho)。完成以下各问：

  1. 利用问题 PP 的 Karush–Kuhn–Tucker（KKT）条件求 x∗x^*。

  2. 求 xˉ(λ,ρ)\bar x(\lambda,\rho)。

  3. 设参数 λ∗∈R\lambda^*\in\mathbb R 满足

    Ax∗+λ∗a=0.Ax^*+\lambda^*a=0.

    证明对任意 ρ∈R+\rho\in\mathbb R_+，都有

    xˉ(λ∗,ρ)=x∗.\bar x(\lambda^*,\rho)=x^*.

  4. 证明对任意 λ∈R\lambda\in\mathbb R、ρ∈R+\rho\in\mathbb R_+，

    12(x∗)TAx∗≥12xˉ(λ,ρ)TAxˉ(λ,ρ)+λ(aTxˉ(λ,ρ)−b)+ρ(aTxˉ(λ,ρ)−b)2.\frac12(x^*)^TAx^* \geq \frac12\bar x(\lambda,\rho)^TA\bar x(\lambda,\rho) +\lambda\bigl(a^T\bar x(\lambda,\rho)-b\bigr) +\rho\bigl(a^T\bar x(\lambda,\rho)-b\bigr)^2.

  5. 已知对任意 λ∈R\lambda\in\mathbb R，极限 lim⁡ρ→∞xˉ(λ,ρ)\lim_{\rho\to\infty}\bar x(\lambda,\rho) 存在。证明无论 λ\lambda 取何值，

    lim⁡ρ→∞xˉ(λ,ρ)=x∗.\lim_{\rho\to\infty}\bar x(\lambda,\rho)=x^*.

Kai​

γ=aTA−1a\gamma=a^TA^{-1}a とおく。 AA は正定値で a≠0a\ne0 なので γ>0\gamma>0 である。

(i) ラグランジアン

L(x,λ)=12xTAx+λ(aTx−b)L(x,\lambda)=\frac12x^TAx+\lambda(a^Tx-b)

の KKT 条件は

Ax∗+λ∗a=0,aTx∗=b.Ax^*+\lambda^*a=0,\qquad a^Tx^*=b.

第1式から x∗=−λ∗A−1ax^*=-\lambda^*A^{-1}a であり、第2式より −λ∗γ=b-\lambda^*\gamma=b である。従って

λ∗=−bγ,x∗=bγA−1a.\boxed{\lambda^*=-\frac b\gamma,\qquad x^*=\frac b\gamma A^{-1}a}.

(ii) P(λ,ρ)P(\lambda,\rho) の目的関数の Hessian は

A+2ρaaTA+2\rho aa^T

であり正定値なので、停留点が唯一の最適解である。停留条件は

Axˉ+λa+2ρ(aTxˉ−b)a=0.A\bar x+\lambda a+2\rho(a^T\bar x-b)a=0.

A−1aA^{-1}a の係数を解くと

xˉ(λ,ρ)=2ρb−λ1+2ργ A−1a.\boxed{\bar x(\lambda,\rho) =\frac{2\rho b-\lambda}{1+2\rho\gamma}\,A^{-1}a}.

実際、

aTxˉ−b=−λγ+b1+2ργa^T\bar x-b=-\frac{\lambda\gamma+b}{1+2\rho\gamma}

を停留条件へ代入すれば確認できる。

(iii) λ∗=−b/γ\lambda^*=-b/\gamma を (ii) に代入すると

xˉ(λ∗,ρ)=2ρb+b/γ1+2ργA−1a=bγA−1a=x∗.\bar x(\lambda^*,\rho) =\frac{2\rho b+b/\gamma}{1+2\rho\gamma}A^{-1}a =\frac b\gamma A^{-1}a=x^*.

これは任意の ρ≥0\rho\geq0 で成立する。

(iv) x∗x^* は aTx∗−b=0a^Tx^*-b=0 を満たすので、 P(λ,ρ)P(\lambda,\rho) の目的関数を Fλ,ρF_{\lambda,\rho} と書けば

Fλ,ρ(x∗)=12(x∗)TAx∗.F_{\lambda,\rho}(x^*)=\frac12(x^*)^TAx^*.

xˉ(λ,ρ)\bar x(\lambda,\rho) は Fλ,ρF_{\lambda,\rho} の大域的最小解であるから

12(x∗)TAx∗≥12xˉTAxˉ+λ(aTxˉ−b)+ρ(aTxˉ−b)2.\boxed{ \frac12(x^*)^TAx^* \geq \frac12\bar x^TA\bar x +\lambda(a^T\bar x-b) +\rho(a^T\bar x-b)^2}.

(v) (ii) の閉形式から、 λ\lambda の値に関係なく

lim⁡ρ→∞2ρb−λ1+2ργ=bγ.\lim_{\rho\to\infty} \frac{2\rho b-\lambda}{1+2\rho\gamma} =\frac b\gamma.

従って

lim⁡ρ→∞xˉ(λ,ρ)=bγA−1a=x∗.\boxed{\lim_{\rho\to\infty}\bar x(\lambda,\rho) =\frac b\gamma A^{-1}a=x^*}.
本页目录