跳到主要内容

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

标签：

Author​

Casablanca

Description​

日本語版​

Q∈Rn×n\boldsymbol{Q} \in \mathbb{R}^{n \times n}, q∈Rn\boldsymbol{q} \in \mathbb{R}^n, u∈Rn\boldsymbol{u} \in \mathbb{R}^n とする． Q,q,u\boldsymbol{Q}, \boldsymbol{q}, \boldsymbol{u} は次の条件 (a)-(c)(c) を満たすとする．ただし，I\boldsymbol{I} は n×nn \times n の単位行列であり，⊤\top は転置を表す．

  • (a) Q+I\boldsymbol{Q} + \boldsymbol{I} は半正定値対称行列である
  • (b) Qu+u+q=0\boldsymbol{Q}\boldsymbol{u} + \boldsymbol{u} + \boldsymbol{q} = 0
  • (c)(c) u⊤u=1\boldsymbol{u}^{\top} \boldsymbol{u} = 1

関数 f:Rn→Rf: \mathbb{R}^n \rightarrow \mathbb{R} と g:Rn→Rg: \mathbb{R}^n \rightarrow \mathbb{R} を以下のように定義する．

f(x)=12x⊤Qx+q⊤xg(x)=f(x)+12x⊤x\begin{aligned} &f(\boldsymbol{x}) = \frac{1}{2}\boldsymbol{x}^{\top} \boldsymbol{Q}\boldsymbol{x} + \boldsymbol{q}^{\top}\boldsymbol{x} \\ &g(\boldsymbol{x}) = f(\boldsymbol{x}) + \frac{1}{2} \boldsymbol{x}^{\top} \boldsymbol{x} \end{aligned}

次の最適化問題 (P1) と (P2) を考える．

(P1):minimizef(x)subject tox⊤x≦1\begin{aligned} \text{(P1)}: &\text{minimize} &f(\boldsymbol{x}) \\ &\text{subject to} &\boldsymbol{x}^{\top}\boldsymbol{x} \leqq 1 \end{aligned}
(P2):minimizeg(x)subject tox⊤x≦1\begin{aligned} \text{(P2)}: &\text{minimize} &g(\boldsymbol{x}) \\ &\text{subject to} &\boldsymbol{x}^{\top}\boldsymbol{x} \leqq 1 \end{aligned}

以下の問いに答えよ．

(i) 任意の x,y∈Rn\boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^n に対して，次の不等式が成り立つことを示せ．

g(x)≧g(y)+∇g(y)⊤(x−y)g(\boldsymbol{x}) \geqq g(\boldsymbol{y}) + \nabla g(\boldsymbol{y})^{\top} (\boldsymbol{x} - \boldsymbol{y})

(ii) 問題 (P2) の大域的最適解を一つ求めよ．さらに，それが実際に (P2) の大域的最適解であることを示せ．

(iii) u\boldsymbol{u} が問題 (P1) の大域的最適解であることを示せ．

English Version​

题目描述​

给定 Q∈Rn×n\boldsymbol Q\in\mathbb R^{n\times n}、 q,u∈Rn\boldsymbol q,\boldsymbol u\in\mathbb R^n，满足：

  1. Q+I\boldsymbol Q+\boldsymbol I 是半正定对称矩阵；
  2. Qu+u+q=0\boldsymbol Q\boldsymbol u+\boldsymbol u+\boldsymbol q=\boldsymbol0；
  3. u⊤u=1\boldsymbol u^\top\boldsymbol u=1，

其中 I\boldsymbol I 为 nn 阶单位矩阵。定义

f(x)=12x⊤Qx+q⊤x,g(x)=f(x)+12x⊤x.f(\boldsymbol x)=\frac12\boldsymbol x^\top\boldsymbol Q\boldsymbol x+ \boldsymbol q^\top\boldsymbol x,\qquad g(\boldsymbol x)=f(\boldsymbol x)+\frac12\boldsymbol x^\top\boldsymbol x.

考虑

(P1):min⁡f(x)满足 x⊤x≦1,(P2):min⁡g(x)满足 x⊤x≦1.\begin{aligned} (\mathrm{P1}):\quad&\min f(\boldsymbol x) \quad\text{满足 }\boldsymbol x^\top\boldsymbol x\leqq1,\\ (\mathrm{P2}):\quad&\min g(\boldsymbol x) \quad\text{满足 }\boldsymbol x^\top\boldsymbol x\leqq1. \end{aligned}

回答：

  1. 证明对任意 x,y∈Rn\boldsymbol x,\boldsymbol y\in\mathbb R^n，
    g(x)≧g(y)+∇g(y)⊤(x−y).g(\boldsymbol x)\geqq g(\boldsymbol y)+ \nabla g(\boldsymbol y)^\top(\boldsymbol x-\boldsymbol y).
  2. 求 P2 的一个全局最优解，并证明其全局最优性。
  3. 证明 u\boldsymbol u 是 P1 的全局最优解。

Kai​

(i)​

g(x)=12x⊤Qx+12x⊤x+q⊤x12x⊤(Q+I)x+q⊤x\begin{aligned} g(x) = & \frac{1}{2} x^\top Q x + \frac{1}{2} x^\top x + q^\top x \\ & \frac{1}{2} x^\top(Q+I)x + q^\top x \\ \end{aligned}

easy to see that g(x)g(x) is convex, and from first-order condition:

g(x)≥∇g(y)⊤(x−y)g(x) \geq \nabla g(y)^{\top} (x-y)

(ii)​

Lagrangian:

L(x,λ)=12x⊤(Q+I)x+q⊤x+λ(x2−1)L(x,\lambda) = \frac{1}{2} x^\top (Q+I)x + q^\top x + \lambda(x^2 - 1)

and we get:

KKT-conditions {(Q+I)x∗+2λIx∗+q=0λ((x∗)2−1)=0λ≥0\text{KKT-conditions } \left\{ \begin{aligned} (Q+I)x^* + 2\lambda I x^* + q & = & \mathbf{0} \\ \lambda ((x^*)^2 - 1) &=&0 \\ \lambda &\geq& 0\\ \end{aligned} \right.

(iii)​

f(x)=12x⊤Qx+q⊤x+12x⊤x−12x⊤xf(x) = \frac{1}{2} x^\top Q x + q^\top x + \frac{1}{2} x^\top x - \frac{1}{2} x^\top x
f(u)=g(u)−12u⊤u=g(u)−12f(u) = g(u) - \frac{1}{2} u^\top u = g(u) - \frac{1}{2}
∀x,f(x)=g(x)−12≥g(u)−12≥g(u)−12=f(u)\forall x, f(x) = g(x) - \frac{1}{2} \geq g(u) - \frac{1}{2} \geq g(u) - \frac{1}{2} = f(u)

thus uu is a global optimal solution to (P1)

本页目录