Setting up and Solving an Optimization Problem

In OPT++, the standard form of the optimization problem is

$\begin{array}{ll} \mbox{minimize} & f(x)\\ \mbox{subject to} & g(x) \ge 0, \\ & h(x) = 0. \end{array}$

where $f: \bf{R}^n \rightarrow \bf{R}$ , $g: \bf{R}^n \rightarrow \bf{R}^{mi}$ , and $h: \bf{R}^n \rightarrow \bf{R}^{me}$ .

To solve an optimization problem with OPT++, an user must 1) write a C++ main routine which set ups the problem and algorithm and 2) write the C++ code that evaluates the function and and associated constraints. A more detailed explanation and an example appear in the following sections.

Problem Setup

As part of the main routine, the user must first construct the nonlinear function object. This provides essential information regarding the function to be optimized. In particular, it provides the dimension of the problem, pointers to the subroutines that initialize and evaluate the function (see User-Defined Functions), and a pointer to the constraints (see Constraint Setup). The constructor can take any one of multiple forms. The most common ones are shown here, along with a description of the type of problem for which each is intended. Further information about these objects can be found the detailed documentation.

NLF0(ndim, fcn, init_fcn, constraint): problem has no analytic derivative information available
NLF1(ndim, fcn, init_fcn, constraint): problem has analytic first derivatives available, but no analytic second derivatives
NLF2(ndim, fcn, init_fcn, constraint): problem has analytic first and second derivatives available
FDNLF1(ndim, fcn, init_fcn, constraint): problem has no analytic derivative information available, but finite differences are used to approximate first derivatives
LSQNLF(ndim, lsqterms, lsqfcn, init_fcn, constraint): problem has a least squares operator, Gauss-Newton is used to approximate Jacobian and Hessian

The arguments to the constructors must be defined before instantiating the function object. The following description holds for the first four nonlinear function objects, which have identical argument lists. We will define the argument list for the LSQNLF later.

The first argument, ndim, is an integer specifying the dimension of the problem. The second argument, fcn, is a pointer to the subroutine that evaluates the function. The form of this pointer/subroutine is described in more detail in the User-Defined Functions subsection. The third argument, init_fcn, is a pointer to the subroutine that initializes the function. Again, the form of this pointer/subroutine is described in the User-Defined Functions subsection. The final argument, constraint, is a pointer to a constraint object. If the optimization problem of interest has no constraints, this argument can be excluded. Otherwise, it can be constructed as described in the Constraint Setup subsection.

Once the problem has been instantiated, it must be initialized with its initFcn method. More information on these objects and their associated methods can be found in the detailed documentation; however, the tutorials on their usage in the Example Problems section will probably be more useful.

For the LSQNLF object, the first argument, ndim, is an integer specifying the dimension of the problem. The second argument, lsqterms, is an integer specifying the number of least square terms in the function. The third argument, lsqfcn, is a pointer to the subroutine that evaluates the least squares operator. The form of this pointer/subroutine is described in more detail in the User-Defined Functions subsection. The remaining arguments have the same meaning as previously defined.

Constraint Setup

Setting up the constraints consists of two main steps. The first step defines the different classes of constraints present. The second step rolls them all up into a single object. The most common forms of the necessary constructors are listed here.

constraint types
- BoundConstraint(numconstraints, lower, upper);
- LinearInequality(A, rhs, stdFlag);
- NonLinearInequality(nlprob, rhs, numconstraints, stdFlag);
- LinearEquation(A, rhs);
- NonLinearEquation(nlprob, rhs, numconstraints);
the whole shebang
- CompoundConstraint(constraints);

The arguments required by the constraint constructors are relatively self-explanatory, but require some implementation effort. numconstraints is an integer specifying the number of constraints of the type being constructed, lower is a ColumnVector containing the lower bounds on the optimization variables, upper is a ColumnVector containing the upper bounds, A is a Matrix containing the coefficients of the terms in the linear constraints, rhs is a ColumnVector containing the values of the right-hand sides of the linear and nonlinear constraints, and nlprob is a function that evaluates the nonlinear constraints. This function is set up in the same manner as the objective function described in the Problem Setup section. The variable, stdFlag is a Boolean variable indicating whether or not inequality constraints are given in standard form. The standard form is given in the detailed documentation. Finally, the single argument, constraints, to the CompoundConstraint constructor is an OptppArray of the constraints created using the constructors of the specific types.

Details about the OptppArray object can be found in the detailed documentation, while information about the ColumnVector and Matrix objects can be found in the NEWMAT documentation. The most useful documentation, however, appears in the Example Problems.

User-Defined Functions

In addition to the main routine, the user must provide additional C++ code that performs the initialization of the problem, the evaluation of the objective function, and the evaluation of any nonlinear constraints. This code must also include the computation of any analytic derivative information that is to be provided. These subroutines may appear in the same file as the main routine or in a separate file, and they must satisfy the interfaces listed below.

The function interfaces are the following:

to initialize the problem
- void (*INITFCN)(ndim, x)
to evaluate the objective function
- void (*USERFCN0)(ndim, x, fx, result): for NLF0 and FDNLF1
- void (*USERFCN1)(mode, ndim, x, fx, gx, result): for NLF1
- void (*USERFCN2)(mode, ndim, x, fx, gx, Hx, result): for NFL2
- void (*USERFCNLSQ0)(ndim, x, lsfx, result): for LSQNLF or
- void (*USERFCNLSQ1)(mode, ndim, x, lsfx, lsgx, result): for LSQNLF

The arguments of these functions are fairly straightforward. ndim is an integer that specifies the dimension of the problem, x is a ColumnVector that contains the values of the optimization variables, fx is the value of the objective function at x, gx is a ColumnVector containing the gradient of the objective function at x, Hx is a SymmetricMatrix containing the Hessian of the objective function at x, mode is an integer encoding of the type of evaluation requested (i.e., function, gradient, Hessian), and result is an integer encoding of the type of evaluations available. For the least squares operator, lsfx is a ColumnVector with each entry containing the value of one of the least squares terms and lsgx is a Matrix containing the Jacobian of the least squares operator at x. The ColumnVector, Matrix, and SymmetricMatrix objects are described in the NEWMAT documentation. The Example Problems demonstrate how to implement the user-defined functions.

Nonlinear constraints are quite similar in nature to the objective function. In fact, they are constructed using the function objects in the Problem Setup section. The interfaces for the subroutines that evaluate the nonlinear constraints, however, are slightly different from those for evaluating the objective function. The interfaces are as follows:

void (*USERNLNCON0)(ndim, x, cx, result): for nonlinear constraints with no analytic first or second derivatives
void (*USERNLNCON1)(mode, ndim, x, cx, cgx, result): for nonlinear constraints with analytic or finite-difference first derivative, but no analyatice second derivative
void (*USERNLNCON2)(mode, ndim, x, cx, cgx, cHx, result): for nonlinear constraints with analytic first and second derivatives

The arguments of these functions are fairly straightforward. ndim is an integer that specifies the dimension of the problem, x is a ColumnVector that contains the values of the optimization variables, cx is a ColumnVector with each entry containing the value of one of the nonlinear constraints at x, cgx is a Matrix with each column containing the gradient of one of the nonlinear constraints at x, cHx is an OptppArray of SymmetricMatrix with each matrix containing the Hessian of one of the nonlinear constraints at x, mode is an integer encoding of the type of evaluation requested (i.e., function, gradient, Hessian), and result is an integer encoding of the type of evaluations available. A description of OptppArray can be found in the detailed documentation. The ColumnVector and SymmetricMatrix objects are described in the NEWMAT documentation. The Example Problems demonstrate how to implement the user-defined functions. In particular, Example 2 demonstrates the use of constraints.

Setting up the Algorithm

Once the nonlinear function (see Problem Setup) has been set up, it is time to construct the algorithm object. This defines the optimization algorithm to be used and provides it with a pointer to the problem to be solved. Once this is done, any algorithmic parameters can be set, and the problem can be solved. The full set of algorithms provided and their constructors can be found throughout the documentation. We list the most common ones here, grouped according to the type of problem expected.

problem has no analytic derivatives (NLF0)
- OptPDS(&nlp): parallel direct search method; handles general constraints, but only bounds robustly
- OptGSS(&nlp, &gsb): generating set search method; handles unconstrained problems only
problem has analytic or finite-difference first derivative (NLF1 or FDNLF1)
- OptCG(&nlp): conjugate gradient method; handles unconstrained problems only
- OptLBFGS(&nlp): limited-memory quasi-Newton method for unconstrained problems; uses L-BFGS for Hessian approximation
- OptQNewton(&nlp): quasi-Newton method for unconstrained problems; uses BFGS for Hessian approximation
- OptFDNewton(&nlp): Newton method for unconstrained problems; uses second-order finite differences for Hessian approximation
- OptBCQNewton(&nlp): quasi-Newton method for bound-constrained problems; uses BFGS for Hessian approximation
- OptBaQNewton(&nlp): quasi-Newton method for bound-constrained problems; uses BFGS for Hessian approximation
- OptBCEllipsoid(&nlp): ellipsoid method for bound-constrained problems
- OptFDNIPS(&nlp): Newton nonlinear interior-point method for generally constrained problems; uses second-order finite differences for Hessian approximation
- OptQNIPS(&nlp): quasi-Newton nonlinear interior-point method for generally constrained problems; uses BFGS for Hessian approximation
problem has analytic first and second derivatives (NLF2)
- OptNewton(&nlp): Newton method for unconstrained problems
- OptBCNewton(&nlp): Newton method for bound-constrained problems
- OptBaNewton(&nlp): Newton method for bound-constrained problems
- OptNIPS(&nlp): nonlinear interior-point method for generally constrained problems
problem has least squares function operator (LSQNLF)
- OptDHNIPS(&nlp): Disaggregated Hessian Newton nonlinear interior-point method for generally constrained problems; uses Gauss-Newton approximations to compute objective function gradient and Hessian; uses quasi-Newton approximations for constraint Hessians;

In these constructors, nlp is the nonlinear function/problem object created as described in the Problem Setup section and gsb is the generating set method described in the Generating Set Search section. All of the Newton methods have a choice of globalization strategy: line search, trust region, or trust region-PDS. Furthermore, there are numerous algorithmic parameters that can be set. These can be found in the detailed documentation for each particular method.

Once the algorithm object has been instantiated and the desired algorithmic parameters set, the problem can then be solved by calling that algorithm's optimize method. Tutorial examples of how to do set up and use the optimization algorithms can be found in the Example Problems.

Example Problems

In order to clarify the explanations given above, we now step through a couple of example problems. These examples are intended to serve as a very basic tutorial. We recommend looking at the additional examples provided in the documentation in order to obtain a broader view of the capabilities of OPT++. In addition, the detailed documentation contains a complete list of the capabilities available.

Previous Section: Installation | Next Section: Alternate Forms of Nonlinear Objects | Back to the Main Page

Last revised July 25, 2006

Bug Reports OPT++ Developers Copyright Information GNU Lesser General Public License

Documentation, generated by

, last revised August 30, 2006.