optimization - CPLEX 二次单纯形？

Question

有谁知道 CPLEX 使用哪种类似单纯形的算法来求解二次规划。它使用的所谓二次单纯形是什么？

提前谢谢你，梅赫迪

Answer 1

我不确定 CPLEX 使用什么，但 Philip Wolfe 修改了 Simplex Method 以解决二次规划。简而言之，这就是它的作用：

给定一个二次规划问题：QPP。p'x + 1/2x'Cx 带有约束 Ax = b

1. C 必须是对称正定（正半定也可以）
2. 使用 Karush-Kuhn-Tucker 条件生成线性约束
3. 修改 Simplex 方法，以便在选择枢轴列时保持互补松弛。
4. 继续其他常见的 Simplex 方法步骤

更多详细信息，请看这篇论文： http: //pages.cs.wisc.edu/~brecht/cs838docs/wolfe-qp.pdf

希望这可以帮助。