OR/MS Today - December 2005|
Maple 10 and the Global Optimization Toolbox
Integrated technical computing system for advanced nonlinear systems modeling and optimization.
By Ignacio Castillo
Maple (Maplesoft, 2005) is an integrated technical computing system that supports rapid prototyping, modular development and full project documentation. Maple allows the creation of documents that integrate mathematical results and their derivations with explanations, plots, and other forms of technical knowledge. One of the compelling features for O.R. professionals and students is that Maple allows gaining problem insight symbolically, numerically and visually. See Parlar (2000) for a discussion of Maple's usefulness in modeling and solving a wide range of O.R. problems, including optimization, stochastic processes, inventory models, queueing systems and simulation.
Optimization in Maple 10
By default, Maple comes with an optimization package (called Optimization) that supports solution strategies based on local search methods. In particular, the package supports solving linear, quadratic and nonlinear problems, and both linear and nonlinear least-squares problems. Both constrained and unconstrained problems are accepted. In general, decision variables are assumed to be continuous; however, the linear programming solver does accept integer variables. For problems that are nonconvex, only local solutions are computed; the nonlinear programming solver, however, provides a global search algorithm for univariate problems.
The Optimization package takes advantage of built-in library routines provided by the Numerical Algorithms Group (NAG). The package performs computations in either the hardware floating-point environment or the arbitrary-precision software floating-point environment. Additionally, Maple offers an interactive Optimization Assistant that supports model formulation and solution, and (through its Optimization Plotter) enables the visualization of the objective function and constraints.
In order to load the Optimization package, the following Maple input statement is used:
As a very simple example, I shall consider a tiny linear optimization problem:
The corresponding screen-shot and solution (by clicking on the Solve button and using the linear solver with default settings) are shown in Figure 1.
Clicking next on the Plot button displays the objective function in the neighborhood of the solution. The objective function surface plot projections also show the constraint lines, as well as the projected location of the computed extremum point as indicated by a small green dot (Figure 2).
Algebraic Model Form. The algebraic form is perhaps the most commonly used method to specify optimization problems. The objective function and the constraints are simply given as algebraic expressions. (This form is accepted also by the interactive Maplet.)
The Optimization package can be used to solve this problem (using default settings) with the single command-line:
Maple returns the solution as a list containing the final minimum (or maximum) value and the computed optimal point; the point is given as a list containing the values of the decision variables.
Note that the Minimize command automatically selects the most appropriate solver for the optimization problem that has been formalized. Also, if the bounds for all decision variables are of the form [0, *), the assume=nonnegative option can be used.
Matrix Model Form. The Optimization package is also able to accept optimization problems formulated in the more traditional matrix notation form (denoted in Maple as matrix form):
The matrix form is the one used by the internal solvers and generally results in best performance. Consider the matrix form of the optimization problem above:
The Optimization package can be used to solve this problem (using default settings) with the single command-line:
The Optimization package offers a command that imports a linear program from a standard MPS data file. This form of the problem may be sent directly to the linear programming solver.
I will mention the nonlinear solver components of the Optimization package briefly, as part of the review on the Global Optimization Toolbox for Maple in the following section.
In recent years, several general purpose global solution strategies have been developed and implemented and matured into reliable systems that work either as stand-alone packages or as solver engines that can be connected to various modeling environments. These new implementations make global solvers available to professionals and students, even outside the global optimization research community.
The Global Optimization Toolbox (GOT), released by Maplesoft in 2004, is the result of a joint development effort by Maplesoft and Pintér Consulting Services. The GOT incorporates a suite of nonlinear optimization methods combined with the modeling power and numerous additional features of Maple (Maplesoft, 2005). The core of the Toolbox is the Lipschitz Global Optimizer (LGO) integrated solver suite. For a current detailed technical description, refer to Pintér (2005); for a software review of the LGO, consult Benson and Sun (2000). In summary, the LGO combines (theoretically) rigorous deterministic and stochastic global search methods with traditional constrained local search methodology, to find solutions to constrained GO problems with continuous or Lipschitz model structure.
Customized versions of the LGO have been successfully implemented as stand-alone compiler-based development environments and as solver engines (currently) for AIMMS, Excel, GAMS, MPL, Mathematica and MATLAB (via a link to TOMLAB). In particular, the Global Optimization Toolbox is a tailored implementation of the LGO that has been fully integrated with Maple. Thus, the GOT can, in principle, utilize and handle all real-valued (continuous) functions that can be defined using Maple. This fact supports considerable generality and flexibility in model development, especially in nonlinear systems modeling.
As expected, GO problems implemented as Maple worksheets retain their portability across platforms and operating systems. Moreover, the use of Maple not only supports full project documentation and model development, but also allows professionals to gain problem insight symbolically, numerically and visually.
The interactive Maplet provides access to the GOT's global search solution strategies, as well as to Maple's built-in local search methods. The objective function and the constraints are defined as algebraic expressions. In order to launch the Maplet, the following Maple input is given (as before):
As an example, I shall consider a small nonconvex optimization problem.
The corresponding screen-shot and solution (by clicking on the Solve button, and using the GOT with default settings) are shown in Figure 3.
The solution found is close to the theoretical optimum (0 attained at the origin). Notice also that the GOT Optimization Assistant also offers access to Maple's local search methods that are in principle applicable to this model.
Clicking next on the Plot button provides visual cues about the nonlinear nature of the objective function and constraints (Figure 4). The plot displays the objective function in the region of the solution with respect to either one (2-D plot) or two (3-D plot) of the decision variables, fixing all other decision variables to their values at the computed optimum. The Optimization Plotter allows the possibility of looking at different subspace projections when pairing (x, y), (x, z), and (y, z) as needed. The objective function surface plot projections also show the constraint curves, as well as the projected location of the computed extremum point as (again) indicated by a small green dot. All such projections can also be rotated, to enhance the visual analysis.
Note that the user could also generate similar plots (independently of the Plotter Assistant) using the command-line mode after the solution has been obtained, using standard Maple input. The interactive Maplet simply facilitates and automates the generation of plots.
Algebraic Model Form. Consider the algebraic form of the optimization problem formulated above:
The GOT can be used to solve this problem (using default settings) with the single command-line:
Maple returns the solution as a list containing the final minimum (or maximum) value and the computed extremum point. The extremum point is a list containing the values of the decision variables.
Note that the second constraint is active at the computed solution:
Note also that Maple's built-in local search method finds an inferior (local) solution, as can be expected:
Operator Model Form. When using the operator form, the objective function and the constraints are provided as procedures: each can take one or more parameters as input and returns a scalar. This form of input is accepted by the command-line GlobalSolve, but not by the interactive Maplet.
The operator form of the optimization problem above is:
The GOT can be used to solve the problem using default settings with the command-line:
As shown above, Maple returns the solution as a list containing the final minimum (or maximum) value and the computed extremum point. The extremum point is a vector containing the values of the decision variables.
Matrix Model Form. All computations performed by the solvers in the Toolbox use floating-point vectors and matrices. Optimization problems specified in algebraic and operator forms are converted internally to matrix form.
In matrix form, the objective function and the constraints are specified as procedures taking vector and matrix parameters. The matrix form is the one used by the internal solvers and generally results in best performance. As with the operator form, this form of input is accepted by the command-line, but not by the interactive Maplet.
Here is the matrix form of the optimization problem defined above:
Given that there are three decision variables and [2, 0] is the list defining the number of inequality and equality constraints respectively, the GOT now can be used to solve the problem using default settings with the command-line statement.
As with the operator form, Maple returns the solution as a list containing the final minimum (or maximum) value and the computed extremum point. The extremum point is a vector containing the values of the decision variables.
Note that for large problem instances, the elegance and compactness of the matrix form can be retained using multiple Maple worksheets, one for the model and one (or several) for data. Data can also be stored in Excel and accessed via the Excel to Maple add-in link.
The first global strategy is based on the classical branch-and-bound algorithm that combines set partitioning steps with deterministic and randomized sampling. In order to ensure computing deterministic bounds for the global solution, this algorithm assumes that the objective function and constraints are Lipschitz continuous.
The second global strategy is a single-start random search algorithm that adaptively reduces the search region on the basis of sample results, gradually focusing the global search on the region that is estimated to contain the global solution. This algorithm assumes continuity of the objective function and the constraints, which guarantees convergence with probability one.
The third strategy uses an adaptive multi-start random search where the total sampling effort is distributed among several local searches. The results of each search leads to a corresponding initial point for the subsequent local search. Again, this algorithm assumes continuity of the model functions, and converges with probability one. This is the default strategy used by the GOT.
The local search method is based on the generalized reduced gradient algorithm and assumes that the objective function and the constraints are smooth in the neighborhood of the approximate global solution. Selecting the local search option of the GOT disables the global search phase so that only a local search is performed.
Regardless of the mode used to formalize and solve an optimization problem, the GOT calls the LGO external code that uses hardware floating precision. However, the model functions can be evaluated within Maple with higher precision (even with arbitrary precision if necessary). This interaction typically leads to high overall precision of the solution obtained.
GOT Solver Options
In general, the quality of the solution depends on the stopping criteria set by the user. This is due to the fact that the global solution strategies search for the numerical solution until one of the stopping criteria is met. The stopping criteria include:
Information regarding the progress of the solver during the solution of an optimization problem is not displayed by default. However, it is possible to receive additional runtime information for both the global and local searches, by setting the information level option higher than its default level 0. The information provided can give indications about the quality of the solution and provide some guidance about the solver options that can be adjusted, if the solution obtained with the given settings is not satisfactory.
The GOT can, in principle, handle all the functions that are defined in Maple. The evaluation of some functions, however, might cause the solver to stop if either the objective function or one of the constraints evaluates to a non-numeric result. The solution procedure also fails if an infeasible or unbounded solution is found (the latter theoretically may not occur, and thus indicates a model error). Finally, as expected, although global search solution strategies do not rely on initial values of the decision variables, the GOT is able to accept initial values if provided.
Application Perspectives and Further Information
General information about Maple, with extensive links to related products, services, examples, tutorials, books and other resources, is available at Maplesoft's Web site: www.maplesoft.com/.
Regarding the GOT add-on, the code is technically sound with robust and efficient global solution strategies. The integration of the LGO solver suite with Maple gives access to a combination of unique modeling and solver capabilities, within a single computing environment.
The GOT can be valuable to O.R. professionals and students who are comfortable with Maple or are willing to learn a little bit of Maple programming. The interactive Maplet interface is intuitive and lends itself well to classroom use and for demonstration and research purposes. The matrix form input to formalize GO problems is elegant and could be quite compact, lending itself well for larger-scale modeling purposes. Future GOT developments could include algorithms to solve mixed-integer global optimization problems (in general, the current GOT handles only small size models within this category). The LGO and its tailored versions have been successfully used in applied decision-making and optimization over the past decade, and it is anticipated that the GOT will also prove to be an effective global/local solver suite.
Ignacio Castillo is an assistant professor of operations and decision sciences at the School of Business & Economics, Wilfrid Laurier University, Waterloo, Ontario, Canada.
OR/MS Today copyright © 2005 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
Web Site © Copyright 2005 by Lionheart Publishing, Inc. All rights reserved.