- 主题:请教线性约束下的二次型求极值算法
设A是N*N 对称非负定矩阵。记x为N维列矢量。
a是一个已知的N维列矢量。
现在给定线性约束 a'x=R(R是常数)
求 f=x'Ax的极小值。
这个有不有什么直观简便的算法?先谢谢了。
(如果A正定则直接可用拉格朗日乘数法求得解析解。)
--
修改:keisadog FROM 223.72.91.*
FROM 223.72.91.*
试过将A进行SVD分解成A=VDV'形式,然后令Y=Vx,然后将约束条件代入。
但这样,对f关于N-1个自由变量求二阶导的矩阵还是非负定。证明不了一阶导数为零的点对应极值。
【 在 shenzhe 的大作中提到: 】
: 用a'x=R可以去掉一个变量,就变成了降了一维的无约束二次函数极值问题?
--
FROM 223.72.91.*
现在a虽然是指定的,但有可能任意啊。
假设A=[1 1;1 1],
a=[0.1;0.1]
可以找到x=[1;-1],使Ax=0。
这个就没法满足线性约束了。
这是实际投资组合问题。就是给定目标收益率,最小化组合的方差。如果任意收益率可以做到方差为零,画面太美…
【 在 bsxfun 的大作中提到: 】
: 如果A不是正定的,最小值不是零吗?
: 因为A不是正定,因此存在非零向量s使得As = 0,将s适当放缩可以满足 a's = R
:
--
修改:keisadog FROM 223.72.91.*
FROM 223.72.91.*
哦。谢谢。
这个问题求解算法倒是不缺。MATLAB里面也有函数。
我就是想知道这个直接拉格朗日方法找出的每一个解是不是都是全局最优。我估计可能有定理保证。只是不知道在哪本书里有这个定理。
注:后来在《凸优化》那本书里找到一个定理,这个问题直接用拉格朗日方法找到的任何一个解都是全局最优解。谢谢。
【 在 bsxfun 的大作中提到: 】
: 呃,你是做alpha量化的吧
: 这个就好办了,直接用cvxopt包
:
--
修改:keisadog FROM 117.136.0.*
FROM 117.136.0.*