Search

We study the problem of finding curves of minimum pointwise-maximum arc-length derivative of curvature, here simply called curves of minimax spirality, among planar curves of fixed length with prescribed endpoints and tangents at the endpoints. We consider the case when simple bounds (constraints) are also imposed on the curvature along the curve. The curvature at the endpoints may or may not be specified. We prove via optimal control theory that the optimal curve is some concatenation of Euler spiral arcs, circular arcs, and straight line segments. When the curvature is not constrained (or when the curvature constraint does not become active), an optimal curve is only made up of a concatenation of Euler spiral arcs, unless the oriented endpoints lie in a line segment or a circular arc of the prescribed length, in which case the whole curve is either a straight line segment or a circular arc segment, respectively. We propose numerical methods and illustrate these methods and the results by means of three example problems of finding such curves., Comment: 23 pages

We consider the problem of finding curves of minimum pointwise-maximum curvature, i.e., curves of minimax curvature, among planar curves of fixed length with prescribed endpoints and tangents at the endpoints. We reformulate the problem in terms of optimal control and use the maximum principle, as well as some geometrical arguments, to produce a classification of the types of solutions. Using the classification, we devise a numerical method which reduces the infinite-dimensional optimization problem to a finite-dimensional problem with just six variables. The solution types, together with some further observations on optimality, are illustrated via numerical examples.

Riemannian cubics in tension are critical points of the linear combination of two objective functionals, namely the squared norms of the velocity and acceleration of a curve on a Riemannian manifold. We view this variational problem of finding a curve as a multi-objective optimization problem and construct the Pareto fronts for some given instances where the manifold is a sphere and where the manifold is a torus. The Pareto front for the curves on the torus turns out to be particularly interesting: the front is disconnected and it reveals two distinct Riemannian cubics with the same boundary data, which is the first known nontrivial instance of this kind. We also discuss some convexity conditions involving the Pareto fronts for curves on general Riemannian manifolds.

We propose a primal--dual technique that applies to infinite dimensional equality constrained problems, in particular those arising from optimal control. As an application of our general framework, we solve a control-constrained double integrator optimal control problem and the challenging control-constrained free flying robot optimal control problem by means of our primal--dual scheme. The algorithm we use is an epsilon-subgradient method that can also be interpreted as a penalty function method. We provide extensive comparisons of our approach with a traditional numerical approach.

We explore the relationship between the dual of a weighted minimum-energy control problem, a special case of linear-quadratic optimal control problems, and the Douglas-Rachford (DR) algorithm. We obtain an expression for the fixed point of the DR operator as applied to solving the optimal control problem, which in turn devises a certificate of optimality that can be employed for numerical verification. The fixed point and the optimality check are illustrated in an example optimal control problem.

Simultaneous optimization of multiple objective functions results in a set of trade-off, or Pareto, solutions. Choosing a, in some sense, best solution in this set is in general a challenging task: In the case of three or more objectives the Pareto front is usually difficult to view, if not impossible, and even in the case of just two objectives constructing the whole Pareto front so as to visually inspect it might be very costly. Therefore, optimization over the Pareto (or efficient) set has been an active area of research. Although there is a wealth of literature involving finite dimensional optimization problems in this area, there is a lack of problem formulation and numerical methods for optimal control problems, except for the convex case. In this paper, we formulate the problem of optimizing over the Pareto front of nonconvex constrained and time-delayed optimal control problems as a bi-level optimization problem. Motivated by existing solution differentiability results, we propose an algorithm incorporating (i) the Chebyshev scalarization, (ii) a concept of the essential interval of weights, and (iii) the simple but effective bisection method, for optimal control problems with two objectives. We illustrate the working of the algorithm on two example problems involving an electric circuit and treatment of tuberculosis and discuss future lines of research for new computational methods., Comment: 25 pages, 4 figures

Splitting and projection-type algorithms have been applied to many optimization problems due to their simplicity and efficiency, but the application of these algorithms to optimal control is less common. In this paper we utilize the Douglas--Rachford (DR) algorithm to solve control-constrained minimum-energy optimal control problems. Instead of the traditional approach where one discretizes the problem and solves it using large-scale finite-dimensional numerical optimization techniques we split the problem in two subproblems and use the DR algorithm to find an optimal point in the intersection of the solution sets of these two subproblems hence giving a solution to the original problem. We derive general expressions for the projections and propose a numerical approach. We obtain analytic closed-form expressions for the projectors of pure, under-, critically- and over-damped harmonic oscillators. We illustrate the working of our approach to solving not only these example problems but also a challenging machine tool manipulator problem. Through numerical case studies, we explore and propose desirable ranges of values of an algorithmic parameter which yield smaller number of iterations.

The Douglas-Rachford and Peaceman-Rachford algorithms have been successfully employed to solve convex optimization problems, or more generally find zeros of monotone inclusions. Recently, the behaviour of these methods in the inconsistent case, i.e., in the absence of solutions has triggered significant consideration. It has been shown that under mild assumptions the shadow sequence of the Douglas-Rachford algorithm converges weakly to a generalized solution when the underlying operators are subdifferentials of proper lower semicontinuous convex functions. However, no convergence behaviour has been proved in the case of Peaceman-Rachford algorithm. In this paper, we prove the convergence of the shadow sequences associated with the Douglas-Rachford algorithm and Peaceman-Rachford algorithm when one of the operators is uniformly monotone and $3^*$ monotone but not necessarily a subdifferential. Several examples illustrate and strengthen our conclusion. We carry out numerical experiments using example instances of optimization problems.

It is well known that the Newton method may not converge when the initial guess does not belong to a specific quadratic convergence region. We propose a family of new variants of the Newton method with the potential advantage of having a larger convergence region as well as more desirable properties near a solution. We prove quadratic convergence of the new family, and provide specific bounds for the asymptotic error constant. We illustrate the advantages of the new methods by means of test problems, including two and six variable polynomial systems, as well as a challenging signal processing example. We present a numerical experimental methodology which uses a large number of randomized initial guesses for a number of methods from the new family, in turn providing advice as to which of the methods employed is preferable to use in a particular search domain., Comment: 29 pages, 4 figures, 19 tables

This paper is concerned with finding an optimal path for an observer, or sensor, moving at a constant speed, which is to estimate the position of a stationary target, using only bearing angle measurements. The generated path is optimal in the sense that, along the path, information, and thus the efficiency of a potential estimator employed, is maximized. In other words, an observer path is deemed optimal if it maximizes information so that the location of the target is estimated with smallest uncertainty, in some sense. We formulate this problem as an optimal control problem maximizing the determinant of the Fisher information matrix, which is one of the possible measures of information. We derive analytical results for optimality using the Maximum Principle. We carry out numerical experiments and discuss the multiple (locally) optimal solutions obtained. We check graphically that the necessary conditions of optimality are verified by the numerical solutions. Finally we provide a comprehensive list of possible extensions for future work., Comment: 17 pages, 6 figures

We propose new mathematical optimization models for generating sparse dynamical graphs, or networks, that can achieve synchronization. The synchronization phenomenon is studied using the Kuramoto model, defined in terms of the adjacency matrix of the graph and the coupling strength of the network, modelling the so-called coupled oscillators. Besides sparsity, we aim to obtain graphs which have good connectivity properties, resulting in small coupling strength for synchronization. We formulate three mathematical optimization models for this purpose. Our first model is a mixed integer optimization problem, subject to ODE constraints, reminiscent of an optimal control problem. As expected, this problem is computationally very challenging, if not impossible, to solve, not only because it involves binary variables but also some of its variables are functions. The second model is a continuous relaxation of the first one, and the third is a discretization of the second, which is computationally tractable by employing standard optimization software. We design dynamical graphs that synchronize, by solving the relaxed problem and applying a practical algorithm for various graph sizes, with randomly generated intrinsic natural frequencies and initial phase variables. We test robustness of these graphs by carrying out numerical simulations with random data and constructing the expected value of the network's order parameter and its variance under this random data, as a guide for assessment., Comment: The adjacency matrices of the 10 graphs studied in this manuscript can be found in the ancillary folder

A popular method for finding the projection onto the intersection of two closed convex subsets in Hilbert space is Dykstra's algorithm. In this paper, we provide sufficient conditions for Dykstra's algorithm to converge rapidly, in finitely many steps. We also analyze the behaviour of Dykstra's algorithm applied to a line and a square. This case study reveals stark similarities to the method of alternating projections. Moreover, we show that Dykstra's algorithm may stall for an arbitrarily long time. Finally, we present some open problems.

The Steklov function $\mu_f(\cdot,t)$ is defined to average a continuous function $f$ at each point of its domain by using a window of size given by $t>0$. It has traditionally been used to approximate $f$ smoothly with small values of $t$. In this paper, we first find a concise and useful expression for $\mu_f$ for the case when $f$ is a multivariate quartic polynomial. Then we show that, for large enough $t$, $\mu_f(\cdot,t)$ is convex; in other words, $\mu_f(\cdot,t)$ convexifies $f$. We provide an easy-to-compute formula for $t$ with which $\mu_f$ convexifies certain classes of polynomials. We present an algorithm which constructs, via an ODE involving $\mu_f$, a trajectory $x(t)$ emanating from the minimizer of the convexified $f$ and ending at $x(0)$, an estimate of the global minimizer of $f$. For a family of quartic polynomials, we provide an estimate for the size of a ball that contains all its global minimizers. Finally, we illustrate the working of our method by means of numerous computational examples.

Multi-objective integer or mixed-integer programming problems typically have disconnected feasible domains, making the task of constructing an approximation of the Pareto front challenging. The present paper shows that certain algorithms which were originally devised for continuous problems can be successfully adapted to approximate the Pareto front for integer, and mixed-integer, multi-objective optimization problems. Relationships amongst various scalarization techniques are established to motivate the choice of a particular scalarization in these algorithms. The proposed algorithms are tested by means of two-, three- and four-objective integer and mixed-integer problems, and comparisons are made. In particular, a new four-objective algorithm is used to solve a rocket injector design problem with a discrete variable, which is a challenging mixed-integer programming problem., Comment: 32 pages

We study the well-known minimum-energy control of the double integrator, along with the simultaneous minimization of the total variation in the control variable. We derive the optimality conditions and obtain the unique optimal solution to the combined problem, where the initial and terminal boundary points are specified. We study the problem from a multi-objective optimal control viewpoint, constructing the Pareto front. We show that the unique asymptotic optimal control function, for the minimization of the total variation alone, is piecewise constant with one switching at the midpoint of the time horizon. For any instance of the boundary conditions of the problem, we prove that the asymptotic optimal total variation is exactly $2/3$ of the total variation of the minimum-energy control. We illustrate the results for a particular instance of the problem and include a link to a video which animates the solutions while moving along the Pareto front., Comment: 14 pages, 4 figures

We introduce a new regularization technique, using what we refer to as the Steklov regularization function, and apply this technique to devise an algorithm that computes a global minimizer of univariate coercive functions. First, we show that the Steklov regularization convexifies a given univariate coercive function. Then, by using the regularization parameter as the independent variable, a trajectory is constructed on the surface generated by the Steklov function. For monic quartic polynomials, we prove that this trajectory does generate a global minimizer. In the process, we derive some properties of quartic polynomials. Comparisons are made with a previous approach which uses a quadratic regularization function. We carry out numerical experiments to illustrate the working of the new method on polynomials of various degree as well as a non-polynomial function., Comment: 31 pages, 5 figures

We show how to compute the \emph{optimal relative backward error} for the numerical solution of the Dahlquist test problem by one-step methods. This is an example of a general approach that uses results from optimal control theory to compute optimal residuals, but elementary methods can also be used here because the problem is so simple. This analysis produces new insight into the numerical solution of stiff problems., Comment: 23 figures (sized incorrectly for this arxiv version---see the worksheet at publish.uwo.ca/~rcorless/Dahlquist/ResidualAnalysis-3D-Contours.mw for better versions

We consider the minimum-energy control of a car, which is modelled as a point mass sliding on the ground in a fixed direction, and so it can be mathematically described as the double integrator. The control variable, representing the acceleration or the deceleration, is constrained by simple bounds from above and below. Despite the simplicity of the problem, it is not possible to find an analytical solution to it because of the constrained control variable. To find a numerical solution to this problem we apply three different projection-type methods: (i)~Dykstra's algorithm, (ii)~the Douglas--Rachford (DR) method and (iii)~the Arag\'on Artacho--Campoy (AAC) algorithm. To the knowledge of the authors, these kinds of (projection) methods have not previously been applied to continuous-time optimal control problems, which are infinite-dimensional optimization problems. The problem we study in this article is posed in infinite-dimensional Hilbert spaces. Behaviour of the DR and AAC algorithms are explored via numerical experiments with respect to their parameters. An error analysis is also carried out numerically for a particular instance of the problem for each of the algorithms.

A realistic generalization of the Markov--Dubins problem, which is concerned with finding the shortest planar curve of constrained curvature joining two points with prescribed tangents, is the requirement that the curve passes through a number of prescribed intermediate points/nodes. We refer to this generalization as the Markov--Dubins interpolation problem. We formulate this interpolation problem as an optimal control problem and obtain results about the structure of its solution using optimal control theory. The Markov--Dubins interpolants consist of a concatenation of circular ($C$) and straight-line ($S$) segments. Abnormal interpolating curves are shown to exist and characterized; however, if the interpolating curve contains a straight-line segment then it cannot be abnormal. We derive results about the stationarity, or criticality, of the feasible solutions of certain structure. In particular, any feasible interpolant with arc types of $CSC$ in each stage is proved to be stationary, i.e., critical. We propose a numerical method for computing Markov--Dubins interpolating paths. We illustrate the theory and the numerical approach by four qualitatively different examples., Comment: 28 pages

Markov-Dubins path is the shortest planar curve joining two points with prescribed tangents, with a specified bound on its curvature. Its structure, as proved by Dubins in 1957 nearly 70 years after Markov posed the problem of finding it, is elegantly simple: a selection of at most three arcs are concatenated, each of which is either a circular arc of maximum (prescribed) curvature or a straight line. The Markov-Dubins problem and its variants have since been extensively studied in practical and theoretical settings. A reformulation of the Markov-Dubins problem as an optimal control problem was subsequently studied by various researchers using the Pontryagin maximum principle and additional techniques, to reproduce Dubins' result. In the present paper, we study the same reformulation, and apply the maximum principle, with new insights, to derive Dubins' result again. We prove that abnormal control solutions, which were ruled out in previous studies, do exist. We characterize them as a concatenation of at most two circular arcs and show that they are also solutions of the normal problem. More importantly, we prove that any feasible path of the types mentioned above is a stationary solution, i.e., that it satisfies the Pontryagin maximum principle. We propose a numerical method for computing Markov-Dubins path. We illustrate the theory and the numerical approach by three qualitatively different examples., Comment: 26 pages, 7 figures