最小长度最小二乘法

该笔记本展示了如何解决*最小长度最小二乘法*问题，该问题找到一个长度最小的向量 \(x \in \mathbf{R}^n\)，以实现特定最小二乘问题的小均方误差（MSE）:

\[\begin{split}\begin{array}{ll} \mbox{minimize} & \mathrm{len}(x) \\ \mbox{subject to} & \frac{1}{n}\|Ax - b\|_2^2 \leq \epsilon, \end{array}\end{split}\]

其中变量是 \(x\)，问题数据是 \(n\)， \(A\)， \(b\)，和 \(\epsilon\)。

这是一个拟凸程序（QCP）。可以使用规定的拟凸编程（DQCP）来指定它，并且可以使用CVXPY来解决它。

!pip install --upgrade cvxpy

import cvxpy as cp
import numpy as np

下面的代码块构建了问题数据。

n = 10
np.random.seed(1)
A = np.random.randn(n, n)
x_star = np.random.randn(n)
b = A @ x_star
epsilon = 1e-2

接下来的代码块构建并解决了QCP问题。

x = cp.Variable(n)
mse = cp.sum_squares(A @ x - b)/n
problem = cp.Problem(cp.Minimize(cp.length(x)), [mse <= epsilon])
print("问题是否为DQCP？：", problem.is_dqcp())

problem.solve(qcp=True)
print("找到一个解，长度为：", problem.value)

问题是否为DQCP？： True
找到一个解，长度为： 8.0

print("MSE: ", mse.value)

MSE:  0.00926009328813662

print("x: ", x.value)

x:  [-2.58366030e-01  1.38434327e+00  2.10714108e-01  9.44811159e-01
 -1.14622208e+00  1.51283929e-01  6.62931941e-01 -1.16358584e+00
  2.78132907e-13 -1.76314786e-13]

print("x_star: ", x_star)

x_star:  [-0.44712856  1.2245077   0.40349164  0.59357852 -1.09491185  0.16938243
  0.74055645 -0.9537006  -0.26621851  0.03261455]