归一化约束二次函数的最小化

计算科学 非线性规划
2021-12-20 01:49:44

我是一名计算机科学专业的学生。我需要帮助来解决受约束的归一化二次函数。我熟悉通过提供对称矩阵和向量作为 quadprog matlab 函数的输入来使用 matlab 求解二次约束优化函数。现在,我遇到了另一种形式的二次函数,描述如下:

min0αC(12αtBαα1N+btα)

在哪里bt=[b1,...,bN]是参数向量。B=[bij]是参数的对称正矩阵。 α1N=i=1Nαi.0αC意思是 i1,...,n,0αiC. 我不知道如何处理这样的功能。我可以将归一化二次函数重写为二次函数吗?是否有任何教程,任何描述解决此类问题的不同数学步骤的链接,以便进行必要的实施?

谢谢。

1个回答

Boyd 和 Vandenberghe 的教科书 Convex Optimization 是一个很好的起点。我强烈建议您获取一份副本(作者在网上发布了一个免费的 .pdf 文件,因此不会花费您任何费用,而且剑桥大学出版社的精装版价格相当合理。)

从 Cholesky 分解您的对称和正定矩阵开始B作为

B=RTR

然后把你的问题写成

minzTzy+bTα

在哪里

z=Rα

y=2αT1N.

引入辅助变量t,并将问题写为

mint+bTα

受制于

zTzyt

z=Rα

y=2αT1N

0αC

在这一点上,你有一个线性目标函数和变量中的一堆线性等式和不等式约束α,z,y, 和t. 此外,约束确保y>0t0.

唯一困难的部分是双曲线约束

zTzyt.

自从y>0, 这可以写成

zTzty.

凸优化的一个聪明技巧(这是 Boyd 和 Vandenberghe 书中的一个练习)是这个双曲约束可以写成二阶锥约束

[2zyt]2y+t

至此,您已经有了一个标准的二阶锥规划问题,可以通过各种求解器来求解。

MATLAB 中用于凸优化的 CVX 包可以使用其“quad_over_lin”函数自动为您重新制定。