A memetic algorithm for cardinality-constrained portfolio optimization with transaction costs

A memetic approach that combines a genetic algorithm (GA) and quadratic programming is used to address the problem of optimal portfolio selection with cardinality constraints and piecewise linear transaction costs. The framework used is an extension of the standard Markowitz mean–variance model that incorporates realistic constraints, such as upper and lower bounds for investment in individual assets and/or groups of assets, and minimum trading restrictions. The inclusion of constraints that limit the number of assets in the final portfolio and piecewise linear transaction costs transforms the selection of optimal portfolios into a mixed-integer quadratic problem, which cannot be solved by standard optimization techniques. We propose to use a genetic algorithm in which the candidate portfolios are encoded using a set representation to handle the combinatorial aspect of the optimization problem. Besides specifying which assets are included in the portfolio, this representation includes attributes that encode the trading operation (sell/hold/buy) performed when the portfolio is rebalanced. The results of this hybrid method are benchmarked against a range of investment strategies (passive management, the equally weighted portfolio, the minimum variance portfolio, optimal portfolios without cardinality constraints, ignoring transaction costs or obtained with L₁ regularization) using publicly available data. The transaction costs and the cardinality constraints provide regularization mechanisms that generally improve the out-of-sample performance of the selected portfolios.     

Continuous-time mean variance portfolio with transaction costs: a proximal approach involving time penalization

This paper proposes a new continuous-time optimization solution that enables the computation of the portfolio problem (based on the utility option pricing and the shortfall risk minimization). We first propose a dynamical stock price process, and then, we transform the solution to a continuous-time discrete-state Markov decision processes. The market behavior is characterized by considering arbitrage-free and assessing transaction costs. To solve the problem, we present a proximal optimization approach, which considers time penalization in the transaction costs and the utility. In order to include the restrictions of the market, as well as those that imposed by the continuous-time space, we employ the Lagrange multipliers approach. As a result, we obtain two different equations: one for computing the portfolio strategies and the other for computing the Lagrange multipliers. Each equation in the portfolio is an optimization problem, for which the necessary condition of a maximum/minimum is solved employing the gradient method approach. At each step of the iterative proximal method, the functional increases and finally converges to a final portfolio. We show the convergence of the method. A numerical example showing the effectiveness of the proposed approach is also developed and presented.     

Rebalancing an investment portfolio in the presence of convex transaction costs,including market impact costs

The inclusion of transaction costs is an essential element of any realistic portfolio optimization. We extend the standard portfolio optimization problem to consider convex transaction costs incurred when rebalancing an investment portfolio. Market impact costs measure the effect on the price of a security that result from an effort to buy or sell the security, and they can constitute a large part of the total transaction costs. The loss to a portfolio from market impact costs is often modelled with a convex function that can be expressed using second-order cone constraints. The Markowitz framework of mean-variance efficiency is used. In order to properly represent the variance of the resulting portfolio, we suggest rescaling by the funds available after paying the transaction costs. This results in a fractional programming problem, which we show can be reformulated as an equivalent convex program of size comparable to the model without transaction costs. We show that an optimal solution to the convex program can always be found that does not discard assets.     

Quadratic programming algorithms for large-scale model predictive control

Quadratic programming (QP) methods are an important element in the application of model predictive control (MPC). As larger and more challenging MPC applications are considered, more attention needs to be focused on the construction and tailoring of efficient QP algorithms. In this study, we tailor and apply a new QP method, called QPSchur, to large MPC applications, such as cross directional control problems in paper machines. Written in C++, QPSchur is an object oriented implementation of a novel dual space, Schur complement algorithm. We compare this approach to three widely applied QP algorithms and show that QPSchur is significantly more efficient (up to two orders of magnitude) than the other algorithms. In addition, detailed simulations are considered that demonstrate the importance of the flexible, object oriented construction of QPSchur, along with additional features for constraint handling, warm starts and partial solution.     

Large scale portfolio optimization with piecewise linear transaction costs

We consider the fundamental problem of computing an optimal portfolio based on a quadratic mean-variance model for the objective function and a given polyhedral representation of the constraints. The main departure from the classical quadratic programming formulation is the inclusion in the objective function of piecewise linear, separable functions representing the transaction costs. We handle the non-smoothness in the objective function by using spline approximations. The problem is first solved approximately using a primal-dual interior-point method applied to the smoothed problem. Then, we crossover to an active set method applied to the original non-smooth problem to attain a high accuracy solution. Our numerical tests show that we can solve large scale problems efficiently and accurately.     

A GRASP based solution approach to solve cardinality constrained portfolio optimization problems

In the current work, a solution methodology which combines a meta-heuristic algorithm with an exact solution approach is presented to solve cardinality constrained portfolio optimization (CCPO) problem. The proposed method is comprised of two levels, namely, stock selection and proportion determination. In stock selection level, a greedy randomized adaptive search procedure (GRASP) is developed. Once the stocks are selected the problem reduces to a quadratic programming problem. As GRASP ensures cardinality constraints by selecting predetermined number of stocks and quadratic programming model ensures the remaining problem constraints, no further constraint handling procedures are required. On the other hand, as the problem is decomposed into two sub-problems, total computational burden on the algorithm is considerably reduced. Furthermore, the performance of the proposed algorithm is evaluated by using benchmark data sets available in the OR Library. Computational results reveal that the proposed algorithm is competitive with the state of the art algorithms in the related literature.     

基于改进粒子群算法的投资组合选择模型

研究了在实际投资决策中存在交易成本(税收和交易费用)和投资数量约束下的投资组合选择问题,并进一步设计了一种求解该问题的改进粒子群算法.最后,给出了一个数值例子,说明该模型和方法的有效性.     

A novel approach to multiparametric quadratic programming

Multiparametric (mp) programming pre-computes optimal solutions offline which are functions of parameters whose values become apparent online. This makes it particularly well suited for applications that need a rapid solution of online optimization problems. In this work, we propose a novel approach to multiparametric programming problems based on an enumeration of active sets and use it to obtain a parametric solution for a convex quadratic program (QP). To avoid the combinatorial explosion of the enumeration procedure, an active set pruning criterion is presented that makes the enumeration implicit. The method guarantees that all regions of the partition are critical regions without any artificial cuts, and further that no region of the parameter space is left unexplored.     

Dynamic option hedging with transaction costs: A stochastic model predictive control approach

This paper proposes stochastic model predictive control as a tool for hedging derivative contracts (such as plain vanilla and exotic options) in the presence of transaction costs. The methodology combines stochastic scenario generation for the prediction of asset prices at the next rebalancing interval with the minimization of a stochastic measure of the predicted hedging error. We consider 3 different measures to minimize in order to optimally rebalance the replicating portfolio: a trade‐off between variance and expected value of hedging error, conditional value at risk, and the largest predicted hedging error. The resulting optimization problems require solving at each trading instant a quadratic program, a linear program, and a (smaller‐scale) linear program, respectively. These can be combined with 3 different scenario generation schemes: the lognormal stock model with parameters recursively identified from data, an identification method based on support vector regression, and a simpler scheme based on perturbation noise. The hedging performance obtained by the proposed stochastic model predictive control strategies is illustrated on real‐world data drawn from the NASDAQ‐100 composite, evaluated for a European call and a barrier option, and compared with delta hedging.     

Quadratic approximate dynamic programming for input‐affine systems

We consider the use of quadratic approximate value functions for stochastic control problems with input‐affine dynamics and convex stage cost and constraints. Evaluating the approximate dynamic programming policy in such cases requires the solution of an explicit convex optimization problem, such as a quadratic program, which can be carried out efficiently. We describe a simple and general method for approximate value iteration that also relies on our ability to solve convex optimization problems, in this case, typically a semidefinite program. Although we have no theoretical guarantee on the performance attained using our method, we observe that very good performance can be obtained in practice.Copyright © 2012 John Wiley & Sons, Ltd.     

The quadratic programming problem with fuzzy relation inequality constraints

The quadratic programming has been widely applied to solve real world problems. The quadratic functions are often applied in the inventory management, portfolio selection, engineering design, molecular study, and economics, etc. Fuzzy relation inequalities (FRI) are important elements of fuzzy mathematics, and they have recently been widely applied in the fuzzy comprehensive evaluation and cybernetics. In view of the importance of quadratic functions and FRI, we present a fuzzy relation quadratic programming model with a quadratic objective function subject to the max-product fuzzy relation inequality constraints. Some sufficient conditions are presented to determine its optimal solution in terms of the maximum solution or the minimal solutions of its feasible domain. Also, some simplification operations have been given to accelerate the resolution of the problem by removing the components having no effect on the solution process. The simplified problem can be converted into a traditional quadratic programming problem. An algorithm is also proposed to solve it. Finally, some numerical examples are given to illustrate the steps of the algorithm.     

An optimal schedule for dollar cost averaging under different transaction costs

Dollar cost averaging is a popular habit adopted by investors who recognize the diffculty in consistently timing the market. Recent technological innovations allow for the direct deposit of a predetermined portion of each paycheck into a brokerage account for the purchase of equities. Since most payperiods are biweekly or monthly, the automatic and frequent purchase of small amounts of equity produces substantial transaction costs. If funds were allowed to accumulate for a time in a money market account prior to equity purchase, then transaction costs may be lowered. However, since equity returns are generally more than that earned in the money market, delayed purchases would forfeit higher returns. In this study, we determine the optimal transaction size to maximize returns. We use the classical economic order quantity framework of inventory management and extend that framework to deal with the special discounting structures commonly offered by brokerage firms. Numerical examples and sensitivity analysis of fixed and variable transaction cost structure models are presented.     

A linear programming algorithm for optimal portfolio selection with transaction costs

We study the optimal portfolio selection problem with transaction costs. In general, the efficient frontier can be determined by solving a parametric non-quadratic programming problem. In a general setting, the transaction cost is a V-shaped function of difference between the existing and the new portfolio. We show how to transform this problem into a quadratic programming model. Hence a linear programming algorithm is applicable by establishing a linear approximation on the utility function of return and variance.     

有交易费的未定权益无套利套期保值定价

针对多种股票参与交易的市场,利用折算函数衡量总资产,给出了有交易费市场情形下的套利机会定义和基本性质,进而利用辅助鞅方法和凸分析方法,得到了套期保值策略的无套利性质和未定权益的套期保值定价公式.     

Sharpe-ratio pricing and hedging of contingent claims in incomplete markets by convex programming

We analyze the problem of pricing and hedging contingent claims in a financial market described by a multi-period, discrete-time, finite-state scenario tree using an arbitrage-adjusted Sharpe-ratio criterion. We show that the writer’s and buyer’s pricing problems are formulated as conic convex optimization problems which allow to pass to dual problems over martingale measures and yield tighter pricing intervals compared to the interval induced by the usual no-arbitrage price bounds. An extension allowing proportional transaction costs is also given. Numerical experiments using S&P 500 options are given to demonstrate the practical applicability of the pricing scheme.     

基于二次规划的直觉模糊数的多属性决策方法

针对属性权重完全未知且属性值为直觉模糊数的多属性决策问题,提出了一种新的决策方法。首先引入了直觉模糊数的一些运算法则、得分函数和精确函数等概念。然后构建了一个二次规划模型,通过求解该模型获得属性的权重。接着利用直觉模糊加权平均(IFWA)算子对属性值进行集结,得到方案的综合属性值。最后利用得分函数和精确函数对方案进行排序并择优。给出的算例说明了该方法的实用性和可行性。     

求解一类特殊的双层规划问题的遗传算法

主要研究上层函数及其约束函数不要求具有凸性和可微性,下层是关于下层决策变量是凸二次规划的双层规划模型,通过Karush-Kuhn-Tucher 条件转化为一个单层规划,利用下层是正定二次规划,将下层的决策变量表示为关于 Lagrangian乘子的表达式,从而降低了搜索空间的维数,设计了遗传算法,并通过数值实验表明该遗传算非常有效。     

机器人路径规划的多目标二次优化方法

基于多目标进化算法的机器人路径规划问题存在求解速度慢的不足,为提高求解效率,提出了一种多目标二次优化方法(MOQO)。在MOQO方法中首先引入二次优化的思想,通过离线的全局优化为在线的局部优化提供一个次优的初始解集,以更有效利用全局优化过程的先验信息和进化信息,从而加速后期的局部优化操作;其次,在MOQO方法中还提出了一种改进的多目标进化算法PPMOEA,以进一步提高优化求解的实时性能。最终的机器人路径规划仿真实验测试了MOQO方法对进化求解操作的加速效果,证明了方法的有效性和可行性。     

基于二次粒子群算法的投资组合优化

投资组合优化问题是一个复杂的组合优化问题,属于NP难问题,传统算法很难解决这一问题。将二次粒子群算法应用到投资组合优化问题中,并采用参数的自适应变化。数值模拟表明该算法在投资组合优化问题中能避免陷入局部最优,加快达到全局最优的收敛速度,并在一定意义下优于标准粒子群算法。     

基于SQP局部搜索的蝙蝠优化算法

针对基本蝙蝠算法存在寻优精度不高,后期收敛速度较慢和易陷入局部最优等问题,提出一种基于序贯二次规划（Sequential Quadratic Programming,SQP）的蝙蝠优化算法。该算法应用佳点集理论构造初始种群,增强了初始种群的遍历性;为避免算法陷入早熟收敛,引入柯西变异算子对种群中精英个体进行变异操作,增加种群多样性;在迭代后期,对最优个体进行SQP局部搜索,提高蝙蝠算法的局部深度搜索能力,保证个体在靠近全局最优值时能够寻优到全局最优解,加快种群进化速度。通过仿真实验结果证明,改进后的蝙蝠算法性能优越,具有良好的寻优精度和收敛速度。