• CP问题求对偶问题的方法

    2010-10-24

    Conic Programming (CP)问题包含Linear Programming, Second Order Conic Programming 和 Semidefinite Programming. 转化原问题为对偶问题的方法是:

    第一,转化原问题为标准CP问题:
    1. 确认变量。
    2. 目标函数为变量的线性函数(略去常数项)。
    3. 区分两类限制:式子限制Ax?b,符号限制x?0(即使变量free,也要显示的写出来)。

    第二,对于所有式子限制,写出对偶变量。一个等式(不等式)对应一个变量,一个矢量式子对应于一个矢量变量。

    第三,按照式子限制的常数项(b),写出对偶问题的目标函数。

    第四,对于所有式子限制,写出相应对偶变量的符号限制(min问题不变),区间需要取对偶。

    第五,对于每一个原问题变量,按照其符号限制,写出对偶问题的式子限制(用到A和c,min问题变号)。

    (记忆规则:对于符号限制,大同小异。)

    (forall 出现在 式子限制: 多个对偶变量。最对偶问题中,目标中求和,限制中求和。
    出现在 符号限制: 多个对偶式子限制。)

    分享到: