Efficient and Simple Heuristic Algorithm for Portfolio Optimization

Abstract

Markowitz model considers what is termed as standard portfolio optimization. The portfolio optimization problem is a problem which based on asset allocation and diversification for maximum return with minimum risk. Thus, the standard portfolio optimization problem happens when the constraints considered are budget and no-short selling. In reality however, portfolio optimization has realistic constraints to be incorporated such as holding sizes, cardinality and transaction cost. When realistic constraints are added into portfolio optimization problem, it becomes too complex to be solved by standard optimization methods which in this case turns to be an extended portfolio optimization problem. Markowitz solution and the standard methods like quadratic programming become inapplicable. With such limitation, heuristic methods are usually used to deal with this extended portfolio optimization problem. Therefore, this paper proposes a heuristic algorithm for the extended portfolio optimization problem. It is a hill climbing algorithm named Hill Climbing Simple (HC-S) which is then validated by solving the standard Markowitz model. In fact, the proposed algorithm is benchmarked with the quadratic programming (QP), which is a standard method. By benchmarking HC-S with QP, it showed that HC-S can attains similar accurate solutions. Also, HC-S demonstrated to be more effective and efficient than threshold accepting (TA), an established algorithm for portfolio optimization since HC-S find solutions with significant higher objective value and require less computing time as compared to standard methods.

 Keywords: Heuristic, Hill Climbing Algorithm, Portfolio Optimization Problem, Threshold Accepting Algorithm.