WIXLIB

Daniel FylstraIntroducing Convex and ConicOptimization for the QuantitativeFinance ProfessionalFew people are aware of a quiet revolution that has taken place inoptimization methods over the last decadeOptimization has played animportant role in quantitativefinance ever since Markowitzpublished his original paper onportfolio selection in 19521.Most “quants” have someknowledge of linear programming as used inbond duration matching, quadratic programming as used in equity portfolio optimization,and nonlinear optimization used with portfolios of derivatives. The finance industry andtechnical literature is home to many different,competing approaches that apply these standard optimization methods to different modelsand risk measures, in an effort to achieve betterinvestment results.But fewer people are aware of a quiet revolution that has taken place in the optimization methods themselves over the last decade.A better understanding of the properties ofoptimization models, and new algorithms –notably interior point or barrier methods –have led to a changed view of the whole fieldof optimization. It is not an exaggeration tosay that linear and quadratic programmingare being replaced – or more properly subsumed – by more powerful and general methods of convex and conic optimization.18Wilmott magazine

What this means for quantitative finance is arelaxing of restrictions on optimization models– for example, using quadratic constraints aseasily as a quadratic objective – and new ways todeal with important problems such as “unnatural” portfolios from optimization that are due to“noise” in the return and covariance or factorparameters of a portfolio model. This articlewill introduce the ideas of convex and conicoptimization, and their applications inquantitative finance.It is not an exaggeration to say that linearand quadratic programming are beingreplaced – or more properly subsumed –by more powerful and general methodsof convex and conic optimizationLinear and quadratic programmingAn optimization problem consists of decisionvariables, an objective function to be maximized orminimized, and constraints that place limits onother functions of the variables. In linear programming, the objective and constraint functions are all linear – hence the simple form:max/mincxsubject tobl Ax buxl x xuwhere x is a vector of decision variables, cx is theobjective function, A is a matrix of coefficientsand Ax computes the constraints, bl and xl arelower bounds, and bu and xu are upper bounds.In quadratic programming, the objective is generalized to a quadratic function of the form:max/minxT Qx cxsubject tobl Ax buxl x xuwhere Q is a matrix of coefficients. In the simplest formulation of the classic Markowitz portfolio optimization problem, Q is a covariancematrix, the objective xT Qx is portfolio variance tobe minimized, and A has just two rows: A budgetconstraint 1x 1 and a portfolio return thresholdax b where a is the expected return of eachsecurity and b is the minimum portfolio return.A factor model that expresses the “beta” orsensitivity of each security to one or moremarket factors also leads to a quadraticprogramming model.Wilmott magazineConvex and non-convex problemsNonlinear optimization is a well-developedfield, with many solution algorithms for problems of the general form:max/minf (x)subject tobl G(x) buxl x xuwhere f (x) is a smooth function, and G(x) is avector of smooth functions of the variables x.Linear and quadratic programming problems arespecial cases of this form, where f (x) cx orxT Qx cx, and G(x) Ax . But solution algorithmsfor this general problem can find only “locallyoptimal” solutions that may not be “globallyoptimal,” and they may fail to find a feasiblesolution even though one exists. Unlike linearand quadratic programming, the time taken tofind a globally optimal solution can rise exponentially with the number of variables and constraints. This severely limits the size of problemsthat can be solved to global optimality. Hencethe aversion to nonlinear optimization for practical quantitative finance problems seems wellfounded. Or is it?In an observation now famous for its prescienceamong optimization researchers, mathematician R. Tyrrell Rockafellar wrote in SIAM Reviewin 19932:“. . . in fact, the great watershed in optimization isn’t between linearity andnonlinearity, but convexity andnonconvexity.”What makes the general optimization problemso hard to solve? It is not the fact that f (x) orG(x) may be nonlinear! It is the fact that f (x) orG(x) may be non-convex.A convex optimization problem is onewhere all of the constraints are convex functions, and the objective is a convex function ifminimizing, or a concave function if maximizing. A non-convex optimization problem is anycase where the objective or any of the constraints are non-convex functions. The difference is dramatic: Convex optimization problems can be efficiently solved to global optimality with up to tens or even hundreds of thousands of variables. In contrast, the best methodsfor global optimization on modern computersusually can solve non-convex problems of only afew hundred variables to global optimality.Even a quadratic programming problem maybe “impossibly” hard to solve (in mathematicalterms, NP-hard) if the objective function xT Qx isnon-convex, which happens when the matrix Qis indefinite3. Fortunately for portfolio optimization, the matrix Q will be positive definite if the19 Classical quadratic programming still requiresthat all constraints are linear; quadratic or moregeneral constraints would put the problem in thedomain of nonlinear optimization. Quantitativefinance professionals have worked hard to createmodels that “fit” within the domain of linear andquadratic programming, and avoid models thatrequire nonlinear optimization methods. Why?

DANIEL FYLSTRAcovariance terms are computed from historicaldata where the number of observations exceedsthe number of securities.Convex functionsWhat do we mean by a convex function?Geometrically, a function is convex if a line segment drawn from any point (x, f (x)) to anotherpoint (y, f (y)) – called the chord from x to y – lieson or above the graph of f, as in the picture below:Quantitative finance professionals haveworked hard to create models that 'fit'within the domain of linear and quadraticprogramming, avoiding models thatrequire nonlinear optimization methods.Why?Interior point methodsand softwareAlgebraically, f is convex if, for any x and y,and any t between 0 and 1,f (tx (1 t)y) tf (x) (1 t)f (y) . A function isconcave if f is convex – i.e. if the chord from x toy lies on or below the graph of f . It is easy to see thatevery linear function – whose graph is a straightline – is both convex and concave. A quadraticfunction xT Qx is convex if Q is positive semi-definite, or concave if Q is negative semi-definite. Anon-convex function “curves up and down” – it isneither convex nor concave. A familiar example isthe sine function; perhaps less familiar is thequadratic xT Qx where Q is indefinite, for examplex21 2x1 x2 1/2(x22 1) which is plotted below:General nonlinear functions may be convexor non-convex. A problem with all convex nonlinear functions can be solved efficiently, toglobal optimality, to very large size; but thesefavorable features are lost if even one problemfunction is non-convex.20Rockafellar’s observation moved from theoretically interesting to practically significant withthe development of interior point methods –first for linear programming, pioneered byKhachian and Karmarkar4 in the 1980s, thenfor more general convex optimization problems, pioneered by Nesterov and Nemirovskii51994. Where the simplex method relies on thefact that the constraints are linear, and movesfrom vertex to vertex where constraints intersect, interior point methods rely only on thefact that the constraints are convex – theymove along the so-called central path definedby a nonlinear barrier function, even for LPproblems.This means, for example, that an interiorpoint method doesn’t “care” whether it is dealing with a quadratic objective or (one or many)quadratic constraints – it will take essentiallythe same number of steps to find the optimalsolution.Commercial interior point optimizationsoftware that handles quadratic constraintshas just begun to appear; examples are theBarrier component of the CPLEX optimizer, theMOSEK optimizer, and the Barrier solver inFrontline Systems’ Premium Solver Platformfor Excel.Efficient portfolios and quadraticconstraintsAs mentioned earlier, quantitative finance professionals have worked hard to make theirmodels “fit” within the domain of linear andquadratic programming. For example, in RobertFernholz’s well-regarded work applying “stochastic portfolio theory”to equity portfolio management6, the linear portfolioreturn threshold constraint isreplaced by a portfolio growththreshold constraint thatincludes a quadratic term.Fernholz remarks that “this constraint is nonlinear, and conventionalquadratic programs cannot be used in thiscase.” He goes on to show that, for enhancedindex (“tracking”) portfolios, the quadratic termin the growth constraint is small in magnitude,and therefore can be neglected – yielding a linear constraint and a conventional QP problem.But with modern interior point methods, thissimplification is no longer necessary – the original problem including the quadratic constraintcan be solved just as reliably, and in about thesame time, as the simplified QP problem.Conic optimizationNesterov and Nemirovskii’s seminal work alsoopened up a natural generalization of linearprogramming, called conic programming, thatshares the favorable characteristics of LP butencompasses a wider range of problems. Andconic quadratic programming – now known assecond order cone programming – shares thefavorable characteristics of QP but encompassesa wider range problems relevant for portfoliooptimization.Wilmott magazine