SOCP Algorithm

SOCP Algorithm

One shortcoming of the Markowitz model is that it considers separate uncertainty sets for the expected return vector \(\boldsymbol\mu\) and for the covariance matrix \(\boldsymbol \Sigma\). As a result, the probability measure with the minimized mean is different from the probability measure with the maximized second moment. In general, this is not the case. Under such circumstances,  SOCP algorithm is provided.

Scholars propose a robust portfolio optimization and selection model using a conic programming approach which can be applied to the mean-variance framework. Second-order cone programming (SOCP) minimizes or maximizes a linear function problem at the intersection of an affine space and a Cartesian product of a finite number of second-order cones. 

Math Forms

A standard second-order cone programming problem can be expressed as the following forms:

\(min \quad c_1^T x_1 + c_2^T x_2 +\cdots + c_r^T x_r\) 

\(s.t. \quad A_1 x_1+A_2 x_2 + \cdots + A_r x_r  \qquad x_i \in \mathcal\kappa^{n_i} \quad i=1,2,\cdots,r\)

Note that \(A_i \in \mathcal{R}^{m \times n_i}， c_i \in \mathcal{R}^{n_i} , b \in \mathcal{R}^m\) are known data, and \(n_1 + n_2 + \cdots +n_r=n,  x_i \in \mathcal\kappa^{n_i}\) are decision variables. \(\mathcal\kappa^{n_i}\)latex is n-dimensional second-order core(SOC) with definitions below：

\(\mathcal\kappa^{n_i}=\{(x_{i1};x_{i2}|x_{x1} \in \mathcal{R}, x_{i2}\in \mathcal{R}^{n_1-1}) |x_{i1} \geq \parallel x_{i2} \parallel \} \)

The expected return lies in the confidence region represented by the ellipsoid \((\hat{x_\varepsilon} – \hat{x_t})^T {\Sigma_\varepsilon}^{-1} (\hat{x_\varepsilon} – \hat{x_t}) \leq k^2 \), generated by estimated expected returns \(\hat{x_\varepsilon\) and covariance matrix \(\Sigma_\varepsilon\) of the estimates of expected returns with probability \(\eta\). And \(k^2 ={\chi_n}^2 (1- \eta) ,{\chi_n}^2\) is the inverse cumulative distribution function of the chi-squared distribution with n degrees of freedom. For a fixed portfolio, the target is:

\(\underset{\hat{x_\varepsilon} – \hat{x_t}}{max} {(\hat{x_\varepsilon} – \hat{x_t})^T \hat{\omega}} \)

\((\hat{x_\varepsilon} – \hat{x_t})^T {\Sigma_\varepsilon}^{-1} (\hat{x_\varepsilon} – \hat{x_t}) \leq k^2 \)

By constructing the Lagrangian of the above formula, it is straightforward to obtain \(\hat{x_t}^T \hat{\omega}=\hat{x_\varepsilon}^T \hat{\omega}-k\parallel {\Sigma_\varepsilon}^{1/2}\hat{\omega} \parallel\). The problem now becomes the robust portfolio selection problem given below:

\(\underset{\omega \in \mathcal{R}^n }{max} {\hat{x_\varepsilon}^T} \omega-k\parallel {\Sigma_\varepsilon}^{1/2}\omega \parallel \)

\(s.t. \omega^T \Sigma \omega \leq \gamma^2\)

\(\omega \in \overline{W} =\{\omega \in \mathcal{R}^n|\sum_{i=1}^n\omega_i=1,\omega\geq 0\}\)

Furthermore, this problem can be straightforwardly written as a second-order cone programming (SOCP) problem:

\(\underset{\omega \in \mathcal{R}^n}{max} \quad\hat{x_\varepsilon}^T\omega-kt\)

\begin{equation}
s.t. \left\{
\begin{array}{**rcl**}
\omega &\in &W \\
\gamma &\geq& \parallel \Sigma^{1/2} \omega \parallel \\
t &\geq& \parallel {\Sigma_\varepsilon}^{1/2} \omega \parallel 
\end{array}
\right.
\end{equation}

Configuration of parameters

For estimation of returns:

• Sample Mean

• Equal Mean

• Linear Shrinkage

For estimation of covariance:

• Sample Covariance

• Equal Correlation

• Linear Shrinkage

• Nonlinear Shrinkage

Optional Constraints

• Position Limits

• Market Impact

• Block List

• Max Loan

References

[1] 戴志锋；文凤华；李董辉，鲁棒均值一半绝对偏差投资组合优化模型, 系统工程，2012, Vol.30(10), pp.28-35

[2] Lobo M S，Boyd S．The worst—case risk of a portfolio，Technical Report[z]． 2000

[3] Tutuncu R H，Koenig M．Robust asset allocation [J]．Annals of Operations Research，2004，132：157~187

[4] Goldfarb D，Iyengar G．Robust portfolio selection problems[J]．Mathematics of Operations Research，2003，28：1～ 38．

[5] 房亮. 二阶锥规划和二阶锥互补问题的算法研究[D].上海交通大学,2010.