Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.      

Continuity in the parameter of the minimum value of an integral functional over the solutions of an evolution control system

The problem of minimization of an integral functional with an integrand that is nonconvex with respect to the control is considered. We minimize our functional over the solution set of a nonlinear evolution control system with a time-dependent subdifferential operator in a Hilbert space. The control constraint is given by a nonconvex closed bounded set. The integrand, the control constraint, the initial conditions and the operators in the equation describing the control system all depend on a parameter. We consider, along with the original problem, the problem of minimizing an integral functional with an integrand convexified with respect to the control over the solution set of the same system, but now subject to the convexified control constraint. By a solution of the control system we mean a “trajectory–control” pair. We prove that for each value of the parameter the convexified problem has a solution, which is the limit of a minimizing sequence of the original problem, and the minimum value of the functional of the convexified problem is a continuous function of the parameter.     

Relaxation of Minimax Optimal Control Problems with Infinite Horizon

A minimax optimal control problem with infinite horizon is studied. We analyze a relaxation of the controls, which allows us to consider a generalization of the original problem that not only has existence of an optimal control but also enables us to approximate the infinite-horizon problem with a sequence of finite-horizon problems. We give a set of conditions that are sufficient to solve directly, without relaxation, the infinite-horizon problem as the limit of finite-horizon problems.     

An approach for solving nonlinear programming problems

In this paper we use measure theory to solve a wide range of the nonlinear programming problems. First, we transform a nonlinear programming problem to a classical optimal control problem with no restriction on states and controls. The new problem is modified into one consisting of the minimization of a special linear functional over a set of Radon measures; then we obtain an optimal measure corresponding to functional problem which is then approximated by a finite combination of atomic measures and the problem converted approximately to a finite-dimensional linear programming. Then by the solution of the linear programming problem we obtain the approximate optimal control and then, by the solution of the latter problem we obtain an approximate solution for the original problem. Furthermore, we obtain the path from the initial point to the admissible solution.     

Solving some optimal control problems using the barrier penalty function method

In this paper we present a new approach to solve a two-level optimization problem arising from an approximation by means of the finite element method of optimal control problems governed by unilateral boundary-value problems. The problem considered is to find a minimum of a functional with respect to the control variablesu. The minimized functional depends on control variables and state variablesx. The latter are the optimal solution of an auxiliary quadratic programming problem, whose parameters depend onu.Our main idea is to replace this QP problem by its dual and then apply the barrier penalty method to this dual QP problem or to the primal one if it is in an appropriate form. As a result we obtain a problem approximating the original one. Its good property is the differentiable dependence of state variables with respect to the control variables. Furthermore, we propose a method for finding an approximate solution of a penalized lower-level problem if the optimal solution of the original QP problem is known. We apply the result obtained to some optimal shape design problems governed by the Dirichlet-Signorini boundary-value problem.This research was supported by the Academy of Finland and the Systems Research Institute of the Polish Academy of Sciences.     

Semi-Infinite Programming Approach to Continuously-Constrained Linear-Quadratic Optimal Control Problems

Consider the class of linear-quadratic (LQ) optimal control problems with continuous linear state constraints, that is, constraints imposed on every instant of the time horizon. This class of problems is known to be difficult to solve numerically. In this paper, a computational method based on a semi-infinite programming approach is given. The LQ optimal control problem is formulated as a positive-quadratic infinite programming problem. This can be done by considering the control as the decision variable, while taking the state as a function of the control. After parametrizing the decision variable, an approximate quadratic semi-infinite programming problem is obtained. It is shown that, as we refine the parametrization, the solution sequence of the approximate problems converges to the solution of the infinite programming problem (hence, to the solution of the original optimal control problem). Numerically, the semi-infinite programming problems obtained above can be solved efficiently using an algorithm based on a dual parametrization method.     

Strong controllability and optimal control of the heat equation with a thermal source

In this paper we consider an optimal control system described byn-dimensional heat equation with a thermal source. Thus problem is to find an optimal control which puts the system in a finite time T, into a stationary regime and to minimize a general objective function. Here we assume there is no constraints on control. This problem is reduced to a moment problem.We modify the moment problem into one consisting of the minimization of a positive linear functional over a set of Radon measures and we show that there is an optimal measure corresponding to the optimal control. The above optimal measure approximated by a finite combination of atomic measures. This construction gives rise to a finite dimensional linear programming problem, where its solution can be used to determine the optimal combination of atomic measures. Then by using the solution of the above linear programming problem we find a piecewise-constant optimal control function which is an approximate control for the original optimal control problem. Finally we obtain piecewise-constant optimal control for two examples of heat equations with a thermal source in one-dimensional.     

Optimal control and admissible relaxation for subdifferential evolution inclusions

In this paper we study the relaxation of optimal control problems monitored by subdifferential evolution inclusions. First under appropriate convexity conditions, we establish an existence result. Then we introduce the relaxed problem and show that it always has a solution under fairly general hypotheses on the data. Subsequently we examine when the relaxation is admissible. So we show that every relaxed trajectory can be approximated by extremal original ones (i.e. original trajectories generated by bang-bang controls) and that the values of the original and relaxed problems are equal. Some examples are also presented.     

Numerical Computation of Optimal Feed Rates for a Fed-Batch Fermentation Model

In this paper, we consider a model for a fed-batch fermentation process which describes the biosynthesis of penicillin. First, we solve the problem numerically by using a direct shooting method. By discretization of the control variable, we transform the basic optimal control problem to a finite-dimensional nonlinear programming problem, which is solved numerically by a standard SQP method. Contrary to earlier investigations (Luus, 1993), we consider the problem as a free final time problem, thus obtaining an improved value of the penicillin output. The results indicate that the assumption of a continuous control which underlies the discretization scheme seems not to be valid. In a second step, we apply classical optimal control theory to the fed-batch fermentation problem. We derive a boundary-value problem (BVP) with switching conditions, which can be solved numerically by multiple shooting techniques. It turns out that this BVP is sensitive, which is due to the rigid behavior of the specific growth rate functions. By relaxation of the characteristic parameters, we obtain a simpler BVP, which can be solved by using the predicted control structure (Lim et al., 1986). Now, by path continuation methods, the parameters are changed up to the original values. Thus, we obtain a solution which satisfies all first-order and second-order necessary conditions of optimal control theory. The solution is similar to the one obtained by direct methods, but in addition it contains certain very small bang-bang subarcs of the control. Earlier results on the maximal output of penicillin are improved.     

A note on the approximation of Dirichlet boundary control problems for the wave equation on curved domains

We consider an exact boundary control problem for the wave equation with given initial and terminal data and Dirichlet boundary control. The aim is to steer the state of the system that is defined on a given domain to a position of rest in finite time. The optimal control that is obtained as the solution of the problem depends on the data that define the problem, in particular on the domain. Often for the numerical solution of the control problem, this given domain is replaced by a polygon. This is the motivation to study the convergence of the optimal controls for the polygon to the optimal controls for the given domain. To study the convergence, the values of the optimal controls that are defined on the boundaries of the approximating polygons are mapped in the normal directions of the polygon to control functions defined on the boundary of the original domain. This map has already been used by Bramble and King, Deckelnick, Guenther and Hinze and by Casas and Sokolowski. Using this map, we can show the strong convergence of the transformed controls as the polygons approach the given domain. An essential tool to obtain the convergence is a regularization term in the objective functions to increase the regularity of the state.     

A Dual Simplex Implementation of a Constraint Selection Algorithm for Linear Programming

The constraint selection approach to linear programming begins by solving a relaxed version of the problem using only a few of the original constraints. If the solution obtained to this relaxation satisfies the remaining constraints it is optimal for the original LP. Otherwise, additional constraints must be incorporated in a larger relaxation. The procedure successively generates larger subproblems until an optimal solution is obtained which satisfies all of the original constraints. Computational results for a dual simplex implementation of this technique indicate that solving several small subproblems in this manner is more computationally efficient than solving the original LP using the revised simplex method.     

Impulsively-controlled systems and reverse dwell time: A linear programming approach

We present a receding horizon algorithm that converges to the exact solution in polynomial time for a class of optimal impulse control problems with uniformly distributed impulse instants and governed by so-called reverse dwell time conditions. The cost has two separate terms, one depending on time and the second monotonically decreasing on the state norm. The obtained results have both theoretical and practical relevance. From a theoretical perspective we prove certain geometrical properties of the discrete set of feasible solutions. From a practical standpoint, such properties reduce the computational burden and speed up the search for the optimum thus making the algorithm suitable for the on-line implementation in real-time problems. Our approach consists in approximating the optimal impulse control problem via a binary linear programming problem with a totally unimodular constraint matrix. Hence, solving the binary linear programming problem is equivalent to solving its linear relaxation. Then, given the feasible solution from the linear relaxation, we find the optimal solution via receding horizon and local search. Numerical illustrations of a queueing system are performed.     

一类线性奇异摄动最优控制问题的渐近解

研究了一类线性奇异摄动最优控制问题的空间对照结构,讨论了初始点固定,终端自由的情形.首先根据变分法得到了一阶最优性条件,其次运用退化最优控制问题的解证明了异宿轨道的存在性,从而结合奇异摄动理论证明了原问题空间对照结构解的存在性.进一步根据解的结构,利用边界层函数法构造了奇异摄动最优控制问题一致有效的形式渐近解.最后,通过例子验证了结果的可行性.     

Homogenization of Optimal Control Problems for Functional Differential Equations

The paper deals with the variational convergence of a sequence of optimal control problems for functional differential state equations with deviating argument. Variational limit problems are found under various conditions of convergence of the input data. It is shown that, upon sufficiently weak assumptions on convergence of the argument deviations, the limit problem can assume a form different from that of the whole sequence. In particular, it can be either an optimal control problem for an integro-differential equation or a purely variational problem. Conditions are found under which the limit problem preserves the form of the original sequence.     

Optimal control of an elastic string with viscous damping

We study bilinear optimal control of a wave equation with one spatial dimension. The problem describes oscillations of an elastic string with viscous damping, and the damping coefficient is taken as the control. The objective functional involves driving the state solution close to a desired profile and incurring a cost on the control. The optimal control is characrerized in terms of an optimality system.     

Continuous relaxation for discrete DC programming

Discrete DC programming with convex extensible functions is studied. A natural approach for this problem is a continuous relaxation that extends the problem to a continuous domain and applies the algorithm in continuous DC programming. By employing a special form of continuous relaxation, which is named “lin-vex extension,” the produced optimal solution of the extended continuous relaxation coincides with the solution of the original discrete problem. The proposed method is demonstrated for the degree-concentrated spanning tree problem, the unfair flow problem, and the correlated knapsack problem.     

An Optimization Problem with a Separable Non-Convex Objective Function and a Linear Constraint

For a class of global optimization (maximization) problems, with a separable non-concave objective function and a linear constraint a computationally efficient heuristic has been developed.The concave relaxation of a global optimization problem is introduced. An algorithm for solving this problem to optimality is presented. The optimal solution of the relaxation problem is shown to provide an upper bound for the optimal value of the objective function of the original global optimization problem. An easily checked sufficient optimality condition is formulated under which the optimal solution of concave relaxation problem is optimal for the corresponding non-concave problem. An heuristic algorithm for solving the considered global optimization problem is developed.The considered global optimization problem models a wide class of optimal distribution of a unidimensional resource over subsystems to provide maximum total output in a multicomponent systems.In the presented computational experiments the developed heuristic algorithm generated solutions, which either met optimality conditions or had objective function values with a negligible deviation from optimality (less than 1/10 of a percent over entire range of problems tested).     

Approximate Solution of Optimization Problems for Infinite-Dimensional Singular Systems

An optimal control problem is considered for a system described by a singular equation of parabolic type. The study bases on a special regularization method. We establish existence of a solution to the regularized problem, as well as the corresponding necessary optimality conditions. The results enable us to find an approximate solution to the original problem even in the absence of solvability.     

Solving the optimal control problem of the parabolic PDEs in exploitation of oil

In this paper, the optimal control problem is governed by weak coupled parabolic PDEs and involves pointwise state and control constraints. We use measure theory method for solving this problem. In order to use the weak solution of problem, first problem has been transformed into measure form. This problem is reduced to a linear programming problem. Then we obtain an optimal measure which is approximated by a finite combination of atomic measures. We find piecewise-constant optimal control functions which are an approximate control for the original optimal control problem.     

Solving some optimal path planning problems using an approach based on measure theory

In this paper we solve a collection of optimal path planning problems using a method based on measure theory. First we consider the problem as an optimization problem and then we convert it to an optimal control problem by defining some artificial control functions. Then we perform a metamorphosis in the space of problem. In fact we define an injection between the set of admissible pairs, containing the control vector function and a collision-free path defined on free space and the space of positive Radon measures. By properties of this kind of measures we obtain a linear programming problem that its solution gives rise to constructing approximate optimal trajectory of the original problem. Some numerical examples are proposed.