【OR】ADMM&Risk Parity Portfilio Model

ADMM(交替方向法)

问题 $(P)$
$\min f(x)+g(y)\\ s.t.\quad Ax+By=d$
该问题具有一定的可分离性.
建立增广拉格朗日函数
$L_A(x, y, \lambda, \sigma)=f(x)+g(y)+\lambda^T(Ax+By-d)+\sigma\lVert Ax+By-d \rVert_2^2$
step 0: 给定初始点 $x^0, \lambda^0, \sigma_0, \varepsilon>0, k=0$
step 1: 计算 $y^{k+1}=\argmin_y L_A(x^k, y, \lambda^k, \sigma_k)， x^{k+1}=\argmin_x L_A(x, y^{k+1}, \lambda^k, \sigma_k)$.
step 2: 如果 $\lVert Ax^{k+1}+By^{k+1}-d\rVert\leq \varepsilon$，算法终止
step 3: 更新乘子 $\lambda^{k+1}=\lambda^k+2\sigma_k(Ax^{k+1}+By^{k+1}-d)$; 更新罚参数 $\sigma_{k+1}=f(\sigma_k)$.

收敛性

(1).设 $f(x), g(y)$为凸函数， $A$或者 $B$矩阵为行满秩. 则 $\{(x^k, y^k)\}$满足 $f(x^k)+g(y^k)\to v(P)$.
(2).设 $\sum\lVert\lambda^{k+1}-\lambda^k\rVert_2^2<\infty$，则 $\{(x^k, y^k)\}$收敛至KKT点.

案例

问题 $(P)$为
$\min f(x)+g(y)\\ s.t.\begin{cases} h_i(x)=0, i=1, \dots, m\\ Ax+By=d\\ w_i(y)=0, i=1, \dots, l \end{cases}$
例：均值-方差模型
$\min x^TQx\\ s.t.\begin{cases} Ax=d\\ a_iy_i\leq x_i\leq b_iy_i\\ y_i\in\{0, 1\} \end{cases}$
其中， $x_i\in\{0\}\cup [a_i, b_i]$为半连续变量. 整数规划问题可以使用分支定界法求解，通过转换问题使用ADMM方法求解.
$\min x^TQx\\ s.t.\begin{cases} Ax=d\\ x=y\\ y_i\in\{0\}\cup[a_i, b_i] \end{cases}$
构造 $L_A(x, y, \lambda, \sigma)=x^TQx+\lambda^T(x-y)+\sigma\lVert x-y\rVert_2^2$
拆分问题
(1) $y^{k+1}: \min\limits_{y_i\in \{0\}\cup[a_i, b_i]}L_A(x^k, y, \lambda^k, \sigma_k)=\sigma_k\sum_{i=1}^n(y_i-v_i)^2+c_k$
(2) $x^{k+1}: \min\limits_{Ax=d} L_A(x, y^{k+1}, \lambda^k, \sigma_k)$ 是一个QP问题.

对(1)提取出子问题
$\min \sum(y_i-v_i)^2 \\ s.t.\quad y_i\in\{0\}\cup[a_i, b_i]$

risk parity portfolio model

设市场有 $n$个资产，第 $i$个资产收益为 $R_i$(随机变量)，记 $R=(R_1, R_2, \dots, R_n)^T，x=(x_1, x_2, \dots, x_n)^T$，组合收益率为
$R(x)=\sum_{i=1}^nR_ix_i=R^Tx$
期望收益为
$\mathbb{E}[R(x)]=\mathbb{E}[\sum R_ix_i]=\sum_{i=1}^n\mu_ix_i$
组合方差为
$\mathbb{V}[R(x)]=\mathbb{V}[\sum R_ix_i]=\sum_{i=1}^n\sum_{j=1}^ncov(R_i, R_j)x_ix_j=\sum_{i=1}^n\sum_{j=1}^n\sigma_{ij}x_ix_j=x^TQx$
其中 $Q=(\sigma_{ij})$协方差矩阵，半正定矩阵，如果不存在某资产收益率可以被其他资产线性表示，则 $Q$为正定矩阵.
MV模型为
$\min x^TQx\\ s.t.\begin{cases} \mu^Tx\geq \rho\\ e^Tx=1 \end{cases}$
需要解决如下两个问题
1.如何表示单个资产所承担的风险
2.如何建模
分析：
方法1
第1个资产的风险： $\sigma_{11}x_1^2+\sum\limits_{j\neq 1}\sigma_{1j}x_1x_j$
推出第 $i$个资产的风险贡献为
$\sigma_{ii}x_i^2+\sum_{j\neq i}\sigma_{ij}x_ix_j=x^TQ_jx$
其中 $Q_1+Q_2+\dots+Q_n=Q$
方法2
计算 $\sqrt{\sum\sum\sigma_{ij}x_ix_j}$作为总风险
定义边际风险(marginal risk)
$\frac{\partial}{\partial x_i}\sqrt{x^TQx}=\frac{1}{2}\frac{1}{\sqrt{x^TQx}}(2\sigma_{ii}x_i+2\sum_{j\neq i}\sigma_{ij}x_j)=\frac{1}{\sqrt{x^TQx}}(\sigma_{ii}x_i+\sum_{j\neq i}\sigma_{ij}x_j)$
第 $i$个资产的风险构成为：
$x_i*\frac{1}{\sqrt{x^TQx}}(\sigma_{ii}x_i+\sum_{j\neq i}\sigma_{ij}x_j)=\frac{1}{\sqrt{x^TQx}}(\sigma_{ii}x_i^2+\sum_{j\neq i}\sigma_{ij}x_ix_j)$
建模：
约束法：
风险贡献上限约束： $x^TQ_ix\leq \alpha, i=1, \dots, n$
等风险贡献约束： $x^TQ_ix=x^TQ_jx, i\neq j$ 或者 $x^TQ_ix=z, i=1,\dots, n$.
目标法：
风险均衡目标： $\min\sum\limits_{i\neq j}|x^TQ_ix-x^TQ_jx|$或者 $\min\sum\limits_{i=1}^n(x^TQ_ix-z)^2$

设置原问题 $(P)$为
$\min\sum_{i=1}^n(x^TQ_ix-z)^2\\ s.t.\quad Ax\leq d$
可以使用ADMM算法求解，引入复制变量
$\min \sum(x^TQ_iy-z)^2\\ s.t. \begin{cases} x=y\\ Ax\leq d \end{cases}$
得到增广拉格朗日函数
$L_A(x, y, z, \lambda, \sigma)=\sum(x^TQ_iy-z)^2+\lambda^T(x-y)+\sigma\lVert x-y\rVert_2^2$
固定点 $(x, z)=(x^k, z^k), \lambda^k, \sigma_k$，求解关于 $y$的QP问题
$y^{k+1}: \min_y L_A(x^k, y, z^k, \lambda^k, \sigma_k)$
固定 $y=y^{k+1}$
求解关于 $(x，z)$的问题
$(x^{k+1}, z^{k+1}): \min_{Ax\leq d} L_A(x, y^{k+1}, z, \lambda^k, \sigma_k)$
判断 $\lVert x-y \rVert\leq \varepsilon$,如果成立则算法终止
否则，更新参数 $\lambda^{k+1}=\lambda^k+2\sigma_k(x^{k+1}-y^{k+1})$和 $\sigma^{k+1}$.

参考资料

ADMM 上海财经大学 崔雪婷