Class notes
sndoc7.pdf
- Course
- Institution
Lecture notes of 116 pages for the course Amplide at Abacus College, Oxford
[Show more]
Seller
Follow
1097434525U
Content preview
User’s Guide for SNOPT Version 7:Software for
Large-Scale Nonlinear Programming∗
Philip E. GILL
Department of Mathematics
University of California, San Diego, La Jolla, CA 92093-0112, USA
Walter MURRAY and Michael A. SAUNDERS
Systems Optimization Laboratory
Department of Management Science and Engineering
Stanford University, Stanford, CA 94305-4026, USA
May 30, 2006
Abstract
SNOPT is a general-purpose system for constrained optimization. It minimizes a
linear or nonlinear function subject to bounds on the variables and sparse linear or
nonlinear constraints. It is suitable for large-scale linear and quadratic programming
and for linearly constrained optimization, as well as for general nonlinear programs.
SNOPT finds solutions that are locally optimal, and ideally any nonlinear functions
should be smooth and users should provide gradients. It is often more widely useful.
For example, local optima are often global solutions, and discontinuities in the function
gradients can often be tolerated if they are not too close to an optimum. Unknown
gradients are estimated by finite differences.
SNOPT uses a sequential quadratic programming (SQP) algorithm. Search di-
rections are obtained from QP subproblems that minimize a quadratic model of the
Lagrangian function subject to linearized constraints. An augmented Lagrangian merit
function is reduced along each search direction to ensure convergence from any starting
point.
On large problems, SNOPT is most efficient if only some of the variables enter
nonlinearly, or there are relatively few degrees of freedom at a solution (i.e., many
constraints are active). SNOPT requires relatively few evaluations of the problem
functions. Hence it is especially effective if the objective or constraint functions (and
their gradients) are expensive to evaluate.
The source code is re-entrant and suitable for any machine with a Fortran compiler
(or the f2c translator and a C compiler). SNOPT may be called from a driver program
in Fortran, C, or Matlab. It can also be used as a stand-alone package, reading data
in the MPS format used by commercial mathematical programming systems.
Keywords: optimization, large-scale nonlinear programming, nonlinear constraints,
SQP methods, limited-storage quasi-Newton updates, Fortran software, C software.
pgill@ucsd.edu http://www.cam.ucsd.edu/~peg
walter@stanford.edu http://www.stanford.edu/~walter
saunders@stanford.edu http://www.stanford.edu/~saunders
∗ Partially supported by National Science Foundation grants DMI-9204208, DMI-9500668, CCR-9988205,
and CCR-0306662, and Office of Naval Research grants N00014-96-1-0274 and N00014-02-1-0076.
,Contents
1. Introduction 4
1.1 Problem types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 The SNOPT interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Overview of the package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6 Subroutine snInit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2. Description of the SQP method 7
2.1 Constraints and slack variables . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Major iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Minor iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 The reduced Hessian and reduced gradient . . . . . . . . . . . . . . . . . . . 8
2.5 The merit function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.6 Treatment of constraint infeasibilities . . . . . . . . . . . . . . . . . . . . . . 10
3. The snOptA interface 11
3.1 Subroutines associated with snOptA . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Exploiting problem structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4 Subroutine snOptA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.5 Subroutine snJac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.6 Subroutine usrfun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.7 Example usrfun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.8 Subroutine snMemA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4. The snOptB interface 31
4.1 Subroutines used by snOptB . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Identifying structure in the objective and constraints . . . . . . . . . . . . . . 31
4.3 Problem dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.4 Subroutine snOptB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.5 User-supplied routines required by snOptB . . . . . . . . . . . . . . . . . . . 39
4.6 Subroutine funcon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.7 Subroutine funobj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.8 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.9 Constant Jacobian elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.10 Subroutine snMemB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5. The snOptC interface 50
5.1 Subroutine snOptC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2 Subroutine usrfun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6. The npOpt interface 53
6.1 Subroutines used by npOpt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.2 Subroutine npOpt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.3 User-supplied subroutines for npOpt . . . . . . . . . . . . . . . . . . . . . . . 58
6.4 Subroutine funobj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.5 Subroutine funcon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.6 Constant Jacobian elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
, 3
7. Optional parameters 62
7.1 The SPECS file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.2 Multiple sets of options in the Specs file . . . . . . . . . . . . . . . . . . . . . 62
7.3 SPECS file checklist and defaults . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.4 Subroutine snSpec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7.5 Subroutines snSet, snSeti, snSetr . . . . . . . . . . . . . . . . . . . . . . . 66
7.6 Subroutines snGet, snGetc, snGeti, snGetr . . . . . . . . . . . . . . . . . . 67
7.7 Description of the optional parameters . . . . . . . . . . . . . . . . . . . . . . 68
8. Output 86
8.1 The PRINT file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.2 The major iteration log . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.3 The minor iteration log . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
8.4 Basis factorization statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
8.5 Crash statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
8.6 EXIT conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
8.7 Solution output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.8 The SOLUTION file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
8.9 The SUMMARY file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
9. Basis files 104
9.1 New and Old basis files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
9.2 Punch and Insert files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
9.3 Dump and Load files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
9.4 Restarting modified problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
References 110
Index 110
, 4 SNOPT 7 User’s Guide
1. Introduction
SNOPT is a general-purpose system for constrained optimization. It minimizes a linear
or nonlinear function subject to bounds on the variables and sparse linear or nonlinear
constraints. It is suitable for large-scale linear and quadratic programming and for linearly
constrained optimization, as well as for general nonlinear programs of the form
NP minimize f0 (x)
x
x
subject to l ≤ f (x) ≤ u,
AL x
where x is an n-vector of variables, l and u are constant lower and upper bounds, f0 (x) is
a smooth scalar objective function, AL is a sparse matrix, and f (x) is a vector of smooth
nonlinear constraint functions {fi (x)}. An optional parameter Maximize may specify that
f0 (x) should be maximized instead of minimized.
Ideally, the first derivatives (gradients) of f0 (x) and fi (x) should be known and coded
by the user. If only some of the gradients are known, SNOPT estimates the missing ones by
finite differences.
Upper and lower bounds are specified for all variables and constraints. The jth constraint
may be defined as an equality by setting lj = uj . If certain bounds are not present, the
associated elements of l or u may be set to special values that are treated as −∞ or +∞.
Free variables and free constraints (“free rows”) have both bounds infinite.
1.1. Problem types
If f0 (x) is linear and f (x) is absent, NP is a linear program (LP) and SNOPT applies the
primal simplex method [2]. Sparse basis factors are maintained by LUSOL [12] as in MINOS
[18].
If only the objective is nonlinear, the problem is linearly constrained (LC) and tends to
solve more easily than the general case with nonlinear constraints (NC). For both nonlinear
cases, SNOPT applies a sparse sequential quadratic programming (SQP) method [8], using
limited-memory quasi-Newton approximations to the Hessian of the Lagrangian. The merit
function for steplength control is an augmented Lagrangian, as in the dense SQP solver
NPSOL [11, 14].
In general, SNOPT requires less matrix computation than NPSOL and fewer evaluations
of the functions than the nonlinear algorithms in MINOS [16, 17]. It is suitable for nonlinear
problems with thousands of constraints and variables, and is most efficient if only some of
the variables enter nonlinearly, or there are relatively few degrees of freedom at a solution
(i.e., many constraints are active). However, unlike previous versions of SNOPT, there is no
limit on the number of degrees of freedom.
1.2. Implementation
SNOPT is implemented as a library of Fortran 77 subroutines. The source code is compatible
with all known Fortran 77, 90, and 95 compilers, and can be converted to C code by the
f2c translator [4] included with the distribution.
All routines in SNOPT are intended to be re-entrant (as long as the compiler allocates
local variables dynamically). Hence they may be used in a parallel or multi-threaded envi-
ronment. They may also be called recursively.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller 1097434525U. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
85443 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now