Adjoint concepts for the optimal control of Burgers equation

Adjoint techniques are a common tool in the numerical treatment of optimal control problems. They are used for efficient evaluations of the gradient of the objective in gradient-based optimization algorithms. Different adjoint techniques for the optimal control of Burgers equation with Neumann boundary control are studied. The methods differ in the point in the numerical algorithm at which the adjoints are incorporated. Discretization methods for the continuous adjoint are discussed and compared with methods applying the application of the discrete adjoint. At the example of the implicit Euler method and the Crank Nicolson method it is shown that a discretization for the adjoint problem that is adjoint to the discretized optimal control problem avoids additional errors in gradient-based optimization algorithms. The approach of discrete adjoints coincides with that of automatic differentiation tools (AD) which provide exact gradient calculations on the discrete level.     

Finding preferred subsets of Pareto optimal solutions

Multi-objective optimization algorithms can generate large sets of Pareto optimal (non-dominated) solutions. Identifying the best solutions across a very large number of Pareto optimal solutions can be a challenge. Therefore it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optimal solutions. This paper analyzes a discrete optimization problem introduced to obtain optimal subsets of solutions from large sets of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. Two exact algorithms and five heuristics are presented to address this problem. Five test problems are used to compare the performances of these algorithms and heuristics. The results suggest that preferred subset of Pareto optimal solutions can be efficiently obtained using the heuristics, while for smaller problems, exact algorithms can be applied.     

Numerical solution of Hopf bifurcation problems

We present two numerical methods for the solution of Hopf bifurcation problems involving ordinary differential equations. The first one consists in a discretization of the continuous problem by means of shooting or multiple shooting methods. Thus a finite-dimensional bifurcation problem of special structure is obtained. It may be treated by appropriate iterative algorithms. The second approach transforms the Hopf bifurcation problem into a regular nonlinear boundary value problem of higher dimension which depends on a perturbation parameter ?. It has isolated solutions in the ?-domain of interest, so that conventional discretization methods can be applied. We also consider a concrete Hopf bifurcation problem, a biological feedback inhibition control system. Both methods are applied to it successfully.     

Regularization methods for optimization problems with probabilistic constraints

We analyze nonlinear stochastic optimization problems with probabilistic constraints on nonlinear inequalities with random right hand sides. We develop two numerical methods with regularization for their numerical solution. The methods are based on first order optimality conditions and successive inner approximations of the feasible set by progressive generation of p-efficient points. The algorithms yield an optimal solution for problems involving α-concave probability distributions. For arbitrary distributions, the algorithms solve the convex hull problem and provide upper and lower bounds for the optimal value and nearly optimal solutions. The methods are compared numerically to two cutting plane methods.     

Complexity and algorithms for nonlinear optimization problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005.     

Optimization of ship manoeuvring within the project GALILEOnautic

The goal of the project GALILEOnautic is to develop a system for autonomous navigation and optimal manoeuvring of cooperative ships within safety-critical areas. In this context, many challenges arise in the field of optimization and optimal control. The research presented here addresses one of them, namely, the calculation of optimal trajectories and controls for a group of cooperative ships navigating within the limits of a harbour. The adopted approach is to embed all aspects of the problem into a single optimal control problem, whose objective is to minimize the time to destination of each ship as well as their overall energy consumption. Path constraints are applied to maintain the ships at a safe distance from each other and from the infrastructure of the harbour. A two-ship scenario is implemented, for which optimal trajectories and controls are successfully computed. The numerical computation of this problem is performed using the software library WORHP, the official ESA NLP solver, and moreover the software TransWORHP, which transcribes optimal control problems into optimization problems. (© 2017 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Abort landing in windshear: Optimal control problem with third-order state constraint and varied switching structure

Optimal abort landing trajectories of an aircraft under different windshear-downburst situations are computed and discussed. In order to avoid an airplane crash due to severe winds encountered by the aircraft during the landing approach, the minimum altitude obtained during the abort landing maneuver is to be maximized. This maneuver is mathematically described by a Chebyshev optimal control problem. By a transformation to an optimal control problem of Mayer type, an additional state variable inequality constraint for the altitude has to be taken into account; here, its order is three. Due to this altitude constraint, the optimal trajectories exhibit, depending on the windshear parameters, up to four touch points and also up to one boundary arc at the minimum altitude level. The control variable is the angle of attack time rate which enters the equations of motion linearly; therefore, the Hamiltonian of the problem is nonregular. The switching structures also includes up to three singular subarcs and up to two boundary subarcs of an angle of attack constraint of first order. This structure can be obtained by applying some advanced necessary conditions of optimal control theory in combination with the multiple-shooting method. The optimal solutions exhibit an oscillatory behavior, reaching the minimum altitude level several times. By the optimization, the maximum survival capability can also be determined; this is the maximum wind velocity difference for which recovery from windshear is just possible. The computed optimal trajectories may serve as benchmark trajectories, both for guidance laws that are desirable to approach in actual flight and for optimal trajectories may then serve as benchmark trajectories both for guidance schemes and also for numerical methods for problems of optimal control.This paper is dedicated to Professor George Leitmann on the occasion of his seventieth birthday.     

An incremental clustering algorithm based on hyperbolic smoothing

Clustering is an important problem in data mining. It can be formulated as a nonsmooth, nonconvex optimization problem. For the most global optimization techniques this problem is challenging even in medium size data sets. In this paper, we propose an approach that allows one to apply local methods of smooth optimization to solve the clustering problems. We apply an incremental approach to generate starting points for cluster centers which enables us to deal with nonconvexity of the problem. The hyperbolic smoothing technique is applied to handle nonsmoothness of the clustering problems and to make it possible application of smooth optimization algorithms to solve them. Results of numerical experiments with eleven real-world data sets and the comparison with state-of-the-art incremental clustering algorithms demonstrate that the smooth optimization algorithms in combination with the incremental approach are powerful alternative to existing clustering algorithms.     

Dynamic programming and Lagrange multipliers for active relaxation of resources in nonlinear non-equilibrium systems

In power production problems maximum power and minimum entropy production and inherently connected by the Gouy–Stodola law. In this paper various mathematical tools are applied in dynamic optimization of power-maximizing paths, with special attention paid to nonlinear systems. Maximum power and/or minimum entropy production are governed by Hamilton–Jacobi–Bellman (HJB) equations which describe the value function of the problem and associated controls. Yet, in many cases optimal relaxation curve is non-exponential, governing HJB equations do not admit classical solutions and one has to work with viscosity solutions. Systems with nonlinear kinetics (e.g. radiation engines) are particularly difficult, thus, discrete counterparts of continuous HJB equations and numerical approaches are recommended. Discrete algorithms of dynamic programming (DP), which lead to power limits and associated availabilities, are effective. We consider convergence of discrete algorithms to viscosity solutions of HJB equations, discrete approximations, and the role of Lagrange multiplier λ associated with the duration constraint. In analytical discrete schemes, the Legendre transformation is a significant tool leading to original work function. We also describe numerical algorithms of dynamic programming and consider dimensionality reduction in these algorithms. Indications showing the method potential for other systems, in particular chemical energy systems, are given.     

A Continuous Implementation of a Second-Variation Optimal Control Method for Space Trajectory Problems

The paper describes a continuous second-variation method to solve optimal control problems with terminal constraints where the control is defined on a closed set. The integration of matrix differential equations based on a second-order expansion of a Lagrangian provides linear updates of the control and a locally optimal feedback controller. The process involves a backward and a forward integration stage, which require storing trajectories. A method has been devised to store continuous solutions of ordinary differential equations and compute accurately the continuous expansion of the Lagrangian around a nominal trajectory. Thanks to the continuous approach, the method adapts implicitly the numerical time mesh and provides precise gradient iterates to find an optimal control. The method represents an evolution to the continuous case of discrete second-order techniques of optimal control. The novel method is demonstrated on bang–bang optimal control problems, showing its suitability to identify automatically optimal switching points in the control without insight into the switching structure or a choice of the time mesh. A complex space trajectory problem is tackled to demonstrate the numerical robustness of the method to problems with different time scales.     

A global optimization method for the design of space trajectories

The problem of optimally designing a trajectory for a space mission is considered in this paper. Actual mission design is a complex, multi-disciplinary and multi-objective activity with relevant economic implications. In this paper we will consider some simplified models proposed by the European Space Agency as test problems for global optimization (GTOP database). We show that many trajectory optimization problems can be quite efficiently solved by means of relatively simple global optimization techniques relying on standard methods for local optimization. We show in this paper that our approach has been able to find trajectories which in many cases outperform those already known. We also conjecture that this problem displays a “funnel structure” similar, in some sense, to that of molecular optimization problems.     

An efficient combined DCA and B&;B using DC/SDP relaxation for globally solving binary quadratic programs

This paper addresses a new continuous approach based on the DC (Difference of Convex functions) programming and DC algorithms (DCA) to Binary quadratic programs (BQP) which play a key role in combinatorial optimization. DCA is completely different from other avalaible methods and featured by generating a convergent finite sequence of feasible binary solutions (obtained by solving linear programs with the same constraint set) with decreasing objective values. DCA is quite simple and inexpensive to handle large-scale problems. In particular DCA is explicit, requiring only matrix-vector products for Unconstrained Binary quadratic programs (UBQP), and can then exploit sparsity in the large-scale setting. To check globality of solutions computed by DCA, we introduce its combination with a customized Branch-and-Bound scheme using DC/SDP relaxation. The combined algorithm allows checking globality of solutions computed by DCA and restarting it if necessary and consequently accelerates the B&B approach. Numerical results on several series test problems provided in OR-Library (Beasley in J Global Optim, 8:429–433, 1996), show the robustness and efficiency of our algorithm with respect to standard methods. In particular DCA provides ϵ-optimal solutions in almost all cases after only one restarting and the combined DCA-B&B-SDP always provides (ϵ−)optimal solutions.     

Continuous Generalized Gradient Descent

This article derives characterizations and computational algorithms for continuous general gradient descent trajectories in high-dimensional parameter spaces for statistical model selection, prediction, and classification. Examples include proportional gradient shrinkage as an extension of LASSO and LARS, threshold gradient descent with right-continuous variable selectors, threshold ridge regression, and many more with proper combinations of variable selectors and functional forms of a kernel. In all these problems, general gradient descent trajectories are continuous piecewise analytic vector-valued curves as solutions to matrix differential equations. We show the monotonicity and convergence of the proposed algorithms in the loss or negative likelihood functions. We prove that approximations of continuous solutions via infinite series expansions are computationally more efficient and accurate compared with discretization methods. We demonstrate the applicability of our algorithms through numerical experiments with real and simulated datasets.     

A modular and efficient approach to computational modeling and sensitivity analysis of robot and human motion dynamics

In this paper a new class library for the computation of the forward multi-body-system (MBS) dynamics of robots and biomechanical models of human motion is presented. By the developed modular modeling approach the library can be flexibly extended by specific modeling elements like joints with specific geometry or different muscle models and thus can be applied efficiently for a number of dynamic simulation and optimization problems. The library not only provides several methods for solving the forward dynamics problem (like articulated body or composite rigid body algorithms) which can transparently be exchanged. Moreover, the numerical solution of optimal control problems, like in the forward dynamics optimization of human motion, is significantly facilitated by the computation of the sensitivity matrix with respect to the control variables. Examples are given to demonstrate the efficiency of the approach. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A framework for analyzing sub-optimal performance of local search algorithms

This paper presents a framework for analyzing and comparing sub-optimal performance of local search algorithms for hard discrete optimization problems. The β-acceptable solution probability is introduced that captures how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. Using this probability, the necessary conditions for a local search algorithm to converge in probability to β-acceptable solutions are derived. To evaluate and compare the effectiveness of local search algorithms, two estimators for the expected number of iterations to visit a β-acceptable solution are obtained. Computational experiments are reported with simulated annealing and tabu search applied to four small traveling salesman problem instances, and the Lin-Kernighan-Helsgaun algorithm applied to eight medium to large traveling salesman problem instances (all with known optimal solutions), to illustrate the application of these estimators.     

Lipschitzianity of optimal trajectories for the Bolza optimal control problem

In this paper we investigate Lipschitz continuity of optimal solutions for the Bolza optimal control problem under Tonelli’s type growth condition. Such regularity being a consequence of normal necessary conditions for optimality, we propose new sufficient conditions for normality of state-constrained nonsmooth maximum principles for absolutely continuous optimal trajectories. Furthermore we show that for unconstrained problems any minimizing sequence of controls can be slightly modified to get a new minimizing sequence with nice boundedness properties. Finally, we provide a sufficient condition for Lipschitzianity of optimal trajectories for Bolza optimal control problems with end point constraints and extend a result from (J. Math. Anal. Appl. 143, 301–316, 1989) on Lipschitzianity of minimizers for a classical problem of the calculus of variations with discontinuous Lagrangian to the nonautonomous case.     

Shape Optimization Under Width Constraint

We introduce new numerical methods to solve optimization problems among convex bodies which satisfy standard width geometrical constraints. We describe two different numerical approaches to handle width equality and width inequality constraints. To illustrate the efficiency of our method, our algorithms are used to approximate optimal solutions of Meissner’s problem and to confirm two conjectures of Heil.     

Globally Convergent Cutting Plane Method for Nonconvex Nonsmooth Minimization

Nowadays, solving nonsmooth (not necessarily differentiable) optimization problems plays a very important role in many areas of industrial applications. Most of the algorithms developed so far deal only with nonsmooth convex functions. In this paper, we propose a new algorithm for solving nonsmooth optimization problems that are not assumed to be convex. The algorithm combines the traditional cutting plane method with some features of bundle methods, and the search direction calculation of feasible direction interior point algorithm (Herskovits, J. Optim. Theory Appl. 99(1):121–146, 1998). The algorithm to be presented generates a sequence of interior points to the epigraph of the objective function. The accumulation points of this sequence are solutions to the original problem. We prove the global convergence of the method for locally Lipschitz continuous functions and give some preliminary results from numerical experiments.     

Complexity and algorithms for convex network optimization and other nonlinear problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. MSC classification: 90C30, 68Q25