由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Mathematics版 - 请教一道线性代数题
相关主题
发包子请教线性代数问题请问一个矩阵的问题!谢谢
问一个lagrange multiplier的简单问题。如何证明一个关于矩阵的猜想?
请问lagrange multiplier的简单问题。再问个数学问题
[求助]lagrange multiplier求教一个矩阵特征值的问题
求问一个简单的线性代数的问题请教Hermitian矩阵分解
求助一道困扰我很久的题目问个对称矩阵的问题
Re: 自然对数e请教一个一直困扰我的矩阵问题
求助,x*y'的特征值是多少?请教一题概率的习题
相关话题的讨论汇总
话题: lambda话题: 二乘话题: 最小话题: infty话题: 线性代数
进入Mathematics版参与讨论
1 (共1页)
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
6
http://clas.ufl.edu/users/hager/papers/Regular/sphere.pdf
讨论了这个问题应该怎么解,理论and实际
P*******L
发帖数: 2637
7
多谢楼上二位的解答
我用这边论文里的算法试试看

【在 p********i 的大作中提到】
: http://clas.ufl.edu/users/hager/papers/Regular/sphere.pdf
: 讨论了这个问题应该怎么解,理论and实际

a********f
发帖数: 444
8
This problem is convex.
l*3
发帖数: 2279
9
不是

【在 a********f 的大作中提到】
: This problem is convex.
1 (共1页)
进入Mathematics版参与讨论
相关主题
请教一题概率的习题求问一个简单的线性代数的问题
用矩阵表达向量的极性求助一道困扰我很久的题目
请教特征值问题Re: 自然对数e
请问对称矩阵的特征值特征向量是连续的吗?求助,x*y'的特征值是多少?
发包子请教线性代数问题请问一个矩阵的问题!谢谢
问一个lagrange multiplier的简单问题。如何证明一个关于矩阵的猜想?
请问lagrange multiplier的简单问题。再问个数学问题
[求助]lagrange multiplier求教一个矩阵特征值的问题
相关话题的讨论汇总
话题: lambda话题: 二乘话题: 最小话题: infty话题: 线性代数