切割平面法和非线性规划

快捷方式: 差异，相似，杰卡德相似系数，参考。

切割平面法和非线性规划之间的区别

切割平面法 vs. 非线性规划

在数学优化中，切割平面法是通过线性不等式对可行集或目标函数进行迭代性优化（即切割）的优化方法的涵盖性术语。该过程通常用来发现混合整数线性规划（MILP）问题的整数解，也可以用来解决常规的、未必可微的凸优化问题。利用切割平面法求解 MILP 由 Ralph E. Gomory 引入。 MILP 的切割平面法通过将整数问题线性松弛为非整数线性问题，并对其进行求解，来求解 MILP 问题。线性规划理论说明，在温和的假定下（如果线性规划存在最优解，并且可行域不包含一条线），总存在一个极值点或顶点是最优的。 检验所获的最优解是否为整数解。如否，则必然存在一线性不等式将最优点和真可行集的凸包分离。找到这样的不等式是分离问题，而这样的不等式就是切割。 切割可以被加入到被松弛的线性规划中，使得当前的非整数解对松弛不再可行。该过程不断重复，直到找到最优整数解。 用于普遍的凸连续优化和变体的切割平面法有不同的名称： Kelley 法， Kelley-Cheney-Goldstein 法和捆绑法。它们常用于不可微的凸最小化问题。对于这类问题，通常的可微优化的梯度法无法使用，而使用这些方法可以高效地得到凸目标函数及其次梯度。这种情况最常出现在双拉格朗日函数的凹优化中。另一种常见情形是 Dantzig-Wolfe 分解应用于结构优化问题中，这类问题通常有含有指数级变量的表达式。通过延迟列生成法按需生成这些变量等同于在对应的对偶问题上切割平面。. 在数学中，非线性规划是求解由一系列未知实函数组成的组方程和不等式（统称为约束）定义的最佳化問題，伴随着一个要被最大化或最小化的目标函数，只是一些约束或目标函数是非線性的。 它是最优化处理非线性问题的一个子领域。.

最优化

最优化，是应用数学的一个分支，主要研究以下形式的问题：.

切割平面法和最优化 · 最优化和非线性规划 · 查看更多 »