Efficient projected gradient methods for cardinality constrained optimization

Sparse optimization has attracted increasing attention in numerous areas such as compressed sensing, financial optimization and image processing. In this paper, we first consider a special class of cardinality constrained optimization problems, which involves box constraints and a singly linear constraint. An efficient approach is provided for calculating the projection over the feasibility set after a careful analysis on the projection subproblem. Then we present several types of projected gradient methods for a general class of cardinality constrained optimization problems. Global convergence of the methods is established under suitable assumptions. Finally, we illustrate some applications of the proposed methods for signal recovery and index tracking.Especially for index tracking, we propose a new model subject to an adaptive upper bound on the sparse portfolio weights. The computational results demonstrate that the proposed projected gradient methods are efficient in terms of solution quality.     

Heuristic algorithms for the cardinality constrained efficient frontier

This paper examines the application of genetic algorithm, tabu search and simulated annealing metaheuristic approaches to finding the cardinality constrained efficient frontier that arises in financial portfolio optimisation. We consider the mean-variance model of Markowitz as extended to include the discrete restrictions of buy-in thresholds and cardinality constraints. Computational results are reported for publicly available data sets drawn from seven major market indices involving up to 1318 assets. Our results are compared with previous results given in the literature illustrating the effectiveness of the proposed metaheuristics in terms of solution quality and computation time.     

Portfolio optimization with an envelope-based multi-objective evolutionary algorithm

The problem of portfolio selection is a standard problem in financial engineering and has received a lot of attention in recent decades. Classical mean–variance portfolio selection aims at simultaneously maximizing the expected return of the portfolio and minimizing portfolio variance. In the case of linear constraints, the problem can be solved efficiently by parametric quadratic programming (i.e., variants of Markowitz’ critical line algorithm). However, there are many real-world constraints that lead to a non-convex search space, e.g., cardinality constraints which limit the number of different assets in a portfolio, or minimum buy-in thresholds. As a consequence, the efficient approaches for the convex problem can no longer be applied, and new solutions are needed.In this paper, we propose to integrate an active set algorithm optimized for portfolio selection into a multi-objective evolutionary algorithm (MOEA). The idea is to let the MOEA come up with some convex subsets of the set of all feasible portfolios, solve a critical line algorithm for each subset, and then merge the partial solutions to form the solution of the original non-convex problem. We show that the resulting envelope-based MOEA significantly outperforms existing MOEAs.     

Fuzzy turnover rate chance constraints portfolio model

One concern of many investors is to own the assets which can be liquidated easily. Thus, in this paper, we incorporate portfolio liquidity in our proposed model. Liquidity is measured by an index called turnover rate. Since the return of an asset is uncertain, we present it as a trapezoidal fuzzy number and its turnover rate is measured by fuzzy credibility theory. The desired portfolio turnover rate is controlled through a fuzzy chance constraint. Furthermore, to manage the portfolios with asymmetric investment return, other than mean and variance, we also utilize the third central moment, the skewness of portfolio return. In fact, we propose a fuzzy portfolio mean–variance–skewness model with cardinality constraint which combines assets limitations with liquidity requirement. To solve the model, we also develop a hybrid algorithm which is the combination of cardinality constraint, genetic algorithm, and fuzzy simulation, called FCTPM.     

Portfolio selection under downside risk measures and cardinality constraints based on DC programming and DCA

In this paper, we consider the case of downside risk measures with cardinality and bounding constraints in portfolio selection. These constraints limit the amount of capital to be invested in each asset as well as the number of assets composing the portfolio. While the standard Markowitz’s model is a convex quadratic program, this new model is a NP-hard mixed integer quadratic program. Realizing the computational intractability for this class of problems, especially large-scale problems, we first reformulate it as a DC program with the help of exact penalty techniques in Difference of Convex functions (DC) programming and then solve it by DC Algorithms (DCA). To check globality of computed solutions, a global method combining the local algorithm DCA with a Branch-and-Bound algorithm is investigated. Numerical simulations show that DCA is an efficient and promising approach for the considered problem.      

基于可信性理论的均值-熵-偏度投资组合模型及其算法求解

本文考虑到证券市场的投资者往往面临着随机和模糊两种不确定性的情形,在模糊随机环境下把证券的收益率视作三角模糊变量,在可信性理论基础上建立了带融资约束条件的均值-熵-偏度三目标投资组合决策模型,拓展了基于可信性理论的投资组合决策模型的研究内容,同时通过对约束条件处理方法,外部档案维护方法等关键算子的改良,提出了一种新的约束多目标粒子群算法。本文运用该算法对模型进行求解,把得到的最优解与传统的多目标粒子群算法得到的最优解进行对比,结果表明新算法得到的最优解的质量会显著地优于传统的多目标粒子群算法的最优解,从而验证了算法的有效性和准确性。该算法可以在三维空间中得到一个分布性和逼近性较好的Pareto最优曲面,满足投资者对不同目标的差异需求,为投资者提供合理的投资组合决策方案。     

An improved penalty function method for solving constrained parameter optimization problems

An effective algorithm is described for solving the general constrained parameter optimization problem. The method is quasi-second-order and requires only function and gradient information. An exterior point penalty function method is used to transform the constrained problem into a sequence of unconstrained problems. The penalty weightr is chosen as a function of the pointx such that the sequence of optimization problems is computationally easy. A rank-one optimization algorithm is developed that takes advantage of the special properties of the augmented performance index. The optimization algorithm accounts for the usual difficulties associated with discontinuous second derivatives of the augmented index. Finite convergence is exhibited for a quadratic performance index with linear constraints; accelerated convergence is demonstrated for nonquadratic indices and nonlinear constraints. A computer program has been written to implement the algorithm and its performance is illustrated in fourteen test problems.     

A new method for mean-variance portfolio optimization with cardinality constraints

Several portfolio selection models take into account practical limitations on the number of assets to include and on their weights in the portfolio. We present here a study of the Limited Asset Markowitz (LAM) model, where the assets are limited with the introduction of quantity and cardinality constraints. We propose a completely new approach for solving the LAM model based on a reformulation as a Standard Quadratic Program, on a new lower bound that we establish, and on other recent theoretical and computational results for such problem. These results lead to an exact algorithm for solving the LAM model for small size problems. For larger problems, such algorithm can be relaxed to an efficient and accurate heuristic procedure that is able to find the optimal or the best-known solutions for problems based on some standard financial data sets that are used by several other authors. We also test our method on five new data sets involving real-world capital market indices from major stock markets. We compare our results with those of CPLEX and with those obtained with very recent heuristic approaches in order to illustrate the effectiveness of our method in terms of solution quality and of computation time. All our data sets and results are publicly available for use by other researchers.     

Fuzzy portfolio selection model with real features and different decision behaviors

In the ever changing financial markets, investor’s decision behaviors may change from time to time. In this paper, we consider the effect of investor’s different decision behaviors on portfolio selection in fuzzy environment. We present a possibilistic mean-semivariance model for fuzzy portfolio selection by considering some real investment features including proportional transaction cost, fixed transaction cost, cardinality constraint, investment threshold constraints, decision dependency constraints and minimum transaction lots. To describe investor’s different decision behaviors, we characterize the return rates on securities by LR fuzzy numbers with different shape parameters in the left- and right-hand reference functions. Then, we design a novel hybrid differential evolution algorithm to solve the proposed model. Finally, we provide a numerical example to illustrate the application of our model and the effectiveness of the designed algorithm.     

Inverse portfolio problem with mean-deviation model

A Markowitz-type portfolio selection problem is to minimize a deviation measure of portfolio rate of return subject to constraints on portfolio budget and on desired expected return. In this context, the inverse portfolio problem is finding a deviation measure by observing the optimal mean-deviation portfolio that an investor holds. Necessary and sufficient conditions for the existence of such a deviation measure are established. It is shown that if the deviation measure exists, it can be chosen in the form of a mixed CVaR-deviation, and in the case of n risky assets available for investment (to form a portfolio), it is determined by a combination of (n + 1) CVaR-deviations. In the later case, an algorithm for constructing the deviation measure is presented, and if the number of CVaR-deviations is constrained, an approximate mixed CVaR-deviation is offered as well. The solution of the inverse portfolio problem may not be unique, and the investor can opt for the most conservative one, which has a simple closed-form representation.     

Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization

We consider general nonlinear programming problems with cardinality constraints. By relaxing the binary variables which appear in the natural mixed-integer programming formulation, we obtain an almost equivalent nonlinear programming problem, which is thus still difficult to solve. Therefore, we apply a Scholtes-type regularization method to obtain a sequence of easier to solve problems and investigate the convergence of the obtained KKT points. We show that such a sequence converges to an S-stationary point, which corresponds to a local minimizer of the original problem under the assumption of convexity. Additionally, we consider portfolio optimization problems where we minimize a risk measure under a cardinality constraint on the portfolio. Various risk measures are considered, in particular Value-at-Risk and Conditional Value-at-Risk under normal distribution of returns and their robust counterparts under moment conditions. For these investment problems formulated as nonlinear programming problems with cardinality constraints we perform a numerical study on a large number of simulated instances taken from the literature and illuminate the computational performance of the Scholtes-type regularization method in comparison to other considered solution approaches: a mixed-integer solver, a direct continuous reformulation solver and the Kanzow–Schwartz regularization method, which has already been applied to Markowitz portfolio problems.     

Integer programming approaches in mean-risk models

This paper is concerned with porfolio optimization problems with integer constraints. Such problems include, among others mean-risk problems with nonconvex transaction cost, minimal transaction unit constraints and cardinality constraints on the number of assets in a portfolio. These problems, though practically very important have been considered intractable because we have to solve nonlinear integer programming problems for which there exists no efficient algorithms. We will show that these problems can now be solved by the state- of-the-art integer programming methodologies if we use absolute deviation as the measure of risk.     

Robustness of optimal portfolios under risk and stochastic dominance constraints

Solutions of portfolio optimization problems are often influenced by a model misspecification or by errors due to approximation, estimation and incomplete information. The obtained results, recommendations for the risk and portfolio manager, should be then carefully analyzed. We shall deal with output analysis and stress testing with respect to uncertainty or perturbations of input data for static risk constrained portfolio optimization problems by means of the contamination technique. Dependence of the set of feasible solutions on the probability distribution rules out the straightforward construction of convexity-based global contamination bounds. Results obtained in our paper [Dupa?ová, J., & Kopa, M. (2012). Robustness in stochastic programs with risk constraints. Annals of Operations Research, 200, 55–74.] were derived for the risk and second order stochastic dominance constraints under suitable smoothness and/or convexity assumptions that are fulfilled, e.g. for the Markowitz mean–variance model. In this paper we relax these assumptions having in mind the first order stochastic dominance and probabilistic risk constraints. Local bounds for problems of a special structure are obtained. Under suitable conditions on the structure of the problem and for discrete distributions we shall exploit the contamination technique to derive a new robust first order stochastic dominance portfolio efficiency test.     

Portfolio optimization with linear and fixed transaction costs

We consider the problem of portfolio selection, with transaction costs and constraints on exposure to risk. Linear transaction costs, bounds on the variance of the return, and bounds on different shortfall probabilities are efficiently handled by convex optimization methods. For such problems, the globally optimal portfolio can be computed very rapidly. Portfolio optimization problems with transaction costs that include a fixed fee, or discount breakpoints, cannot be directly solved by convex optimization. We describe a relaxation method which yields an easily computable upper bound via convex optimization. We also describe a heuristic method for finding a suboptimal portfolio, which is based on solving a small number of convex optimization problems (and hence can be done efficiently). Thus, we produce a suboptimal solution, and also an upper bound on the optimal solution. Numerical experiments suggest that for practical problems the gap between the two is small, even for large problems involving hundreds of assets. The same approach can be used for related problems, such as that of tracking an index with a portfolio consisting of a small number of assets.     

The benefits of differential variance-based constraints in portfolio optimization

The main problem of portfolio optimization is parameter estimation error. Various methods have been suggested to mitigate this problem, among which are shrinkage, resampling, Bayesian updating, naïve diversification, and imposing constraints on the portfolio weights. This study suggests two substantial extensions of the constrained optimization approach: the Variance-Based Constraints (VBC), and the Global Variance-Based Constraints (GVBC) methods. By the VBC method the constraint imposed on the weight of a given stock is inversely proportional to its standard deviation: the higher a stock’s sample standard deviation, the higher the potential estimation error of its parameters, and therefore the tighter the constraint imposed on its weight. GVBC employs a similar idea, but instead of imposing a sharp boundary constraint on each stock, a quadratic “cost” is assigned to deviations from the naive 1/N weight, and a single global constraint is imposed on the total cost of all deviations. Comparing ten optimization methods we find that the two new suggested methods typically yield the best performance, as measured by the Sharpe ratio. GVBC ranks first. These results are obtained for two different datasets, and are also robust to the number of assets under consideration.     

基于因子模型的指数跟踪及实证分析

指数跟踪是指数基金和机构投资者广泛使用的被动投资管理策略. 通过建立股票收益的多因子模型, 提出了将组合的贝塔值控制在合适范围内, 并在期望超额收益非负的条件下, 最小化组合风险的指数跟踪模型. 同时,考虑到实际需要, 在模型中限制了组合中股票的数量和持有量.实证分析结果表明, 通过选取不同的控制参数,
该模型产生的跟踪组合既能实现较小的跟踪误差,也能实现一定的超额收益.     

Equal Risk Bounding is better than Risk Parity for portfolio selection

Risk Parity (RP), also called equally weighted risk contribution, is a recent approach to risk diversification for portfolio selection. RP is based on the principle that the fractions of the capital invested in each asset should be chosen so as to make the total risk contributions of all assets equal among them. We show here that the Risk Parity approach is theoretically dominated by an alternative similar approach that does not actually require equally weighted risk contribution of all assets but only an equal upper bound on all such risks. This alternative approach, called Equal Risk Bounding (ERB), requires the solution of a nonconvex quadratically constrained optimization problem. The ERB approach, while starting from different requirements, turns out to be strictly linked to the RP approach. Indeed, when short selling is allowed, we prove that an ERB portfolio is actually an RP portfolio with minimum variance. When short selling is not allowed, there is a unique RP portfolio and it contains all assets in the market. In this case, the ERB approach might lead to the RP portfolio or it might lead to portfolios with smaller variance that do not contain all assets, and where the risk contributions of each asset included in the portfolio is strictly smaller than in the RP portfolio. We define a new riskiness index for assets that allows to identify those assets that are more likely to be excluded from the ERB portfolio. With these tools we then provide an exact method for small size nonconvex ERB models and a very efficient and accurate heuristic for larger problems of this type. In the case of a common constant pairwise correlation among all assets, a closed form solution to the ERB model is obtained and used to perform a parametric analysis when varying the level of correlation. The practical advantages of the ERB approach over the RP strategy are illustrated with some numerical examples. Computational experience on real-world and on simulated data confirms accuracy and efficiency of our heuristic approach to the ERB model also in comparison with some state-of-the-art local and global optimization codes.     

An improved hybrid global optimization method for protein tertiary structure prediction

First principles approaches to the protein structure prediction problem must search through an enormous conformational space to identify low-energy, near-native structures. In this paper, we describe the formulation of the tertiary structure prediction problem as a nonlinear constrained minimization problem, where the goal is to minimize the energy of a protein conformation subject to constraints on torsion angles and interatomic distances. The core of the proposed algorithm is a hybrid global optimization method that combines the benefits of the αBB deterministic global optimization approach with conformational space annealing. These global optimization techniques employ a local minimization strategy that combines torsion angle dynamics and rotamer optimization to identify and improve the selection of initial conformations and then applies a sequential quadratic programming approach to further minimize the energy of the protein conformations subject to constraints. The proposed algorithm demonstrates the ability to identify both lower energy protein structures, as well as larger ensembles of low-energy conformations.     

Second-Order Optimality Conditions and Improved Convergence Results for Regularization Methods for Cardinality-Constrained Optimization Problems

We consider nonlinear optimization problems with cardinality constraints. Based on a continuous reformulation, we introduce second-order necessary and sufficient optimality conditions. Under such a second-order condition, we can guarantee local uniqueness of Mordukhovich stationary points. Finally, we use this observation to provide extended local convergence theory for a Scholtes-type regularization method, which guarantees the existence and convergence of iterates under suitable assumptions. This convergence theory can also be applied to other regularization schemes.     

An algorithm for solving global optimization problems with nonlinear constraints

In this paper we propose an algorithm using only the values of the objective function and constraints for solving one-dimensional global optimization problems where both the objective function and constraints are Lipschitzean and nonlinear. The constrained problem is reduced to an unconstrained one by the index scheme. To solve the reduced problem a new method with local tuning on the behavior of the objective function and constraints over different sectors of the search region is proposed. Sufficient conditions of global convergence are established. We also present results of some numerical experiments.