-
Notifications
You must be signed in to change notification settings - Fork 30
/
Copy pathREADME
182 lines (142 loc) · 7.55 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
NAME
OOQP - A package for solving convex quadratic programming problems.
SYNOPSIS
This directory contains OOQP, a package for solving convex quadratic
programming problems (QP). These are optimization problems in which the
objective function is a convex quadratic function and the constraints
are linear functions of a vector of real variables. They have the
following general form:
minimize (1/2) * x' * Q * x + c' * x
subject to A * x = b
C * x >= d
where Q is a symmetric positive semidefinite n by n matrix, x is a
n-vector of variables, A and C are matrices of dimensions m_a by n and
m_c by n, respectively, and c, b, and d are vectors of appropriate
dimensions.
Many QPs that arise in practice are highly structured. That is, the
matrices that define them have properties that can be exploited in
designing efficient solution techniques. In addition to the wide
variations in problem structure, there is wide divergence in the ways in
which the problem data and variables for a QP can be stored on a
computer. This distribution of OOQP contains code for the implementation
of solvers for a number of QP formulations, including a formulation for
general QPs in which the Hessian and constraint matrices are sparse. The
code in the distribution also provides a framework and examples for
users who wish to implement solvers that are tailored to their own
specific structured QPs and their specific computational environments.
OBTAINING OOQP
Visit <http://www.cs.wisc.edu/~swright/ooqp> to obtain the latest
version of OOQP.
GETTING STARTED
The file INSTALL, included in this directory, is the installation guide
for the OOQP package.
Further documentation is available in the doc/ directory. For an index
of the available documentation, point your favorite html viewer (e.g.
Firefox) at the file doc/index.html. On many systems, this can be done
by entering a string of the following form into the location window on
the browser:
file:/full/path/OOQP/doc/index.html
The OOQP Users Guide, which contains a more complete description of OOQP
and its capabilities, can be found at doc/ooqp-userguide.pdf. This file
is in PDF format, which may be read by such programs as Adobe Acrobat
Reader. If your browser contains a PDF plug-in, you may simply click on
the link "Users Guide" from the doc/index.html file to display the
Guide.
Those wishing to use the OOQP framework to develop customized QP solvers
should first read the Users Guide, and then browse through the reference
manual, which is presented as a collection of web pages in the directory
doc/reference_manual, also available as a link from doc/index.html
PROBLEM FORMULATIONS SUPPORTED IN THE OOQP DISTRIBUTION
The OOQP distribution contains a solver for general sparse QPs, together
a number of modules for solving certain structured QPs. Documentation
for these modules can be found in the doc/formulations directory. The
modules are as follows.
QpGen
This module solves general convex quadratic programs with sparse
data. This problem is discussed at length in the Users Guide.
QpBound
This module solves bound-constrained quadratic programs, in which
the only constraints are bounds on the variables. The formulation is
as follows.
minimize (1/2) * x' * Q * x + c' * x
subject to l <= x <= u
See QpBound for more information.
Svm This module creates a support vector machine classifier for solving
the pattern classification problem in machine learning. See the Svm
for more information.
Huber
Solves the Huber regression problem. See Huber.
COMMAND LINE EXECUTABLES
The installation process will generate a number of command-line
executables. A typical executable will be named
formulation-linag-solver.exe
Where the strings "formulation", "linalg" and "solver" will be replaced
by appropriate values. The "formulation" string will be one of the
problem formulations given in the preceding section, expressed in
lowercase characters: qpgen, qpbound, svm, or huber. The "solver" string
indicates the optimization algorithm used to solve the QP. It will have
one of the following values:
mehrotra
Mehrotra's predictor-corrector algorithm
gondzio
Mehrotra's algorithm with Gondzio's higher-order corrections
The "linalg" string is meant to represent how the linear algebra
operations are performed. Typical values are "sparse", "dense" and
"petsc". In some cases, the string will more specific, also referring to
the linear solver used to solve linear equations, for instance
"sparse-ma57." The linalg string does not appear in the names of the
executables "svm-gondzio.exe" and "huber-gondzio.exe", for which we felt
it would be redundant. (In these formulations, dense matrices are used
to represent the larger, structured matrices that appear in the QP
formulation.)
Not all combinations of formulations, algorithms, and linear algebra
packages are supported or provided. See the INSTALL file for information
on how to build all supported executables. A users guide for executables
based on the QpGen formulation may be found in doc/ooqp-userguide.pdf.
For other executables, see the man page of their respective formulation
in doc/formulations.
USE WITH MATLAB
Some QP solvers supplied with OOQP may be invoked within the Matlab
environment. Installation instructions, in addition to the general
instructions found in INSTALL, have been supplied in the README_Matlab
file. Once the Matlab interface has been properly installed,
documentation is available from within Matlab, as described in the
README_Matlab file.
USE WITH AMPL
A solver for the QpGen formulation may be invoked from within Ampl. Use
of this solver is documented in the OOQP Users Guide.
EXAMPLES
The examples/ directory contains sample data and example programs
demonstrating the use of OOQP. See the examples/README file for
information on the contents of the examples directory.
The src/QpExample directory contains an implementation of the
formulation discussed extensively in the OOQP Users Guide. These files
can be modified in the manner described in the Users Guide to create a
specialized QP solver.
CONTENTS OF THE DISTRIBUTION
The OOQP distribution contains the following top-level subdirectories:
config/
Helper files for configuring OOQP. This is part of the GNU Autoconf
system and is of no interest to most users.
doc/
Documentation for the distribution. Point a browser at
doc/index.html to see the available documentation.
doc-src/
Files use to create the documentation for the distribution. These
are of no interest to most users.
examples/
Example problems and programs. See examples/README.
include/
Header files for OOQP. The header files are copied from src/ into
this directory as part of the installation process.
lib/
Compiled libraries for OOQP (once you compile them).
src/
Source files for the OOQP distribution.
CREDITS
OOQP is maintained by:
E. Michael Gertz
Stephen Wright
Computer Sciences Department, University of Wisconsin, Madison.
<http://www.cs.wisc.edu/~swright/>