Download User's Guide for SQOPT Version 7: Software for Large

1.
1.
Introduction
3
Introduction
SQOPT is a software package for solving large-scale linear programming or convex quadratic
programming problems of the form
LQP
minimize
q(x)
x
subject to l ≤
≤ u,
Ax
x
where x is an n-vector of variables, l and u are constant lower and upper bounds, A is
an m × n sparse matrix, and q(x) is a linear or quadratic objective function that may be
specified in a variety of ways.
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 +∞.
SQOPT is suitable for large problems in which the matrix A is sparse—i.e., when there
are sufficiently many zero elements in A to justify storing them implicitly. The matrix A is
input via parameters Acol(*), indA(*), locA(*) that allow you to specify the pattern of
nonzero elements in A (see Section 3.1).
1.1.
Convex objective functions
The possible forms for q(x) are summarized in Table 1. The most general form is
q(x) = φ + cTx + 12 xTHx = φ +
n
X
cj xj +
j=1
1
2
n X
n
X
xi Hij xj ,
(1.1)
i=1 j=1
where φ (phi) is a constant, c is a constant n-vector, and H is a constant symmetric n × n
matrix called the Hessian, with elements {Hij }. The defining feature of a convex quadratic
program (QP) is that H must be positive semidefinite (xTHx ≥ 0 for all x). If SQOPT
encounters a negative xTHx, it terminates with the error indicator INFO = 53.
If H = 0, then q(x) = φ + cTx and the problem is a linear program (LP). Rather than
defining an H with zero elements, you may define H to have dimension zero by setting
ncolH = 0 when calling subroutine sqOpt.
If H = 0, φ = 0, and c = 0, there is no objective function and the problem is a feasible
point problem (FP). SQOPT terminates when it finds a point that satisfies the constraints on
x. If no feasible point exists, several options are available for finding a point that minimizes
the constraint violations. (See the optional parameter Elastic mode.)
SQOPT exploits structure in the Hessian by requiring H to be defined implicitly in a
subroutine that computes the product Hx for any given vector x. Such products can be
computed efficiently if H is a sparse matrix or a sum of matrices of low rank.
Table 1: Choices for the convex objective function q(x).
Problem type
Quadratic Programming (QP)
Objective function q
T
φ+c x+
1 T
2 x Hx
T
Hessian matrix H
Symmetric positive semidefinite
Linear Programming (LP)
φ+c x
H=0
Feasible Point (FP)
Not Applicable
φ = 0, c = 0, H = 0