An algebraic approach to Integer Portfolio problems

AN ALGEBRAIC APPROACH TO INTEGER PORTFOLIO PROBLEMS F. CASTRO, J. GAGO-VARGAS, M.I. HARTILLO, J. PUERTO, AND J.M. UCHA Abstract. Integer variables allow the treatment of some portfolio optimization problems in a more realistic way and introduce the possibility of adding some natural features to the model. We propose an algebraic approach to maximize the expected return under a given admissible level of risk measured by the covariance matrix. To reach an optimal portfolio it is an essential ingredient the computation of different test sets (via Gr¨obner basis) of linear subproblems that are used in a dual search strategy. 1. Introduction Mean-variance portfolio construction lies at the heart of modern asset management and has been among the most investigated fields in the economic and financial literature. The classical Markowitz’s approach, cf. [Mar52], or [Mar00] for a recent reissue of his work, rests on the assumption that investors choose among nrisky assets to look for their corresponding weights wiin their portfolios, on the basis of (1) previously estimated expected returns µi, and (2) the corresponding risk of the portfolio measured by the covariance matrix Ω. Portfolios are considered mean-variance efficient in two senses: •If they minimize the variance for a given admissible return R: (MVP1) min w1. . . wnΩ   w1 . . . wn   , subject to µ1w1+· · · +µnwn≥R, w1+· · · +wn= 1, wj∈R. •If they maximize the expected return for a given admissible risk (variance) r2: (MVP2) max µ1w1+· · · +µnwn, subject to w1. . . wnΩ   w1 . . . wn   ≤r2, w1+· · · +wn= 1, wi∈R. In problems (MVP1) and (MVP2) the weights wistand for the percentage of a given asset in the portfolio. It is well-known that both problems give dual views of 1 2 F. CASTRO, J. GAGO-VARGAS, M.I. HARTILLO, J. PUERTO, AND J.M. UCHA a common analysis since they correspond to two scalarizations of the more general bicriteria approach: obtaining the entire set Wof mean-variance efficient portfolios. In this sense, (MVP1) and (MVP2) are equivalent in that Wcan be obtained either solving (MVP1) or (MVP2) parametrically on R(admissible returns) or r (admissible risks), respectively; see [SNT85] for further details. Although the standard statement of the mean-variance portfolio problem uses continuous variables, there are different reasons to consider integer variables, as it is pointed out in different authors [SM05, LT08, BL07, You98, CF07]. Our goal is to treat problem (MVP2) in its integer version based on the following considerations: •In real markets, we can buy or sell only an integer amount of assets, so considering real weights in the portfolio is actually an approximation. As it is well known already for linear problems, the rounding of the real values obtained for one optimal portfolio with continuous weights may produce, in principle, an infeasible solution or a very bad approximation to the optimal integer solution. We think that this is indeed the case for a portfolio that potentially considers future contracts, as in [GK08] for commodity futures, to obtain lower correlations concluding on the benefits of diversification. We show this behaviour in Example 5.2. •The need to diversify the investments in a number of industrial sectors [BL07]. •The constraint of buying stocks by lots [BL07, CF07, JHLM01]. •Another reason for the use of integer variables, usually binary, appears in practice because portfolio managers and their clients often hate small active positions and very large number of assets, the reason being that they produce big transaction and monitoring costs. Hence it is rather usual to add the constraints associated to the following conditions: (1) there should be at least some previously decided minimum percentage (lower bounds), and (2) there should be a maximum number of assets (upper bounds). Furthermore, transaction costs are included as linear constraints in the return equation, using decision variables, as in [LT08]. The above mentioned requirements enrich any portfolio model for real applications and require 0-1 or, more generally, integer variables. Nevertheless, as far as we know there are no specific algorithms to solve these problems. Note that methods in semi-definite programming deal with this problem, but they are oriented to the continuous case. See also [SM05] for a set of routines that handles these problems in the continuous case. In our approach, it is natural to consider non negative integer variables x1, . . . , xnfor the quantities of each product. Then it is necessary to take into account •the unit prices a1, . . . , anof the products, •the expected returns of each stock µ1, . . . , µn, •and the total available budget B. Then Problem (MVP2), in its integer version, can be restated as max Pn i=1 µixi=µtx subject to Pn i=1 aixi=atx≤B, Q(x)≤B2r2, x∈(Z+)n, AN ALGEBRAIC APPROACH TO INTEGER PORTFOLIO PROBLEMS 3 where Q(x) = a1x1. . . anxnΩ   a1x1 . . . anxn   . 1.1. Previous works and our approach. There have been several works with different techniques to treat Problem (MVP1) in an integer framework. •For (MVP1): piecewise linear approximation in [Sha71] and [Sto73], absolute deviation selection in [YK91], branch-and-cut techniques in [Bie96] and minimax selection approach in [You98]. •For (MVP1) with additional transaction cost: dual Lagrangian relaxation in [MM91, GK87], linear terms transformation in [LC98], separable terms transformation in [Sha71, Sto73], and parallel distributed computation reformulating the objective function into an ellipse and using piecewise linearization in [LT08]. For Problem (MVP2) the literature is not so wide, although this approach is very usual in practice for the so called benchmark portfolios, as used in [MM08]. The results of [BPT00] have been in some sense a milestone in applying tools of Algebraic Geometry (namely Gr¨obner bases) to optimization, although this method is not effective for Problem (MVP2). See [AL94, Ch.1,2], [CLO05, Ch. 2], or [BW05] for introductions to this subject. Our goal is to present a new algorithm to deal with portfolio problems with integer variables and non-linear constraints. The method is based on the computation of some test sets using Grobner bases. These bases are computed from a linear integer subproblem that contains the original linear constraints together with some new cuts induced by the non-linear constraints. The use of the reversal test-set allows us to design a dual search algorithm that moves from the optimal solution of the linear subproblems towards the optimal solution of the entire portfolio problem. Our approach is new with respect to the cited references, and we will see in the last section that it is effective to deal with portfolios with number of stocks comparable to those in the literature (see [CF07, LT08]). The paper is organized as follows. In Section 2 we fix the formulation of the problem to be treated with the method explained in [TTN95]. In Section 3 the successive additions of linear constraints are explained, and the dual search algorithm based on a test-set computed from a Gr¨obner basis is applied to find an optimal point of Problem (1). It is also included an illustrative example. Section 4 explains the existence of a lower bound r2 bto the risk value r2below that it is not necessary to invest the whole budget to get an optimal portfolio. Section 5 contains some computational experiments and Section 6 draws some conclusions on the paper. 2. Preliminaries If one accepts the integer version of model (MVP2) to obtain efficient portfolios, the objective function and all constraints but one —that is quadratic— are linear. This is related to the form of the problem treated in [TTN95]. To solve an integer programming problem (P) with linear objective function under different linear and nonlinear constraints, the following general approach can be applied (see [TTN95] for a complete example): 4 F. CASTRO, J. GAGO-VARGAS, M.I. HARTILLO, J. PUERTO, AND J.M. UCHA (1) First obtain a test-set for a linear part of (P), let us call it (P0). A test-set Tis a set of vectors in Znsuch that, given a feasible point Fof (P0), if none of the feasible points obtained adding the elements of Tto Fimproves the value of the objective function, then Fis an optimum of (P0). A test-set of a linear integer problem can be obtained via Gr¨obner bases ([CT91], see [Stu96, ch. 5] for a modern introduction). The best known way of obtaining these bases is using programs as 4ti2 ([tt08]), that takes advantage of the special structure of the toric ideals corresponding to linear integer problems. Programs for general Gr¨obner bases are not so good for big examples. (2) Starting at the optimum of the linear problem (P0), which is possibly an infeasible point for problem (P), use the reversal test-set —so decreasing the objective function each time a vector of Tis applied— to move throughout the set (tree) of feasible points of (P0) until you obtain feasible points for the whole problem (P). In our case, it means, portfolios with admissible risk. If this happens, one can prune the remaining feasible solutions. Our approach consists of applying this general idea to Problem (1) mixing it with some bounds obtained from the continuous relaxation of the problem, to reduce the feasible region described by the linear constraints, as in [LT08]. The initial problem is (P) max {µtx|atx≤B, Q(x)≤B2r2,x∈(Z+)n}, and its linear relaxation is (P0) max {µtx|atx≤B, x∈(Z+)n}. The purpose of the following section is to explain how to obtain additional linear constraints to improve the accuracy of the linear description of problem (P), taking advantage of geometrical properties of the definition of risk. We look for some linear constraints based on the convexity of the hyperquadric given by the covariance matrix Ω, which is symmetric positive definite. However, too many constraints means too many elements in the Gr¨obner basis, so the point will be to find the precise trade-off between constraints to eliminate unnecessary points in our searching, and at the same time not to increase the basis unnecessarily. 3. A dual search algorithm based on a test-set A direct approach to problem (P) following [TTN95] may lead to a non practical procedure to find the optimum. If we compute a test-set related to problem (P0), and move along the set of solutions of the linear relaxation of problem (P), the number of points to be processed is huge, even for a small number of variables. The main drawback of the procedure is the great number of integer solutions to be visited between the starting point and the feasible region of the problem (P). In order to avoid this enormous enumeration, some cuts can be added, using the convexity of the hyperquadric defined by the symmetric positive definite matrix Q. We assume that a black box is available providing solutions to linear continuous optimization problems with quadratic convex constraints, as the function fmincon in Matlab, the different implementations of semi-definite programming compared in [Mit03], or even the linear time in fixed dimension algorithm by [Dye92]. AN ALGEBRAIC APPROACH TO INTEGER PORTFOLIO PROBLEMS 5 3.1. Starting tasks. In order to improve our representation of problem (P), we proceed as follows: •The first step is the computation of the continuous solution ucof the problem max {µtx|atx≤B, Q(x)≤B2r2,x∈(R+)n}, which gives us a return µtuc=Rc. Clearly the discrete return is less than or equal to bRcc(function ComputeContinuousOptimum in Algorithm 1). •Secondly, we need a good discrete feasible point, which will give us a lower bound for the return. The problem (P) is always feasible, because the origin belongs to the region, but this point it is not very useful. The rounded point ud=buccis not always feasible, as it is well-known. •In order to get a feasible starting point, it is possible to decrease each coordinate until we get a feasible point. After that, the point can be improved so that the return cannot be increased in any direction inside the feasible region (function ComputeDiscreteApprox in Algorithm 1). From this point pewe will reach the discrete optimum. Let Re=µtpebe the return associated with the discrete feasible point pe. A new valid formulation of the problem is max {µtx|atx≤B, Re≤µtx≤ bRcc, Q(x)≤B2r2,x∈(Z+)n}. 3.2. Addition of new linear constraints. From the above formulation, we improve our description of problem (P) in two ways. (1) Adjusting hyperplanes to the hyperquadric given by upper and lower bounds on the variables. To this end, for j= 1, . . . , n, we solve the continuous problems (function ComputeLowerBounds in Algorithm 1) min {xj|atx≤B, Re≤µtx≤ bRcc, Q(x)≤B2r2,x∈(R+)n}. The above minimum values give us an integer lower bound bjfor each variable xj, applying the ceiling function. The constraints bj≤xjare not going to be involved in the computation of the test-set through the Gr¨obner basis. This is because we can write bj+yj=xj, where yj≥0, and this change of variables do not alter the coefficient matrix of the linear cuts, nor the linear cost function. Since the computation of the Gr¨obner basis does depend only of this matrix, there is no extra computation time. In a similar way, the maximization problems max {xj|atx≤B, Re≤µtx≤ bRcc, Q(x)≤B2r2,x∈(R+)n} for j= 1, . . . , n, provides us upper bounds. However, these linear constraints highly increase the size of the test-set. We will only use them to fix variables, because the upper and lower bounds of some variables are equal in many examples. This fact allows us reducing the dimensionality of the problem. We consider the polytope P={x∈Rn|atx≤B, µtx≤ bRcc,µtx≥Re,b≤x} where b≤xstands for the conditions bi≤xi, i = 1, . . . , n. 6 F. CASTRO, J. GAGO-VARGAS, M.I. HARTILLO, J. PUERTO, AND J.M. UCHA (2) Adding nearly tangent hyperplanes to shrink the polytope. The main idea is the addition of cuts so that the farthest regions of the polytope Pcould be cut off. To do that, we use a point of Pwhere the function Qtakes its greatest value. This is equivalent to solve the continuous problem max {Q(x)|x∈P}. It is coded as function ComputeMaxRisk in Procedure NewPolytope. Note that this problem can be efficiently solved since it is of polynomial complexity [KTH79]. Let pmax be a solution of Problem (2), sbe the half-line from the feasible point peto pmax, and p0=Q ∩ sthe intersection point of swith the hyperquadric Qdefined by the function Q(x) = B2r2. Let Hbe the supporting hyperplane to Qat the point p0. By the convexity of Q, the hyperplane Hdefines a linear half-space that contains the interior of Q. The coefficients of the hyperplane Hare real numbers, so its normal vector nmay have non integer components. However, we are looking for linear constraints with integer coefficients, so we round the vector nto an integer vector ˜ n∈Zn(variable Prec in Procedure NewPolytope). Then we proceed to compute the independent term cof the tangent hyperplane to Qwhose normal vector is equal to ˜ n, and such that the half-space ˜ ntx≤˜c=dcedefines a linear half-space which contains the interior of Q. This process can be iterated as many times as we wish (Algorithm NewPolytope), shrinking the polytope P. Nevertheless, there should be a trade-off between the number of new hyperplanes and the size of the Gr¨obner basis associated with the system, so the maximum number of cuts allowed is a parameter of the algorithm. Additionally, the difference between r2 m= max{Q(x)|x∈P}and the initial risk r2 0is another stopping criterion, passed as the parameter Tol to the algorithm. 3.3. Dual iterations with the test-set. Now after the above two phases Problem 1 is transformed to max µtx s. t. atx≤B, Re≤µtx≤ bRcc, ˜ nt kx≤˜ck, k = 1, . . . , s, x≥b,x∈∈ (Z+)n, Q(x)≤B2r2, where ˜ nt kx≤˜ck, k = 1, . . . , s are the new cuts. The test-set Gis associated with the linear problem max µtx s. t. atx≤B, µtx≤ bRcc, ˜ nt kx≤˜ck, k = 1, . . . , s, x≥b,x∈(Z+)n. AN ALGEBRAIC APPROACH TO INTEGER PORTFOLIO PROBLEMS 7 The condition Re≤µtxis tested inside the tree-search, and used to prune leaves. The value of Reis updated as soon as a new feasible point with a better return is found. Once we have the test-set of the above polytope we proceed with the resolution method. The main bottleneck of our approach is the search over the tree defined by the test-set. The number of points to be processed is strongly related to the initial feasible point pefound because: (1) The estimated return Redefines the lowest facet of the polytope Pin terms of the objective value. (2) The upper and lower bounds for the variables xiare strongly determined by Re. The closer is Reto the optimal value, the narrower is the interval for each variable xi. On the other hand, to apply the reversal test-set search we need an initial (and usually non feasible) point, but not far from feasibility. We take the point pbounds built by considering the independent terms of the linear constraints of Problem (3.3), after applying the translation bi+yi=xi, i.e., pbounds = (b, B −atb,bRcc − µtb,˜ck−˜ ntb)t. The starting point for the reversal test-set tree search is the point pini, the reduced of pbounds by the test-set G. This is the solution of the linear problem (3.3), as shown in [CT91]. With the reversal test-set, we search over the tree of nodes (feasible points for the linear problem) until we obtain a feasible point for the entire problem, including the quadratic constraint (function TreeSearch in Algorithm 1). If the switch SwFictBounds is set to true, the search is stopped in the first point that improves the estimated return given by the incumbent point pe. Although the tree search has to end, a maximum number of processed records is passed to the procedure TreeSearch as a parameter. It could happen that the number of points processed exceeds the maximum allowed, and the optimum had not been found. If a new feasible point p0 eis found (SwImprove = true), the bounds can be recomputed. The test-set is still valid for the new search. The only new computations are the independent terms of the hyperplanes and the reduction to find the starting point. However, if the test-set were huge, it would be better to compute the new linear cuts given by the new estimated point p0 eand its associated Gr¨obner basis. In general, the Gr¨obner basis will be shorter, and the elapsed time spent in the tree search will be shortened. 3.4. Restricted search in a region. In the case that a new feasible point is not found after a given number of processed points (SwImprove = false), it is then possible to apply a branch-and-cut technique with the bounds. Indeed, let pebe the feasible point that gives the value Re, and bthe vector of lower bounds for the variables xi, i = 1, . . . , n. Compute a point b0=b+α(pe−b),0< α < 1 (usually 8 F. CASTRO, J. GAGO-VARGAS, M.I. HARTILLO, J. PUERTO, AND J.M. UCHA α= 1/2), which we call fictitious bound, and consider the following problem: (1) max µtx s. t. atx≤B, Re≤µtx≤ bRcc, ˜ nt kx≤˜ck, k = 1, . . . , s, x≥b0,x∈(Z+)n, Q(x)≤B2r2. Solving the above problem, we expect to find a new feasible point to relaunch the search process. The idea is simple: the search is restricted to a smaller region, but the solution of the original problem is not guaranteed to be in that region. It is a heuristic technique to take advantage that this new problem does not need a new test-set. In our implementation, this search can be launched by setting the switch SwFictBounds equal to true. The process is stopped as soon as a new point is found, and then we start again. If no point is found after the maximum number of allowed nodes (variable MaxNumNodes in Algorithm 1), then we stop, and the point peis our best value. The pseudocode of the main algorithm is described in DiscreteOptimum. The procedure NewPolytope presents the pseudocode of the strengthening of the polytope Pby adding valid cuts. The switch SwEOP is used to mark the end of the process. 3.5. An illustrative example. Let a= (6075,3105)tbe the vector of prices, and µ= (12500,10000)tthe vector of returns, with the covariance matrix equals to Ω = .832843e−4.485325e−4 .485325e−4.651298e−3. Let B= 9 ×106be the budget, and r2= 3 ×10−5the fixed risk. The continuous optimum is uc= (772.754778,215.028056)t, with a total return Rc= 11809715.29. Then bRcc= 11809715, and rounding ucwe get the point ud= (773,215), which is not a feasible point. Subtracting from the components, we eventually reach a feasible point pe= (773,214), whose associated return is Re= 11802500. The lower bounds b1and b2are now computed, solving first the continuous problems min {xi|atx≤B, Re≤µtx≤Rc, Q(x)≤r2B2,x∈(R+)2}, where (2) Q(x) = a1x1a2x2Ωa1x1 a2x2. The respective continuous values are ˜ b1= 752.69, rounded to b1= 753, and ˜ b2= 190.58, rounded to b2= 191. We want to solve the problem max {µtx|atx≤B, Re≤µtx≤ bRcc, Q(x)≤r2B2,x≥b,x∈(Z+)2}. In the associated linear problem max {µtx|µtx+z1=bRcc,atx+z2=B, x≥b,x∈(Z+)2} we change the variables xi=yi+bi, and the resulting linear problem has the same coefficient matrix. The computation of a Gr¨obner basis leads to the test-set formed AN ALGEBRAIC APPROACH TO INTEGER PORTFOLIO PROBLEMS 9 by vectors v1= (−4,5,8775,0)t,v2= (−1,1,2970,2500)t,v3= (0,−1,3105,10000)t, v4= (1,−2,135,7500)t,v5= (2,−3,−2835,5000)t,v6= (3,−4,−5805,2500)t. Now, we reduce the point pbounds = (b1, b2, B−a1b1−a2b2,bRcc−µ1b1−µ2b2)t= (753,191,3832470,487215)t with the test-set to get the linear problem optimum, which is the starting point pini of the tree search. In this case, pini = (791,192,3598515,2215). We now show the path followed by the search procedure in the tree of solutions of the linear part of the problem. In each node, we write the distance ∆1to the continuous return associated with it, that is, ∆1=bRcc − µt(p+vi). The initial distance is ∆e= 7215, the difference between bRccand Re. The larger the value, the smaller the return. Therefore, values larger than ∆emeans that the corresponding branch can be pruned. The list of nodes to be processed are then ordered by ∆1. Note that black dots ‘•’ mean pruned nodes, and white dots ‘◦’ mean new nodes. The points are shortened to the two first components to save space. ?Node p= (791,192)t,∆e= 7215. Leaves p+vi, i = 1,...,6: –p+v1= (787,197)t,∆1= 2215, r2≥r2 0. New node ◦. –p+v2= (790,193)t,∆1= 4715, r2≥r2 0. New node ◦. –p+v3= (791,191)t,∆1= 12215 >∆e. Pruned by ∆e. –p+v4= (792,190)t,∆1= 9715. Pruned by bound b2= 191. –p+v5= (793,189)t,∆1= 7215. Pruned by bound b2= 191. –p+v6= (794,188)t,∆1= 4715. Pruned by bound b2= 191. The above information gives rise to the following descendants. ◦(791,192) ''++,,-- //•(794,188) ◦(787,197) ◦(790,193) •(791,191) •(792,190) •(793,189) List of ordered nodes: {(787,197)t,(790,193)t}. ?Node p= (787,197)t,∆e= 7215. Leaves p+vi, i = 1,...,6: –p+v1= (783,202)t,∆1= 2215, r2≥r2 0. New node ◦. –p+v2= (786,198)t,∆1= 4715, r2≥r2 0. New node ◦. –p+v3= (787,196)t,∆1= 12215 >∆e. Pruned by ∆e. –p+v4= (788,195)t,∆1= 9715 >∆e. Pruned by ∆e. –p+v5= (789,194)t,∆1= 7215 = ∆e. Pruned by ∆e. –p+v6= (790,193)t. Already in the list of nodes to be processed. The corresponding diagram is displayed as ◦(787,197) ''++,,-- //•(790,193) ◦(783,202) ◦(786,198) •(787,196) •(788,195) •(789,194) List of ordered nodes {(783,202)t,(786,198)t,(790,193)t}. ?Node p= (783,202)t,∆e= 7215. Leaves p+vi, i = 1,...,6: –p+v1= (779,207)t, ∆1= 2215 <∆e, r2≤r2 0. Feasible point, and improvement. Update ∆e= 2215. 16 F. CASTRO, J. GAGO-VARGAS, M.I. HARTILLO, J. PUERTO, AND J.M. UCHA [BPT00] D. Bertsimas, G. Perakis, and S. Tayur. A new algebraic geometry algorithm for integer programming. Management Science, 46(7):999–1008, 2000. [BW05] D. Bertsimas and R. Weismantel. Optimization over Integers. Dynamic Ideas, 2005. [CF07] M. Corazza and D. Favaretto. On the existence of solutions to the quadratic mixedinteger mean-variance portfolio selection problem. European Journal of Operational Research, 176(3):1947–1960, 2007. [Chn09] Michael T. Chng. Economic linkages across commodity futures: Hedging and trading implications. Journal of Banking & Finance, 33:958–970, 2009. [CLO05] David A. Cox, John Little, and Donal O’Shea. Using algebraic geometry, volume 185 of Graduate Texts in Mathematics. Springer, New York, second edition, 2005. [CT91] Pasqualina Conti and Carlo Traverso. Buchberger algorithm and integer programming. In Applied algebra, algebraic algorithms and error-correcting codes (New Orleans, LA, 1991), volume 539 of Lecture Notes in Comput. Sci., pages 130–139. Springer, Berlin, 1991. [Dye92] Martin E. Dyer. A class of convex programs with applications to computational geometry. In Symposium on Computational Geometry, pages 9–15, 1992. [GK87] Monique Guignard and Siwhan Kim. Lagrangean decomposition: a model yielding stronger Lagrangean bounds. Mathematical Programming, 39(2):215–228, 1987. [GK08] H. Geman and C. Kharoubi. WTI crude oil futures in portfolio diversification: The time-to-maturity effect. Journal of Banking and Finance, 32(12):2553–2559, December 2008. [JHLM01] N. J. Jobst, M. D. Horniman, C. A. Lucas, and G. Mitra. Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints. Quantitative Finance, 1(5):489–501, 2001. [KTH79] M. K. Kozlov, S. P. Tarasov, and L. G. Haˇcijan. Polynomial solvability of convex quadratic programming. Dokl. Akad. Nauk SSSR, 248(5):1049–1051, 1979. Translated in Sov. Math., Dokl. 20, 1108-1111 (1979). [LC98] H.-L. Li and C.-T. Chang. An approximate approach of global optimization for polynomial programming problems. European Journal of Operational Research, 107(3):625– 632, 1998. [LT08] Han-Lin Li and Jung-Fa Tsai. A distributed computation algorithm for solving portfolio problems with integer variables. European Journal of Operational Research, 186(2):882–891, 2008. [Mar52] Harry M. Markowitz. Portfolio selection. Journal of Finance, 7:77–91, 1952. [Mar00] Harry M. Markowitz. Mean-variance analysis in portfolio choice and capital markets. Wiley, New York, 2000. [Mit03] H. D. Mittelmann. An independent benchmarking of SDP and SOCP solvers. Math. Program., 95(2, Ser. B):407–430, 2003. Computational semidefinite and second order cone programming: the state of the art. [MM91] Philippe Michelon and Nelson Maculan. Lagrangean decomposition for integer nonlinear programming with linear constraints. Mathematical Programming, 52(2, Ser. B):303–313, 1991. [MM08] Richar O. Michaud and Robert O. Michaud. Efficient asset management: a practical guide to stock portfolio optimization and asset allocation. Oxford University Press, New York, 2008. [Sha71] W. Sharpe. A linear programming approximation for the general portfolio analysis. Journal of Finance and Quantitative Analysis, 6:1263–1275, 1971. [SM05] Bernd Scherer and R. Douglas Martin. Introduction to modern portfolio optimization with NUOPT and S-PLUS. Springer, New York, 2005. [SNT85] Yoshikazu Sawaragi, Hirotaka Nakayama, and Tetsuzo Tanino. Theory of multiobjective optimization, volume 176 of Mathematics in Science and Engineering. Academic Press Inc., Orlando, FL, 1985. [Sto73] B. Stone. A linear programming formulation of the general portfolio selection model. Journal of Financial and Quantitative Analysis, 8:621–636, 1973. [Stu96] Bernd Sturmfels. Gr¨obner bases and convex polytopes, volume 8 of University Lecture Series. American Mathematical Society, Providence, RI, 1996. [tt08] 4ti2 team. 4ti2—a software package for algebraic, geometric and combinatorial problems on linear spaces. Available at www.4ti2.de, 2008. AN ALGEBRAIC APPROACH TO INTEGER PORTFOLIO PROBLEMS 17 [TTN95] Sridhar R. Tayur, Rekha R. Thomas, and N. R. Natraj. An algebraic geometry algorithm for scheduling in presence of setups and correlated demands. Mathematical Programming, 69(3, Ser. A):369–401, 1995. [YK91] H. Yamakozi and H. Konno. Mean absolute deviation portfolio optimization model and its application to Tokyo stock market. Management Science, 37:519–531, 1991. [You98] M.R. Young. A minimax portfolio selection rule with linear programming solution. Management Science, 5(44):637–683, 1998. 18 F. CASTRO, J. GAGO-VARGAS, M.I. HARTILLO, J. PUERTO, AND J.M. UCHA Appendix Procedure NewPolytope(polytope P, matrix Q, point pe,Tol,r0, MaxNumCuts) NumCuts = 0 ; pmax, r2 m=ComputeMaxRisk(P, Q) ; /* solve the problem max Q(x),x∈P. */; while r2 m−r2 0> Tol and NumCuts ≤MaxNumCuts do s=pe+λ(pmax −pe), λ ≥0 ; p0=s∩Q; v=TangentToQuadric(Q, p0) ; DirApprox =Round(v, P rec) ; /* round with number of digits = Prec */; Coef =TangentToQuadricV(DirApprox, Q) ; /* independent term of the tangent hyperplane Qand normal vector equal to DirApprox */ ; Coef =Ceil(Coef) ; /* the best integer to leave the quadric in a half-space */ ; H:= DirApproxtx−Coef ; /* new linear cut */ ; NumCuts =NumCuts + 1; P=Polytope(P, H) ; /* add a new cut to polytope P*/ ; pmax, r2 m=ComputeMaxRisk(P, Q) ; end return P Depto. de ´ Algebra, Universidad de Sevilla. Apdo. 1160, E-41080 Sevilla (Spain) E-mail address:[email protected] Depto. de ´ Algebra, Universidad de Sevilla. Apdo. 1160, E-41080 Sevilla (Spain) E-mail address:[email protected] Dpto. de Matem´ atica Aplicada I, E.T.S. de Ingenier´ ıa Inform´ atica, Av. Reina Mercedes, s/n, 41012 Sevilla, Spain E-mail address:[email protected] Dpto. de Estad´ ıstica e I.O., Facultad de Matem´ aticas, apdo. 1160, 41080 Sevilla, Spain E-mail address:[email protected] Depto. de ´ Algebra, Universidad de Sevilla. Apdo. 1160, E-41080 Sevilla (Spain) E-mail address:[email protected] AN ALGEBRAIC APPROACH TO INTEGER PORTFOLIO PROBLEMS 19 Algorithm 1: DiscreteOptimum Data: budget B, risk r2 0, matrix Q, vector a, vector µ,MaxNumCuts, MaxNumNodes, T ol Result:Optimum,NumNodesP roc pc=ComputeContinuousOptimum(B, r2 0, Q, a,µ), gc=µtpc, α = 1/2 ; pe, ge=ComputeDiscreteApprox(pc, B, a, r2 0, Q) ; SwEOP = false, SwFictBounds = false, SwImprove = false, SwNumNodes = false, ListOfV ariables = (1 : dim) ; while not SwEOP do if not SwFictBounds then b, ListOfV ariables =ComputeLowerBounds(ListOfV ariables, pe) ; end P=Polytope(atx≤B, µtx≤gc,µtx≥gd,x≥b) ; NumNodesProc = 0 ; while not (SwEOP or SwImprove or SwNumNodes)do P=NewPolytope(P, Q, pe, Tol, r0, MaxNumCuts) ; G=ComputeTestSet(P),pini =Reduce(pbounds, G) ; SwNumNodes, SwImprove, Optimum = TreeSearch(pini, G, Q, a, B, r2 0,b,pe, MaxNumNodes, SwFictBounds) ; if SwFictBounds then if not SwImprove then SwEOP = true ; else pe=Optimum, ge=µtOptimum, SwF ictBounds = false ; end else if not SwNumNodes then SwEOP = true ; else if not SwImprove then b=b+α(pe−b), SwF ictBounds = true ; end end end end end