Sequential Quadratic Programming Method
The Large-Scale SQP Solver's Sequential Quadratic
Programming method typically requires fewer major iterations or
trial solutions than a Generalized Reduced Gradient (GRG) method. In
both methods, each major iteration requires gradients of the problem
functions, computed via finite differencing - which requires many
recalculations of the Excel worksheet (one for each variable in the
problem). Since the time for recalculation tends to dominate total
solution time, an SQP method that requires fewer major iterations is
typically faster than a GRG method, even though it "does more
work" at each major iteration - and this speed advantage grows
with the size of the problem. In V8.0, these solution methods
are greatly enhanced -- the Large-Scale SQP Solver now handles
problems with up to ten times as many degrees of freedom as in
previous versions!
Sparse Matrix Storage
Sparse matrix storage methods take advantage of sparsity
in large models, where subsets of the constraints typically
depend on only a small subset of the variables. For example, the Jacobian
matrix (the matrix of partial derivatives of the objective and
constraints with respect to the variables) for a problem with 2,000
variables and 2,000 constraints would take about 32 megabytes for
matrix storage using dense storage methods, but if this problem has
the sparsity typical of larger models, it would take as little as 1
to 1.5 megabytes using the sophisticated sparse matrix storage methods in the Large-Scale
SQP Solver.
Improved Methods for Numerical Stability
Large nonlinear models require hundreds of
thousands to millions of floating-point arithmetic calculations.
Because of the finite precision inherent in computer arithmetic, small
numerical errors occur in these calculations. Nonlinear models
are particularly susceptible to the cumulative effect of these
errors, which can lead to a numerically unstable or ill-conditioned
matrix representation of the problem.
The Large-Scale SQP Solver uses several advanced
methods to deal with numerical stability, including advanced matrix
factorization methods, and "elastic programming"
methods for dealing with infeasibility in the QP subproblems or the
overall problem. Thanks
to these methods, the Large-Scale SQP Solver can find very good or
optimal solutions to problems that could not be solved at all with
more primitive nonlinear optimizers.
Options for Mixed-Integer Nonlinear Problems
In Version 8.0, the Large-Scale SQP Solver
offers several new methods for faster solution of linear programming
problems with integer variables. It uses preprocessing
and probing techniques to preset values for some binary integer
variables based on the settings of others. It automatically
recognizes, and takes advantage of "cliques" (also called Special
Ordered Sets), tightens bounds on constraints, and reorders the
variables to be branched upon. It also uses cut generation
techniques to automatically add new constraints, known as knapsack
cuts or lifted cover inequalities, that reduce the size
of the LP feasible region without eliminating any integer
solutions. These methods can save
significant time on LP/MIP problems, depending on the model.
Back to Large-Scale SQP Solver
Engine Product
Overview
