|
The research of the numerical optimization community, and hence our work as well, develops tools, underlying theory and techniques, for solving large-scale optimizationproblems as may occur in engineering and science. Real-life applications that can benefit from our work abound. Manufacturers seek maximum efficiency in the design of theirproduction processes. Investors aim at creating portfolios that avoid high risk while yielding a good return. Traffic planners need to decide on the level and ways of routing traffic to minimize congestion. Finding the `best' solution for such processes commonly involves constructing a mathematical model to describe such problems. The resulting models are usually complex and large scale, depending on a large number of parameters. Models with millions of variables and restrictions are not uncommon. It is therefore imperative to implement the model on a computer and to use computer algorithms for solving it. The methods and codes aim to solve the given problem efficiently, and robustly, thus allowing the software to be employed in a variety of contexts and to be run on a diverse range of computers. Since computers cannot solve mathematical problems exactly, only approximately, one of our priorities is to ensure that the solution obtained by applying our algorithms to the models is highly accurate, close to the `true' solution of the problem.Providing theoretical guarantees that the algorithm will successfully solve the user's problem is also crucial. A useful such `safety net' is for example, the provision of global convergence of the algorithm, namely, showing the algorithm will converge to a problem solution irrespectively of the initial guess used to start the algorithm. Establishing thespeed at which the method approaches the solution is important not only to the practitioner, who is keen to have a fast algorithm, but also computationally, since for example, a fast method better prevents the accumulation of numerical errors by the simple fact of taking less time to solve the problem. The direct relation between rate of convergence and time spent solving the problem implies the latter investigation also gives us an indication how long the algorithm will take to solve the problem; we often refer to the latter as an efficiency or complexity question. We have been involved in the development of a new class of methods, Adaptive Regularization with Cubics (ARC), and related software for nonlinear optimization problems, for which efficiency estimates can be given that are better than for other standard methods, such as the classical Newton and steepest-descent methods. This is a first in the context of the problems that interest us, namely functions that `wiggle' a lot, or in standard terms, that may have many local solutions, not just one global optimum. It turns out that not only are these methods theoretically interesting, but also numerically: we implemented our method on the computer and found that it does better than existing methods for this class of problems when tested on some standard test problems. We are excited by these developments and now plan to do a `proper' computer implementation and extensive testing to see how well the ARC method does. Also, we want to see if the ARC efficiency estimate is the best possible; then, no other method could ever perform better than ARC on nonlinear problems. We are also interested in extending ARC so that it can be guaranteed to compute not just a local solution, but the global one, which is a much more challenging task. Finally, we care about the situation when the problem unknowns are restricted to belong to certain possibly-complicated sets; we also intend to develop ARC to take these restrictions into account. If our work is successful, the ARC software will become part of an optimization library, GALAHAD, that is freely available to the research community, and that has been used to solve many applications.
|