Systems Optimization Laboratory

SOL Technical Reports

To request hard copies of SOL reports, for files not downloadable here, please email Walter Murray: walter@stanford.edu

A few OR reports are included from the Department of Operations Research.

2020

• S. Regev and M. A. Saunders (2020), SSAI: A symmetric sparse approximate inverse preconditioner for the conjugate gradient methods PCG and PCGLS, working paper, ICME, Stanford University, Jun 2020, 16 pages, submitted to SIAM SISC Copper Mountain issue.

2017

• D. Ma, K. L. Judd, D. Orban, and M. A. Saunders (2017), Stabilized optimization via an NCL algorithm, working paper, Stanford University, Dec 2017, 13 pages.
  Revised as D. Ma, K. L. Judd, D. Orban and M. A. Saunders, Stabilized optimization via an NCL algorithm, pp 173-191 in M. Al-Baali et al. (eds.), Numerical Analysis and Optimization, NAO-IV, Muscat, Oman, January 2017, Springer Proceedings in Mathematics and Statistics, Volume 235, Springer International Publishing AG (2018).

2015

• D. Ma and M. A. Saunders (2015), SMO vs PDCO for SVM: Sequential minimal optimization vs primal-dual interior method for convex objectives for support vector machines, working paper, Dept of Management Science and Engineering, Stanford University, Jan 2015, 5 pages.

2014

• D. Ma and M. A. Saunders (2014), Solution of multiscale linear programs using Quad precision, Report SOL 2014-1, Apr 2014, 5 pages.
  Revised 24 Aug 2014 as Solving multiscale linear programs using the simplex method in quadruple precision, pp 223-235 in M. Al-Baali, L. Grandinetti, and A. Purnama (eds.), Numerical Analysis and Optimization, NAO-III, Muscat, Oman, Springer Proceedings in Mathematics and Statistics, Volume 134, Springer International Publishing Switzerland (2015).

2013

• J. D. Lee, Y. Sun, and M. A. Saunders (2013), Proximal Newton-type methods for minimizing composite functions, Report SOL 2013-1, revised Mar 2014, 24 pages.
• Y. Sun, R. M. T. Fleming, I. Thiele, and M. A. Saunders (2013), Robust flux balance analysis of multiscale biochemical reaction networks, Report SOL 2013-2, 8 pages. Published BMC Bioinformatics 14:240 (2013). Local copy: BMCBioinformatics2013robustFBA.pdf.

2011

• R. M. T. Fleming, C. M. Maes, M. A. Saunders, Y. Ye and B. Ø. Palsson (2011), A variational principle for computing nonequilibrium fluxes and potentials in genome-scale biochemical networks, Report SOL 2011-1, 17 pages. Submitted 5 Apr 2011 to J. of Theoretical Biology. Accepted 26 Sep 2011. Published J. of Theoretical Biology 292 (2012) 71-77. Local copy: FleMSYP2012.pdf.

• D. C.-L. Fong and M. A. Saunders (2011), CG versus MINRES: An empirical comparison, Report SOL 2011-2R, to appear in SQU Journal for Science, 17:1 (2012), 44--62.
• S. Akle, O. A. Dalal, R. M. T. Fleming, M. A. Saunders, N. A. Taheri, and Y. Ye (2011), Existence of positive steady states for mass conserving and mass-action chemical reaction networks with a single terminal-linkage class, Report SOL 2011-3, 16 pages. Submitted 25 Oct 2011 to J. of Mathematical Biology.

2010

• V. Pereyra, M. A. Saunders, and J. Castillo (2010), Equispaced Pareto front construction for constrained biobjective optimization, Report SOL 2010-1, 15 pages. Published in Mathematical and Computer Modelling, available online Feb 2011.

• D. C.-L. Fong and M. A. Saunders (2010), LSMR: An iterative algorithm for sparse least-squares problems, Report SOL 2010-2R1 (revised Mar 14, 2011), 21 pages. SIAM J. Sci. Comput. 33:5, 2950-2971, published electronically Oct 27, 2011.

• D. C.-L. Fong and M. A. Saunders (2010), LSMR: An iterative algorithm for sparse least-squares problems, Report SOL 2010-2, 22 pages. This version contains Section 10.4, a suggestion for using the Golub-Kahan process to compute singular vectors of dense matrices.

• S.-C. T. Choi, C. C. Paige and M. A. Saunders (2010), MINRES-QLP: A Krylov subspace method for indefinite or singular symmetric systems, Report SOL 2010-3, 26 pages. SIAM J. Sci. Comput., submitted 08 Mar 2010, revised 30 Mar 2011, accepted Apr 27, 2011. SIAM J. Sci. Comput. 33:4, 1810-1836, published electronically Aug 4, 2011.

2009

• E. Kostina, M. A. Saunders, and I. Schierle, Computation of covariance matrices for constrained parameter estimation problems using LSQR, Report SOL 2009-1, 11 pages.

2008

• P. W. Glynn and G. Infanger (2008), Simulation-based confidence bounds for two-stage stochastic programs, Report SOL 2008-1, 18 pages.

2007

• J. F. Grcar, M. A. Saunders, and Z. Su (2007), Estimates of optimal backward perturbations for linear least squares problems, Report SOL 2007-1, 21 pages.

2006

• M. J. O'Sullivan and M. A. Saunders (2006), Stabilizing policy improvement for large-scale infinite-horizon dynamic programming, Report SOL 2006-1, 19 pages. Published in SIAM J. Matrix. Anal. Appl. 31:2 (2009), 434-459.

2004

• T.-C. Liang, T.-C. Wang, and Y. Ye (2004), A gradient search method to round the semidefinite programming relaxation solution for ad hoc wireless sensor network localization, Report SOL 2004-2, 27 pages.

2001

• A. De Miguel and W. Murray (2001), Two decomposition algorithms for nonconvex optimization problems with global variables, Report SOL 2001-1, 32 pages.
• A. De Miguel and W. Murray (2001), Generating optimization problems with global variables, Report SOL 2001-2, 14 pages.
• T. Dorstenstein (2001), Constructive and exchange algorithms for the frequency assignment problem, Report SOL 2001-3, 20 pages.

• A. Gupta and W. Murray (2000), Optimal investment with behavioral utilities using a binomial tree model for asset-returns, Report SOL 2000-1, 31 pages.
• A. Gupta and W. Murray (2000), How to spend and invest retirement savings, Report SOL 2000-2, 25 pages.

• G. Infanger (1999), Managing risk using multi-stage stochastic optimization, Report SOL 99-2, Dept of EESOR, Stanford University, 57 pages.

• A. George and M. A. Saunders (1999), Solution of sparse linear equations using Cholesky factors of augmented systems, Report SOL 99-1, Dept of EESOR, Stanford University, 9 pages. Revised Oct 26, 2000 (draft), 12 pages.

• P. E. Gill, W. Murray, and M. A. Saunders (1998), User's guide for SNOPT 5.3: A Fortran package for large-scale nonlinear programming, Report SOL 98-1, 67 pages.

• R. Entriken (1997), Language constructs for modeling stochastic linear programs, Report SOL 97-1, 17 pages.
• R. Entriken & S. Voessner (1997), Genetic algorithms for production simulation, Report SOL 97-2, 14 pages.
• P. E. Gill, W. Murray, and M. A. Saunders (1997), SNOPT: An SQP algorithm for large-scale constrained optimization, Report SOL 97-3, Dept of EESOR, Stanford University, 37 pages.
• S. Voessner, M. O’Sullivan, & U. Kausch (1997), Improving the efficiency of genetic algorithms for constrained optimization, Report SOL 97-4, 9 pages.
• S. Voessner (1997), Convergence measures for genetic algorithms, Report SOL 97-5, 10 pages.
• I. Bongartz, A. R. Conn, N. I. M. Gould, M. A. Saunders and Ph. L. Toint (1997), A numerical comparison between the LANCELOT and MINOS packages for large-scale constrained optimization, Report SOL 97-6, Dept of EESOR, Stanford University, 19 pages.
• I. Bongartz, A. R. Conn, N. I. M. Gould, M. A. Saunders and Ph. L. Toint (1997), A numerical comparison between the LANCELOT and MINOS packages for large-scale constrained optimization: the complete results, Report SOL 97-7, Dept of EESOR, Stanford University, 50 pages.
• M. O’Sullivan (1997), Linking MINOS & MATLAB, Report SOL 97-8, 27 pages.

• M. A. Saunders (1996), Computing projections with LSQR, Report SOL 96-1, 8 pages. In BIT 37:1 (1997) 96-104.
• M. Prindiville (1996), Advances in the application of stochastic programming techniques in mortgage finance, Report SOL 96-2, 85 pages.
• M. A. Saunders and J. A. Tomlin (1996), Stable reduction to KKT systems in barrier methods for linear and quadratic programming, Report SOL 96-3, Dept of EESOR, Stanford University, 9 pages.
• M. A. Saunders and J. A. Tomlin (1996), Solving regularized linear programs using barrier methods and KKT systems, Report SOL 96-4, Dept of EESOR, Stanford University, 12 pages.

• M. A. Saunders (1995), Cholesky-based methods for sparse least squares: The benefits of regularization, Report SOL 95-1, Dept of Operations Research, Stanford University, 10 pages. In L. Adams and J. L. Nazareth (eds.), Linear and nonlinear conjugate gradient-related methods, SIAM, Philadelphia, 92-100.
• G. Infanger (1995), Scheduling using relaxation and decomposition, Report SOL 95-2, 20 pages.
• W. Murray and F. Prieto (1995), A second-derivative method for nonlinearly constrained optimization, Report SOL 95-3, 48 pages.
• P. E. Gill, W. Murray, and M. A. Saunders (1995), User's guide for QPOPT 1.0: A Fortran package for quadratic programming, Report SOL 95-4, Dept of Operations Research, Stanford University, 38 pages.
• R. Entriken and C. Yu, (1995), Absolute deviation as a measure of risk, Report SOL 95-5, 9 pages.
• G. B. Dantzig and G. Infanger (1995), A Probabilistic lower bound for two-stage stochastic programs, Report SOL 95-6, 22 pages.

• G. B. Dantzig and G. Infanger (1994), Intelligent control - optimization under uncertainty for the control of hydro power systems, Report SOL 94-1, 16 pages.
• G. B. Dantzig and D. Morton (1994), Interstage dependency in multistage stochastic linear programming, Report SOL 94-2, 17 pages.
• A. Forsgren and W. Murray (1994), Newton methods for large-scale linear inequality-constrained minimization, Report SOL 94-3, 17 pages.
• M. A. Saunders (1994), Solution of sparse rectangular systems using LSQR and CRAIG, Report SOL 94-4, 14 pages. In BIT 35 (1996) 588-604.

• A. Forsgren, P. E. Gill and W. Murray (1993), Computing modified Newton directions using a partial Cholesky factorization, Report SOL 93-1, 14 pages.
• S. Guu and R. W. Cottle (1993), On processing a class of linear complementarity problems by a perturbation method, Report SOL 93-2, 17 pages.
• W. Murray and F. Prieto (1993), A sequential quadratic programming algorithm using an incomplete solution of the subproblem, Report SOL 93-3, 53 pages.
• P. E. Gill, M. A. Saunders and J. Shinnerl (1993), On the numerical stability of quasi-definite systems, Report SOL 93-4, 8 pages. See On the stability of Cholesky factorization for quasi-definite systems, SIAM Journal on Matrix Analysis and Applications. 17(1), 35--46 (1996).

• H. Chen, P. Pardalos and M. A. Saunders (1993), The simplex algorithm with a new primal and dual pivot rule, Report SOL 93-5, 8 pages.
• D. Morton (1993), Algorithmic advances in stochastic programming, Report SOL 93-6, (1993), 115 pages.
• G. Infanger (1993), Decomposition and (importance) sampling techniques for multi-stage stochastic linear programs, Report SOL 93-7, 41 pages.
• A. Krishna (1993), Enhanced algorithms for stochastic programming, Report SOL 93-8, 83 pages.

• S. A. Leichner, G. B. Dantzig and J. W. Davis (1992), A strictly improving phase I algorithm using least-squares subproblems, Report SOL 92-1. See A strictly improving linear programming Phase I algorithm, Annals of Operations Research 46/47 (1993), 409-430.

• S. A. Leichner, G. B. Dantzig and J. W. Davis (1992), A strictly improving linear programming algorithm based on a series of phase I problems, Report SOL 92-2. See A strictly improving linear programming Phase I algorithm, Annals of Operations Research 46/47 (1993), 409-430.

• L. Mathiesen (1992), Pricing of electricity in the presence of water uncertainty, Report SOL 92-3.

• S. Eldersveld (1992), Large-scale sequential quadratic programming algorithms, Report SOL 92-4.
• G. B. Dantzig (1992), An epsilon-precise feasible solution to a linear program with a convexity constraint in 1/eps^2 iterations independent of problem size, Report SOL 92-5. Submitted to Mathematical Programming Series B.
• G. B. Dantzig (1992), Bracketing to speed convergence illustrated on the von Neumann algorithm for finding a feasible solution to a linear program with a convexity constraint, Report SOL 92-6.
• S. Guu and R. W. Cottle (1992), Notes on Po and its subclasses, Report SOL 92-7.
• G. Infanger (1992), Planning under uncertainty--solving large-scale stochastic linear programs, Report SOL 92-8. Published as a book.

• F. Jarre, F. and M. A. Saunders (1991), An adaptive primal-dual method for linear programming, Report SOL 91-1.
• D. B. Ponceleon (1991), Barrier methods for large-scale quadratic programming, Report SOL 91-2.
• P. E. Gill, W. Murray, D. B. Ponceleon and M. A. Saunders (1991), Primal-dual methods for linear programming, Report SOL 91-3.
• G. B. Dantzig, and G. Infanger (1991), Large-scale stochastic linear programs: importance sampling and Benders decomposition, Report SOL 91-4. Submitted for Publication in Mathematical Programming.
• G. B. Dantzig (1991), Converting a converging algorithm into a polynomially bounded algorithm, Report SOL 91-5.
• G. Infanger (1991), Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs, Report SOL 91-6. In Annals of Operations Research 39 (1992) 69-95.
• P. E. Gill, W. Murray, D. B. Ponceleon and M. A. Saunders (1991), Solving reduced KKT systems in barrier methods for linear and quadratic programming, Report SOL 91-7.
• F. Jarre (1991), An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices, Report SOL 91-8.
• F. Jarre and M. A. Saunders (1991), Practical aspects of an interior-point method for convex programming, Report SOL 91-9.
• G. B. Dantzig, J. K. Ho and G. Infanger (1991), Solving stochastic linear programs on a hypercube multicomputer, Report SOL 91-10. Submitted for Publication in Operations Research.
• G. B. Dantzig and G. Infanger (1991), Multi-stage stochastic linear programs for portfolio optimization, Report SOL 91-11. In Proceedings of the Annual Symposium of RAMP (Research Association of Mathematical Programming) Tokyo, November 1991.

• S. K. Eldersveld and M. C. Rinar (1990), A vectorization algorithm for the solution of large, sparse triangular systems of equations, Report SOL 90-1.
• S. K. Eldersveld and M. A. Saunders (1990), A block-LU update for large-scale linear programming, Report SOL 90-2. In SIAM Journal on Matrix Analysis and Applications 13 (1992), 191-201.
• P. H. McAllister, J. C. Stone and G. B. Dantzig (1990), An interactive model management system: user interface and system design, Report SOL 90-3
• G. B. Dantzig and Yinyu Ye (1990), A build-up interior method for linear programming. Report SOL 90-4. Submitted to Mathematical Programming.
• J. Yao (1990), A generalized complementarity problem in hilbert space, Report SOL 90-5. Submitted to Journal of Mathematical Analysis and Applications.
• A. L. Forsgren and W. Murray (1990), Newton methods for large-scale linear equality-constrained minimization, Report SOL 90-6.
• J. Yao (1990), Monotone complementarity problem in hilbert space, Report SOL 90-7. Submitted to Bulletin of the Australian Mathematical Society.
• P. E. Gill, W. Murray, D. B. Ponceleon and M. A. Saunders (1990), Preconditioners for indefinite systems arising in optimization, Report SOL 90-8. In SIAM Journal on Matrix Analysis and Applications. 13 (1992), 292--311.
• R. W. Cottle and Yow-Yieh Chang (1990), Least-Index Resolution of degeneracy in linear complementarity problems with sufficient matrices, Report SOL 90-9. Submitted for Publication in SIAM Journal on Matrix Analysis and Applications.
• R. W. Cottle and Jen-Chih Yao (1990), Pseudo-monotone complementarity problems in hilbert space, Report SOL 90-10. In Journal of Optimization Theory and Applications, 75(2), November 1992.
• E. Schweitzer (1990), Modifying MINOS for solving the dual of a linear program, Report SOL 90-11. Submitted to Mathematical Programming.
• W. Murray and F. J. Prieto (1990), A sequential quadratic programming algorithm using an incomplete solution of the subproblem, Report SOL 90-12.
• W. Murray and F. J. Prieto (1990), A second-derivative method for nonlinearly constrained optimization, Report SOL 90-13.
• B. C. Eaves and A. J. Hoffman (1990), Covers by polars of arrangements, Report SOL 90-14.
• B. C. Eaves and U. G. Rothblum (1990), A discounted-cost continuous-time flexible manufacturing and operator scheduling model solved by deconvexification over time, Report SOL 90-15.
• F. Jarre (1990), Interior-point methods for convex programming, Report SOL 90-16. Accepted for publication in Applied Mathematics and Optimization.
• R. W. Cottle and Sy-Ming Guu (1990), Two characterizations of sufficient matrices, Report SOL 90-17.

• H. Hu (1989), On the feasibility of a generalized linear program, Report SOL 89-1.
• H. Hu (1989), Semi-infinite programming, Report SOL 89-2. Accepted for publication in Mathematical Programming.
• R. W. Cottle (1989), The principal pivoting method revisited, Report SOL 89-3. Published in Mathematical Programming 48, Series B, (1990) North-Holland, Pp. 369-385.
• A. Krishna (1989), Note On Degeneracy, Report SOL 89-4. Submitted for Publication in Mathematical Programming.
• K. Zikan (1989), An efficient exact algorithm for the "LEAST-SQUARES" image registration problem, Report SOL 89-5. Accepted for publication in Pattern Analysis and Machine Intelligence.
• A. Marxen (1989 Ph.D. thesis), Primal barrier methods for linear programming, Report SOL 89-6.
• F. Prieto (1989 Ph.D. thesis), Sequential quadratic programming algorithms for optimization, Report SOL 89-7.
• A. Diener (1989 Ph.D. thesis), Near-optimal operation of a multi-plant manufacturing system with central procurement, Report SOL 89-8.
• A. Diener (1989 Ph.D. thesis), Near-optimal operation of a single machine with continuous buffer feed, Report SOL 89-9.
• P. F. De Mazancourt (1989 Ph.D. thesis), A matrix factorization and its application to large-scale linear programming, Report SOL 89-10.
• A. L. Forsgren, P. E. Gill and W. Murray (1989), On the identification of local minimizers in inertia-controlling methods for quadratic programming, Report SOL 89-11.
• A. L. Forsgren, P. E. Gill and W. Murray (1989), A modified Newton method for unconstrained minimization, Report SOL 89-12.
• G. Infanger (1989), Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs, Report SOL 89-13.
• B. C. Eaves and U. G. Rothblum (1989) A class of "ONTO" multifunctions, Report SOL 89-14.
• J. Yao (1989), Generalized quasi-variational inequality and implicit complementarity problems, Report SOL 89-15. "The generalized implicit complementarity problem with applications" to appear in Journal of Mathematical Analysis and Applications. "The generalized implicit complementarity problem" submitted to Journal of Mathematical Analysis and Applications.
• J. Yao (1989), A basic theorem of complementarity for the generalized variational- like inequality problem, Report SOL 89-16. To appear in Journal of Mathematical Analysis and Applications.
• R. Entriken (1989 Ph.D. thesis), The parallel decomposition of linear programs, Report SOL 89-17. Chapter 4 submitted to ORSA Journal on Computing.
• J. Yao (1989), On mean value iterations with application to variational inequality problems, Report SOL 89-18.
• J. Yao (1989), Fixed points by Ishikawa Iterations, Report SOL 89-19. Submitted to Journal of Mathematical Analysis and Applications.

1987

• I. J. Lustig (1987), An analysis of an available set of linear programming test problems, Report SOL 87-11, 53 pages.

1986

• P. E. Gill, W. Murray, M. A. Saunders, and M. H. Wright (1986), User's guide for NPSOL 5.0: A Fortran package for nonlinear programming, Report SOL 86-1 (revised July 1998).

1983

• S. T. McCormick (1983), A combinational approach to some sparse matrix problems, Report SOL 83-5, 69 pages.
• P. E. Gill, W. Murray, M. A. Saunders and M. H. Wright (1983), Documentation for FDCALC and FDCORE, Report SOL 83-6, 21 pages.

1980

• G. B. Dantzig (1980), Expected number of steps of the simplex method for a linear program with a convexity constraint, Report SOL 80-3, 34 pages.
• N. Zadeh (1980), What is the worst case behavior of the simplex algorithm?, Report OR 80-27, 28 pages.
• J. R. Birge (1980), Solution methods for stochastic dynamic linear programs, Report SOL 80-29.

1979

• N. Buras (1979), Determining the feasibility of integrating water resource constraints into energy models, Report SOL 79-4, 97 pages.
• R. Fourer (1979), Solving staircase linear programs by the simplex method, 1: Inversion, Report SOL 79-18, 80 pages. In Mathematical Programming 23 (1982) 274-313.

1978

• W. Murray and M. H. Wright (1978), Projected Lagrangian methods based on the trajectories of penalty and barrier functions, Report SOL 78-23, 67 pages.

1977

• T. J. Connolly, G. B. Dantzig, and S. C. Parikh (1977), The Stanford pilot energy/economic model, Report SOL 77-19, 45 pages.
• P. J. Jansen (1977), Decision under several objectives, Report SOL 77-20, 65 pages.

1976

• J. A. Tomlin (1976), A program for solving linear complementarity problems by Lemke's method, Report SOL 76-16, 40 pages.

1975

• M. Kallio and E. L. Porteus (1975), A class of methods for linear programming, Report SOL 75-7, 9 pages.
• J. A. Tomlin (1975), A parametric bounding method for finding a minimum l-infinity-norm solution to a system of equations, Report SOL 75-12, 20 pages.

1974

• C. Winkler (1974), Basis factorization for block-angular linear programs: unified theory of partitioning and decomposition using the simplex method, Report SOL 74-19, 126 pages.