MINOS (optimization software)

MINOS is a Fortran software package for solving linear and nonlinear mathematical optimization problems. MINOS (Modular In-core Nonlinear Optimization System) may be used for linear programming, quadratic programming, and more general objective functions and constraints, and for finding a feasible point for a set of linear or nonlinear equalities and inequalities.[1]

MINOS was first developed by Bruce Murtagh and Michael Saunders, mostly at the Systems Optimization Laboratory in the Department of Operations Research at Stanford University.[2] In 1985, Saunders was awarded the inaugural Orchard-Hays prize [3] by the Mathematical Programming Society (now the Mathematical Optimization Society) for his work on MINOS. Despite being one of the first general-purpose constrained optimization solvers to emerge, the package remains heavily used. MINOS is supported in the AIMMS, AMPL, APMonitor, GAMS, and TOMLAB modeling systems. In addition, it remains one of the top-used solvers on the NEOS Server[4][5] and in GAMS.[6]

Operation

Ideally, the user should provide gradients of the nonlinear functions. (This is automatic in most of the modeling systems mentioned above.) If some or all of the gradients are not provided, MINOS will approximate the missing ones by finite differences, but this could be slow and less reliable. If the objective function is convex and the constraints are linear, the solution obtained will be a global minimizer. Otherwise, the solution obtained may be a local minimizer.

For linear programs, a two-phase primal simplex method is used. The first phase minimizes the sum of infeasibilities. For problems with linear constraints and a nonlinear objective, a reduced-gradient method is used. A quasi-Newton approximation to the reduced Hessian is maintained to obtain search directions. The method is most efficient when many constraints or bounds are active at the solution.

For problems with nonlinear constraints, a linearly constrained Lagrangian method is used.[7] This involves a sequence of major iterations, each of which solves (perhaps approximately) a linearly constrained subproblem. The subproblem objective is an augmented Lagrangian, and the subproblem constraints are linearizations of the nonlinear constraints at the current point.

MINOS is intended for large sparse problems. There is no fixed limit on problem size. Most working storage is contained in one double-precision array (which should be sufficiently large). The source code is suitable for all scientific machines with a Fortran compiler.

References

  1. ^ B.A. Murtagh, M.A. Saunders (2003). "MINOS 5.51 User's Guide" (PDF).
  2. ^ B.A. Murtagh, M.A. Saunders (1978). "Large-scale linearly constrained optimization" (PDF). Mathematical Programming. 14: 41–72. doi:10.1007/BF01588950. S2CID 38638809.
  3. ^ Beale-Orchard-Hays Prize winners
  4. ^ NEOS Server
  5. ^ Saunders, Michael (2013). Optimization Algorithms and Software at SOL (PDF).
  6. ^ GAMS/MINOS Solver guide
  7. ^ More, Jorge J.; Wright, Stephen J. (1993). "Chapter 8: Constrained Optimization". Optimization Software Guide. Frontiers in Applied Mathematics. doi:10.1137/1.9781611970951.ch8.

Further reading


Stub icon

This article about mathematics software is a stub. You can help Wikipedia by expanding it.