東京大学 情報理工学系研究科 コンピュータ科学専攻 2021年2月実施 問題4

Author

zephyr

Description

Let and () be natural numbers and be the set of real numbers. Denote by the transposition operator of a vector and a matrix. Define the inner product of two column vectors as . Let be a -dimensional column vector, an matrix where is invertible, and an -dimensional column vector. Consider solving the following optimization problem by using the Lagrange multipliers method:

where . The Lagrange function is given by

where is the Lagrange multipliers.

Let be positive real values. The sets of column vectors and form an orthonormal basis of and , respectively; that is, they are all unit vectors and orthogonal to each other. Suppose that the singular value decomposition of is

where is an matrix, is an matrix, and is a matrix given by

Moreover, define

Answer the following questions. Describe not only an answer but also the derivation process.

(1) Express using only .

(2) Express using only and ().

(3) Suppose we wish to express the stationary points of in the form of and . Express the matrices and using only .

(4) Express in question (3) using only .

---

设 和 () 为自然数， 为实数集。记 为向量和矩阵的转置算子。定义两个列向量 的内积为 。设 为一个 维列向量， 是一个 矩阵，其中 可逆， 是一个 维列向量。考虑使用拉格朗日乘子法求解以下优化问题：

其中 。拉格朗日函数为

其中 是拉格朗日乘子。

设 为正实数。列向量集合 和 分别构成 和 的正交基；即它们都是单位向量且彼此正交。假设 的奇异值分解为

其中 是一个 矩阵， 是一个 矩阵， 是一个 矩阵，给出如下

此外，定义

回答以下问题。描述答案的同时也要给出推导过程。

(1) 使用仅 表示 。

(2) 使用仅 和 () 表示 。

(3) 假设我们希望用 和 表示 的驻点。使用仅 表示矩阵 和 。

(4) 使用仅 表示问题 (3) 中的 。

Kai

(1)

Given:

we can write:

where

To find :

Notice:

therefore:

Thus,

(2)

Given:

we have:

Since is an matrix with singular values on the diagonal, is an diagonal matrix:

Therefore,

Thus,

(3)

To solve the optimization problem using Lagrange multipliers:

we need to find and such that:

First, compute :

Next, compute :

Substituting into :

Since is invertible,

Then,

Therefore,

Thus,

(4)

From question 3, we have:

Using :

we know:

Therefore:

Another way to see this is to use the given SVD of and from Question 2:

Then,

Thus,

Knowledge

最优化 奇异值分解 线性代数 拉格朗日乘数法

难点思路

这道题目涉及多个知识点的综合运用，特别是拉格朗日乘数法和奇异值分解的结合使用。重点在于理解矩阵运算和变换的基本性质。

解题技巧和信息

• 拉格朗日乘数法：在求解带有约束的最优化问题时非常有用。
• 奇异值分解：帮助简化矩阵运算，特别是对于逆矩阵和伪逆矩阵的计算。

重点词汇

• inner product 内积
• transpose 转置
• Lagrange multipliers 拉格朗日乘数
• singular value decomposition 奇异值分解
• orthonormal basis 正交归一基

参考资料

1. 《线性代数及其应用》David C. Lay，第四章：奇异值分解
2. 《最优化理论》Edwin K. P. Chong and Stanislaw H. Zak，第三章：拉格朗日乘数法