京都大学 情報学研究科 知能情報学専攻 2022年2月実施 基礎科目 F1-2

标签：

• 京都大学
• 链式法则
• 约束最优化
• 熵
• 强凸性与强凹性

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

Q.1

(1) Prove

$$\log(xy)=\log x+\log y\qquad (x,y>1)$$

using the definition

$$\log x=\int_1^x\frac1t\,dt.$$

(2) Let $f(x)=a^x$, where $a>0$. Derive $df(x)/dx$ using the chain rule.

Q.2

Let

$$f(p_1,p_2,\ldots,p_n)=-\sum_{i=1}^{n}p_i\log p_i,$$

where

$$\sum_{i=1}^{n}p_i=1,\qquad 0<p_i<1,\qquad n\ge2,$$

and $\log$ denotes the natural logarithm.

(1) Prove that $f$ is strictly concave and non-negative.

(2) Using Lagrange multipliers, derive the $p_i$ that maximize $f$ and give the maximum value.

题目描述

1. 使用 $\log x=\int_1^xdt/t$ 的定义证明 $\log(xy)=\log x+\log y$（$x,y>1$）；再用链式法则求 $f(x)=a^x$（$a>0$）的导数。

2. 在 $\sum_i p_i=1$、$0<p_i<1$、$n\ge2$ 下，令

   $$f(p_1,\ldots,p_n)=-\sum_{i=1}^{n}p_i\log p_i.$$
   1. 证明 $f$ 严格凹且非负；
   2. 用拉格朗日乘数法求最大化 $f$ 的 $p_i$ 及最大值。

Kai

Q.1

(1)

Split the integral at $x$ and substitute $t=xu$ in the second part:

$$\begin{aligned} \log(xy) &=\int_1^{xy}\frac{dt}{t}\\ &=\int_1^x\frac{dt}{t}+\int_x^{xy}\frac{dt}{t}\\ &=\log x+\int_1^y\frac{x\,du}{xu}\\ &=\boxed{\log x+\log y}. \end{aligned}$$

(2)

Because $f(x)>0$,

$$\log f(x)=\log(a^x)=x\log a.$$

Differentiating both sides by the chain rule,

$$\frac{f'(x)}{f(x)}=\log a.$$

Thus

$$\boxed{f'(x)=a^x\log a}.$$

Q.2

(1)

For $0<p_i<1$, $\log p_i<0$, so every term $-p_i\log p_i$ is positive. Hence $f>0$, and in particular $f$ is non-negative.

Its Hessian is

$$\nabla^2f= -\operatorname{diag}\left(\frac1{p_1},\ldots,\frac1{p_n}\right).$$

For every nonzero vector $\boldsymbol{v}$,

$$\boldsymbol{v}^{\mathsf T}\nabla^2f\,\boldsymbol{v} =-\sum_{i=1}^{n}\frac{v_i^2}{p_i}<0.$$

Therefore $f$ is strictly concave on the positive orthant, and hence also on the probability simplex.

(2)

Use the Lagrangian

$$\mathcal{L} =-\sum_{i=1}^{n}p_i\log p_i +\lambda\left(\sum_{i=1}^{n}p_i-1\right).$$

The stationary conditions are

$$\frac{\partial\mathcal{L}}{\partial p_i} =-(\log p_i+1)+\lambda=0.$$

Thus all $p_i$ are equal. The constraint gives

$$\boxed{p_i=\frac1n\qquad(i=1,\ldots,n)}.$$

Strict concavity makes this stationary point the unique global maximum, whose value is

$$\boxed{ f_{\max} =-\sum_{i=1}^{n}\frac1n\log\frac1n =\log n.}$$