对偶间隙
对偶间隙是应用数学中最佳化问题的词语，是指原始解和对偶解之间的差距。若formula_1是对偶问题解对应的值，而formula_2是原始问题最佳解对应的值，则对偶间隙为formula_3。针对最小化的最佳化问题，对偶间隙恒大于等于零。对偶间隙为零若且唯若的条件成立，不然对偶间隙为严格正值，此时即为。
一般而言，给定二个的分隔 formula_4及formula_5。假定函数formula_6，可以定义原始问题为
formula_7
若有限制条件，可以整合到函数formula_8中，方式是令formula_9，其中formula_10是示性函数。则令formula_11是使得formula_12。则对偶间隙即为以下的差值
formula_13
其中formula_14为二个变数的凸共轭。
在计算最优化中，会提到另一种「对偶间隙」，是对偶解以及原始问题次最佳但是可行解之间的差距。这种对偶间隙反映了目前可行，但可能只是次最佳的迭代解，和对偶问题解之间的差距。对偶问题解是指规律性条件下，等于原始问题凸松弛（convex relaxation）下的解。凸松弛是指将问题中非凸可行集合改为闭凸包，将非凸函数改为凸的闭集（函数的是原始目标函数的闭凸包）。
生成维基百科快照图片，大概需要3-30秒！
如果网站内容有侵犯您的版权
请联系：pinbor@iissy.com
请联系：pinbor@iissy.com
Copyright ©2014 iissy.com, All Rights Reserved.