在优化问题的求解中，我们常常会看到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.