- 对于凸形
结论1:凸形可行域只有1个峰,只要达到那个峰,我们就达到了最优,是全局最优。
结论2:至少有一个顶点是峰。
单纯形法:
- 单纯形是什么?数学上可以写成一堆线性不等式限制出来的区域。
- 单纯形法,仅适用于求解线性规划,线性规划又是凸优化的一种。因为线性规划的定义域是单纯形,单纯形是凸的,即线性规划是定义域为凸、目标函数为线性的问题。
- 先找到一个顶点,然后从这个顶点,沿着某条边线,走到下一个顶点,直到最优。方向的选择可以有很多种,最多使用的是比较短视的方法:沿着最陡峭的那一条,追求当前步上升最快。
- 单纯形法寻找路线优化目标函数,直至达到一个峰,而该峰就是全局最优。
Slater’s condition 根据wiki,
Slater’s condition (or Slater condition) is a sufficient condition for strong duality to hold for a convex optimization problem, named after Morton L. Slater. Informally, Slater’s condition states that the feasible region must have an interior point.
即在对偶问题中gap为0要满足的条件,即可行域中必须有内点的条件。线性规划的对偶理论没出现的时候,线性规划是不知道能不能解的。也就是说,对偶理论能够证明一个线性规划问题不存在解。思路是找到一个跟原问题的对偶问题密切相关的问题,如果这个问题有解,原问题就没解。
那么证明便归为两个主要部分,1 如何转化为对偶问题 2 为什么两个问题的解相关?
首先[问题要满足是凸优化]。对于凸优化来说,在满足constraint qualifications(如上文的slater condition为其中一种,满足该条件,这里涉及到仿射函数即可表示为f=A*w+b 。仿射函数其实就是线性变换liner。)情况下,gap=0,为强对偶。
其次[在求解凸优化时引入乘子以及最优解需要满足的条件]。在凸优化中的非线性优化问题下,该问题满足一些constraint qualifications,当存在不等式约束时(只有等式约束时,即拉格朗日function求偏导(也就是KKT turns into the Lagrange conditions)),我们用KKT引进 Lagrange multipliers,这些乘子需要满足KKT 的四个条件。注意到这里的目标函数与约束函数一定是continuously differentiable at a point x(local optimum点),如果functions are non-differentiable,subdifferential
versions of Karush–Kuhn–Tucker (KKT) conditions are available.对偶问题, 这里代表Lagrangian dual problem,还有其他对偶问题 Wolfe dual problem and the Fenchel dual problem。
Lagrangian dual problem 需要先形成一个L函数,这个原问题的解是,
- todo
- 用数学表达:
凸优化问题:
reference:
[1]https://cowles.yale.edu/sites/default/files/files/pub/d00/d0080.pdf
[2]https://en.wikipedia.org/wiki/Convex_optimization
本文链接: https://satyrswang.github.io/2021/03/11/对偶/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!