在学习机器学习的理论课程(数学,经济学,优化,金融等)时,经常会发现“双重问题”的概念。
对偶任务通常用于获得优化问题中目标功能的较低(或较高)估计。 此外,对于优化问题的几乎所有有意义的陈述,对偶问题都有有意义的解释。 也就是说,如果您面临一个重要的优化问题,那么它的双重问题也很可能很重要。
在本文中,我将讨论圆锥对偶性。 在我看来,这种构造双重任务的方式值得关注。
下一个...
通常如何构建双重任务?
给出一些优化问题:
根据以下方案构造双重任务:
该方案的主要困难在于搜索步骤
。
如果问题不是凸的,那么这就是棺材-通常情况下,它不能在多项式时间内解决(如果
)以及本文中的此类问题,我们以后将不再赘述。
假设问题是凸的,那又是什么?
如果问题是平稳的,那么我们可以使用一阶最优条件
。 在这种情况下,如果一切正常,就可以推断出或
和
或直接起作用
。
如果问题不顺利,那么我们可以使用一阶条件的类似物
(在这里
表示函数的微分
),但是此过程通常要复杂得多。
有时存在一个等效的“平滑”优化问题,并且可以为此构造对偶问题。 但是,通常为了改善结构(从不光滑到光滑),总是必须增加尺寸。
圆锥对偶
有很多优化任务(以下示例)均采用以下表示形式:
在哪里
-矩阵
-矢量
-非退化凸锥。
在这种情况下,可以根据以下方案构造双重任务:
根据以下方案构造双重任务:
共轭锥在哪里
用于锥
定义为
K ^ * = \左\ {y \ in R ^ k | z ^ T y \ geq 0,\ quad \ forall z \ in K \ right \} 。
如我们所见,构造对偶问题的整个复杂性已转移到对偶圆锥的构造上。 但令人高兴的是,构建双锥具有良好的演算,而且经常可以立即写出双锥。
例子
假设我们需要为该问题构造一个双重优化问题:
在这里
,
您会注意到的第一件事:目标函数始终可以线性化!
相反,线性目标函数总是存在一个等效问题:
现在您需要使用一些秘密知识:许多
K_1 = \ {(x,t)\ in R ^ n \ times R | \ quad \ | x \ | _1 \ leq t \}
和
K_2 = \ {(x,t)\ in R ^ n \ times R | \ quad \ | x \ | _2 \ leq t \}
是凸锥。
因此,我们得出问题的等效表示法:
现在我们可以立即写出一个双重问题:
或者,为了简化一点,
在哪里
。
进一步研究的链接: