Interval Analysis: Contributions to static and dynamic optimization
Elwin de Weerdt · Research Repository (Delft University of Technology) · 2010
The field of global optimization has been an active one for many years. By far the most applied methods are gradient and evolutionary based algorithms. The most appearing drawback of those types of methods is that one cannot guarantee that the global solution is found within finite time. Moreover, if the global solution is found (by chance), the methods cannot provide a guaranteed feedback to the user stating that the provided solution is the global one. Therefore, no natural stopping conditions are available for most of the existing optimization algorithms. There are, however, other tools available, which do provide the guarantee that the global solution is found and that have natural stopping conditions. Interval analysis in combination with interval arithmetic is such a tool. Interval arithmetic was initially developed to cope with rounding errors in digital computers. Using interval arithmetic, one can perform reliable computing such that catastrophic numeric errors can be prevented (the explosion of the Ariane 5 rocket on June 4, 1996 was caused by a simple numeric overflow). It was soon found, that interval arithmetic could be used to form guaranteed bounds on any type of function or numeric algorithm for any domain. These bounds provide the crucial information needed to perform global optimization. Interval analysis is the group name of all methods that use the information obtained from guaranteed bounds to solve global optimization problems. Developed in the 1960’s, interval analysis gained popularity during the 90’s when digital computers became increasingly powerful. Nowadays, interval analysis has been widely applied in the field of static optimization, i.e. optimization that does not involve differential algebraic equations, and verified integration. However, interval analysis has not been applied often in the field of dynamic optimization. The goal of the research is to investigate whether interval analysis, in combination with interval arithmetic, can be used to solve non-linear, constrained, dynamic optimization problems. Moreover, the possibility of extending existing theory in the field of static optimization is investigated. The focus of the research lies on trajectory optimization (a specific case of dynamic optimization). The most important condition of the designed solvers is that the dynamic constraints, formed by the equations of motion, must be satisfied for all time instances. To reach the research objectives, the theory and application of both interval arithmetic and interval analysis have been thoroughly investigated. The work is divided into two parts. The first part is on static optimization, which includes the discussion on interval arithmetic and describes the basics regarding interval analysis. The existing theory of inclusion functions, formed via interval arithmetic, has been evaluated and extended upon. The development of the Polynomial Inclusion Function, a new type of inclusion function, shows that significant improvements are possible in this field. During the review of interval analysis, its main virtues and limitations were demonstrated. The most important advantages are the guarantee that all optimal solutions are found to any degree of accuracy and that the user knows when the solution set has been found. The main limitation is the curse of dimensionality: the computational load grows, for most problems, exponentially with al linear increase in problem dimension. The author believes that this curse is mainly caused by two aspects of the current implementation of interval analysis. The first aspect is the widening of the inclusion function due to the dependency effects. The dependency effects can be partially prevented by efficient implementation of function evaluations and through application of advanced inclusion functions. However, a generic efficient method for preventing dependency effects is still not available. The other aspect causing the curse of dimensionality is the current inefficient handling of available information. The optimization algorithms within interval analysis are commonly based on branch and bound algorithms. Through a process of elimination, one is left with a list of domains in which the optimal solution set must lie. Current methods for eliminating (part of) the domain, such as the Newton step, do not use the gathered/available information efficiently. This is mainly due to the definition of the domain and the storage of the information, i.e. keeping track of infeasible regions. It is the author’s opinion that this is the reason that the application of interval analysis is limited to solving lower dimensional problems. Despite the curse of dimensionality, interval analysis based solvers can solve complicated, non-linear, constrained problems. This has been shown in multiple chapters in the first part. Complicated problems, such as neural network output optimization and the problem integer ambiguity resolution in the field of Global Navigation Satellite Systems, are solved rigorously by interval analysis based solvers. The applications show that equality and inequality constraints are efficiently handled using interval analysis. Moreover, they show that interval analysis can be used to solve real-life problems and demonstrate that interval analysis is a strong global optimization tool. The second part of the research is on dynamic optimization, thereby focusing on trajectory optimization. The trajectory optimization problem is infinite dimensional with begin and end-point constraints, dynamic constraints (the equations of motion), and possibly additional equality and inequality constraints. The problem is infinite dimensional since the states and controls need to be specified for each time instance. In the field of trajectory optimization one can identify two classes of methods: indirect methods and direct methods. Disregarding the optimization problems for which an analytic solution is present, both classes require a transformation to make the problem solvable. Three transformation methods have been considered: control parameterization, state parameterization, and control and state parameterization. With control parameterization, the control is defined for each time step using a polynomial and the states are computed using explicit integration. For state parameterization, the states are defined and the controls are deduced via the equations of motion (implicit integration). The last method applies parameterization of both the states and controls with respect to time. Trajectories are sought that satisfy the dynamic constraints at given time instances. The nature of the transformation methods implies that the first two methods can be used to find trajectories that satisfy the dynamic constraints at all time instances, while the latter cannot be used for this purpose. Therefore, only the first two methods have been thoroughly investigated. The last method was only briefly reviewed. The main conclusion regarding the control parameterization approach is that it suffers greatly from the required explicit integration. Although verified integration is possible and sharp bounds on the trajectories can be provided, the problem is to prove the existence of a solution within a given domain of the search space. Without the ability to update the estimate of the minimal cost function value early in the optimization process, the computational load becomes very high. Despite the drawback of control parameterization, it has been demonstrate that this approach can be used to find the global solution, although, currently, only very low dimensional problems can be solved. Higher dimensional problems can be solved using the state parameterization approach. By using simplex splines, the begin- and end-point constraints can be implicitly satisfied, which significantly reduces the problem complexity. The limitation is that the approach is only suitable for fully controllable systems. For systems that are not fully controllable one needs to apply explicit integration for all dependent states. This will increase the computational load significantly and would eliminate most of the benefits of the state parameterization approach. An interval analysis based solver has been applied to solve the problem of satellite trajectory planning for formation flying. Although still suffering from the curse of dimensionality, the results demonstrate that interval analysis can be used to solve the problem rigorously. Moreover, it has been shown that the performance of the solver is superior to gradient based solvers when constraints are imposed. The main conclusion of the research is that it is possible to apply interval analysis to dynamic optimization. The current status of the solvers (in this thesis and in literature) allows one to solve only ‘lower’ dimensional problems. Radical changes in the approach of handling information and keeping track of infeasible regions must be made to make interval analysis applicable to higher dimensional problems. Despite the limitations of interval analysis, the presented results clearly demonstrate the virtues of interval analysis based solvers in the field of global optimization. Several new exciting research opportunities have been identified, such as nonlinear stability analysis using interval analysis, the combination of interval analysis and evolutionary algorithms, and a new way of forming inclusion functions to boost the efficiency of interval analysis based solvers. Overall, the potential of interval analysis is very large and the author believes that interval analysis will become one of the most important tools in the field of global optimization in the near future.