This paper describes a practical algorithm for large-scale mean-variance portfolio optimization. The emphasis is on developing an efficient computational approach applicable to the broad range of portfolio models employed by the investment community. What distinguishes these from the “usual” quadratic program is (i) the form of the covariance matrix arising from the use of factor and scenario models of return, and (ii) the inclusion of transactions limits and costs. A third aspect is the question of whether the problem should be solved parametrically in the risk-reward trade off parameter, λ, or separately for several discrete values of λ. We show how the parametric algorithm can be made extremely efficient by “sparsifying” the covariance matrix with the introduction of a few additional variables and constraints, and by treating the transaction cost schedule as an essentially nonlinear nondifferentiable function. Then we show how these two seemingly unrelated approaches can be combined to yield good approximate solutions when minimum trading size restrictions (“buy or sell at least a certain amount, or not at all”) are added. In combination, these approaches make possible the parametric solution of problems on a scale not heretofore possible on computers where CPU time and storage are the constraining factors.