MINOS (optimization software)

Last updated

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]

Contents

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.

Related Research Articles

Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.

<span class="mw-page-title-main">Mathematical optimization</span> Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Multi-disciplinary design optimization (MDO) is a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines. It is also known as multidisciplinary system design optimization (MSDO), and Multidisciplinary Design Analysis and Optimization (MDAO).

In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear. An optimization problem is one of calculation of the extrema of an objective function over a set of unknown real variables and conditional to the satisfaction of a system of equalities and inequalities, collectively termed constraints. It is the sub-field of mathematical optimization that deals with problems that are not linear.

In mathematical optimization, the active-set method is an algorithm used to identify the active constraints in a set of inequality constraints. The active constraints are then expressed as equality constraints, thereby transforming an inequality-constrained problem into a simpler equality-constrained subproblem.

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard. With recent advancements in computing and optimization algorithms, convex programming is nearly as straightforward as linear programming.

SNOPT, for Sparse Nonlinear OPTimizer, is a software package for solving large-scale nonlinear optimization problems written by Philip Gill, Walter Murray and Michael Saunders. SNOPT is mainly written in Fortran, but interfaces to C, C++, Python and MATLAB are available.

The Frank–Wolfe algorithm is an iterative first-order optimization algorithm for constrained convex optimization. Also known as the conditional gradient method, reduced gradient algorithm and the convex combination algorithm, the method was originally proposed by Marguerite Frank and Philip Wolfe in 1956. In each iteration, the Frank–Wolfe algorithm considers a linear approximation of the objective function, and moves towards a minimizer of this linear function.

In mathematical optimization, constrained optimization is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The objective function is either a cost function or energy function, which is to be minimized, or a reward function or utility function, which is to be maximized. Constraints can be either hard constraints, which set conditions for the variables that are required to be satisfied, or soft constraints, which have some variable values that are penalized in the objective function if, and based on the extent that, the conditions on the variables are not satisfied.

In mathematical optimization and related fields, relaxation is a modeling strategy. A relaxation is an approximation of a difficult problem by a nearby problem that is easier to solve. A solution of the relaxed problem provides information about the original problem.

In the field of mathematical optimization, Lagrangian relaxation is a relaxation method which approximates a difficult problem of constrained optimization by a simpler problem. A solution to the relaxed problem is an approximate solution to the original problem, and provides useful information.

The Galahad library is a thread-safe library of packages for the solution of mathematical optimization problems. The areas covered by the library are unconstrained and bound-constrained optimization, quadratic programming, nonlinear programming, systems of nonlinear equations and inequalities, and non-linear least squares problems. The library is mostly written in the Fortran 90 programming language.

Sequential quadratic programming (SQP) is an iterative method for constrained nonlinear optimization which may be considered a quasi-Newton method. SQP methods are used on mathematical problems for which the objective function and the constraints are twice continuously differentiable, but not necessarily convex.

Penalty methods are a certain class of algorithms for solving constrained optimization problems.

Augmented Lagrangian methods are a certain class of algorithms for solving constrained optimization problems. They have similarities to penalty methods in that they replace a constrained optimization problem by a series of unconstrained problems and add a penalty term to the objective, but the augmented Lagrangian method adds yet another term designed to mimic a Lagrange multiplier. The augmented Lagrangian is related to, but not identical with, the method of Lagrange multipliers.

Convex Over and Under ENvelopes for Nonlinear Estimation (Couenne) is an open-source library for solving global optimization problems, also termed mixed integer nonlinear optimization problems. A global optimization problem requires to minimize a function, called objective function, subject to a set of constraints. Both the objective function and the constraints might be nonlinear and nonconvex. For solving these problems, Couenne uses a reformulation procedure and provides a linear programming approximation of any nonconvex optimization problem.

Artelys Knitro is a commercial software package for solving large scale nonlinear mathematical optimization problems.

Sequential linear-quadratic programming (SLQP) is an iterative method for nonlinear optimization problems where objective function and constraints are twice continuously differentiable. Similarly to sequential quadratic programming (SQP), SLQP proceeds by solving a sequence of optimization subproblems. The difference between the two approaches is that:

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


E-to-the-i-pi.svg

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.