Bilevel cutting-plane algorithm for cardinality-constrained mean-CVaR portfolio optimization

Abstract

This paper studies mean-risk portfolio optimization models using the conditional value-at-risk (CVaR) as a risk measure. We also employ a cardinality constraint for limiting the number of invested assets. Solving such a cardinality-constrained mean-CVaR model is computationally challenging for two main reasons. First, this model is formulated as a mixed-integer optimization (MIO) problem because of the cardinality constraint, so solving it exactly is very hard when the number of investable assets is large. Second, the problem size depends on the number of asset return scenarios, and the computational efficiency decreases when the number of scenarios is large. To overcome these challenges, we propose a high-performance algorithm named the bilevel cutting-plane algorithm for exactly solving the cardinality-constrained mean-CVaR portfolio optimization problem. We begin by reformulating the problem as a bilevel optimization problem and then develop a cutting-plane algorithm for solving the upper-level problem. To speed up computations for cut generation, we apply to the lower-level problem another cutting-plane algorithm for efficiently minimizing CVaR with a large number of scenarios. Moreover, we prove the convergence properties of our bilevel cutting-plane algorithm. Numerical experiments demonstrate that, compared with other MIO approaches, our algorithm can provide optimal solutions to large problem instances faster.

Appendices

Appendix A: Proof of Theorem 1

Problem (10) is formulated as follows:

$$\begin{aligned} f({\varvec{z}})=\mathop {\hbox {minimize}}\limits _{a,{\varvec{q}},v,{\varvec{x}}}&\quad \frac{1}{2\gamma }{\varvec{x}}^\top {\varvec{x}} + a + v \end{aligned}$$

(35a)

$$\begin{aligned} {{\,\mathrm{subject~to}\,}}&\quad v\ge \frac{1}{1-\beta }\sum _{s \in {\mathcal {S}}}p_s q_s, \end{aligned}$$

(35b)

$$\begin{aligned}&\quad q_s \ge -({\varvec{r}}^{(s)})^\top {\varvec{Z}}{\varvec{x}} - a \quad (\forall s\in {\mathcal {S}}), \end{aligned}$$

(35c)

$$\begin{aligned}&\quad {\varvec{A}} {\varvec{Z}} {\varvec{x}} \le {\varvec{b}}, \end{aligned}$$

(35d)

$$\begin{aligned}&\quad {\varvec{1}}^\top {\varvec{Z}} {\varvec{x}} = 1, \end{aligned}$$

(35e)

$$\begin{aligned}&\quad {\varvec{Z}} {\varvec{x}} \ge {\varvec{0}}, \end{aligned}$$

(35f)

$$\begin{aligned}&\quad {\varvec{q}}\ge {\varvec{0}}. \end{aligned}$$

(35g)

The Lagrange function of Problem (35) is expressed as

$$\begin{aligned} \begin{aligned} {\mathcal {L}}(a,{\varvec{q}},v,{\varvec{x}}, \eta ,{\varvec{\alpha }}, {\varvec{\zeta }}, \lambda ,{\varvec{\pi }},{\varvec{\theta }})&:= \frac{1}{2\gamma }{\varvec{x}}^\top {\varvec{x}} + a + v - \eta \left( v-\frac{1}{1-\beta }\sum _{s \in {\mathcal {S}}}p_sq_s\right) \\&\qquad -\sum _{ s\in {\mathcal {S}}}\alpha _{s}\left( q_s +({\varvec{r}}^{(s)})^\top {\varvec{Z}} {\varvec{x}} +a\right) \\&\qquad -{\varvec{\zeta }}^\top \left( {\varvec{b}} - {\varvec{A}}{\varvec{Z}}{\varvec{x}}\right) - \lambda \left( {\varvec{1}}^\top {\varvec{Z}}{\varvec{x}}-1\right) -{\varvec{\pi }}^\top {\varvec{Z}}{\varvec{x}}- {\varvec{\theta }}^\top {\varvec{q}}, \end{aligned} \end{aligned}$$

where $\eta \ge 0,~{\varvec{\alpha }} := (\alpha _{s})_{s\in {\mathcal {S}}} \ge {\varvec{0}},~{\varvec{\zeta }} \ge {\varvec{0}},~\lambda \in {\mathbb {R}},~{\varvec{\pi }} \ge {\varvec{0}},~\mathrm {and}~{\varvec{\theta }} \ge {\varvec{0}}$ are Lagrange multipliers. Then, the Lagrange dual problem of Problem (35) is posed as:

$$\begin{aligned} \max _{\begin{array}{c} \eta \ge 0,~{\varvec{\alpha }}\ge {\varvec{0}},~{\varvec{\zeta }}\ge {\varvec{0}},\\ \lambda \in {\mathbb {R}},~{\varvec{\pi }} \ge {\varvec{0}},~{\varvec{\theta }} \ge {\varvec{0}} \end{array}}~\min _{\begin{array}{c} a\in {\mathbb {R}},~{\varvec{q}} \in {\mathbb {R}}^S,\\ v\in {\mathbb {R}},~{\varvec{x}}\in {\mathbb {R}}^N \end{array}}~{\mathcal {L}}(a,{\varvec{q}},v,{\varvec{x}}, \eta ,{\varvec{\alpha }}, {\varvec{\zeta }}, \lambda ,{\varvec{\pi }},{\varvec{\theta }}). \end{aligned}$$

(36)

Recall that Problem (35) is feasible. Also, the objective function is proper convex, and all the constraints are linear in Problem (35). Then, the strong duality holds; see, for example, Section 5.2.3 in Boyd and Vandenberghe [17]. As a result, $f({\varvec{z}})$ is equal to the optimal objective value of Problem (36). Now, let us focus on the inner minimization problem:

$$\begin{aligned} \min _{\begin{array}{c} a\in {\mathbb {R}},~{\varvec{q}} \in {\mathbb {R}}^S,\\ v\in {\mathbb {R}},~{\varvec{x}}\in {\mathbb {R}}^N \end{array}}~{\mathcal {L}}(a,{\varvec{q}},v,{\varvec{x}}, \eta ,{\varvec{\alpha }}, {\varvec{\zeta }}, \lambda ,{\varvec{\pi }},{\varvec{\theta }}). \end{aligned}$$

(37)

Note that Problem (37) is an unconstrained convex quadratic optimization problem and its objective function is linear in $(a, {\varvec{q}}, v)$. Because Problem (37) must be bounded, the Lagrange multipliers are required to satisfy the following conditions:

$$\begin{aligned} \nabla _{a}{\mathcal {L}}&= 1 - \sum _{s\in {\mathcal {S}}}\alpha _s = 0, \end{aligned}$$

(38)

$$\begin{aligned} \nabla _{{\varvec{q}}}{\mathcal {L}}&= \frac{\eta }{1-\beta }{\varvec{p}} - {\varvec{\alpha }}-{\varvec{\theta }} = 0, \end{aligned}$$

(39)

$$\begin{aligned} \nabla _{v}{\mathcal {L}}&=1 -\eta = 0. \end{aligned}$$

(40)

Also, the following optimality condition should be satisfied:

$$\begin{aligned} \nabla _{{\varvec{x}}}{\mathcal {L}}&= \frac{1}{\gamma } {\varvec{x}} - {\varvec{Z}} \left( \sum _{s\in {\mathcal {S}}}\alpha _{s}{\varvec{r}}^{(s)} - {\varvec{A}}^{\top } {\varvec{\zeta }} + \lambda {\varvec{1}} + {\varvec{\pi }} \right) = {\varvec{0}}. \end{aligned}$$

(41)

According to Eqs. (38), (39), (40), and (41), the optimal objective value of Problem (37) is calculated as

$$\begin{aligned} -\frac{\gamma }{2} {\varvec{\omega }}^\top {\varvec{Z}}^2 {\varvec{\omega }} - {\varvec{b}}^\top {\varvec{\zeta }} + \lambda , \end{aligned}$$

where ${\varvec{\omega }}\in {\mathbb {R}}^N$ is a vector of auxiliary decision variables satisfying

$$\begin{aligned} {\varvec{\omega }} = \sum _{s\in {\mathcal {S}}}\alpha _{s}{\varvec{r}}^{(s)} - {\varvec{A}}^\top {\varvec{\zeta }} + \lambda {\varvec{1}} + {\varvec{\pi }}. \end{aligned}$$

Because ${\varvec{z}} \in \{0,1\}^N$, it holds that ${\varvec{\omega }}^\top {\varvec{Z}}^2{\varvec{\omega }} = {\varvec{z}}^\top ({\varvec{\omega }}\circ {\varvec{\omega }})$. Therefore, the Lagrange dual problem (36) is formulated as follows:

$$\begin{aligned} f({\varvec{z}})=&\mathop {\hbox {maximize}}\limits _{{\varvec{\alpha }}, {\varvec{\zeta }}, \lambda , {\varvec{\omega }}} \quad -\frac{\gamma }{2} {\varvec{z}}^\top ({\varvec{\omega }}\circ {\varvec{\omega }}) - {\varvec{b}}^\top {\varvec{\zeta }} + \lambda \\&\!\!\!\quad {{\,\mathrm{subject~to}\,}}\quad {\varvec{\omega }} \ge \sum _{s\in {\mathcal {S}}}\alpha _{s}{\varvec{r}}^{(s)} - {\varvec{A}}^\top {\varvec{\zeta }} + \lambda {\varvec{1}}, \\&\quad \quad \quad \quad \quad \quad \quad \quad \sum _{s\in {\mathcal {S}}}\alpha _s = 1, \\&\quad \quad \quad \quad \qquad \quad \quad \alpha _s \le \frac{p_s}{1-\beta } \quad (\forall s\in {\mathcal {S}}), \\&\quad \quad \quad \quad \qquad \quad \quad {\varvec{\alpha }} \ge {\varvec{0}},~{\varvec{\zeta }}\ge {\varvec{0}}, \end{aligned}$$

where we substitute $\eta =1$, and eliminate the nonnegative variables ${\varvec{\pi }}$ and ${\varvec{\theta }}$. $\square$

Table 6 Numerical results for the four datasets (port1, ind49, sbm100, and port5) with $(S,\gamma )=(10^5,10/\sqrt{N})$ for $k\in \{5,10,15\}$

Fig. 3

Results for port1 with $(S,k)=(10^5,10)$ for $\gamma \in \{10^{0.2i}/\sqrt{N}\mid i=0,1,\dots ,20\}$

Fig. 4

Results for ind49 with $(S,k)=(10^5,10)$ for $\gamma \in \{10^{0.2i}/\sqrt{N}\mid i=0,1,\dots ,20\}$

Fig. 5

Results for sbm100 with $(S,k)=(10^5,10)$ for $\gamma \in \{10^{0.2i}/\sqrt{N}\mid i=0,1,\dots ,20\}$

Fig. 6

Results for port5 with $(S,k)=(10^5,10)$ for $\gamma \in \{10^{0.2i}/\sqrt{N}\mid i=0,1,\dots ,20\}$

Appendix B: Proof of Theorem 2

Problem (26) is formulated as follows:

$$\begin{aligned} f_{{\mathcal {K}}}({\varvec{z}})=\mathop {\hbox {minimize}}\limits _{a, v,{\varvec{x}}}&\quad \frac{1}{2\gamma }{\varvec{x}}^\top {\varvec{x}} + a + v \end{aligned}$$

(42a)

$$\begin{aligned} {{\,\mathrm{subject~to}\,}}&\quad v \ge \frac{1}{1-\beta }\sum _{s \in {\mathcal {J}}}p_s( -({\varvec{r}}^{(s)})^\top {\varvec{Z}}{\varvec{x}} - a) \quad (\forall {\mathcal {J}} \in {\mathcal {K}}), \end{aligned}$$

(42b)

$$\begin{aligned}&\quad v\ge 0, \end{aligned}$$

(42c)

$$\begin{aligned}&\quad {\varvec{A}} {\varvec{Z}} {\varvec{x}} \le {\varvec{b}}, \end{aligned}$$

(42d)

$$\begin{aligned}&\quad {\varvec{1}}^\top {\varvec{Z}} {\varvec{x}} = 1, \end{aligned}$$

(42e)

$$\begin{aligned}&\quad {\varvec{Z}} {\varvec{x}} \ge {\varvec{0}}. \end{aligned}$$

(42f)

The Lagrange function of Problem (42) is expressed as

$$\begin{aligned} \begin{aligned} {\mathcal {L}}(a, v, {\varvec{x}}, {\varvec{\alpha }},\xi ,{\varvec{\zeta }},\lambda ,{\varvec{\pi }})&:= \frac{1}{2\gamma }{\varvec{x}}^\top {\varvec{x}} + a + v-\sum _{ {\mathcal {J}}\in {\mathcal {K}}}\alpha _{{\mathcal {J}}}\left( v + \frac{1}{1-\beta }\sum _{s\in {\mathcal {J}}}p_s\left( ({\varvec{r}}^{(s)})^\top {\varvec{Z}} {\varvec{x}} +a\right) \right) \\&\qquad -\xi v-{\varvec{\zeta }}^\top \left( {\varvec{b}} - {\varvec{A}}{\varvec{Z}}{\varvec{x}}\right) - \lambda \left( {\varvec{1}}^\top {\varvec{Z}}{\varvec{x}}-1\right) -{\varvec{\pi }}^\top {\varvec{Z}}{\varvec{x}}, \end{aligned} \end{aligned}$$

where ${\varvec{\alpha }} := (\alpha _{{\mathcal {J}}})_{{\mathcal {J}}\in {\mathcal {K}}} \ge {\varvec{0}},~\xi \ge 0,~ {\varvec{\zeta }}\ge {\varvec{0}},~\lambda \in {\mathbb {R}},~\mathrm {and}~{\varvec{\pi }} \ge {\varvec{0}}$ are Lagrange multipliers. Recall that Problem (42) is feasible. Then, the strong duality holds as well as the proof of Theorem 1, and $f_{{\mathcal {K}}}({\varvec{z}})$ is equal to the optimal objective value of the following Lagrange dual problem:

$$\begin{aligned} \max _{\begin{array}{c} {\varvec{\alpha }}\ge {\varvec{0}},~\xi \ge 0,~{\varvec{\zeta }}\ge {\varvec{0}},\\ \lambda \in {\mathbb {R}},~{\varvec{\pi }} \ge {\varvec{0}} \end{array}}~\min _{a\in {\mathbb {R}},~v\in {\mathbb {R}},~{\varvec{x}}\in {\mathbb {R}}^N} \quad {\mathcal {L}}(a, v, {\varvec{x}}, {\varvec{\alpha }}, \xi ,{\varvec{\zeta }},\lambda ,{\varvec{\pi }}). \end{aligned}$$

(43)

Now, let us consider the inner minimization problem:

$$\begin{aligned} \min _{a\in {\mathbb {R}},~v\in {\mathbb {R}},~{\varvec{x}}\in {\mathbb {R}}^N} \quad {\mathcal {L}}(a, v, {\varvec{x}}, {\varvec{\alpha }}, \xi ,{\varvec{\zeta }},\lambda ,{\varvec{\pi }}). \end{aligned}$$

(44)

Similarly to the proof of Theorem 1, the following conditions must be satisfied:

$$\begin{aligned}&\nabla _{a}{\mathcal {L}} = 1 - \frac{1}{1-\beta }\sum _{{\mathcal {J}}\in {\mathcal {K}}}\alpha _{{\mathcal {J}}} \sum _{s\in {\mathcal {J}}} p_s = 0, \end{aligned}$$

(45)

$$\begin{aligned}&\nabla _{v}{\mathcal {L}} =1 -\sum _{{\mathcal {J}}\in {\mathcal {K}}}\alpha _{{\mathcal {J}}}-\xi = 0, \end{aligned}$$

(46)

$$\begin{aligned}&\nabla _{{\varvec{x}}}{\mathcal {L}}= \frac{1}{\gamma } {\varvec{x}} - {\varvec{Z}} \left( \frac{1}{1-\beta }\sum _{{\mathcal {J}}\in {\mathcal {K}}}\alpha _{{\mathcal {J}}} \sum _{s\in {\mathcal {J}}} p_s {\varvec{r}}^{(s)} - {\varvec{A}}^\top {\varvec{\zeta }} + \lambda {\varvec{1}} + {\varvec{\pi }} \right) = {\varvec{0}}. \end{aligned}$$

(47)

According to Eqs. (45), (46), and (47), the optimal objective value of Problem (44) is calculated as

$$\begin{aligned} -\frac{\gamma }{2} {\varvec{\omega }}^\top {\varvec{Z}}^2 {\varvec{\omega }} - {\varvec{b}}^\top {\varvec{\zeta }} + \lambda , \end{aligned}$$

where ${\varvec{\omega }}\in {\mathbb {R}}^N$ is a vector of auxiliary decision variables satisfying

$$\begin{aligned} {\varvec{\omega }} = \frac{1}{1-\beta }\sum _{{\mathcal {J}}\in {\mathcal {K}}}\alpha _{{\mathcal {J}}} \sum _{s\in {\mathcal {J}}} p_s {\varvec{r}}^{(s)} - {\varvec{A}}^\top {\varvec{\zeta }}+ \lambda {\varvec{1}} + {\varvec{\pi }}. \end{aligned}$$

Because ${\varvec{z}} \in \{0,1\}^N$, it holds that ${\varvec{\omega }}^\top {\varvec{Z}}^2{\varvec{\omega }} = {\varvec{z}}^\top ({\varvec{\omega }}\circ {\varvec{\omega }})$. Therefore, the Lagrange dual problem (43) is formulated as follows:

$$\begin{aligned} f_{{\mathcal {K}}}({\varvec{z}})=\mathop {\hbox {maximize}}\limits _{{\varvec{\alpha }}, {\varvec{\zeta }}, \lambda , {\varvec{\omega }}}&\quad -\frac{\gamma }{2} {\varvec{z}}^\top ({\varvec{\omega }}\circ {\varvec{\omega }}) - {\varvec{b}}^\top {\varvec{\zeta }} + \lambda \\ {{\,\mathrm{subject~to}\,}}&\quad {\varvec{\omega }} \ge \frac{1}{1-\beta }\sum _{{\mathcal {J}} \in {\mathcal {K}}} \alpha _{{\mathcal {J}}} \sum _{s\in {\mathcal {J}}}p_s {\varvec{r}}^{(s)} -{\varvec{A}}^\top {\varvec{\zeta }} +\lambda {\varvec{1}}, \\&\quad \sum _{{\mathcal {J}}\in {\mathcal {K}}}\alpha _{{\mathcal {J}}} \le 1, \\&\quad \sum _{{\mathcal {J}}\in {\mathcal {K}}}\alpha _{{\mathcal {J}}} \sum _{s\in {\mathcal {J}}}p_s = 1-\beta , \\&\quad {\varvec{\alpha }} \ge {\varvec{0}},~{\varvec{\zeta }}\ge {\varvec{0}}, \end{aligned}$$

where we eliminate the nonnegative variables $\xi$ and ${\varvec{\pi }}$. $\square$

Fig. 7

Objective value (34) for the three datasets (port1, ind49, and sbm100) with $(S,k)=(10^5,10)$ for $\gamma \in \{10^{0.2i}/\sqrt{N}\mid i=0,1,\dots ,20\}$

Appendix C: Detailed experimental results of sensitivity analysis

Table 6 gives the numerical results for the four datasets (ind49, sbm100, port1, and port5) with the cardinality parameter $k \in \{5, 10, 15\}$. Here, we set $\gamma =10/\sqrt{N}$ for the $\ell _2$-regularization term and $S=10^5$ as the number of scenarios. Table 6 shows that BCP and BCPc were almost always faster than the other methods when $k\in \{10, 15\}$. Also, BCP and BCPc tended to be faster with larger k. In the case of the port5 dataset, for example, BCP solved the problem with $k=15$ in 73.7 s, whereas it failed to complete the computation within 3600 s with $k=5$.

Figures 3, 4, 5, and 6 show the numerical results for the four datasets (ind49, sbm100, port1, and port5) with the regularization parameter $\gamma \in \{10^{0.2i}/\sqrt{N}\mid i=0,1,\dots ,20\}$. Here, we set $k=10$ for the cardinality constraint and $S=10^5$ as the number of scenarios. We can see from Figs. 3, 4, 5, and 6 that the performances of BCP and BCPc were not greatly affected by $\gamma$, and they were generally faster than the other methods when they completed the computations within 3600 s. In addition, BCP and BCPc tended to be faster with smaller $\gamma$ for each dataset.

Figure 7 shows “Reg$+$CVaR” and “CVaR” defined in Eq. (34) for the three datasets (ind49, sbm100, and port1) with the regularization parameter $\gamma \in \{10^{0.2i}/\sqrt{N}\mid i=0,1,\dots ,20\}$. For each dataset, the objective value (i.e., “Reg$+$CVaR”) was close to CVaR when $\gamma \ge 10^2/\sqrt{N}$, and CVaR almost converged to its minimum value when $\gamma \ge 10/\sqrt{N}$.