P*******L 发帖数: 2637 | 1 题目本身是约束最小二乘:
min ||Ax - b||
s.t. ||x|| = d
||x|| 表示 x 的 L2 norm。
我用 Lagrange multiplier,把题目转化为寻找一个常数 y 使得
(A'A - yI)x = A'b
存在一个解 x,并且 x 满足 ||x|| = d。
请问我有什么地方算错吗?下面应该怎么算?
谢谢! | l*3 发帖数: 2279 | 2 算的有点问题. A'b那有个系数2应该.
另外这往下好像不好算. | l*3 发帖数: 2279 | 3 这个在优化里好像对应叫trust region method, 你现在考虑的是这么个问题:
(A'A + \lambda I)x = 2A'b
|x|=d
而且, 如果A是列满秩的话, 可以看到A'A 是一个任意的正定矩阵, A'b可以是任意一个
向量, (也就是说这里的 min 最小二乘本身并不因为 "最小二乘" 带来什么特殊性)
在优化里面, 对应如下问题:
(H + \lambda I) x = b
|x|=d
其中H是一个对称阵, b是一个任意非零向量.
那么, 当 \lambda \to \infty 的时候, |x|\to 0
你要做的就是缩小\lambda, 当\lambda 小到 H 的某一个特征值的负数的时候, |x| \
to infty,
你要找的那个极小点, 对应于第一次 |x|从0 变到 \infty 时恰巧到 d的那个点.
优化里叫trust region method, 你搜搜. | P*******L 发帖数: 2637 | 4 找到了一篇论文
http://link.springer.com/article/10.1007%2FBF01385796
方法跟你说的类似,都要寻找一个 \lambda 使得 ||x|| = d
问题在于有多个 \lambda 满足这个
而且寻找 \lambda 的计算量很大
【在 l*3 的大作中提到】 : 这个在优化里好像对应叫trust region method, 你现在考虑的是这么个问题: : (A'A + \lambda I)x = 2A'b : |x|=d : 而且, 如果A是列满秩的话, 可以看到A'A 是一个任意的正定矩阵, A'b可以是任意一个 : 向量, (也就是说这里的 min 最小二乘本身并不因为 "最小二乘" 带来什么特殊性) : 在优化里面, 对应如下问题: : (H + \lambda I) x = b : |x|=d : 其中H是一个对称阵, b是一个任意非零向量. : 那么, 当 \lambda \to \infty 的时候, |x|\to 0
| l*3 发帖数: 2279 | 5 是有多个这样的lambda, 你要找的, 是最小的那个lambda (这里以 表达式为 (H -
lambda I) x = b 为准, 其中H对称)
我学的trust region 是教可以用牛顿法/拟牛顿法去找.
也可以对问题先进行分析:
你可以先对H做特征矩阵分解 (特征向量正交), 然后把 |x|^2的精确表达式写出来, 是
一个关于lambda的分段凸函数, 其值在每个特征值处去向infty (如果b在对应的特征向
量上分量不为0的话).
其实我的意思是, 这个问题我好像不知道有啥精确求解方法. 如果你是出于优化或是什
么的实际需要, 那有问题可以继续留言问. 如果是理论表达式的话, 那就无力了.
【在 P*******L 的大作中提到】 : 找到了一篇论文 : http://link.springer.com/article/10.1007%2FBF01385796 : 方法跟你说的类似,都要寻找一个 \lambda 使得 ||x|| = d : 问题在于有多个 \lambda 满足这个 : 而且寻找 \lambda 的计算量很大
| p********i 发帖数: 2003 | | P*******L 发帖数: 2637 | 7 多谢楼上二位的解答
我用这边论文里的算法试试看
【在 p********i 的大作中提到】 : http://clas.ufl.edu/users/hager/papers/Regular/sphere.pdf : 讨论了这个问题应该怎么解,理论and实际
| a********f 发帖数: 444 | | l*3 发帖数: 2279 | 9 不是
【在 a********f 的大作中提到】 : This problem is convex.
|
|