二阶锥规划的对偶形式推导

二阶锥规划(Second Order Cone Program (SOCP))通常出现在包含电网dist-flow潮流模型中，应用面非常的广泛。如若考虑电网中的随机因素（例如：负荷波动、可再生能源出力波动），则不可避免的需要用鲁棒或者随机模型考虑其随机因素从而进行风险对冲。又因为鲁棒模型中需要对内层的场景问题通过对偶转化为单层优化，鲁棒模型中二阶锥约束的对偶推导尤为重要。

先说结论：二阶锥规划问题的对偶形式

考虑如下SOCP：

其中，其对偶问题如下所示：

变量为： ，参数为：, 和 .

使用拉格朗日函数法推导互补松弛条件

首先，为了方便问题描述，将SOCP重写成如下形式：

则根据三个约束构造其拉格朗日函数，并按照以及无关项合并同类项。

最终如下：

$$
\begin{aligned}
& L(x, y, t, \lambda, \nu, \mu) \
&=c^T x+\sum_{i=1}^m \lambda_i\left(\left|y_i\right|2-t_i\right)+\sum{i=1}^m \nu_i^T\left(y_i-A_i x-b_i\right)+\sum_{i=1}^m \mu_i\left(t_i-c_i^T x-d_i\right) \
&=\left(c-\sum_{i=1}^m A_i^T \nu_i-\sum_{i=1}^m \mu_i c_i\right)^T x+\sum_{i=1}^m\left(\lambda_i\left|y_i\right|2+\nu_i^T y_i\right)+\sum{i=1}^m\left(-\lambda_i+\mu_i\right) t_i \
&-\sum_{i=1}^n\left(b_i^T \nu_i+d_i \mu_i\right) .
\end{aligned}
$$

项有界的条件

为了保证拉格朗日对偶函数有界，现找出分别关于求极值时候有界的条件。考虑：

由于x无约束，所以该项若有界，则系数必须为0，即为：

项有界的条件

有界则要求即可。

项有界的条件

先说结论

首先由于是二阶锥问题中不等式约束的对偶变量，所以非负，所以也是非负，所以必须是小于零的数，否则y趋于无穷对偶无界，原问题无解。

首先假设，则有：

所以

即该项有界：

在进行反证，如果假设，并且其中非负，在构造其中（由于符号相反，在前面说过了），

最后一项由于假设是一个恒小于零的数，因此:

所以这一项有界的结论得证。

推导对偶形式

本节根据上面的结论推导对偶形式

$$
\begin{array}{ll}
\max {\lambda, \nu, \mu}\inf {y_i,x_i,t_i}&L(x, y, t, \lambda, \nu, \mu) =0+0+0-\sum{i=1}^n\left(b_i^T \nu_i+d_i \mu_i\right)\
\text { subject to } &\sum{i=1}^m\left(A_i^T \nu_i+\mu_i c_i\right)=c,\forall i,\
&\lambda_i = \mu_i, \forall i,\
&\left|\nu_i\right|_2 \leq \lambda_i ,\forall i,
\end{array}
$$

约掉里面的，并且将换元为

$$
\begin{array}{ll}
\max {\nu, \mu}&L(\nu, \mu) =\sum{i=1}^n\left(b_i^T \nu_i+d_i \mu_i\right)\
\text { subject to } &\sum_{i=1}^m\left(A_i^T \nu_i+\mu_i c_i\right)+c=0,\forall i,\
&\left|\nu_i\right|_2 \leq \mu_i ,\forall i,
\end{array}
$$

与文章开头的形式一样。

想法

这种对偶打眼一看是肯定想不明白的，细致的推到一遍对理解二阶锥约束很有帮助。有意思的一点是变量的互补松弛条件中让和等价了，相当与二阶锥约束RHS线性约束的对偶与二阶锥约束的对偶变量其实是等价的，很有意思。

参考

[1] https://www.di.ens.fr/~aspremon/PDF/MVA/Duality.pdf

[2] Kong (https://math.stackexchange.com/users/387172/kong), Dual of a Second Order Cone Program (SOCP), URL (version: 2018-04-15): https://math.stackexchange.com/q/2738165