# Autonomous Sparse Mean-CVaR Portfolio Optimization

Yizun Lin  Yangyu Zhang  Zhao-Rong Lai  Cheng Li

###### Abstract

The $\ell_{0}$-constrained mean-CVaR model poses a significant challenge due
to its NP-hard nature, typically tackled through combinatorial methods
characterized by high computational demands. From a markedly different
perspective, we propose an innovative autonomous sparse mean-CVaR portfolio
model, capable of approximating the original $\ell_{0}$-constrained mean-CVaR
model with arbitrary accuracy. The core idea is to convert the $\ell_{0}$
constraint into an indicator function and subsequently handle it through a
tailed approximation. We then propose a proximal alternating linearized
minimization algorithm, coupled with a nested fixed-point proximity algorithm
(both convergent), to iteratively solve the model. Autonomy in sparsity refers
to retaining a significant portion of assets within the selected asset pool
during adjustments in pool size. Consequently, our framework offers a
theoretically guaranteed approximation of the $\ell_{0}$-constrained mean-CVaR
model, improving computational efficiency while providing a robust asset
selection scheme.

Mean-CVaR, $\ell_{0}$ constraint, tailed approximation, proximal alternating
linearized minimization

##  1 Introduction

Value-at-risk (VaR, Jorion 1997) is a widely-used downside-risk metric in
finance that assesses the extreme percentage loss in a disadvantageous
situation. Since it fails to satisfy the subadditivity property (Artzner et
al., 1999), it is improved to its tail statistic named conditional value-at-
risk (CVaR, Rockafellar & Uryasev 2000). CVaR not only has the good
theoretical property of coherence (Artzner et al., 1999; Gotoh & Takeda,
2011), but also accords with dual stochastic dominance (Ogryczak &
Ruszczyński, 2002). Moreover, CVaR is more tractable than VaR from the
perspective of optimization. It can serve as the risk metric in Markowitz’s
mean-risk criterion (Markowitz, 1952) which balances the expected return and
the risk of a portfolio. The original mean-CVaR model with linear constraints
can be efficiently solved by linear programming (Rockafellar & Uryasev, 2000).

In practical portfolio optimization (PO), it is desirable to constrain the
scale of selected assets while keeping an appropriate investing performance,
in order to reduce transaction cost and managerial burden. This can be done
via the managerial approach, such as the endowment model (Dimmock et al.,
2023), market crashes (Liu & Loewenstein, 2013), and the revenue-driven
resource allocation (Chao et al., 2009). However, these methods still demand
professional knowledge in management and finance. Recently, the arising
development in machine learning methods for management science provides an
alternative way for PO. For example, (Ban et al., 2018) propose the
performance-based regularization with a data-driven strategy to improve the
out-of-sample performance in PO. (Brodie et al., 2009) adopt the $\ell_{1}$
regularization to construct a sparse and stable Markowitz portfolio (SSMP).
(Lai et al., 2018) and (Luo et al., 2020) propose short-term sparse portfolio
optimization models with $\ell_{1}$ and $\ell_{0}$ regularizations,
respectively. (Lai et al., 2020) propose a sparse structure for the covariance
estimation based on the spectral decomposition.

Among all the sparsity approaches, the $\ell_{0}$ constraint can exactly
control the number of selected assets. However, the $\ell_{0}$ constraint
generally leads to an NP-hard problem that has a very high computational
complexity. A general approach to exactly solve the $\ell_{0}$-constrained
problems is the combinatorial approach, such as the mixed-integer optimization
(Günlük & Linderoth, 2010) and the branch-and-bound procedure (Kobayashi et
al., 2021). For example, (Bertsimas & Cory-Wright, 2022) propose a cutting-
plane approach with some heuristics to exactly solve an $\ell_{0}$-constrained
mean-variance model, which saves some computational time according to the
experimental results. (Kobayashi et al., 2021) further adopt this approach to
exactly solve an $\ell_{0}$-constrained mean-CVaR model. It is essentially a
branch-and-bound algorithm: for each visit of a node (a combinatorial case),
it conducts one ordinary mean-CVaR optimization. Since its experimental
results show that the number of visited nodes ranges from about 1,300 to more
than 77,000, the computational complexity is still high in practical portfolio
management. Moreover, (Kobayashi et al., 2021) requires the commercial
optimizer Gurobi111https://www.gurobi.com/ to deploy this cutting-plane
approach. We try to run the program, but it prompts an error that the models
are too large in our experiments. In summary, the existing exactly-solving
approaches have high computational complexity and rely on the external
commercial optimizer, thus economic and practical approaches still need to be
developed.

Instead of exactly solving the $\ell_{0}$-constrained mean-CVaR model, we
propose an autonomous sparse mean-CVaR (ASMCVaR) PO model that can approximate
it to arbitrary accuracy. The core idea is to convert the $\ell_{0}$
constraint into an indicator function and approximate it to arbitrary accuracy
through a tailed approximation approach (Definition 3.1). By this way, we can
replace the nonconvex and complex geometric structure of $\ell_{0}$ constraint
by a simple and more tractable tailed approximation. To solve the ASMCVaR
model, we develop a Proximal Alternating Linearized Minimization Algorithm
(PALM) with a nested Fixed-Point Proximity Algorithm (FPPA) that can handle
all the constraints and guarantee convergence. It saves much computational
complexity and keeps a certain accuracy at the same time. ASMCVaR can keep a
large proportion of assets in the selected asset pool when adjusting the pool
size, which reduces managerial burden and delivers convenience. Our main
contributions can be summarized as follows.

  * 1.

We propose an ASMCVaR model and prove that it can approximate the
$\ell_{0}$-constrained mean-CVaR model to arbitrary accuracy based on item 2.

  * 2.

We propose a tailed approximation for the indicator function of the $\ell_{0}$
constraint. We also find that this approximation can be arbitrarily accurate
as the positive approximation parameter tends to $0$. See Definition 3.1 and
Figure 1 for more detail.

  * 3.

We propose a convergent PALM algorithm with a nested FPPA to iteratively solve
ASMCVaR. It does not require any external or commercial optimizers.

  * 4.

ASMCVaR can keep a large proportion of assets in the selected asset pool when
adjusting the pool size, thus the selected assets are stable. It is beneficial
to practical portfolio management when the manager needs to adjust the asset
pool size.

##  2 Preliminaries and Related Works

We present some preliminaries on CVaR, and then introduce some approximate or
exact solutions to the $\ell_{0}$-constrained mean-CVaR model.

###  2.1 VaR and CVaR

VaR measures the percentage loss of portfolio return in a bad scenario and
with a certain confidence level $c$:

$\mathrm{Pr}\\{\mathrm{VaR}\leqslant-r_{s}\\}=1-c,$

where $\mathrm{Pr}\\{\cdot\\}$ denotes the probability of an event and $r_{s}$
denotes the rate of return of a portfolio (representing some kind of investing
strategy). Specifically, if $\mathrm{VaR}(c=95\%)=0.1$, then this investing
strategy may suffer a loss greater than $10\%$ with a probability of $5\%$.

CVaR further averages the values greater than the VaR at a given confidence
level $c$:

$\mathrm{CVaR}:=\min\limits_{\tau\in\mathbb{R}}\left\\{\tau+\frac{1}{1-c}\mathbb{E}\left(\max\\{-r_{s}-\tau,0\\}\right)\right\\},$

where $\mathbb{E}(\cdot)$ denotes the expectation of a random variable.

###  2.2 Original Mean-CVaR Model

In a real-world investing environment, the CVaR can be formulated as a linear
program. Let
$\bm{R}:=[\bm{r}_{1}^{\top};\cdots;\bm{r}_{T}^{\top}]\in\mathbb{R}^{T\times
N}$ be the sample return matrix of $N$ assets and $T$ observations gathered
from a financial market. Accordingly, a portfolio (investing strategy) can be
seen as an $N$-dimensional vector $\bm{w}$. Then the sample returns of this
portfolio are $\\{\bm{r}_{t}^{\top}\bm{w}\\}_{t=1}^{T}$. Using the sample
average estimator for CVaR yields

$\displaystyle\min\limits_{\bm{w}\in\mathbb{R}^{N},\ \tau\in\mathbb{R},\
\bm{z}\in\mathbb{R}^{T}}\left\\{\tau+\frac{1}{(1-c)T}\bm{1}^{\top}_{T}\bm{z}\right\\}$
(1)
$\displaystyle\text{s.t.}\quad\bm{z}\geqslant-\bm{R}\bm{w}-\tau{\bm{1}}_{T},\quad\bm{z}\geqslant\bm{0}_{T},$
(2) $\displaystyle\
\bm{w}\in\Delta:=\left\\{\bm{w}\in\mathbb{R}^{N}:\bm{w}\geqslant\bm{0}_{N},\bm{w}^{\top}\bm{1}_{N}=1\right\\},$
(3) $\displaystyle\ (\bm{w}^{\top}\hat{\bm{\mu}}=\rho),$ (4)

where $\bm{z}$ is the auxiliary variable to deal with the positive part in the
expectation. $\bm{1}_{T}$ or $\bm{0}_{T}$ is a vector of $1$ or $0$ with
dimensionality shown in the subscript, respectively. The inequality for
vectors dominates each dimension. In (2), inequality constraints for $\bm{z}$
can be used instead of equality constraints because $\bm{z}$ is greater than
$\bm{0}_{T}$ and the objective is a minimization. (3) is the simplex
constraint that consists of the no-short-selling constraint and the self-
financing constraint, respectively. Such constraints ensure feasibility of the
portfolio in real-world investment. (4) is an optional constraint for the
expected portfolio return, where
$\hat{\bm{\mu}}=\frac{1}{T}\bm{R}^{\top}\bm{1}_{T}$ is the sample asset return
vector. (1)$\sim$(4) constitute the original mean-CVaR model (Rockafellar &
Uryasev, 2000). Since all the constraints are convex and linear, this model
can be efficiently solved by the simplex method.

###  2.3 Mean-CVaR Model with $\ell_{1}$ Regularization

A widely adopted approach for sparsity is to impose $\ell_{1}$ regularization.
This method is favored for its compatibility with widely recognized solving
techniques, such as the linear programming, the Lasso (Tibshirani, 1996) and
the LARS (Efron et al., 2004) algorithms. (Cheng & Gao, 2015) propose a mean-
CVaR model with a re-weighted $\ell_{1}$ regularization as follows:

$\begin{split}&\min\limits_{\bm{w}\in\mathbb{R}^{N},\tau\in\mathbb{R},\bm{z}\in\mathbb{R}^{T}}\left\\{\tau+\frac{1}{(1-c)T}\bm{1}^{\top}_{T}\bm{z}+\bm{\lambda}^{\top}\bm{w}\right\\}\\\
&\text{s.t.}\ \
\bm{z}{\geqslant-}\bm{R}\bm{w}{-}\tau{\bm{1}}_{T},\bm{z}\geqslant\bm{0}_{T},\bm{w}\in\Delta,(\bm{w}^{\top}\hat{\bm{\mu}}=\rho),\end{split}$
(5)

where $\bm{\lambda}\in\\{\bm{x}\in\mathbb{R}^{N}:\bm{x}\geqslant\bm{0}_{N}\\}$
is the weight vector for the $\ell_{1}$ regularization. Since
$\bm{w}\geqslant\bm{0}_{N}$, the re-weighted $\ell_{1}$ regularization in (5)
can be simplified:
$\sum_{i=1}^{N}\lambda_{i}|w_{i}|=\sum_{i=1}^{N}\lambda_{i}w_{i}=\bm{\lambda}^{\top}\bm{w}$.
This formulation can also be efficiently solved by linear programming. In each
outer-iteration, the algorithm updates $\bm{\lambda}$ by some rules regarding
$\bm{w}$, for example, $\lambda_{i}^{k+1}=1/(|w_{i}^{k}|+\epsilon)$. Then in
the inner-iteration, (5) is solved with fixed $\bm{\lambda}^{k+1}$ to obtain
$\bm{w}^{k+1}$. This approach enjoys a low computational cost, but it cannot
exactly control the number of selected assets. One can just empirically tune
$\bm{\lambda}$ to get a rough number of selected assets. Besides, it is also
intractable to assess the accuracy of approximation of $\ell_{1}$
regularization to the $\ell_{0}$ constraint.

###  2.4 $\ell_{0}$-constrained Mean-CVaR Model

To impose exact sparsity on the portfolio, the $\ell_{0}$ constraint should be
used:

$\displaystyle\min\limits_{\bm{w}\in\mathbb{R}^{N},\ \tau\in\mathbb{R},\
\bm{z}\in\mathbb{R}^{T}}\left\\{\tau+\frac{1}{(1-c)T}\bm{1}^{\top}_{T}\bm{z}\right\\}$
(6) $\displaystyle\text{s.t.}\ \bm{z}\geqslant-\bm{R}\bm{w}-\tau{\bm{1}}_{T},\
\bm{z}\geqslant\bm{0}_{T},\ \bm{w}\in\Delta,\
(\bm{w}^{\top}\hat{\bm{\mu}}=\rho),$ $\displaystyle\hskip
15.00002pt\|\bm{w}\|_{0}\leqslant m,$ (7)

where $\Delta$ is defined in (3), and $\|\bm{w}\|_{0}$ represents the number
of nonzero components in $\bm{w}$. The $\ell_{0}$ constraint in (7) is also
called the $m$-sparse constraint, since $m$ controls the number of selected
assets. The above $\ell_{0}$-constrained mean-CVaR problem is NP-hard. To
solve it by the combinatorial approach, (Kobayashi et al., 2021) introduce an
auxiliary variable
$\bm{y}\in\mathcal{Z}_{N}^{m}:=\\{\bm{y}\in\\{0,1\\}^{N}:\bm{1}_{N}^{\top}\bm{y}\leqslant
m\\}$, then (7) is equivalent to the logical constraint

$\bm{y}\in\mathcal{Z}_{N}^{m},\quad y_{i}=0\Rightarrow w_{i}=0.$ (8)

Let $\bm{Y}:=\mathrm{diag}(\bm{y})$ be the diagonalized matrix for $\bm{y}$.
Then model (6) can be reformulated as a bilevel optimization problem

$\displaystyle\text{(upper-
level)}\qquad\min_{\bm{y}\in\mathcal{Z}_{N}^{m}}f(\bm{y}),$ (9) (lower-level)
$\displaystyle
f(\bm{y})=\min_{\bm{w}\in\mathbb{R}^{N},\tau\in\mathbb{R},\bm{z}\in\mathbb{R}^{T}}\
\left\\{\frac{1}{2\gamma}\bm{w}^{\top}\bm{w}{+}\tau{+}\frac{1}{(1{-}c)T}\bm{1}^{\top}_{T}\bm{z}\right\\}$
(10) $\displaystyle\text{s.t.}\
\bm{z}{\geqslant-}\bm{R}\bm{Y}\bm{w}{-}\tau{\bm{1}}_{T},\bm{z}{\geqslant}\bm{0}_{T},\bm{Y}\bm{w}{\in}\Delta,(\bm{w}^{\top}\bm{Y}\hat{\bm{\mu}}{=}\rho),$
(11)

where the logical constraint (8) is embedded in $\bm{Y}\bm{w}$. Note that
$\bm{w}=\bm{Y}\bm{w}$ after minimization (2.4), thus
$(\bm{Y}\bm{w})^{\top}\bm{Y}\bm{w}$ is replaced by $\bm{w}^{\top}\bm{w}$
(Bertsimas & Cory-Wright, 2022). As $\gamma\rightarrow+\infty$, this bilevel
optimization can approximate the $\ell_{0}$-constrained mean-CVaR optimization
to arbitrary accuracy.

In the upper-level optimization, (Kobayashi et al., 2021) solve the following
problem

$\min_{(\bm{y},\theta)\in\mathcal{Z}_{N}^{m}\times\mathbb{R}}\theta\quad\text{s.t.}\quad(\bm{y},\theta)\in\mathcal{F}^{k}\subseteq\mathcal{Z}_{N}^{m}\times\mathbb{R}$
(12)

to obtain the node $(\bm{y}^{k},\theta^{k})$ of the $k$-th visit, where
$\mathcal{F}^{k}$ denotes the $k$-th feasible region for $(\bm{y},\theta)$.
$\theta$ indicates any possible value for $f(\bm{y})$ in the current
iteration, and its infimum provides a lower bound for $f(\bm{y})$. To
initialize, one can just solve a continuously-relaxed and lower-bounded
version of (6)$\sim$(7) to obtain $\theta^{1}$ for all
$\bm{y}\in\mathcal{Z}_{N}^{m}$ and pick up any
$\bm{y}^{1}\in\mathcal{Z}_{N}^{m}$. In the lower-level optimization,
(2.4)$\sim$(11) is a convex quadratic optimization for which efficient
algorithms exist. If it is infeasible, then $\mathcal{F}^{k+1}$ is obtained by
removing $(\bm{y}^{k},\theta^{k})$ from $\mathcal{F}^{k}$; or else it can be
solved to obtain $f(\bm{y}^{k})$. Since $f(\bm{y})$ is convex in
$\bm{y}\in[0,1]^{N}$, the set

$\\{(\bm{y},\theta)\in\mathcal{Z}_{N}^{m}\times\mathbb{R}:\theta\geqslant
f(\bm{y}^{k})+\bm{g}_{\bm{y}^{k}}^{\top}(\bm{y}-\bm{y}^{k})\\}$ (13)

provides new lower bounds for all the unvisited cases
$\bm{y}\in\mathcal{Z}_{N}^{m}$, where $\bm{g}_{\bm{y}^{k}}$ is a subgradient
of $f$ at $\bm{y}^{k}$. Intersecting (13) and $\mathcal{F}^{k}$ yields
$\mathcal{F}^{k+1}$. Either feasible or infeasible, the lower-level
optimization narrows down the searching region from $\mathcal{F}^{k}$ to
$\mathcal{F}^{k+1}$. Then in the next visit (iteration), (12) is solved in
$\mathcal{F}^{k+1}$. During this procedure, $LB^{k}:=\theta^{k}$ serves as the
current uniform lower bound for all the unvisited cases, while
$UB^{k}:=\min_{1\leqslant j\leqslant k}f(\bm{y}^{j})$ serves as the current
uniform upper bound for all the visited cases. If $(UB^{k}-LB^{k}<\epsilon)$
for a sufficiently small positive $\epsilon$, then $\\{\bm{y}^{j}:1\leqslant
j\leqslant k,f(\bm{y}^{j})=UB^{k}\\}$ can be considered as the
$\epsilon$-optimal solution set. In fact, this is a branch-and-bound strategy.

Though the above bilevel optimization takes the exact solving objective as the
initial intention, it involves two approximations: one is the term
$\frac{1}{2\gamma}\bm{w}^{\top}\bm{w}$ in (2.4), the other is the $\epsilon$
optimality of the gap $(UB^{k}-LB^{k})$. Moreover, this branch-and-bound
approach may visit tens of thousands of combinatorial cases to achieve
satisfactory optimality. In addition, external commercial optimizers are also
required to deploy the whole algorithm. The program is unable to run in our
experiments because the models are too large. To develop economic and
practical methods, we propose to approximate the $\ell_{0}$-constrained mean-
CVaR model from a very different perspective based on a tailed approximation.

##  3 Autonomous Sparse Mean-CVaR Portfolio Optimization

In this section, we propose an Autonomous Sparse Mean-CVaR (ASMCVaR) model and
develop a Proximal Alternating Linearized Minimization (PALM) algorithm to
solve this model.

###  3.1 Autonomous Sparse Mean-CVaR Model

Before introducing the ASMCVaR model, we revise the $\ell_{0}$-constrained
Mean-CVaR model and reformulate it as a nonconvex three-term optimization
model. Note that there is an equality constraint $\bm{w}^{\top}\bm{\mu}=\rho$
in the Mean-CVaR model (6). In general, the expected return level $\rho$ is
generally set to a positive number. However, this constraint is not always
feasible not only in reality but also in theory. The satisfaction of a tight
equality constraint for the return level in PO with an ever-changing financial
market is difficult. To avoid this problem, we use a regularization term
$({\bm{w}}^{\top}\hat{\bm{\mu}}-\rho)^{2}$ in the objective function instead
of using the equality constraint. In this way, the portfolio return
${\bm{w}}^{\top}\hat{\bm{\mu}}$ is balanced between the expected level $\rho$
and the risk metric CVaR. Then the revised $\ell_{0}$-constrained Mean-CVaR
model is given by

$\begin{split}&\min\limits_{\begin{subarray}{c}\bm{w}\in\mathbb{R}^{N},\
\tau\in\mathbb{R},\
\bm{z}\in\mathbb{R}^{T}\end{subarray}}\left\\{\tau+\frac{1}{(1-c)T}\bm{1}^{\top}_{T}\bm{z}+\lambda(\bm{w}^{\top}\bm{\mu}-\rho)^{2}\right\\}\\\
&\text{s.t.}\ \bm{z}\geqslant-\bm{R}\bm{w}-\tau{\bm{1}}_{T},\
\bm{z}\geqslant\bm{0}_{T},\ \bm{w}\in\Delta,\ \|\bm{w}\|_{0}\leqslant
m.\end{split}$ (14)

For notation simplicity, we define $N_{1}:=N+1+T$, $N_{2}:=2T+N+2$. We then
rewrite model (14) as a more compact form. To this end, we let
$\bm{v}:=(\bm{w}^{\top},\tau,\bm{z}^{\top})^{\top}\in\mathbb{R}^{N_{1}}$,

$\bm{h}_{1}{:=}\bigg{(}\bm{0}_{N}^{\top},1,\frac{1}{(1{-}c)T}\bm{1}_{T}^{\top}\bigg{)}^{\top},\
\bm{h}_{2}{:=}\left(\bm{\mu}^{\top},\bm{0}_{1+T}^{\top}\right)^{\top},$ (15)
$\begin{split}&\tilde{\bm{Q}}:=\left(\begin{array}[]{ccc}\bm{R}&\bm{1}_{T}&\bm{I}_{T}\\\
\bm{0}_{T\times
N}&\bm{0}_{T}&\bm{I}_{T}\end{array}\right)\in\mathbb{R}^{2T\times N_{1}},\\\
&\widetilde{\bm{I}}:=\left(\bm{I}_{N}\ \
\bm{0}_{N\times(T+1)}\right)\in\mathbb{R}^{N\times N_{1}},\end{split}$

and define

$\displaystyle\bm{Q}:=\left(\begin{array}[]{@{}cc@{}}\lx@intercol\hfil\tilde{\bm{Q}}\hfil\lx@intercol\\\
\bm{I}_{N}&\bm{0}_{N\times(T+1)}\\\ \bm{1}_{N}^{\top}&\bm{0}_{T+1}^{\top}\\\
\bm{-1}_{N}^{\top}&\bm{0}_{T+1}^{\top}\\\
\end{array}\right)\in\mathbb{R}^{N_{2}\times N_{1}},$ (20)
$\displaystyle\bm{q}:=\left(\begin{array}[]{@{}c@{}}\bm{0}_{2T+N}\\\ 1\\\
-1\\\ \end{array}\right)\in\mathbb{R}^{N_{2}}.$ (24)

Then model (14) can be rewritten as the following model with respect to
(w.r.t.) $\bm{v}$:

$\begin{split}&\min\limits_{\bm{v}\in\mathbb{R}^{N_{1}}}\left\\{\bm{h}_{1}^{\top}\bm{v}+\lambda(\bm{h}_{2}^{\top}{\bm{v}}-\rho)^{2}\right\\}\\\
&\text{s.t.}\ \bm{Q}\bm{v}\geqslant\bm{q},\ \
\|\tilde{\bm{I}}\bm{v}\|_{0}\leqslant m.\end{split}$ (25)

Model (25) comprises two constraints. In fact, it can be reformulated as an
equivalent three-term unconstrained minimization model. For this purpose, we
define two indicator functions

$\begin{split}&\iota_{\bm{q}}(\bm{u}):=\begin{cases}0,&\text{if}\
\bm{u}\geqslant\bm{q};\\\ +\infty,&\text{otherwise},\end{cases}\\\
&\iota_{m}(\bm{w}):=\begin{cases}0,&\text{if}\ \|\bm{w}\|_{0}\leqslant m;\\\
+\infty,&\text{otherwise},\end{cases}\end{split}$

for $\bm{u}\in\mathbb{R}^{N_{2}}$ and $\bm{w}\in\mathbb{R}^{N}$, respectively;
and define

$f(\bm{v}):=\bm{h}_{1}^{\top}\bm{v}+\lambda(\bm{h}_{2}^{\top}{\bm{v}}-\rho)^{2},\
\ \bm{v}\in\mathbb{R}^{N_{1}}.$ (26)

Then model (25) is equivalent to the following model:

$\min\limits_{\bm{v}\in\mathbb{R}^{N_{1}}}\left\\{\Phi(\bm{v}):=f(\bm{v})+\iota_{\bm{q}}(\bm{Q}\bm{v})+\iota_{m}(\widetilde{\bm{I}}\bm{v})\right\\}.$
(27)

Directly solving model (27) is very tough due to the nondifferentiability of
$\iota_{\bm{q}}$ and the nonconvexity of $\iota_{m}$. Instead, we introduce a
surrogate model of model (27) and develop an efficient algorithm to solve the
surrogate model. To this end, we introduce a function to approximate the exact
$m$-sparse function $\iota_{m}$. For vector $\bm{w}\in\mathbb{R}^{N}$, let
$\\{j_{1},j_{2},\ldots$,$j_{N}\\}$ be any rearrangement of
$\\{1,2,\cdots,N\\}$ such that
$|w_{j_{1}}|\geqslant|w_{j_{2}}|\geqslant\cdots\geqslant|w_{j_{N}}|$. Then we
call $\\{j_{1},j_{2},\cdots,j_{m}\\}$ an $m$-largest absolute value ($m$-LAV)
index set of $\bm{w}$. Note that the $m$-LAV index sets of $\bm{w}$ may not be
unique since the components of $\bm{w}$ may not be distinct. Throughout this
paper, for $\bm{w}\in\mathbb{R}^{N}$, we denote by $J_{\bm{w}}^{m}$ an $m$-LAV
index set of $\bm{w}$. By smoothing the giant leap of $\iota_{m}$ between
$\|\bm{w}\|_{0}\leqslant m$ and $\|\bm{w}\|_{0}>m$, we construct the following
tailed approximation.

######  Definition 3.1 (Tailed Approximation of $\ell_{0}$ Constraint).

The tailed approximation for the $m$-sparse indicator function is defined by

$\tilde{\iota}_{m,\gamma}(\bm{w})=\begin{cases}0,&\mbox{if}\
\|\bm{w}\|_{0}\leqslant m;\\\
\frac{1}{2\gamma}\sum\limits_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}}^{m}}w_{j}^{2},&\mbox{if}\ \|\bm{w}\|_{0}>m.\end{cases}$ (28)

where $\gamma>0$ is the approximation parameter.

When $\|\bm{w}\|_{0}>m$, the tail term
$\frac{1}{2\gamma}\sum\limits_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}}^{m}}w_{j}^{2}>0$, then
$\frac{1}{2\gamma}\sum\limits_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}}^{m}}w_{j}^{2}\nearrow+\infty$ as $\gamma\searrow 0$. Hence for any
fixed $\bm{w}$, either $\tilde{\iota}_{m,\gamma}(\bm{w})=\iota_{m}(\bm{w})$
($\|\bm{w}\|_{0}\leqslant m$) or
$\tilde{\iota}_{m,\gamma}(\bm{w})\nearrow\iota_{m}(\bm{w})$ as $\gamma\searrow
0$ ($\|\bm{w}\|_{0}>m$). Figure 1 shows a diagram for
$\tilde{\iota}_{m,\gamma}(\bm{w})$ with $N=10$ and $m=5$.

Figure 1: Diagram for tailed approximation of $\ell_{0}$ constraint:
$\tilde{\iota}_{m,\gamma}(\bm{w})$ with $N=10$ and $m=5$. As $\gamma\searrow
0$, $\frac{1}{2\gamma}\sum_{k=6}^{10}w_{j_{k}}^{2}\nearrow+\infty$ and
$\tilde{\iota}_{m,\gamma}(\bm{w})\nearrow\iota_{m}(\bm{w})$ for any fixed
$\bm{w}$ ($\|\bm{w}\|_{0}>5$).

Now the proposed ASMCVaR model is given by

$\min\limits_{\bm{v}\in\mathbb{R}^{N_{1}}}\left\\{\Psi(\bm{v}):=f(\bm{v})+\iota_{\bm{q}}(\bm{Q}\bm{v})+\tilde{\iota}_{m,\gamma}(\widetilde{\bm{I}}\bm{v})\right\\}.$
(29)

We then establish the relationship between the solutions of model (27) and the
ASMCVaR model. For this purpose, we need the following technical lemma, whose
proof is given in Supplementary A.1.

######  Lemma 3.2.

Let $\bm{v}^{*}$ be a solution of model (29) and
$\bm{w}^{*}:=\tilde{\bm{I}}\bm{v}^{*}$. Then there exists a constant
$\tilde{L}>0$ such that

$w_{j}^{*}\leqslant\sqrt{2\tilde{L}\gamma},\ \ \mbox{for all}\
j\in\mathbb{N}_{N}\backslash J_{\bm{w}^{*}}^{m}.$ (30)

The following theorem indicates that the optimal value of $f$ in (29) can
approximate that in (27) to arbitrary accuracy by letting $\gamma\searrow 0$.

######  Theorem 3.3.

Let $\bm{v}^{*}$ and $\bm{v}^{**}$ be solutions of models (29) and (27),
respectively. Then there exists a constant $\tilde{L}>0$ such that

$0\leqslant f(\bm{v}^{**})-f(\bm{v}^{*})\leqslant\sqrt{2\tilde{L}^{3}\gamma}.$
(31)

The proof is given in Supplementary A.2. To solve model (29), we further
rewrite it as an optimization model w.r.t. two variables $\bm{v}$ and $\bm{y}$
as follows:

$\min\limits_{\bm{v}\in\mathbb{R}^{N_{1}},\
\bm{y}\in\mathbb{R}^{N}}\left\\{G(\bm{v},\bm{y}):=H(\bm{v},\bm{y})+\iota_{\bm{q}}(\bm{Q}\bm{v})+\iota_{m}(\bm{y})\right\\},$
(32)

where

$H(\bm{v},\bm{y}):=f(\bm{v})+\frac{1}{2\gamma}\left\|\widetilde{\bm{I}}\bm{v}-\bm{y}\right\|_{2}^{2},\
\ \gamma>0.$ (33)

This model can be directly solved by the proximal alternating linearized
minimization algorithm (Attouch et al., 2013; Bolte et al., 2014). We shall
then prove the equivalence of the solutions of models (29) and (32). To this
end, we need the following two lemmas. We let

$\Omega_{m}:=\\{\bm{w}\in\mathbb{R}^{N}:\|\bm{w}\|_{0}\leqslant m\\},$ (34)

and define the thresholding operator $\mathcal{S}_{m}$ w.r.t. the $m$ largest
components by

$[\mathcal{S}_{m}(\bm{w})]_{j}:=\begin{cases}w_{j},&\text{if}\ j\in
J_{\bm{w}}^{m};\\\ 0,&\text{if}\ j\in\mathbb{N}_{N}\backslash
J_{\bm{w}}^{m},\end{cases}$ (35)

for $\bm{w}\in\mathbb{R}^{N}$. Note that $\mathcal{S}_{m}(\bm{w})$ may not be
unique and it depends on a corresponding $m$-LAV index set of $\bm{w}$.
Throughout this paper, the equality $\bm{x}=\mathcal{S}_{m}(\bm{w})$
represents $\bm{x}\in\mathcal{S}_{m}(\bm{w})$.

######  Lemma 3.4.

If a pair $(\bm{v}^{*},\bm{y}^{*})$ is a solution of model (32), then
$\bm{y}^{*}=\mathcal{S}_{m}(\widetilde{\bm{I}}\bm{v}^{*})$.

######  Lemma 3.5.

Let $G$ be defined in (32), $\bm{v}\in\mathbb{R}^{N_{1}}$. If
$\tilde{\bm{y}}=\mathcal{S}_{m}(\widetilde{\bm{I}}\bm{v})$, then

$G(\bm{v},\tilde{\bm{y}})\leqslant G(\bm{v},\bm{y}),\
\forall\bm{y}\in\mathbb{R}^{N}.$ (36)

The proof of Lemma 3.4 and Lemma 3.5 are given in Supplementary A.3 and A.4,
respectively. According to these two lemmas, we have the following theorem,
whose proof is provided in Supplementary A.5.

######  Theorem 3.6.

Let functions $\Psi$ and $G$ be defined by (29) and (32), respectively. Then

$\Psi(\bm{v})=G(\bm{v},\bm{y}),\ \
\forall\bm{v}\in\mathbb{R}^{N_{1}},\bm{y}=\mathcal{S}_{m}(\widetilde{\bm{I}}\bm{v}).$
(37)

Moreover, a pair $(\bm{v}^{*},\bm{y}^{*})$ is a solution of model (32) if and
only if $\bm{v}^{*}$ is a solution of model (29) and
$\bm{y}^{*}=\mathcal{S}_{m}(\widetilde{\bm{I}}\bm{v}^{*})$.

We remark that the original model (27) presents a three-term single-variable
optimization problem (w.r.t. $\bm{v}$), comprising a convex and differentiable
term $f$, a convex but nondifferentiable term $\iota_{\bm{q}}\circ{\bm{Q}}$,
and a nonconvex and nondifferentiable term $\iota_{m}\circ\tilde{\bm{I}}$.
This model cannot be directly tackled using the PALM algorithm. Resolving such
multi-term nondifferentiable optimization models typically necessitates the
introduction of proximity operators through subdifferential. When dealing with
the summation of two functions $\varphi_{1}$ and $\varphi_{2}$, where at least
one function is differentiable, the additivity property of subdifferential
($\partial$) holds:

$\partial(\varphi_{1}+\varphi_{2})(\bm{x})=\partial\varphi_{1}(\bm{x})+\partial\varphi_{2}(\bm{x}).$

If $\varphi_{1}$ and $\varphi_{2}$ are both nondifferentiable, this property
may not hold. The absence of additivity in subdifferential complicates the
design of proximity algorithms to solve the original model. Theoretical proof
of convergence becomes exceedingly challenging under such circumstances.

The proposed relaxation technique precisely aims to convert the original model
into a three-term dual-variable optimization model (w.r.t. $\bm{v}$ and
$\bm{y}$) in the form of (32), which can be solved via the PALM algorithm. The
advantage of such a format lies in its ability to decompose the model into two
separate optimization problems, each concerning variables $\bm{v}$ and
$\bm{y}$ respectively. Moreover, due to the differentiability of $H$, the
subdifferentials corresponding to these two problems exhibit additivity, thus
greatly facilitating the theoretical convergence analysis of the PALM
algorithm. Furthermore, we demonstrate, through Theorems 3.3 and 3.6, the
equivalence of solutions in both formats in the sense of approximation,
thereby ensuring the effectiveness of utilizing the PALM algorithm to solve
the model.

###  3.2 Proximal Alternating Linearized Minimization

In this subsection. We employ the Proximal Alternating Linearized Minimization
(PALM) algorithm to solve model (32). We verify in the following proposition
that the partial gradients $\nabla_{\bm{v}}H(\bm{v},\bm{y})$ and
$\nabla_{\bm{y}}H(\bm{v},\bm{y})$ of function $H$ defined by (33) are both
globally Lipschitz continuous, which is required for the convergence of PALM
(Bolte et al., 2014).

######  Proposition 3.7.

Let function $H$ be defined by (33). Then there exist positive real numbers
$L_{1}$ and $L_{2}$ such that

$\displaystyle\|\nabla_{\bm{v}}H(\bm{v}_{1},\bm{y})$
$\displaystyle-\nabla_{\bm{v}}H(\bm{v}_{2},\bm{y})\|_{2}\leqslant
L_{1}\|\bm{v}_{1}-\bm{v}_{2}\|_{2},$
$\displaystyle\forall\bm{v}_{1},\bm{v}_{2}\in\mathbb{R}^{N_{1}},\
\forall\bm{y}\in\mathbb{R}^{N};$
$\displaystyle\|\nabla_{\bm{y}}H(\bm{v},\bm{y}_{1})$
$\displaystyle-\nabla_{\bm{y}}H(\bm{v},\bm{y}_{2})\|_{2}\leqslant
L_{2}\|\bm{y}_{1}-\bm{y}_{2}\|_{2},$
$\displaystyle\forall\bm{y}_{1},\bm{y}_{2}\in\mathbb{R}^{N},\
\forall\bm{v}\in\mathbb{R}^{N_{1}}.$

The proof is given in Supplementary A.6. For function
$\psi:\mathbb{R}^{n}\to(-\infty,+\infty]$, we recall that the proximity
operator of $\psi$ at $\bm{x}\in\mathbb{R}^{n}$ is defined by

$\mathrm{prox}_{\psi}(\bm{x}):=\mathop{\rm
arg\,min}\limits_{\bm{u}\in\mathbb{R}^{n}}\left\\{\frac{1}{2}\|\bm{u}-\bm{x}\|_{2}^{2}+\psi(\bm{u})\right\\}.$

Then the iterative scheme of PALM to solve model (32) can be given by

$\begin{cases}\bm{v}^{k+1}=\mathrm{prox}_{\iota_{\bm{q}}\circ\bm{Q}}\big{(}\bm{v}^{k}-\beta_{1}\nabla_{\bm{v}}H(\bm{v}^{k},\bm{y}^{k})\big{)},\\\
\bm{y}^{k+1}=\mathcal{S}_{m}\big{(}\bm{y}^{k}-\beta_{2}\nabla_{\bm{y}}H(\bm{v}^{k+1},\bm{y}^{k})\big{)},\end{cases}$

where $\beta_{1}$ and $\beta_{2}$ are two introduced step-size parameters. As
shown in (Bolte et al., 2014), to guarantee the convergence of PALM, it
suffices to let $\beta_{1}\in\left(0,\frac{1}{L_{1}}\right)$ and
$\beta_{2}\in\left(0,\frac{1}{L_{2}}\right)$, where
$L_{1}:=2\lambda\|\bm{h}_{2}\|_{2}^{2}+\frac{1}{\gamma}$ and
$L_{2}:=\frac{1}{\gamma}$.

To implement the PALM algorithm, we need the closed form of
$\mathrm{prox}_{\iota_{\bm{q}}\circ\bm{Q}}$, which requires solving the
following minimization problem:

$\mathop{\rm
arg\,min}\limits_{\bm{u}\in\mathbb{R}^{N_{1}}}\left\\{\frac{1}{2}\|\bm{u}-\bm{v}\|_{2}^{2}+\iota_{\bm{q}}(\bm{Q}\bm{u})\right\\},$
(38)

for a given $\bm{v}\in\mathbb{R}^{N_{1}}$. However, obtaining the closed-form
solution of $\mathrm{prox}_{\iota_{\bm{q}}\circ\bm{Q}}$ is very tough, due to
the complexity of matrix $\bm{Q}$. Instead, we use the Fixed-Point Proximity
Algorithm (FPPA, Micchelli et al. 2011) to solve model (38) iteratively.
Before this, we give the closed form of operator
$\mathrm{prox}_{\iota_{\bm{q}}}$. From the definition of proximity operator,
it is easy to see that

$\mathrm{prox}_{\iota_{\bm{q}}}(\bm{x}){=}\mathop{\rm
arg\,min}\limits_{\bm{u}\in\left\\{\bm{z}\in\mathbb{R}^{N_{2}}:\bm{z}\geqslant\bm{q}\right\\}}\left\\{\frac{1}{2}\|\bm{u}{-}\bm{x}\|_{2}^{2}\right\\}{=}\max\left\\{\bm{x},\bm{q}\right\\}.$

The whole ASMCVaR approach is summarized as Algorithm 1 in Supplementary A.7,
with PALM and FPPA in the outer and the inner iterations, respectively.

It is noteworthy that both the proposed relaxation (tailed approximation)
technique and the PALM algorithm can be readily extended to various other
machine learning problems. To exemplify this, we have introduced two
additional modules. Firstly, we apply the proposed relaxation technique and
the PALM algorithm to the sparse regression problem, as detailed in
Supplementary A.8. Secondly, we have developed a PyTorch module based on this
relaxation technique and PALM, facilitating its application to deep learning
scenarios. The codes for these two modules are available in the folders
Sparse_Relaxation_Test and Pytorch_Demo, respectively, accessible via the
link: https://github.com/linyizun2024/ASMCVaR.

##  4 Experimental Results

We conduct extensive experiments on $6$ real-world financial data sets from
Kenneth R. French’s Data
Library222http://mba.tuck.dartmouth.edu/pages/faculty/ken.french/data_library.html,
whose details are provided in Table 1. They contain monthly price relative
sequences of some portfolios formed by different criteria, and one portfolio
here is considered as one asset actually. Both FF25 and FF25EU contain $25$
portfolios, while the former is built on BE/ME (book equity to market equity)
and investment from the US market, the latter is built on ME and prior return
from the European market. FF32 consists of 32 portfolios built on BE/ME and
investment from the US market, while FF49 consists of 49 industry portfolios
from the US market. FF100 and FF100MEOP consist of 100 portfolios from the US
market. FF100 is built on ME and BE/ME, while FF100MEOP is built on ME and
operating profitability, respectively.

Table 1: Information of 6 real-world monthly benchmark data sets.

Data Set | Region | Time | Months | # Assets
---|---|---|---|---
FF25 | US | Jul/1971 - May/2023 | 623 | 25
FF25EU | EU | Nov/1990 - May/2023 | 391 | 25
FF32 | US | Jul/1971 - May/2023 | 623 | 32
FF49 | US | Jul/1971 - May/2023 | 623 | 49
FF100 | US | Jul/1971 - May/2023 | 623 | 100
FF100MEOP | US | Jul/1971 - May/2023 | 623 | 100

To assess the effectiveness of the proposed ASMCVaR, we take 9 state-of-the-
art PO methods as well as 1 baseline into comparison. They are SSMP (Brodie et
al., 2009), SSPO (Lai et al., 2018), SPOLC (Lai et al., 2020), S1, S2, S3 (Luo
et al., 2020), Mean-CVaR (Rockafellar & Uryasev, 2000), Mean-CVaR-$\ell_{1}$
(Cheng & Gao, 2015), MT-CVaR (Lai et al., 2022), and the 1/N strategy
(baseline, DeMiguel et al. 2009). We also try to run the cutting plane
approach (Kobayashi et al., 2021) for Mean-CVaR-$\ell_{0}$ but the program
prompts an error that the models are too large in our experiments. There are 3
slightly different versions in (Luo et al., 2020): S1 is deterministic but S2
and S3 are randomized. Thus we average the results of 10 times for S2 and S3.
The parameters for these competitors are set according to their original
papers, while those for ASMCVaR will be set in Section 4.1.

We adopt the standard moving-window trading scheme in the literature (Cover,
1991; Li et al., 2016; Lai & Yang, 2023) to assess the investing performance
of different methods. Assume we observe $\mathscr{T}$ trading periods for $N$
assets in a financial market. Without loss of generality, we can assume the
initial wealth $S^{(0)}=1$ and the cumulative wealth (CW) $S^{(t)}$ at time
$t$ increases (or decreases) with a factor:
$S^{(t)}=S^{(t-1)}\cdot((\mathbf{x}^{(t)})^{\top}\hat{\bm{w}}^{(t)})$, where
$\mathbf{x}^{(t)}:=\bm{r}_{t}+\bm{1}_{N}$ denotes the price relative vector at
time $t$ and $\hat{\bm{w}}^{(t)}$ denotes the portfolio for a strategy built
on the time window $[t-T:t-1]$. At the beginning where there may be
insufficient observations for some strategies, the 1/N strategy can be
temporally used. This procedure goes on to the end and forms a backtest CW
sequence $\\{S^{(t)}\\}_{t=0}^{\mathscr{T}}$ that can be used in the
assessment. We set for all the methods $T=60$ as a conventional setting for
the time window size in the literature (Goto & Xu, 2015; Ao et al., 2019). All
the data sets and codes of this section are accessible via the link:
https://github.com/linyizun2024/ASMCVaR/tree/main/Codes_for_Experiments_in_Paper.

###  4.1 Parameter Setting and Autonomous Sparsity

The model parameters in (29) are set as follows: the confidence level is set
as a conventional one $c=0.99$. The expected return level is empirically set
as $\rho=0.02$ based on observations from real-world financial markets. The
approximation parameter is set as $\gamma=10^{-5}$, which indicates a tight
approximation of $\ell_{0}$ constraint. The mixing parameter is set as

$\begin{split}\lambda&=\frac{\sqrt{T}\bm{h}_{1}[(N+2):(N+1+T)]^{\top}(\bm{1}_{T}/T)}{(\bm{h}_{2}[1:N]^{\top}(\bm{1}_{N}/N)-\rho)^{2}}\\\
&=\frac{1}{(1-c)\sqrt{T}(\bar{r}-\rho)^{2}},\end{split}$

where $\bm{h}_{1}[(N+2):(N+1+T)]$ and $\bm{h}_{2}[1:N]$ denote the last $T$
indices of $\bm{h}_{1}$ and the first $N$ indices of $\bm{h}_{2}$,
respectively. $\bar{r}$ is the mean return of the entries of $\bm{R}$. This
setting of $\lambda$ is a quotient between the CVaR term and the return term
in (26) with equal weights $\bm{1}_{T}/T$ and $\bm{1}_{N}/N$. As for the
number of selected assets $m$, we assess $3$ different sparsities: $m_{1}=10$,
$m_{2}=15$, and $m_{3}=20$.

The algorithm parameters can be conveniently set based on the convergence
criteria. For FPPA, we set $\theta=1.99/\|\tilde{\bm{Q}}\|_{2}^{2}$. Its
maximum iteration and relative difference tolerance are set as
$MaxIter_{1}=200$ and $tol_{1}=0.001$. For PALM, the learning rates are set as
$\beta_{1}=\frac{0.99}{L_{1}}$ and $\beta_{2}=\frac{0.99}{L_{2}}$,
respectively. Its maximum iteration and relative difference tolerance are set
as $MaxIter_{2}=10^{4}$ and $tol_{2}=10^{-4}$.

We further investigate the sparsity parameter $m$ and find that the support
sets of two different sparsities overlap with a large proportion. To be
specific, ASMCVaR produces a portfolio $\hat{\bm{w}}^{(t,j)}$ for each
sparsity $m_{j}$ and each trade time $t$. The overlapped proportion can be
computed by

$p^{(t)}_{j}:=\frac{|supp(\hat{\bm{w}}^{(t,j)})\cap
supp(\hat{\bm{w}}^{(t,j+1)})|}{|supp(\hat{\bm{w}}^{(t,j)})|},\quad j=1,2.$

The sample means $\bar{p}_{j}$ and the sample standard deviations (STD)
$\hat{\sigma}(p_{j})$ of $\\{p^{(t)}_{j}\\}_{t=1}^{\mathscr{T}}$ on the
benchmark data sets are presented in Table 2. More than $89\%$ assets overlap
on average between two different sparsities. We call this property autonomous
sparsity since a large proportion of assets can remain in the selected asset
pool when the portfolio manager adjusts the pool size. It helps to save
transaction costs and reduce the managerial burden.

Table 2: Proportion of overlapped assets for ASMCVaR with different sparsities
on 6 benchmark data sets.

| FF25 | FF25EU | FF32 | FF49 | FF100 |  | FF100
---
MEOP
$\bar{p}_{1}$ | 0.9115 | 0.9147 | 0.8919 | 0.9468 | 0.9222 | 0.9018
$\hat{\sigma}(p_{1})$ | 0.1182 | 0.1215 | 0.1307 | 0.0832 | 0.1060 | 0.1154
$\bar{p}_{2}$ | 0.9554 | 0.9553 | 0.9348 | 0.9372 | 0.9543 | 0.9478
$\hat{\sigma}(p_{2})$ | 0.0808 | 0.0854 | 0.0958 | 0.0825 | 0.0766 | 0.0724

###  4.2 Cumulative Wealth

The CW sequence $\\{S^{(t)}\\}_{t=0}^{\mathscr{T}}$ represents the investing
gain of a method along with time. The final CWs of different methods on 6
benchmark data sets are provided in Table 4. ASMCVaR with any of the 3
sparsity settings outperforms all the other competitors on all 6 data sets.
For example, the final CW of ASMCVaR is about 10 times those of Mean-CVaR and
Mean-CVaR-$\ell_{1}$ on FF100. Figure 2 in Supplementary A.9 shows the CW
plots of different methods on the benchmark data sets. The CW sequences of
ASMCVaR ($m=10$, red color) are steadily over others on most trade times.
Besides, ASMCVaR has increasing trends in the long run, indicating that it is
growing in wealth during the backtests.

Table 3: $\alpha$ factors with p-values of t-tests of different portfolio
optimization models on 6 benchmark data sets.

Method | FF25 | FF25EU | FF32 | FF49 | FF100 | FF100MEOP
---|---|---|---|---|---|---
$\alpha$ | p-value | $\alpha$ | p-value | $\alpha$ | p-value | $\alpha$ | p-value | $\alpha$ | p-value | $\alpha$ | p-value
1/N | 0 | 0.4318 | -0.0031 | 1 | 0.0001 | 0.3782 | 0 | 0.5487 | -0.0004 | 0.9427 | -0.0002 | 0.9083
SSMP | 0.0002 | 0.4465 | -0.0027 | 0.9992 | -0.0028 | 0.9744 | 0.0017 | 0.1935 | -0.0068 | 0.9999 | -0.0051 | 0.9983
SSPO | -0.0024 | 0.9440 | -0.0098 | 1 | -0.0046 | 0.9994 | -0.0056 | 0.9278 | -0.0100 | 0.9999 | -0.0071 | 0.9996
SPOLC | -0.0032 | 0.9984 | -0.0103 | 1 | -0.0011 | 0.8050 | -0.0037 | 0.9008 | -0.0073 | 1 | -0.0050 | 0.9977
S1 | -0.0027 | 0.9701 | -0.0104 | 1 | -0.0049 | 0.9997 | -0.0062 | 0.9463 | -0.0110 | 1 | -0.0069 | 0.9991
S2 | -0.0029 | 0.9740 | -0.0101 | 1 | -0.0050 | 0.9996 | -0.0062 | 0.9475 | -0.0106 | 1 | -0.0072 | 0.9994
S3 | -0.0028 | 0.9738 | -0.0103 | 1 | -0.0049 | 0.9997 | -0.0062 | 0.9465 | -0.0110 | 1 | -0.0068 | 0.9991
Mean-CVaR | 0.0009 | 0.1133 | -0.0014 | 0.9216 | 0.0019 | 0.0183 | 0.0025 | 0.0098 | -0.0006 | 0.7222 | 0.0017 | 0.0405
Mean-CVaR-$\ell_{1}$ | 0.0015 | 0.0339 | -0.0011 | 0.8947 | 0.0017 | 0.0300 | 0.0027 | 0.0065 | 0 | 0.4987 | 0.0006 | 0.2969
MT-CVaR | -0.0041 | 0.9984 | -0.0090 | 1 | -0.0067 | 1 | -0.0044 | 0.8979 | -0.0105 | 1 | -0.0050 | 0.9891
ASMCVaR($m=10$) | 0.0022 | 0.0006 | 0.0027 | 0 | 0.0027 | 0.0002 | 0.0029 | 0.0049 | 0.0023 | 0.0038 | 0.0020 | 0.0060
ASMCVaR($m=15$) | 0.0019 | 0.0029 | 0.0027 | 0 | 0.0025 | 0.0001 | 0.0024 | 0.0112 | 0.0025 | 0.0012 | 0.0017 | 0.0109
ASMCVaR($m=20$) | 0.0019 | 0.0017 | 0.0025 | 0 | 0.0024 | 0.0001 | 0.0023 | 0.0098 | 0.0024 | 0.0010 | 0.0016 | 0.0114

Table 4: Final cumulative wealths of different portfolio optimization models
on 6 benchmark data sets.

Method | FF25 | FF25EU | FF32 | FF49 | FF100 |  | FF100
---
MEOP
1/N | 355.98 | 13.05 | 424.42 | 235.48 | 364.87 | 348.70
SSMP | 248.67 | 13.47 | 158.98 | 186.79 | 10.09 | 26.06
SSPO | 129.35 | 1.22 | 30.20 | 1.33 | 0.89 | 3.90
SPOLC | 57.53 | 0.96 | 169.60 | 5.44 | 2.39 | 8.23
S1 | 100.76 | 1.08 | 29.47 | 1.09 | 0.54 | 4.31
S2 | 83.10 | 1.19 | 25.93 | 1.15 | 0.66 | 3.55
S3 | 96.26 | 1.11 | 29.45 | 1.09 | 0.55 | 4.38
Mean-CVaR | 333.41 | 18.60 | 331.14 | 150.15 | 70.31 | 306.40
Mean-CVaR-$\ell_{1}$ | 440.32 | 18.58 | 332.55 | 178.93 | 102.11 | 163.77
MT-CVaR | 34.58 | 1.53 | 7.96 | 4.93 | 0.61 | 11.66
ASMCVaR($m=10$) | 973.23 | 122.82 | 1122.76 | 758.66 | 966.32 | 783.47
ASMCVaR($m=15$) | 827.18 | 123.13 | 1303.80 | 694.83 | 1126 | 712.45
ASMCVaR($m=20$) | 872.03 | 113.28 | 1317.01 | 767.61 | 1117.20 | 714.49

###  4.3 $\alpha$ Factor

According to the Capital Asset Pricing Model (CAPM, Sharpe 1964), a portfolio
cannot exclude the influence from the underlying financial market. To derive a
pure excess return to the market, the $\alpha$ factor is proposed (Lintner,
1965) and becomes a popular score for the relative performance to the market.
Let $r_{s}$ and $r_{m}$ denote the returns for a nontrivial strategy and the
Market strategy, respectively. The portfolio return $r_{s}$ can be decomposed
into the market return component $r_{m}$ and the $\alpha$ factor:

$\mathbb{E}\left(r_{s}\right)=\beta\mathbb{E}\left(r_{m}\right)+\alpha.$

$\beta$ and $\alpha$ can be computed by the linear regression:

$\hat{\beta}=\frac{\hat{c}\left(r_{s},r_{m}\right)}{\hat{\sigma}^{2}\left(r_{m}\right)},\quad\hat{\alpha}=\bar{r}_{s}-\hat{\beta}\bar{r}_{m},$

where $\hat{c}(\cdot,\cdot)$ and $\hat{\sigma}^{2}(\cdot)$ are the sample
covariance and variance, respectively. $\bar{r}_{s}$ denotes the sample mean,
which can be computed by
$\bar{r}_{s}=\frac{1}{\mathscr{T}}\sum_{t=1}^{\mathscr{T}}{r}_{s}^{(t)}$,
where ${r}_{s}^{(t)}=(\mathbf{x}^{(t)})^{\top}\hat{\bm{w}}_{s}^{(t)}-1$ and
$\hat{\bm{w}}_{s}^{(t)}$ is the portfolio of this nontrivial strategy at time
$t$. $\bar{r}_{m}$ can be computed likewise. We adopt the uniform-buy-and-hold
strategy (Li et al., 2016) as the conventional representative of the market
return. To test whether $\alpha>0$ is statistically significant, the right-
tailed t-test can also be implemented.

Table 3 shows the $\alpha$ factors with p-values of t-tests of different
methods. ASMCVaR($m=10$) achieves the highest $\alpha$s among all the compared
methods on all 6 data sets. Moreover, ASMCVaR($m=10$) achieves positive
$\alpha$s at the significance level of $1\%$ in all the cases, since all the
p-values are smaller than $1\%$. Hence ASMCVaR obtains positive excess returns
to the market with high statistical significance.

###  4.4 Sharpe Ratio

Since an investor usually has to take a higher risk to obtain a higher return
in financial markets, it is necessary to develop risk-adjusted returns to
evaluate this balancing performance. The Sharpe ratio (SR, Sharpe 1966) is
such a metric that takes the ratio between return and risk of a strategy:

$SR=\frac{\bar{r}_{s}-r_{f}}{\hat{\sigma}\left(r_{s}\right)},$

where the risk-free return is set as $r_{f}=0$ in this paper. The (monthly)
SRs for different methods on the 6 data sets are shown in Table 5. ASMCVaR
with $m=10$, $m=15$ or $m=20$ achieves the highest SRs among all the
competitors on all the data sets. For example, the SRs of ASMCVaR are about
$45.7\%$ higher than those of Mean-CVaR and Mean-CVaR-$\ell_{1}$ on FF25EU.
These results indicate that ASMCVaR performs well in balancing return and
risk.

Table 5: Sharpe ratios of different portfolio optimization models on 6
benchmark data sets.

Method | FF25 | FF25EU | FF32 | FF49 | FF100 |  | FF100
---
MEOP
1/N | 0.2278 | 0.1576 | 0.2236 | 0.2059 | 0.2089 | 0.2077
SSMP | 0.1935 | 0.1598 | 0.1536 | 0.1659 | 0.0883 | 0.1085
SSPO | 0.1545 | 0.0412 | 0.1182 | 0.0588 | 0.0425 | 0.0685
SPOLC | 0.1453 | 0.0316 | 0.1735 | 0.0753 | 0.0563 | 0.0864
S1 | 0.1498 | 0.0370 | 0.1169 | 0.0559 | 0.0327 | 0.0709
S2 | 0.1446 | 0.0408 | 0.1137 | 0.0571 | 0.0367 | 0.0670
S3 | 0.1486 | 0.0381 | 0.1170 | 0.0559 | 0.0331 | 0.0712
Mean-CVaR | 0.2305 | 0.1803 | 0.2375 | 0.2220 | 0.1738 | 0.2204
Mean-CVaR-$\ell_{1}$ | 0.2392 | 0.1862 | 0.2330 | 0.2262 | 0.1815 | 0.1939
MT-CVaR | 0.1251 | 0.0505 | 0.0844 | 0.0767 | 0.0325 | 0.0911
ASMCVaR($m=10$) | 0.2610 | 0.2758 | 0.2638 | 0.2339 | 0.2446 | 0.2363
ASMCVaR($m=15$) | 0.2541 | 0.2765 | 0.2615 | 0.2286 | 0.2503 | 0.2326
ASMCVaR($m=20$) | 0.2558 | 0.2713 | 0.2603 | 0.2300 | 0.2501 | 0.2322

###  4.5 Transaction Cost

The transaction cost with portfolio change is inevitable in practical
portfolio management. We adopt the proportional transaction cost model (Blum &
Kalai, 1999; Lai & Yang, 2023) to compute the CW at the beginning of the
$t$-th trade time:

$\displaystyle
S^{(\mathscr{T})}{=}S^{(0)}\prod_{t=1}^{\mathscr{T}}\bigg{[}\big{(}(\mathbf{x}^{(t)})^{\top}\hat{\bm{w}}^{(t)}\big{)}\Big{(}1{-}\frac{\nu}{2}\sum_{i=1}^{N}\big{|}\hat{w}_{i}^{(t)}{-}\tilde{w}_{i}^{(t-1)}\big{|}\Big{)}\bigg{]},$
$\displaystyle\tilde{w}_{i}^{(t-1)}=\frac{\hat{w}_{i}^{(t-1)}\cdot\mathrm{x}_{i}^{(t-1)}}{(\mathbf{x}^{(t-1)})^{\top}\hat{\bm{w}}^{(t-1)}},$

where $\tilde{w}_{i}^{(t-1)}$ denotes the evolved portfolio weight of the
$i$-th asset at the end of the $(t-1)$-th trade time, and
$\tilde{\bm{w}}^{(0)}$ can be initialized as $\bm{0}_{N}$. $\nu$ is the
bidirectional transaction cost rate, which is examined in the range
$[0,0.5\%]$. When the cost rates of buying and selling are the same, changing
the evolved portfolio $\tilde{\bm{w}}^{(t-1)}$ to the next portfolio
$\tilde{\bm{w}}^{(t)}$ yields a proportional transaction cost of
$\frac{\nu}{2}\sum_{i=1}^{N}\big{|}\hat{w}_{i}^{(t)}-\tilde{w}_{i}^{(t-1)}\big{|}$.

When $\nu$ changes from $0$ to $0.5\%$, the final CWs for different methods
are plotted in Figure 3 of Supplementary A.10. ASMCVaR outperforms all the
other competitors on all the data sets with all $\nu$, showing a good
performance against the transaction cost. Note that the 1/N strategy is well
known for its little turnover rate mechanism, but ASMCVaR still has an
advantage over 1/N, especially with low and medium cost rates. Moreover, if a
mutual fund has sufficient capital, then the transaction cost rate $\nu$ can
be negotiated to be low. Hence ASMCVaR is effective in practical portfolio
management with transaction cost.

##  5 Conclusion

We develop an autonomous sparse mean-CVaR (ASMCVaR) model for portfolio
optimization. It aims to optimize a mean-CVaR objective function under the
$\ell_{0}$ and the simplex constraints for exact and feasible asset selection.
It is an NP-hard problem and the existing combinatorial approach requires a
high computational cost. From a markedly different perspective, we propose to
convert the $\ell_{0}$ constraint into an indicator function and handle it
with a tailed approximation. By this way, ASMCVaR can approximate the
$\ell_{0}$-constrained mean-CVaR model to arbitrary accuracy. We also develop
a proximal alternating linearized minimization algorithm, coupled with a
nested fixed-point proximity algorithm (both convergent) to iteratively solve
ASMCVaR. It has a good property of autonomous sparsity because a large
proportion of assets can remain in the selected asset pool when adjusting the
pool size. Experimental results show that ASMCVaR achieves state-of-the-art
performance in several common evaluating metrics of investing performance and
risk control.

A direct impact of ASMCVaR is to provide a novel tailed approximation approach
to the long-standing NP-hard $\ell_{0}$-constrained problem. It can be
conveniently transferred to other related $\ell_{0}$-constrained problems via
similar establishment. Further improvements on ASMCVaR may lie in accelerating
the solving algorithm with momentum methods, generalizing the objective
function to a broader class of functions, or considering more constraints with
practical sense.

## Acknowledgements

The authors thank the anonymous reviewers for their constructive comments and
valuable suggestions in improving this paper. This work was supported in part
by National Natural Science Foundation of China under Grant 62176103, in part
by Guangdong Basic and Applied Basic Research Foundation under Grant
2021A1515110541, and in part by the Science and Technology Planning Project of
Guangzhou under Grants 2024A04J3940 and 2024A04J9896.

## References

  * Ao et al. (2019) Ao, M., Li, Y., and Zheng, X.  Approaching mean-variance efficiency for large portfolios.  _The Review of Financial Studies_ , 32(7):2890–2919, 2019.
  * Artzner et al. (1999) Artzner, P., Delbaen, F., Eber, J.-M., and Heath, D.  Coherent measures of risk.  _Mathematical Finance_ , 9(3):203–228, 1999.
  * Attouch et al. (2013) Attouch, H., Bolte, J., and Svaiter, B. F.  Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods.  _Mathematical Programming_ , 137(1):91–129, 2013\.
  * Ban et al. (2018) Ban, G.-Y., Karoui, N. E., and Lim, A. E. B.  Machine learning and portfolio optimization.  _Management Science_ , 64(3):1136–1154, Mar. 2018\.
  * Bertsimas & Cory-Wright (2022) Bertsimas, D. and Cory-Wright, R.  A scalable algorithm for sparse portfolio selection.  _INFORMS Journal on Computing_ , 34(3):1489–1511, 2022.
  * Blum & Kalai (1999) Blum, A. and Kalai, A.  Universal portfolios with and without transaction costs.  _Machine Learning_ , 35(3):193–205, 1999.
  * Bolte et al. (2014) Bolte, J., Sabach, S., and Teboulle, M.  Proximal alternating linearized minimization for nonconvex and nonsmooth problems.  _Mathematical Programming_ , 146(1):459–494, 2014\.
  * Brodie et al. (2009) Brodie, J., Daubechies, I., Mol, C. D., Giannone, D., and Loris, I.  Sparse and stable Markowitz portfolios.  _Proceedings of the National Academy of Sciences of the United States of America_ , 106(30):12267–12272, Jul. 2009.
  * Chao et al. (2009) Chao, R. O., Kavadias, S., and Gaimon, C.  Revenue driven resource allocation: Funding authority, incentives, and new product development portfolio management.  _Management Science_ , 55(9):1556–1569, 2009\.
  * Cheng & Gao (2015) Cheng, R. and Gao, J.  On cardinality constrained mean-cvar portfolio optimization.  In _The 27th Chinese Control and Decision Conference (2015 CCDC)_ , pp. 1074–1079, 2015.
  * Cover (1991) Cover, T. M.  Universal portfolios.  _Mathematical Finance_ , 1(1):1–29, Jan. 1991\.
  * DeMiguel et al. (2009) DeMiguel, V., Garlappi, L., and Uppal, R.  Optimal versus naive diversification: How inefficient is the 1/N portfolio strategy?  _The Review of Financial Studies_ , 22(5):1915–1953, May 2009.
  * Dimmock et al. (2023) Dimmock, S. G., Wang, N., and Yang, J.  The endowment model and modern portfolio theory.  _Management Science_ , pp. 1–26, Apr. 2023.  doi: 10.1287/mnsc.2023.4759.
  * Efron et al. (2004) Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R.  Least angle regression.  _Annals of Statistics_ , 32(2):407–451, 2004\.
  * Goto & Xu (2015) Goto, S. and Xu, Y.  Improving mean variance optimization through sparse hedging restrictions.  _The Journal of Financial and Quantitative Analysis_ , 50(6):1415–1441, 2015.
  * Gotoh & Takeda (2011) Gotoh, J.-Y. and Takeda, A.  On the role of norm constraints in portfolio selection.  _Computational Management Science_ , 8:323–353, 2011.
  * Günlük & Linderoth (2010) Günlük, O. and Linderoth, J.  Perspective reformulations of mixed integer nonlinear programs with indicator variables.  _Mathematical Programming_ , 124(1):183–205, 2010\.
  * Jorion (1997) Jorion, P.  _Value at Risk: The New Benchmark for Managing Financial Risk_.  McGraw-Hill, New York, 1997.
  * Kobayashi et al. (2021) Kobayashi, K., Takano, Y., and Nakata, K.  Bilevel cutting-plane algorithm for cardinality-constrained mean-cvar portfolio optimization.  _Journal of Global Optimization_ , 81(2):493–528, 2021.
  * Lai & Yang (2023) Lai, Z.-R. and Yang, H.  A survey on gaps between mean-variance approach and exponential growth rate approach for portfolio optimization.  _ACM Computing Surveys_ , 55(2):1–36, Mar. 2023\.  Article No. 25.
  * Lai et al. (2018) Lai, Z.-R., Yang, P.-Y., Fang, L., and Wu, X.  Short-term sparse portfolio optimization based on alternating direction method of multipliers.  _Journal of Machine Learning Research_ , 19(63):1–28, Oct. 2018.
  * Lai et al. (2020) Lai, Z.-R., Tan, L., Wu, X., and Fang, L.  Loss control with rank-one covariance estimate for short-term portfolio optimization.  _Journal of Machine Learning Research_ , 21(97):1–37, Jun. 2020.
  * Lai et al. (2022) Lai, Z.-R., Li, C., Wu, X., Guan, Q., and Fang, L.  Multitrend conditional value at risk for portfolio optimization.  _IEEE Transactions on Neural Networks and Learning Systems_ , pp. 1–14, 2022.  doi: 10.1109/TNNLS.2022.3183891.
  * Li et al. (2016) Li, B., Sahoo, D., and Hoi, S. C.  OLPS: a toolbox for on-line portfolio selection.  _Journal of Machine Learning Research_ , 17(1):1242–1246, 2016.
  * Lintner (1965) Lintner, J.  The valuation of risk assets and the selection of risky investments in stock portfolios and capital budgets.  _Review of Economics and Statistics_ , 47(1):13–37, Feb. 1965.
  * Liu & Loewenstein (2013) Liu, H. and Loewenstein, M.  Market crashes, correlated illiquidity, and portfolio choice.  _Management Science_ , 59(3):715–732, 2013.
  * Luo et al. (2020) Luo, Z., Yu, X., Xiu, N., and Wang, X.  Closed-form solutions for short-term sparse portfolio optimization.  _Optimization_ , 2020.
  * Markowitz (1952) Markowitz, H. M.  Portfolio selection.  _Journal of Finance_ , 7(1):77–91, Mar. 1952\.
  * Micchelli et al. (2011) Micchelli, C. A., Shen, L., and Xu, Y.  Proximity algorithms for image models: denoising.  _Inverse Problems_ , 27(4):045009, 2011.
  * Ogryczak & Ruszczyński (2002) Ogryczak, W. and Ruszczyński, A.  Dual stochastic dominance and related mean-risk models.  _SIAM Journal on Optimization_ , 13:60–78, 2002.
  * Rockafellar & Uryasev (2000) Rockafellar, R. T. and Uryasev, S.  Optimization of conditional value-at-risk.  _Journal of Risk_ , 2(3):21–41, 2000.
  * Sharpe (1964) Sharpe, W. F.  Capital asset prices: A theory of market equilibrium under conditions of risk.  _Journal of Finance_ , 19(3):425–442, Sep. 1964\.
  * Sharpe (1966) Sharpe, W. F.  Mutual fund performance.  _Journal of Business_ , 39(1):119–138, Jan. 1966\.
  * Tibshirani (1996) Tibshirani, R.  Regression shrinkage and selection via the lasso.  _Journal of the Royal Statistical Society_ , 58(1):267–288, 1996.

##  Appendix A Supplementary Materials

###  A.1 Proof of Lemma 3.2

###### Proof.

For the case $\|\bm{w}^{*}\|_{0}\leqslant m$, it is obvious that (30) holds,
since $w_{j}^{*}=0$ for all $j\in\mathbb{N}_{N}\backslash J_{\bm{w}^{*}}^{m}$.
We then consider the case $\|\bm{w}^{*}\|_{0}>m$. In this case, we construct
an approximation
$\tilde{\bm{v}}:=(\tilde{\bm{w}}^{\top},\tilde{\tau},\tilde{\bm{z}}^{\top})^{\top}\in\mathbb{R}^{N_{1}}$
of $\bm{v}^{*}:=((\bm{w}^{*})^{\top},\tau^{*},(\bm{z}^{*})^{\top})^{\top}$
such that it satisfies the constraints of (25), that is, the constraints of
(14). Note that $\bm{v}^{*}$ satisfies that $\bm{Q}\bm{v}^{*}\geqslant\bm{q}$.
We let $\tilde{w}_{j}=w_{j}^{*}$ for $j\in
J_{\bm{w}^{*}}^{m}\backslash\\{j_{1}\\}$, $\tilde{w}_{j}=0$ for
$j\in\mathbb{N}_{N}\backslash J_{\bm{w}^{*}}^{m}$ and
$\tilde{w}_{j_{1}}=w_{j_{1}}^{*}+\sum\limits_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}^{*}}^{m}}w_{j}^{*}$. Then $\tilde{\bm{w}}\in\Delta$ and
$\|\tilde{\bm{w}}\|_{0}\leqslant m$. For $\tilde{\bm{z}}$ and $\tilde{\tau}$,
we define $\delta:=\max\limits_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}^{*}}^{m}}\\{w_{j}^{*}\\}$ and
$\zeta:=\max\limits_{i\in\mathbb{N}_{T},j\in\mathbb{N}_{N}}\\{|r_{i,j}-r_{i,j_{1}}|\\}$,
where $r_{i,j}$ is the $(i,j)$th component of matrix $\bm{R}$ in model (29),
and then let $\tilde{\bm{z}}=\bm{z}^{*}$, $\tilde{\tau}=\tau^{*}+\delta\zeta$.
It is obvious that $\tilde{\bm{z}}\geqslant{\bm{0}}_{T}$ since
$\bm{z}^{*}\geqslant{\bm{0}}_{T}$. To show that
$\bm{Q}\tilde{\bm{v}}\geqslant\bm{q}$, it remains to be shown that

$\tilde{\tau}{\bm{1}}_{T}\geqslant-\tilde{\bm{z}}-\bm{R}\tilde{\bm{w}}.$ (39)

Note that
$\bm{R}\bm{w}^{*}-\bm{R}\tilde{\bm{w}}=\sum\limits_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}^{*}}^{m}}w_{j}^{*}\left(\bm{r}^{(j)}-\bm{r}^{(j_{1})}\right)$, where
$\bm{r}^{(j)}$ is the $j$th column of $\bm{R}$. From the definitions of
$\delta$ and $\zeta$, we have that

$\tilde{\tau}{\bm{1}}_{T}\geqslant\tau^{*}{\bm{1}}_{T}+\sum_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}^{*}}^{m}}w_{j}^{*}\left(\bm{r}^{(j)}-\bm{r}^{(j_{1})}\right)=\tau^{*}{\bm{1}}_{T}+\bm{R}\bm{w}^{*}-\bm{R}\tilde{\bm{w}}.$
(40)

Then (39) follows from (40) and the fact
$\tau^{*}{\bm{1}}_{T}\geqslant-\bm{z}^{*}-\bm{R}\bm{w}^{*}$.

Now we know that $\tilde{\iota}_{m,\gamma}(\tilde{\bm{w}})=0$ and
$\iota_{\bm{q}}(\bm{Q}\tilde{\bm{v}})=0$. Hence

$\Psi(\tilde{\bm{v}})=f(\tilde{\bm{v}}).$ (41)

The fact $\bm{w}^{*}\in\Delta$ gives that
$\|\bm{w}^{*}\|_{2}\leqslant\sqrt{\|\bm{w}^{*}\|_{1}}=1$, where
$\|\cdot\|_{2}$ and $\|\cdot\|_{1}$ denote the $\ell_{2}$ and $\ell_{1}$
norms, respectively. Similarly, we also have $\|\tilde{\bm{w}}\|_{2}\leqslant
1$. In addition,

$\|\bm{w}^{*}-\tilde{\bm{w}}\|_{2}^{2}=\left(\sum_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}^{*}}^{m}}w_{j}^{*}\right)^{2}+\sum_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}^{*}}^{m}}(w_{j}^{*})^{2}\leqslant[(N-m)^{2}+(N-m)]\delta^{2}$

Then it follows from the definition of function $f$ in (26) that

$\displaystyle|f(\bm{v}^{*})-f(\tilde{\bm{v}})|$
$\displaystyle=|(\tau^{*}-\tilde{\tau})+\lambda({\bm{\mu}}^{\top}\bm{w}^{*}-\rho)^{2}-\lambda({\bm{\mu}}^{\top}\tilde{\bm{w}}-\rho)^{2}|$
$\displaystyle\leqslant\delta\zeta+\lambda|{\bm{\mu}}^{\top}(\bm{w}^{*}+\tilde{\bm{w}})-2\rho)|\cdot|{\bm{\mu}}^{\top}(\bm{w}^{*}-\tilde{\bm{w}})|$
$\displaystyle\leqslant\delta\zeta+\lambda\left(2\|\bm{\mu}\|_{2}+2\rho\right)\|\bm{\mu}\|_{2}\|\bm{w}^{*}-\tilde{\bm{w}}\|_{2}$
$\displaystyle\leqslant\tilde{L}\delta\leqslant\tilde{L},$ (42)

where

$\tilde{L}:=\zeta+2\lambda\sqrt{[(N-m)^{2}+(N-m)]}\left(\|\bm{\mu}\|_{2}^{2}+\rho\|\bm{\mu}\|_{2}\right).$
(43)

This together with (41) and the fact
$\Psi(\bm{v}^{*})\leqslant\Psi(\tilde{\bm{v}})$ yields that

$f(\bm{v}^{*})+\tilde{L}\geqslant
f(\tilde{\bm{v}})\geqslant\Psi(\bm{v}^{*})=f(\bm{v}^{*})+\tilde{\iota}_{m,\gamma}(\bm{w}^{*})\geqslant
f(\bm{v}^{*})+\frac{1}{2\gamma}\delta^{2}.$

Thus $\delta\leqslant\sqrt{2\tilde{L}\gamma}$, which implies the desired
result. ∎

###  A.2 Proof of Theorem 3.3

###### Proof.

For the case $\|\tilde{\bm{I}}\bm{v}^{*}\|_{0}\leqslant m$, since
$\tilde{\iota}_{m,\gamma}(\widetilde{\bm{I}}\bm{v}^{*})=\iota_{m}(\widetilde{\bm{I}}\bm{v}^{**})=0$
and $\iota_{\bm{q}}(\bm{Q}\bm{v}^{*})=\iota_{\bm{q}}(\bm{Q}\bm{v}^{**})=0$, it
is obvious that $f(\bm{v}^{*})=f(\bm{v}^{**})$, and hence (31) holds. For the
case $\|\tilde{\bm{I}}\bm{v}^{*}\|_{0}>m$, we define $\tilde{\bm{v}}$ as an
approximation of $\bm{v}^{*}$, following the same definition as in the proof
of Lemma 3.2. Then $\bm{Q}\tilde{\bm{v}}\geqslant\bm{q}$ and
$\|\tilde{\bm{I}}\tilde{\bm{v}}\|_{0}\leqslant m$. Further,
$f(\bm{v}^{**})\leqslant f(\tilde{\bm{v}})$. By Lemma 3.2 and the inequality
(42) in its proof, we know that
$|f(\bm{v}^{*})-f(\tilde{\bm{v}})|\leqslant\tilde{L}\delta\leqslant\sqrt{2\tilde{L}^{3}\gamma}$,
where $\tilde{L}$ is defined by (43) and
$\delta:=\max\limits_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}^{*}}^{m}}\\{w_{j}^{*}\\}$. Thus

$f(\bm{v}^{**})\leqslant f(\tilde{\bm{v}})\leqslant
f(\bm{v}^{*})+\sqrt{2\tilde{L}^{3}\gamma}.$ (44)

The prerequisite $\bm{v}^{*}$ and $\bm{v}^{**}$ are solutions of models (29)
and (27) gives that $\Psi(\bm{v}^{*})\leqslant\Psi(\bm{v}^{**})$ and
$\Psi(\bm{v}^{**})=f(\bm{v}^{**})$. Hence

$f(\bm{v}^{*})\leqslant\Psi(\bm{v}^{*})\leqslant f(\bm{v}^{**}).$ (45)

Now (31) can be obtained by (44) and (45) directly. This completes the proof.
∎

###  A.3 Proof of Lemma 3.4

###### Proof.

Since $(\bm{v}^{*},\bm{y}^{*})$ is a solution of model (32), we have that
$\|\bm{y}^{*}\|_{0}\leqslant m$ and

$G(\bm{v}^{*},\bm{y}^{*})\leqslant G(\bm{v}^{*},\bm{y}),\
\forall\bm{y}\in\mathbb{R}^{N}.$ (46)

Subtracting $f(\bm{v}^{*})+\iota_{\bm{q}}(\bm{Q}\bm{v}^{*})$ on both sides of
(46) yields that

$\frac{1}{2\gamma}\|\widetilde{\bm{I}}\bm{v}^{*}-\bm{y}^{*}\|_{2}^{2}+\iota_{m}(\bm{y}^{*})\leqslant\frac{1}{2\gamma}\|\widetilde{\bm{I}}\bm{v}^{*}-\bm{y}\|_{2}^{2}+\iota_{m}(\bm{y}),\
\forall\bm{y}\in\mathbb{R}^{N}.$ (47)

Let $\bm{w}^{*}:=\tilde{\bm{I}}\bm{v}^{*}$. Then (47) implies that

$\|\bm{w}^{*}-\bm{y}^{*}\|_{2}^{2}\leqslant\|\bm{w}^{*}-\bm{y}\|_{2}^{2},\
\forall\bm{y}\in\Omega_{m}.$ (48)

We consider two cases for $\bm{w}^{*}$. If $\bm{w}^{*}\in\Omega_{m}$, (48)
implies that $\bm{y}^{*}=\bm{w}^{*}$, that is,
$\bm{y}^{*}=\mathcal{S}_{m}(\bm{w}^{*})$.

We then consider the case $\bm{w}^{*}\notin\Omega_{m}$. In this case, we have
$\|\bm{y}^{*}\|_{0}=m$. Suppose not, then $\|\bm{y}^{*}\|_{0}<m$. Since
$\bm{w}^{*}\notin\Omega_{m}$, we know that $\bm{w}^{*}$ has at least $m+1$
nonzero components. Hence there exists some $j^{\prime}\in\mathbb{N}_{N}$ such
that $y_{j^{\prime}}^{*}=0$ and $w_{j^{\prime}}^{*}\neq 0$. By letting
$\bm{y}\in\Omega_{m}$ such that

$y_{j^{\prime}}=w_{j^{\prime}}^{*}\ \ \mbox{and}\ \ y_{j}=y_{j}^{*}\
\mbox{for}\ j\in\mathbb{N}_{N}\backslash\\{j^{\prime}\\},$ (49)

then

$\|\bm{w}^{*}-\bm{y}^{*}\|^{2}-\|\bm{w}^{*}-\bm{y}\|^{2}=(w_{j^{\prime}}^{*}-y_{j^{\prime}}^{*})^{2}>0,$
(50)

which contradicts (48). Thus $\|\bm{y}^{*}\|_{0}=m$. Note that the components
in $\bm{w}^{*}$ may not be distinct. We let
$J_{1},J_{2},J_{3}\subset\mathbb{N}_{N}$ be three index sets such that
$|w_{j}^{*}|>|w_{j_{m}}^{*}|$ for all $j\in J_{1}$,
$|w_{j}^{*}|=|w_{j_{m}}^{*}|$ for all $j\in J_{2}$, and
$|w_{j}^{*}|<|w_{j_{m}}^{*}|$ for all $j\in J_{3}$, respectively.

$(i)$ We first prove that $y_{j}^{*}=w_{j}^{*}$ for all $j\in J_{1}$ if
$J_{1}\neq\varnothing$. To this end, we show that $y_{j}^{*}\neq 0$ for all
$j\in J_{1}$. Assume that there exists some $j^{\prime}\in J_{1}$ such that
$y_{j^{\prime}}^{*}=0$. Since $\|\bm{y}^{*}\|_{0}=m$, there must be some
$j^{\prime\prime}\in\mathbb{N}_{N}\backslash J_{1}$ such that
$y_{j^{\prime\prime}}^{*}\neq 0$. Note that
$|w_{j^{\prime}}^{*}|>|w_{j^{\prime\prime}}^{*}|$. By letting
$\bm{y}\in\Omega_{m}$ such that

$y_{j^{\prime}}=w_{j^{\prime}}^{*},\ y_{j^{\prime\prime}}=0\ \mbox{and}\
y_{j}=y_{j}^{*}\ \mbox{for}\
j\in\mathbb{N}_{N}\backslash\\{j^{\prime},j^{\prime\prime}\\},$ (51)

then

$\|\bm{w}^{*}-\bm{y}^{*}\|_{2}^{2}-\|\bm{w}^{*}-\bm{y}\|_{2}^{2}=(w_{j^{\prime}}^{*})^{2}+(w_{j^{\prime\prime}}^{*}-y_{j^{\prime\prime}}^{*})^{2}-(w_{j^{\prime\prime}}^{*})^{2}>0,$
(52)

which contradicts (48). Hence $y_{j}^{*}\neq 0$ for all $j\in J_{1}$. Now we
are able to prove by contradiction that $y_{j}^{*}=w_{j}^{*}$ for all $j\in
J_{1}$. Assume that there exists $j^{\prime}\in J_{1}$ such that
$y_{j}^{*}\neq w_{j^{\prime}}^{*}$. Since $y_{j^{\prime}}^{*}\neq 0$, letting
$\bm{y}\in\mathbb{R}^{N}$ be given by (49), then $\bm{y}\in\Omega_{m}$ and
(50) holds, which contradicts (48). Hence $y_{j}^{*}=w_{j}^{*}$ for all $j\in
J_{1}$.

$(ii)$ We next prove that $y_{j}^{*}=0$ for all $j\in J_{3}$ if
$J_{3}\neq\varnothing$. Otherwise, there exists $j^{\prime\prime}\in J_{3}$
such that $y_{j^{\prime\prime}}^{*}\neq 0$. Note that the number of elements
in $J_{1}\cup J_{2}=\mathbb{N}_{N}\backslash J_{3}$ is greater than or equal
to $m$. To guarantee that $\|\bm{y}^{*}\|_{0}=m$, there must be some
$j^{\prime}\in\mathbb{N}_{N}\backslash J_{3}$ such that
$y_{j^{\prime}}^{*}=0$. In this case, we let $\bm{y}\in\Omega_{m}$ be given by
(51). Note that $|w_{j^{\prime}}^{*}|>|w_{j^{\prime\prime}}^{*}|$. We have
that (52) holds, which contradicts (48). Hence $y_{j}^{*}=0$ for all $j\in
J_{3}$.

Note that $J_{1}\subsetneqq J_{\bm{w}^{*}}^{m}$, $J_{\bm{w}^{*}}^{m}\backslash
J_{1}\subset J_{2}$. In addition, $\bm{w}^{*}\notin\Omega_{m}$ implies that
$w_{j}^{*}\neq 0$ for all $j\in J_{1}\cup J_{2}$. Let
$m_{1}\in\\{0,1,\ldots,m-1\\}$ be the number of elements in $J_{1}$. The fact
$\|\bm{y}^{*}\|_{0}=m$ together with $(i)$ and $(ii)$ implies that there must
be an index set $J_{2}^{\prime}\subset J_{2}$ with $(m-m_{1})$ components such
that $y_{j}^{*}\neq 0$ for $j\in J_{2}^{\prime}$ and $y_{j}^{*}=0$ for $j\in
J_{2}\backslash J_{2}^{\prime}$. As shown in $(i)$, we can also prove that
$y_{j}^{*}=w_{j}^{*}$ for $j\in J_{2}^{\prime}$. Now by setting $J=J_{1}\cup
J_{2}^{\prime}$, then it is an $m$-LAV index set of $\bm{w}$. In addition, we
see from (35) that $\bm{y}^{*}=\mathcal{S}_{m}(\widetilde{\bm{I}}\bm{v}^{*})$,
which completes the proof. ∎

###  A.4 Proof of Lemma 3.5

###### Proof.

Let $\bm{w}:=\widetilde{\bm{I}}\bm{v}$. We first prove that

$\|\tilde{\bm{y}}-\bm{w}\|_{2}^{2}\leqslant\|\bm{y}-\bm{w}\|_{2}^{2},\
\forall\bm{y}\in\Omega_{m}.$ (53)

If $\bm{w}\in\Omega_{m}$, then it is easy to see from the definition (35) of
operator $\mathcal{S}_{m}$ that $\tilde{\bm{y}}=\bm{w}$ and hence (53) holds.
For the case $\bm{w}\notin\Omega_{m}$, since
$\tilde{\bm{y}}=\mathcal{S}_{m}(\widetilde{\bm{I}}\bm{v})$, we know that
$\tilde{\bm{y}}\in\Omega_{m}$ and

$\|\tilde{\bm{y}}-\bm{w}\|_{2}^{2}=\sum_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}}^{m}}w_{j}^{2}.$ (54)

For any $\bm{y}\in\Omega_{m}$, there exists an index set
$J_{\bm{y}}\subset\mathbb{N}_{N}$ with $m$ elements such that $y_{j}=0$ for
all $j\in\mathbb{N}_{N}\backslash J_{\bm{y}}$. Since $J_{\bm{w}}^{m}$ contains
the $m$ largest components of $\bm{w}$ in absolute value, we have that
$\sum\limits_{j\in J_{\bm{w}}^{m}}w_{j}^{2}\geqslant\sum\limits_{j\in
J_{\bm{y}}}w_{j}^{2}$, which together with (54) implies that

$\|\bm{y}-\bm{w}\|_{2}^{2}\geqslant\sum_{j\in\mathbb{N}_{N}\backslash
J_{\bm{y}}}w_{j}^{2}\geqslant\sum_{j\in\mathbb{N}_{N}\backslash
J_{\bm{w}}^{m}}w_{j}^{2}=\|\tilde{\bm{y}}-\bm{w}\|_{2}^{2}.$

This completes the proof of (53). Now by (53), we have

$\frac{1}{2\gamma}\|\tilde{\bm{y}}-\widetilde{\bm{I}}\bm{v}\|_{2}^{2}+\iota_{m}(\tilde{\bm{y}})\leqslant\frac{1}{2\gamma}\|\bm{y}-\widetilde{\bm{I}}\bm{v}\|_{2}^{2}+\iota_{m}(\bm{y}),\
\forall\bm{y}\in\mathbb{R}^{N}.$ (55)

Adding $f(\bm{v})+\iota_{\bm{q}}(\bm{Q}\bm{v})$ on both sides of (55) yields
(36) immediately. ∎

###  A.5 Proof of Theorem 3.6

###### Proof.

Let $\bm{w}:=\tilde{\bm{I}}\bm{v}$. The definition of
$\tilde{\iota}_{m,\gamma}$ in (28) implies that
$\tilde{\iota}_{m,\gamma}(\bm{w})=\frac{1}{2\gamma}\|\bm{w}-\mathcal{S}_{m}(\bm{w})\|_{2}^{2}$.
Then for $\bm{y}=\mathcal{S}_{m}(\bm{w})$, we know that $\iota_{m}(\bm{y})=0$
and
$\tilde{\iota}_{m,\gamma}(\bm{w})=\frac{1}{2\gamma}\|\bm{w}-\bm{y}\|_{2}^{2}$.
Hence $\Psi(\bm{v})=G(\bm{v},\bm{y})$.

Suppose that $(\bm{v}^{*},\bm{y}^{*})$ is a solution of model (32). From Lemma
3.4, we know that $\bm{y}^{*}=\mathcal{S}_{m}(\widetilde{\bm{I}}\bm{v}^{*})$,
and hence $\Psi(\bm{v}^{*})=G(\bm{v}^{*},\bm{y}^{*})$. If $\bm{v}^{*}$ is not
a solution of model (29), then there exists
$\tilde{\bm{v}}\in\mathbb{R}^{N_{1}}$ such that
$\Psi(\tilde{\bm{v}})<\Psi(\bm{v}^{*})$. In this case, we have that
$G(\tilde{\bm{v}},\tilde{\bm{y}})=\Psi(\tilde{\bm{v}})<\Psi(\bm{v}^{*})=G(\bm{v}^{*},\bm{y}^{*})$,
for any $\tilde{\bm{y}}=\mathcal{S}_{m}(\widetilde{\bm{I}}\tilde{\bm{v}})$,
which contradicts the assumption that $(\bm{v}^{*},\bm{y}^{*})$ is a solution
of model (32). This proves that $\bm{v}^{*}$ is a solution of model (29).

Conversely, suppose that $\bm{v}^{*}$ is a solution of model (29) and
$\bm{y}^{*}=\mathcal{S}_{m}(\widetilde{\bm{I}}{\bm{v}^{*}})$. We confirm that
$(\bm{v}^{*},\bm{y}^{*})$ is a solution of model (32). If it is not true,
according to Lemma 3.5, we can find vectors
$\bar{\bm{v}}\in\mathbb{R}^{N_{1}}$ and
$\bar{\bm{y}}=\mathcal{S}_{m}(\widetilde{\bm{I}}{\bar{\bm{v}}})$ such that
$G(\bar{\bm{v}},\bar{\bm{y}})<G(\bm{v}^{*},\bm{y}^{*})$. We see from (37) that
$\Psi(\bar{\bm{v}})=G(\bar{\bm{v}},\bar{\bm{y}})$ and
$\Psi(\bm{v}^{*})=G(\bm{v}^{*},\bm{y}^{*})$. Hence
$\Psi(\bar{\bm{v}})<\Psi(\bm{v}^{*})$, which contradicts that $\bm{v}^{*}$ is
a solution of model (29). This completes the proof. ∎

###  A.6 Proof of Proposition 3.7

###### Proof.

Compute that

$\displaystyle\nabla_{\bm{v}}H(\bm{v},\bm{y})=\bm{h}_{1}+2\lambda\left(\bm{h}_{2}\bm{h}_{2}^{\top}\bm{v}-\rho\bm{h}_{2}\right)+\frac{1}{\gamma}\left(\widetilde{\bm{I}}^{\top}\widetilde{\bm{I}}\bm{v}-\widetilde{\bm{I}}^{\top}\bm{y}\right),$
$\displaystyle\nabla_{\bm{y}}H(\bm{v},\bm{y})=\frac{1}{\gamma}(\bm{y}-\widetilde{\bm{I}}\bm{v}).$

Let

$L_{1}:=2\lambda\|\bm{h}_{2}\|_{2}^{2}+\frac{1}{\gamma}\ \ \mbox{and}\ \
L_{2}:=\frac{1}{\gamma}.$

Then for all $\bm{v}_{1},\bm{v}_{2}\in\mathbb{R}^{N_{1}}$ and
$\bm{y}\in\mathbb{R}^{N}$,

$\displaystyle\|\nabla_{\bm{v}}H(\bm{v}_{1},\bm{y})-\nabla_{\bm{v}}H(\bm{v}_{2},\bm{y})\|_{2}$
$\displaystyle=\left\|\left(2\lambda\bm{h}_{2}\bm{h}_{2}^{\top}+\frac{1}{\gamma}\widetilde{\bm{I}}^{\top}\widetilde{\bm{I}}\right)(\bm{v}_{1}-\bm{v}_{2})\right\|_{2}$
$\displaystyle\leqslant\left\|\left(2\lambda\bm{h}_{2}\bm{h}_{2}^{\top}+\frac{1}{\gamma}\widetilde{\bm{I}}^{\top}\widetilde{\bm{I}}\right)\right\|_{2}\cdot\|\bm{v}_{1}-\bm{v}_{2}\|_{2}$
$\displaystyle\leqslant\left(2\lambda\|\bm{h}_{2}\|_{2}^{2}+\frac{1}{\gamma}\right)\|\bm{v}_{1}-\bm{v}_{2}\|_{2}$
$\displaystyle=L_{1}\|\bm{v}_{1}-\bm{v}_{2}\|_{2}.$

For all $\bm{y}_{1},\bm{y}_{2}\in\mathbb{R}^{N}$ and
$\bm{v}\in\mathbb{R}^{N_{1}}$,

$\|\nabla_{\bm{y}}H(\bm{v},\bm{y}_{1})-\nabla_{\bm{y}}H(\bm{v},\bm{y}_{2})\|_{2}=\frac{1}{\gamma}\|\bm{y}_{1}-\bm{y}_{2}\|_{2}=L_{2}\|\bm{y}_{1}-\bm{y}_{2}\|_{2},$

which completes the proof. ∎

###  A.7 Algorithm for ASMCVaR

Algorithm 1 ASMCVaR

0: Given the sample asset price relative matrix $\bm{X}\in\mathbb{R}^{T\times
N}$; the parameters $m$ and $\lambda$; the maximum iteration numbers
$(MaxIter_{1},MaxIter_{2})$ and tolerances $(tol_{1},tol_{2})$. Set the
approximation parameter $\gamma$, the expected return level $\rho$ and the
confidence level $c$.Preparation: Compute the return matrix
$\bm{R}=\bm{X}-\bm{1}_{T\times N}$, the sample mean vector
$\hat{\bm{\mu}}=\frac{1}{T}\bm{R}^{\top}\bm{1}_{T}$. Let matrix $\bm{Q}$ and
vector $\bm{q}$ be given by (20), $\widetilde{\bm{I}}$ be given by (3.1),
$\bm{h}_{1}$ and $\bm{h}_{2}$ be given by (15). Compute the Lipschitz
constants $L_{1}=2\lambda\|\bm{h}_{2}\|_{2}^{2}+\frac{1}{\gamma}$ and
$L_{2}=\frac{1}{\gamma}$.Initialization: Given the initial vectors by
$\bm{v}^{0}=\left(\frac{1}{N}\bm{1}_{N}^{\top},\bm{0}_{1+T}^{\top}\right)^{\top}$
and $\bm{y}^{0}=\frac{1}{N}\bm{1}_{N}$. Set $\beta_{1}=\frac{0.99}{L_{1}}$ and
$\beta_{2}=\frac{0.99}{L_{2}}$ in PALM. Set
$\theta=\frac{1.99}{\|\bm{Q}\|_{2}^{2}}$ in
FPPA.repeat$\bm{p}^{k}{=}\bm{v}^{k}{-}\beta_{1}\left[\bm{h}_{1}{+}2\lambda\left(\bm{h}_{2}\bm{h}_{2}^{\top}\bm{v}^{k}{-}\rho\bm{h}_{2}\right){+}\frac{1}{\gamma}\left(\widetilde{\bm{I}}^{\top}\widetilde{\bm{I}}\bm{v}^{k}{-}\widetilde{\bm{I}}^{\top}\bm{y}^{k}\right)\right]$
repeat1\.
$\bm{x}^{l}=\bm{Q}\bm{p}^{k}+\bm{z}^{l}-\theta\bm{Q}\bm{Q}^{\top}\bm{z}^{l}$2\.
$\bm{z}^{l+1}=\bm{x}^{l}-\max\left\\{\bm{x}^{l},\bm{q}\right\\}$3\. $l=l+1$
until $\frac{\|\bm{z}^{l}-\bm{z}^{l-1}\|_{2}}{\|\bm{z}^{l-1}\|_{2}}\leqslant
tol_{1}$ or $l>MaxIter_{1}$.4.
$\bm{v}^{k+1}=\bm{p}^{k}-\theta\bm{Q}^{\top}\bm{z}^{l}$5\.
$\bm{y}^{k+1}=\mathcal{S}_{m}\left(\bm{y}^{k}-\beta_{2}\left(\frac{1}{\gamma}(\bm{y}^{k}-\widetilde{\bm{I}}\bm{v}^{k+1})\right)\right)$6\.
$k=k+1$until
$\frac{\|\bm{v}^{k}-\bm{v}^{k-1}\|_{2}}{\|\bm{v}^{k-1}\|_{2}}\leqslant
tol_{2}$ or $k>MaxIter_{2}$.

0: Portfolio $\bm{w}^{*}=\bm{v}_{1:N}^{k}$.

###  A.8 PALM for Relaxed Sparse Regression

To see the performance of the proposed relaxation technique and the PALM
algorithm for the sparse regression problem, we consider the following two
models:

$\min_{\bm{\beta}}\left\\{\frac{1}{2}\|{\bm{X}}{\bm{\beta}}-\bm{y}\|_{2}^{2}+\iota_{m}(\bm{\beta})\right\\},$
$\min_{\bm{\beta},\bm{\eta}}\left\\{\frac{1}{2}\|\bm{X}\bm{\beta}-\bm{y}\|_{2}^{2}+\frac{1}{2\gamma}\|\bm{\beta}-\bm{\eta}\|_{2}^{2}+\iota_{m}(\bm{\eta})\right\\}.$

They correspond to the original model (27) and the relaxed dual-variable
optimization model (32), respectively. We conducted two sets of experiments to
validate two aspects:

  * 1.

The equivalence of the above relaxation model and original model, in the sense
of approximation.

  * 2.

The effectiveness of the PALM algorithm for solving the relaxation model.

In these experiments, data sets comprising 50 samples are synthetically
generated according to the model $y=\bm{x}^{\top}\bm{\beta}^{*}+\epsilon$,
where $\bm{\beta}^{*}=({\bm{1}}_{3},{\bm{0}}_{7})^{\top}\in\mathbb{R}^{10}$
represents the true coefficient vector and $\epsilon$ denotes the random error
following a normal distribution $\mathcal{N}(0,1)$. The input vector
$\bm{x}\in\mathbb{R}^{10}$ is generated by a normal distribution with mean
zero and covariance matrix $\bm{\Sigma}\in\mathbb{R}^{10\times 10}$, where
$\Sigma_{ij}:=0.5^{|i-j|}$. We set the sparsity level $m$ as 3. The direct
exhaustive approach is utilized to enumerate all possible support set
configurations, totaling $C_{10}^{3}=120$ cases. By comparing the optimal
solutions corresponding to these 120 cases, we can ascertain the exact
globally optimal solutions of the aforementioned two models. The iterative
scheme of the PALM algorithm for solving the above relaxed model can be given
by

$\begin{cases}\bm{\beta}^{k+1}=\bm{\beta}^{k}-\alpha_{1}\left[\bm{X}^{\top}(\bm{X}\bm{\beta}^{k}-\bm{y})+\frac{1}{\gamma}(\bm{\beta}^{k}-\bm{\eta}^{k})\right],\\\
\bm{\eta}^{k+1}=\mathcal{S}_{m}\left(\left(1-\frac{\alpha_{2}}{\gamma}\right)\bm{\eta}^{k}+\frac{\alpha_{2}}{\gamma}\bm{\beta}^{k+1}\right),\end{cases}$

where $\mathcal{S}_{m}$ is defined by (35). Parameters $\alpha_{1}$ and
$\alpha_{2}$ are set as
$0.99\cdot\|\bm{X}^{\top}\bm{X}+\frac{1}{\gamma}\bm{I}\|_{2}^{-1}$ and
$0.99\gamma$, respectively. To ensure a better convergence, we conduct
$5\times 10^{6}$ iterations of PALM. The initial vectors for iteration are
casually chosen as $\bm{\beta}^{0}=\bm{\eta}^{0}=\bm{0}_{10}$.

To demonstrate the robustness of our findings, we repeated each of the
aforementioned two sets of experiments for 10 times, with different $\bm{X}$
and $\bm{y}$ in each run. Through the first set of experiments, we observed
that for sufficiently small $\gamma$ (e.g., $10^{-7}$), the solutions of the
original and relaxed models are identical. This suggests that as $\gamma$
tends to zero, the optimal solution of the relaxed model indeed converges to
that of the original model. In the subsequent set of experiments, we observed
that across the 10 trials, the solutions obtained by PALM consistently
approached the optimal solutions of the relaxed model to a remarkable degree.
This reflects that in certain scenarios, PALM may be capable of directly
converging to the globally optimal solution of the original nonconvex
optimization model, even though the initializations may not necessarily be
very close to the true solution.

###  A.9 Cumulative Wealth Plots (Figure 2)

(a) FF25 (b) FF25EU

(c) FF32 (d) FF49

(e) FF100 (f) FF100MEOP

Figure 2: Cumulative wealths of different portfolio optimization models along
with trade time on 6 benchmark data sets.

###  A.10 Transaction Cost Plots (Figure 3)

(a) FF25 (b) FF25EU

(c) FF32 (d) FF49

(e) FF100 (f) FF100MEOP

Figure 3: Final cumulative wealths of different portfolio optimization models
w.r.t. transaction cost rate $\nu$ on $6$ benchmark data sets.