|
|
最优化问题中的非线性、非凸规划问题，高效可行的求解算法有哪些？
关注者
54
被浏览
78,432
5 个回答
这个问题表面上是问的非线性规划的求解，实际上想问的却是非凸函数的最优化问题。
关于直接求解非凸优化，目前为止 尚未完全 解决所有非凸情况下的问题。但是一些特殊形式的非凸问题（如原函数可以分段，各自区间内凸函数、线性二层规划、可通过松弛变量直接转化为凸函数等），基于规模和复杂程度已经有各种形式的高效解法（遗传算法、分枝限界、凹凸化法等）。
而对于具体的非凸优化问题，一般需要人为采取些trick来辅助求解。如随机初始位置的梯度法、修改约束条件/加松弛变量牺牲一定精度转化为凸等等。
非凸优化很难，不能解出来是正常现象，能解出来才不正常。
没有针对所有非凸优化都有效的算法，具体用什么算法，要看你的非凸函数的其他特性。例如，是否光滑？维数多高？具有哪些特别结构？
很多非凸优化问题都是通过转化为凸优化问题来求解的，直接求解的算法往往都是启发式的算法。