欢迎您进入某某电器有限公司

开丰注册登录站

造洁净厨房 做健康美食

油烟净化一体机批发定制首选服务商

全国免费咨询热线400-123-4567

当前位置: 主页 » 开丰动态 » 行业动态

优化间隙optimality gap和对偶间隙duality gap是怎样的概念呢?

文章出处:网络 人气:发表时间:2024-08-26 05:18

在优化问题的求解中,我们常常会看到optimality gap和duality gap的概念。所谓的optimality gap是怎样的概念呢?真正的最优解与所求的所谓最优解之间的差距吗?而duality gap的概念是否是包含在optimality gap里的呢?

Optimality gap 可以看做是当前找到的最优解 (best known solution),与最优解的界 (a value that bounds the best solution) 之间的距离。按照这个定义 duality gap 可以视为其中一个measure。

注意,这个gap指的不是与最优解之间的gap,因为在解优化问题之前,我们往往不知道最优解是多少(如果知道就不用解了)。

比如整数规划问题,如果我们能够找到任意一组可行解,那就能得到一组 best found solution;如果我们把整数变量线性化,我们可以得到一个目标函数的 lower bound (假设是min的问题)。这样一来,optimality gap 就可以通过计算目标函数的差值得到。

一般来说这些Gap都是在迭代算法里面用来衡量算法是否收敛和解的质量的。

Duality Gap是Primal解和Dual解对应的目标函数值的差距。差距越小说明最优解的上界和下界越小。也就是说越来越靠近最优解。当然Cplex等求解器里面也直接把这个叫做Optimality Gap.

Optimality Gap是严格意思上是真的最优解和现有解对应的目标函数值的差距。如果你知道真正的Optimal Solution, Optimality Gap就可以很容易求解。当然有的时候就算你不知道Optimal Solution,也可以估算Optimality Gap。一个典型的例子就是在评价很多近似算法的时候用到的approximate rate.

返回顶部

平台注册入口