Portfolio Optimization  

under Nonconvex Transaction Costs  

with the Global Optimization Toolbox 

Jason Schattman 

Introduction 

The two competing goals of investment are long-term growth of capital and low risk.  The Markowitz model, first formulated in 1952, is a quadratic programming optimization model for balancing these two goals.  The decision variables are the amounts invested in each asset.  The objective is to minimize the variance of a portfolio's total return, subject to the constraints that (1) the expected growth of the portfolio is at least some target level, and (2) that we don't invest more capital than we have. 

 

In its original form, the Markowitz model assumes no transaction costs, and thus, it is easily solved with quadratic programming.  Researchers have studied numerous convex generalizations of the Markowitz model, for example, by adding convex (usually linear) transaction costs, or other linear constraints. 

 

In this Maple application demonstration, we assume the investor pays nonconvex transaction costs on asset purchases; in particular, these costs are computed by a concave, piecewise-linear function of the amounts invested.  This cost structure arises in practice whenever a broker offers volume discounts on commission rates. Under these conditions, the Markowitz model becomes a nonconvex optimization problem that is not easily solved using local-search optimization algorithms.  However, we solve it easily using the Maple Global Optimization Toolbox. 

 

Key words: portfolio optimization, transaction costs, nonconvex, global optimization, quadratic programming 

Original formulation of the Markowitz model 

As a basis for comparison, we first formulate the original Markowitz model without transaction costs and solve it on an example instance using quadratic programming. 

 

Let be the amounts we buy, b the amount of capital we have, R the random vector of asset returns over some period, r the expected value of R, g the minimum growth (in dollars) we hope to obtain, and Q the covariance matrix of R.   

The objective function is , which can be shown to be equal to .  
If, for example, n = 3, we would solve the following quadratic program. 

minimize
subject to  

nonnegative 

 

 

Suppose we have the following data. 

 

 

 

Our objective function is . 

 

 

(2.1)

 

 

Our constraints are 

 

 

 

	(2.2)

 

 

Since the objective function is quadratic in x, y and z and the constraints are linear, we can use quadratic programming to solve the problem. We use QPSolve, the quadratic programming solver that comes with base Maple.  

 

 

(2.3)

 

 

Even though asset y's expected return is negative (-4%), its covariance with the other two assets is sufficiently negative to provide diversification benefits, i.e., reduce the variance of total return.  Thus, its optimal allocation under this model is positive. 

 

Adding transaction costs to the model 

Suppose we pay a commission of on the purchase of x dollars of an investment, where the function t is set by the broker, and that these costs come out of our investment budget.  Then the budget constraint for the three-asset problem becomes  

 

 

(3.1)

 

 

For simplicity, suppose first that the commission rate is a constant percentage of the purchase amount, that is, , with 0 < c < 1.  If, for example, ,  then the budget constraint would be 

 

 

(3.2)

 

We first solve the model under this linear cost function.  As expected, the minimum variance increases because our purchasing power is reduced, forcing us to invest relatively more in the highest-return, highest-variance asset in order to achieve the growth target of $1,000. 

 

 

(3.3)

 

 

Now suppose that the broker offers us a volume discount on commissions, so that the commission is given by a concave, piecewise-linear function in the purchase amount.  This cost structure is very common in practice.  

 

Below we construct and plot a concave, piecewise-linear transaction cost function . 

 

Transaction Cost Function 

 

 

Below we plot the budget constraints of the example problem under zero transaction costs (the red surface) and piecewise-linear transaction costs (the blue surface).   

 

Notice that the region bound by the red surface is convex (a tetrahedron), whereas the feasible region bound by the blue surface is nonconvex.  The nonconvexity is what makes this a challenging optimization problem and one appropriate for global optimization techniques. 

 

Plot Budget Constraints 

 

Solving the nonconvex model with the Global Optimization Toolbox. 

Recall the solution to the original problem with zero costs. 

 

 

(4.1)

 

 

We first attempt to solve the nonconvex problem using the local-search solver built into Maple, taking as initial point the optimal solution to the zero-cost problem. On this data, the local solver runs into trouble because the constraints are nondifferentiable in several places, and most local solvers assume continuous first derivatives on all inputs. 

 

 

Error, (in Optimization:-NLPSolve) no improved point could be found

 

 

The Global Optimization Toolbox routines handle the problem on any set of data. 

 

 

(4.2)

 

 

Below is a diagram showing the location of the optimal allocation (in green) on the boundary of the feasible region.  The surfaces representing the budget constraint (blue) and the growth constraint (grey) are shown. 

 

Location of Optimal Allocation 

 

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.