The WIND The WIND 
Nonlinear constrained optimization problems come in many forms and with many different properties. Numerical methods for the solution of optimization problems often exploit specific problem properties to gain efficiency. One important property is the size of the problem. Although the problem size refers to the number of variables and the number of constraints, there is no defined point at which a problem is considered large. Problems with hundreds or thousands of variables and constraints are currently considered large.
More importantly, many large problems exhibit the property of sparsity of the Jacobian matrix as well. That is, most elements of the matrix of first partial derivatives of the objective function and constraint functions with respect to the variables are zero. When we speak of large scale problems, we also mean sparse problems. Our solver for large problems, Lsgrg2, exploits sparsity to make the solution process much more efficient. Lsgrg2 is capable of solving problems with thousands of variables and thousands of constraints that would not be possible to solve with conventional methods.
Lsgrg2 makes the efficiency gains in the inner loop where it uses linear algebra codes specifically designed to deal with sparse systems. To show the significant savings in time, we consider a problem with N variables and N-1 constraints. The Jacobian matrix for our problem has about 4 nonzero coefficients in each row. The graph below shows the time (in seconds) used to solve problems of various sizes. All problems were solved on a Pentium 120 system.
|
You can see from the graph that the time to solve this problem in full mode is significantly larger than the time to solve it in sparse mode. The memory requirements are also significantly larger in full mode. When N = 500, the time to solve in full mode is 235 seconds compared to just 21 seconds when sparse mode is used. The real importance of having a sparse optimizer is not that it can solve your current problems faster (although it can). No, the real importance is that you can now solve problems that (previously) you could not even attempt.
The time to solve large problems can also be reduced by providing derivatives directly rather that having Lsgrg2 compute them numerically (using forward differences). Numerical derivatives require N function evaluations. It is often the case that derivatives can be computed in much less time than the time needed for N function evaluations and often derivatives can be computed in about the time needed for one function evaluation. The issue comes down to the time needed to perform function evaluations. In the simplest problems, total solution time is doubled when derivatives are computed numerically. When functions are more complicated and more costly to evaluate, the factor can be 5 or 10 or more. Since large problems often take minutes or hours to solve, a reduction in the solution time by a factor of 2 or more is significant. Lsgrg2 makes it possible for the user to provide derivatives directly.
Large Scale Applications-- Large sparse applications occur many times when problems have a large number of constraints and these constraints (individually) depend on a small number of variables. This happens quite naturally when modeling cash flows and process flows. We list several applications below that can benefit from Lsgrg2:
Windward Technologies has undertaken a development project in global optimization. Most optimization problems have many local optima, and most optimization algorithms are designed to converge to one of these local optima. Important exceptions to this statement are certain classes of problems where local optima are necessarily global optima. These exceptions include linear programs and more generally convex programs.
WTI is developing software that uses GRG2 or LSGRG2 as a kernel for a comprehensive global optimization algorithm. This software should be especially effective for troublesome nonlinear least squares problems as well as other notoriously difficult global problems.
An important distinction between this software and most other software in the global optimization area is the ability to treat problems that have nonlinear equality and inequality constraints. This is a major improvement over the usual situation where unconstrained problems are normally addressed.
Our approach to these difficult problems is straightforward. We plan to generate starting points for GRG2 or LSGRG2 through various well-known strategies. These strategies include
A major issue is efficiency. That is, we expect to develop insight and code that will determine the proper number of iterations for the GRG algorithm in order to determine if the current guess should be saved and explored further. In the early stages of searching for a global minimum it makes no sense to find a highly accurate solution to a local minimum which is not global. In the latter stages, the GRG algorithm should be run to conclusion so that the best solution can be found.
If you or your company has a particularly difficult optimization problem with several
local optima, we invite you to submit this problem for inclusion in our test suite.
Two of WTI 's products are listed in the MATLAB Connections Directory. This publication highlights add-on functions for MATLAB. Our products (GRG2 and BCLS) are designed with MATLAB interfaces.
We have developed a new Excel add-in. We delivered an Excel application that generates
Pareto plots from raw data. Engineers at Shell Oil Company are currently using this
software.
On 3 September 1996, Cray Research announced that once again Slowinski and Gage have set a new record by finding the prime
21257787-1
which has 378,632 digits. This is the largest known prime by far-the next largest has "only" 258,716 digits. It is also the 34th Mersenne prime to be discovered (though it might not be the 34th in order of size as the entire region below it has not been checked).
The proof of this 378,632 digit number's primality (using the traditional Lucas-Lehmer test) took about 6 hours on one CPU of a CRAY T94 super computer. Richard Crandall and others independently verified the primality. The first and the most interesting of these was George Woltman who was 90% of the way through that very number when asked to check the result on April 15th. According to the San Jose Mercury News article he said "It hurt for a few days, but I got over it." Woltman's program is available over the Internet and will check this new prime in about 60 hours on a 90MHz Pentium.
For more information on this particular topic and on primes in general we direct the
interested reader to: http://www.utm.edu/research/primes/
Tom Aird attended IFAC (International Federation of Automatic Control) 96 which was held in San Francisco, June 30 - July 5 and the 1996 IEEE Conference on Control Applications held in Dearborn Michigan, Sept. 15-18.
Tom joined Visual Solutions in their exhibit to give demos and explain VisSim / OptimizePRO to many of the conference attendees.
Tom will attend the fall meeting of the Dean's Advisory Council, School of Science,
Purdue University, in Lafayette Indiana, Oct. 19-21.
ON SITE CONSULTING We find that many of our clients have an explicit need to upgrade or add optimization to their products, but they do not have the time to invest in coming up to speed on the new technologies. At WTI we recognize this need and offer a site visit and consultation on your specific software needs. The cost for this service is $500 a day, plus expenses.
GUARANTEE We are so convinced in the quality of this service and our products in
general that if you are not completely satisfied, we offer a 90 day money-back guarantee.
This is a quarterly newsletter of Windward Technologies, Inc. Please let us know what
your interests are and what sort of articles you would like to see. Please contact us if
you would like to have your name added to our newsletter mailing list or if you would like
to contribute an article to the newsletter!
| Phone: | 281-564-6523 |
| Fax: | 281-564-6921 |
| Mail: | Windward Technologies, Inc. |
| 12039 Mulholland | |
| Meadows, TX 77477 | |
| E-mail: | info@maxthis.com |
Regards,
Tom Aird
TomAird@aol.com and
Phil Smith
PWSmith@aol.com
