用户: Solution/ 试卷: 数值代数与优化

125 春期末考

第一题, 除矩阵向量运算外, 任何作为解答的算法需要自行实现, 不能直接调用矩阵分解, 线性方程组求解等库函数. 例如, 若将 LU 分解作为解答, 需要自行实现 LU 分解算法, 不得直接调用 MATLAB 自带 [L,U]=lu(A) 函数.

第二题, 允许调用矩阵分解等库函数, 但不允许直接调用优化求解器.

一、

Given a symmetric matrix $A\in {\mathbb{R}}^{n\times n}$. We look for a unitary matrix $W$ such that, $$W=\left(\begin{array}{cc}A& \ast \\ \ast & \ast \end{array}\right),$$where $\ast$ denotes an unspecified block of the matrix. The matrix given in the dataset is $A^2$. (1) (10 pt) Give an if-and-only-if condition on $A$ such that the unitary matrix $W$ exists. (2) (10 pt) Assume $A$ could be embedded into a unitary matrix $W$, where the size of $W$ is a power of $2$, i.e., $W\in {\mathbb{R}}^{2^k\times 2^k}$ for some integer $k$. Design a unitary matrix $W$. (3) (20 pt) Design an algorithm taking $A^2$ as the input and compute the application of $W$ on a given vector. [Your algorithm should include factorization of $A$. The algorithm could be tailored to the specific structure of $A^2$ in the dataset.] (4) (10 pt) Let $n$ be the size of $A$. Embed $A$ into $W$ of size $2n$. Write the value of $$\left(\begin{array}{ccccc}1& 1& 0& \cdots & 0\end{array}\right)W(e_1+e_{n+1}),$$for each $A^2$ in the dataset, where $e_i\in {\mathbb{R}}^{2n}$ is a zero column vector with $1$ at the $i$-th position.

二、

Given two nonsingular matrix $A\in {\mathbb{R}}^{m\times k}$ and $B\in {\mathbb{R}}^{k\times n}$ with $k<\min (m,n)$, a weight vector $c\in {\mathbb{R}}^n$, and a vector $b\in {\mathbb{R}}^m$. Consider the following linear program, $$\underset{\begin{array}{c}ABx=b\\ x\ge 0\end{array}}{\min }{c}^{\top }x.$$ (1) (10 pt) Write the KKT condition for above system. (2) (20 pt) Design and implement an algorithm to solve the linear program. [The algorithm could be tailored to the specific structure of matrices in the dataset.] (3) (5 pt) Based on the given datasets, analyze the computational complexity, and give a complexity upper bound for your designed algorithm. (4) (15 pt) Apply the designed algorithm to given matrices. Write the minimum objective values. [Keep 6 decimal digits in your answer.]