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

标签：

• Kyoto-University
• Karush-Kuhn-Tucker-Conditions
• Arithmetic-Mean-Geometric-Mean-Inequality-via-Optimization
• Convexity-of-Power-Compositions

Author

Casablanca, 祭音Myyura

Description

日本語版

以下の問 (i)、(ii) に答えよ。

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

$$\begin{aligned} \text{(P) } &\text{Maximize } \ \theta(\boldsymbol{x}) \\ &\text{subject to } \ \boldsymbol{x} \in X \end{aligned}$$

ただし、(P) の決定変数は $x \in \mathbb{R}^n$ であり、 $\theta : \mathbb{R}^n \rightarrow \mathbb{R}$ と $X \subseteq \mathbb{R}^n$ は以下のように定義された目的関数と実行可能領域である。

$$\theta(\boldsymbol{x}) = \left( \prod_{i=1}^{n} x_i \right)^{\frac{1}{n}}, \quad X = \left\{ \boldsymbol{x} \in \mathbb{R}^n \middle| \sum_{i=1}^{n} x_i = 1, \, x_i \geqq 0 \ (i = 1, \ldots, n) \right\}$$

問題 (P) は唯一の最適解 $\boldsymbol{x}^*$ を持ち、関数 $\theta$ は $\mathbb{R}_{+}^n$ 上で凹関数（すなわち、 $-\theta$ は凸関数）であることが知られている。 ただし、 $\mathbb{R}_{+}^n = \{ \boldsymbol{x} \in \mathbb{R}^n \mid x_i > 0 \ (i = 1, \ldots, n) \}$ である。

以下の (a), (b), $(c)$ に答えよ。

(a) 問題 (P) のカルーシュ・キューン・タッカー条件 (Karush-Kuhn-Tucker 条件) を書け。(問題 (P) が最大化問題であることに注意すること。)

(b) 問題 (P) の最適解 $\boldsymbol{x}^*$ を求めよ。

$(c)$ $\gamma_i \in \mathbb{R}, \, \gamma_i \geqq 0 \ (i = 1, \ldots, n)$ とする。問題 (P) の最適解 $\boldsymbol{x}^*$ を利用して、以下の算術幾何平均の不等式が成り立つことを示せ。

$$\frac{1}{n} \sum_{i=1}^{n} \gamma_i \geqq \left( \prod_{i=1}^{n} \gamma_i \right)^{\frac{1}{n}}$$

(ii) 正の整数 $n$ に対して、 $\mathcal{F}_n$ を $\mathbb{R}^n$ から $\mathbb{R}$ への非負の凸関数の集合とする。以下の (A), (B) に答えよ。

(A) $f \in \mathcal{F}_n$ が与えられたとき、関数 $g_f : \mathbb{R}^n \rightarrow \mathbb{R}$ を $g_f(\boldsymbol{x}) = f(\boldsymbol{x})^2 \ (\boldsymbol{x} \in \mathbb{R}^n)$ と定義する。そのとき、任意の $f \in \bigcup_{n=1}^{\infty} \mathcal{F}_n$ に対して、 $g_f$ が凸関数であることを示せ。

(B) 正の数 $\alpha \in \mathbb{R}$ と $f \in \mathcal{F}_n$ が与えられたとき、関数 $h_{f,\alpha} : \mathbb{R}^n \rightarrow \mathbb{R}$ を $h_{f,\alpha}(\boldsymbol{x}) = f(\boldsymbol{x})^{\alpha} \ (\boldsymbol{x} \in \mathbb{R}^n)$ と定義する。 そのとき、すべての $\alpha \geqq \alpha^*$ と $f \in \bigcup_{n=1}^{\infty} \mathcal{F}_n$ に対して、 $h_{f,\alpha}$ が凸関数であるような最小な $\alpha^* \in \mathbb{R}$ を求めよ。その際、 $\alpha^*$ が最小であることを示せ。

English Version

题目描述

回答以下两大题。

1. 考虑以 $\boldsymbol{x}\in\mathbb{R}^n$ 为决策变量的非线性规划

$$\begin{aligned} (P):\quad &\text{最大化}\quad \theta(\boldsymbol{x}) =\left(\prod_{i=1}^n x_i\right)^{1/n}\\ &\text{约束于}\quad \boldsymbol{x}\in X =\left\{\boldsymbol{x}\in\mathbb{R}^n\ \middle|\ \sum_{i=1}^n x_i=1,\quad x_i\geqq0\ (i=1,\ldots,n)\right\}. \end{aligned}$$

已知 $(P)$ 有唯一最优解 $\boldsymbol{x}^*$，且 $\theta$ 在

$$\mathbb{R}_+^n =\left\{\boldsymbol{x}\in\mathbb{R}^n\mid x_i>0\ (i=1,\ldots,n)\right\}$$

上为凹函数（等价地，$-\theta$ 为凸函数）。完成下列各问：

1. 写出 $(P)$ 的 KKT 条件；注意这是最大化问题。
2. 求 $(P)$ 的最优解 $\boldsymbol{x}^*$。
3. 给定 $\gamma_i\in\mathbb{R}$ 且 $\gamma_i\geqq0$（$i=1,\ldots,n$），利用上述 $\boldsymbol{x}^*$ 证明算术—几何平均不等式

$$\frac1n\sum_{i=1}^n\gamma_i \geqq \left(\prod_{i=1}^n\gamma_i\right)^{1/n}.$$

2. 对每个正整数 $n$，令 $\mathcal{F}_n$ 表示所有从 $\mathbb{R}^n$ 到 $\mathbb{R}$ 的非负凸函数所成的集合。

   1. 对 $f\in\mathcal{F}_n$ 定义 $g_f:\mathbb{R}^n\to\mathbb{R}$ 为 $g_f(\boldsymbol{x})=f(\boldsymbol{x})^2$。证明对任意 $f\in\bigcup_{n=1}^{\infty}\mathcal{F}_n$，函数 $g_f$ 都是凸函数。
   2. 给定正数 $\alpha$ 和 $f\in\mathcal{F}_n$，定义 $h_{f,\alpha}:\mathbb{R}^n\to\mathbb{R}$ 为 $h_{f,\alpha}(\boldsymbol{x})=f(\boldsymbol{x})^\alpha$。 求最小实数 $\alpha^*$，使得对每个 $\alpha\geqq\alpha^*$ 以及每个 $f\in\bigcup_{n=1}^{\infty}\mathcal{F}_n$， $h_{f,\alpha}$ 都是凸函数；还须证明所求 $\alpha^*$ 确实最小。

Kai

(i)

(a)

$$\begin{aligned} \text{(P)}: \text{Minimize } \ &-\theta (x) \\ \text{subject to } \ &\boldsymbol{1}^\top x = 1 \\ &x \succeq \boldsymbol{0} \end{aligned}$$

Lagrangian:

$$L(x, \mu,\lambda) = -\theta (x) + \mu (\boldsymbol{1}^\top x - 1)-\lambda^\top x$$

Since the uniform feasible point has positive objective value, every optimizer is in $\mathbb R_+^n$. The KKT conditions are therefore

$$\text{KKT-conditions } \left\{ \begin{aligned} &-\frac{\theta(x)}{n x_i}+\mu-\lambda_i=0,\qquad i=1,\ldots,n,\\ &\boldsymbol{1}^\top x=1,\qquad x\succeq0,\\ &\lambda\succeq0,\qquad \lambda_i x_i=0,\quad i=1,\ldots,n. \end{aligned} \right.$$

(b)

$x^*$, $\mu^*$ and $\lambda^*$ satisfy the KKT conditions for

$$x^* = \left[\frac 1n, \frac 1n, \ldots , \frac 1n\right]^\top,\qquad \mu^*=\frac1n,\qquad \lambda^*=\boldsymbol0.$$

Since $-\theta$ is convex, the KKT conditions are sufficient; the stated uniqueness then gives this as the unique optimal solution.

$(c)$

If $\sum_i\gamma_i=0$, the claim is immediate. Otherwise, put $x_i=\gamma_i/\sum_j\gamma_j$. Since $\theta(x)\leq\theta(x^*)=1/n$,

$$\left(\prod_{i=1}^{n} \gamma_i\right)^{\frac 1n} =\left(\sum_{i=1}^{n}\gamma_i\right)\theta(x) \leq \frac 1n \sum_{i=1}^{n}\gamma_i.$$

(ii)

(A)

For any $f \in \bigcup_{n=1}^{\infty} \mathcal{F}_n$ , w.l.o.g, let $f : \mathbb{R}^k \rightarrow \mathbb{R}$ be an nonnegative function. Then

$$\theta g_f( x_1) + (1-\theta)g_f(x_2) = \theta f( x_1)^2 + (1-\theta) f( x_2)^2$$

$$g_f(\theta x_1 + (1-\theta)x_2) = f(\theta x_1 + (1-\theta)x_2) ^ 2 \leq (\theta f( x_1) + (1-\theta) f( x_2)) ^2$$

For $a=f(x_1)\geq0$ and $b=f(x_2)\geq0$,

$$\theta a^2+(1-\theta)b^2-(\theta a+(1-\theta)b)^2 =\theta(1-\theta)(a-b)^2\geq0.$$

Therefore,

$$g_f(\theta x_1 + (1-\theta)x_2) \leq \theta g_f( x_1) + (1-\theta)g_f(x_2)$$

(B)

$$\alpha ^* = 1$$

for $\alpha \geq 1$ :

$$\theta f(x_1)^{\alpha} + (1-\theta)f(x_2) ^{\alpha} \geq (\theta f(x_1) + (1-\theta)f(x_2))^{\alpha}$$

since $\theta f(x_1) + (1-\theta)f(x_2) \geq f(\theta x_1 + (1-\theta)x_2)$ , and $t^{\alpha}$ increases for $t>0$ then

$$(\theta f(x_1) + (1-\theta)f(x_2))^{\alpha} \geq (f(\theta x_1 + (1-\theta)x_2))^{\alpha } = h(\theta x_1 + (1-\theta)x_2)$$

thus $h$ is convex for $\alpha \geq 1$ .

For $0<\alpha<1$, let $f(x)=|x|\in\mathcal F_1$. Then

$$h_{f,\alpha}(1)=1> \frac{h_{f,\alpha}(0)+h_{f,\alpha}(2)}2=2^{\alpha-1},$$

so $h_{f,\alpha}$ is not convex. Hence $\alpha^*=1$.