A Technique for Stochastic Control Problems with Unbounded Control Set

We describe a change of time technique for stochastic control problems with unbounded control set. We demonstrate the technique on a class of maximization problems that do not have optimal controls. Given such a problem, we introduce an extended problem which has the same value function as the original problem and for which there exist optimal controls that are expressible in simple terms. This device yields a natural sequence of suboptimal controls for the original problem. By this we mean a sequence of controls for which the payoff functions approach the value function.     

All Stackelberg Location Equilibria in the Hotelling's Duopoly Model on a Tree with Parametric Prices

The sequential Hotelling's duopoly model on a tree was studied by Eiselt (1992), who developed conditions for the existence of location equilibria when location decisions are nodes and prices are parametric. In this paper, this competition model is also analyzed, but considering that locations for the two firms can be any pair of points on the tree, nodes or points in the edges. First, a condition is given under which both the leader and the follower get a positive profit. In this setting, the problem of finding optimal locations for each of them is studied with different and equal prices. In both cases, the set of optimal locations for the follower is generated for any location of the leader as well as the set of optimal locations for the leader. As a consequence the entire set of Stackelberg solutions to this competition model is obtained.     

Numerical solution of minimax optimal control problems by multiple shooting technique

This paper presents the application of the multiple shooting technique to minimax optimal control problems (optimal control problems with Chebyshev performance index). A standard transformation is used to convert the minimax problem into an equivalent optimal control problem with state variable inequality constraints. Using this technique, the highly developed theory on the necessary conditions for state-restricted optimal control problems can be applied advantageously. It is shown that, in general, these necessary conditions lead to a boundary-value problem with switching conditions, which can be treated numerically by a special version of the multiple shooting algorithm. The method is tested on the problem of the optimal heating and cooling of a house. This application shows some typical difficulties arising with minimax optimal control problems, i.e., the estimation of the switching structure which is dependent on the parameters of the problem. This difficulty can be overcome by a careful application of a continuity method. Numerical solutions for the example are presented which demonstrate the efficiency of the method proposed.     

Optimal control of impulsive switched systems with minimum subsystem durations

This paper presents a new computational approach for solving optimal control problems governed by impulsive switched systems. Such systems consist of multiple subsystems operating in succession, with possible instantaneous state jumps occurring when the system switches from one subsystem to another. The control variables are the subsystem durations and a set of system parameters influencing the state jumps. In contrast with most other papers on the control of impulsive switched systems, we do not require every potential subsystem to be active during the time horizon (it may be optimal to delete certain subsystems, especially when the optimal number of switches is unknown). However, any active subsystem must be active for a minimum non-negligible duration of time. This restriction leads to a disjoint feasible region for the subsystem durations. The problem of choosing the subsystem durations and the system parameters to minimize a given cost function is a non-standard optimal control problem that cannot be solved using conventional techniques. By combining a time-scaling transformation and an exact penalty method, we develop a computational algorithm for solving this problem. We then demonstrate the effectiveness of this algorithm by considering a numerical example on the optimization of shrimp harvesting operations.     

A computational method for free terminal time optimal control problem governed by nonlinear time delayed systems

This paper considers a free terminal time optimal control problem governed by nonlinear time delayed system, where both the terminal time and the control are required to be determined such that a cost function is minimized subject to continuous inequality state constraints. To solve this free terminal time optimal control problem, the control parameterization technique is applied to approximate the control function as a piecewise constant control function, where both the heights and the switching times are regarded as decision variables. In this way, the free terminal time optimal control problem is approximated as a sequence of optimal parameter selection problems governed by nonlinear time delayed systems, each of which can be viewed as a nonlinear optimization problem. Then, a fully informed particle swarm optimization method is adopted to solve the approximate problem. Finally, two free terminal time optimal control problems, including an optimal fishery control problem, are solved by using the proposed method so as to demonstrate its applicability.     

Inverse optimization: towards the optimal parameter set of inverse LP with interval coefficients

We study the inverse optimization problem in the following formulation: given a family of parametrized optimization problems and a real number called demand, determine for which values of parameters the optimal value of the objective function equals to the demand. We formulate general questions and problems about the optimal parameter set and the optimal value function. Then we turn our attention to the case of linear programming, when parameters can be selected from given intervals (“inverse interval LP”). We prove that the problem is NP-hard not only in general, but even in a very special case. We inspect three special cases—the case when parameters appear in the right-hand sides, the case when parameters appear in the objective function, and the case when parameters appear in both the right-hand sides and the objective function. We design a technique based on parametric programming, which allows us to inspect the optimal parameter set. We illustrate the theory by examples.     

Optimal control of a class of strongly nonlinear parabolic systems

This paper considers some typical optimal control problems for a class of strongly nonlinear parabolic systems. After some necessary preparation, it is shown that the family of admissible trajectories is a weakly closed and weakly sequentially compact subset of a reflexive Banach space and that the set of attainable states at any given time is a weakly compact subset of a Hilbert space. Using these basic results, proofs of existence of optimal controls are presented. A terminal control problem, a special Bolza problem, and a time optimal control problem are solved, and the necessary conditions of optimality for the corresponding control problems are given.     

The computational complexity of bilevel assignment problems

In bilevel optimization problems there are two decision makers, the leader and the follower, who act in a hierarchy. Each decision maker has his own objective function, but there are common constraints. This paper deals with bilevel assignment problems where each decision maker controls a subset of edges and each edge has a leader’s and a follower’s weight. The edges selected by the leader and by the follower need to form a perfect matching. The task is to determine which edges the leader should choose such that his objective value which depends on the follower’s optimal reaction is maximized. We consider sum- and bottleneck objective functions for the leader and follower. Moreover, if not all optimal reactions of the follower lead to the same leader’s objective value, then the follower either chooses an optimal reaction which is best (optimistic rule) or worst (pessimistic rule) for the leader. We show that all the variants arising if the leader’s and follower’s objective functions are sum or bottleneck functions are NP-hard if the pessimistic rule is applied. In case of the optimistic rule the problem is shown to be NP-hard if at least one of the decision makers has a sum objective function.     

Numerical optimization methods for controlled systems with parameters

First- and second-order numerical methods for optimizing controlled dynamical systems with parameters are discussed. In unconstrained-parameter problems, the control parameters are optimized by applying the conjugate gradient method. A more accurate numerical solution in these problems is produced by Newton’s method based on a second-order functional increment formula. Next, a general optimal control problem with state constraints and parameters involved on the righthand sides of the controlled system and in the initial conditions is considered. This complicated problem is reduced to a mathematical programming one, followed by the search for optimal parameter values and control functions by applying a multimethod algorithm. The performance of the proposed technique is demonstrated by solving application problems.     

Algorithms for solving discrete optimal control problems with infinite time horizon and determining minimal mean cost cycles in a directed graph as decision support tool

Time-discrete systems with a finite set of states are considered. Discrete optimal control problems with infinite time horizon for such systems are formulated. We introduce a certain graph-theoretic structure to model the transitions of the dynamical system. Algorithms for finding the optimal stationary control parameters are presented. Furthermore, we determine the optimal mean cost cycles. This approach can be used as a decision support strategy within such a class of problems; especially so-called multilayered decision problems which occur within environmental emission trading procedures can be modelled by such an approach.     

Efficient robust optimization for robust control with constraints

This paper proposes an efficient computational technique for the optimal control of linear discrete-time systems subject to bounded disturbances with mixed linear constraints on the states and inputs. The problem of computing an optimal state feedback control policy, given the current state, is non-convex. A recent breakthrough has been the application of robust optimization techniques to reparameterize this problem as a convex program. While the reparameterized problem is theoretically tractable, the number of variables is quadratic in the number of stages or horizon length N and has no apparent exploitable structure, leading to computational time of per iteration of an interior-point method. We focus on the case when the disturbance set is ∞-norm bounded or the linear map of a hypercube, and the cost function involves the minimization of a quadratic cost. Here we make use of state variables to regain a sparse problem structure that is related to the structure of the original problem, that is, the policy optimization problem may be decomposed into a set of coupled finite horizon control problems. This decomposition can then be formulated as a highly structured quadratic program, solvable by primal-dual interior-point methods in which each iteration requires time. This cubic iteration time can be guaranteed using a Riccati-based block factorization technique, which is standard in discrete-time optimal control. Numerical results are presented, using a standard sparse primal-dual interior point solver, that illustrate the efficiency of this approach.     

Stochastic differential portfolio games for an insurer in a jump-diffusion risk process

We discuss an optimal portfolio selection problem of an insurer who faces model uncertainty in a jump-diffusion risk model using a game theoretic approach. In particular, the optimal portfolio selection problem is formulated as a two-person, zero-sum, stochastic differential game between the insurer and the market. There are two leader-follower games embedded in the game problem: (i) The insurer is the leader of the game and aims to select an optimal portfolio strategy by maximizing the expected utility of the terminal surplus in the “worst-case” scenario; (ii) The market acts as the leader of the game and aims to choose an optimal probability scenario to minimize the maximal expected utility of the terminal surplus. Using techniques of stochastic linear-quadratic control, we obtain closed-form solutions to the game problems in both the jump-diffusion risk process and its diffusion approximation for the case of an exponential utility.     

An Exact Penalty Function Method for Continuous Inequality Constrained Optimal Control Problem

In this paper, we consider a class of optimal control problems subject to equality terminal state constraints and continuous state and control inequality constraints. By using the control parametrization technique and a time scaling transformation, the constrained optimal control problem is approximated by a sequence of optimal parameter selection problems with equality terminal state constraints and continuous state inequality constraints. Each of these constrained optimal parameter selection problems can be regarded as an optimization problem subject to equality constraints and continuous inequality constraints. On this basis, an exact penalty function method is used to devise a computational method to solve these optimization problems with equality constraints and continuous inequality constraints. The main idea is to augment the exact penalty function constructed from the equality constraints and continuous inequality constraints to the objective function, forming a new one. This gives rise to a sequence of unconstrained optimization problems. It is shown that, for sufficiently large penalty parameter value, any local minimizer of the unconstrained optimization problem is a local minimizer of the optimization problem with equality constraints and continuous inequality constraints. The convergent properties of the optimal parameter selection problems with equality constraints and continuous inequality constraints to the original optimal control problem are also discussed. For illustration, three examples are solved showing the effectiveness and applicability of the approach proposed.     

Real-Time Solution of Bi-Level Optimal Control Problems

Bi-level optimal control problems are presented as an extension to classical optimal control problems. Hereby, additional constraints for the primary problem are considered, which depend on the optimal solution of a secondary optimal control problem. A demanding problem is the numerical complexity, since at any point in time the solution of the optimal control problem as well as a complete solution of the secondary problem have to be determined. Hence we deal with two dependent variables in time. The numerical solution of the bi-level problem is illustrated by an application of a container crane. Jerk and energy optimal trajectories with free final time are calculated under the terminal condition that the crane system comes to be at rest at a predefined location. In enlargement additional constraints are investigated to ensure that the crane system can be brought to a rest position by a safety stop at a free but admissible location in minimal time from any state of the trajectory. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Minimizing the sum of job completion times on capacitated two-parallel machines

This paper considers a scheduling problem with two identical parallel machines. One has unlimited capacity; the other can only run for a fixed time. A given set of jobs must be scheduled on the two machines with the goal of minimizing the sum of their completion times. The paper proposes an optimal branch and bound algorithm which employs three powerful elements, including an algorithm for computing the upper bound, a lower bound algorithm, and a fathoming condition. The branch and bound algorithm was tested on problems of various sizes and parameters. The results show that the algorithm is quite efficient to solve all the test problems. In particular, the total computation time for the hardest problem is less than 0.1 second for a set of 100 problem instances. An important finding of the tests is that the upper bound algorithm can actually find optimal solutions to a quite large number of problems.     

Optimal control of information epidemics modeled as Maki Thompson rumors

We model the spread of information in a homogeneously mixed population using the Maki Thompson rumor model. We formulate an optimal control problem, from the perspective of single campaigner, to maximize the spread of information when the campaign budget is fixed. Control signals, such as advertising in the mass media, attempt to convert ignorants and stiflers into spreaders. We show the existence of a solution to the optimal control problem when the campaigning incurs non-linear costs under the isoperimetric budget constraint. The solution employs Pontryagin’s Minimum Principle and a modified version of forward backward sweep technique for numerical computation to accommodate the isoperimetric budget constraint. The techniques developed in this paper are general and can be applied to similar optimal control problems in other areas.We have allowed the spreading rate of the information epidemic to vary over the campaign duration to model practical situations when the interest level of the population in the subject of the campaign changes with time. The shape of the optimal control signal is studied for different model parameters and spreading rate profiles. We have also studied the variation of the optimal campaigning costs with respect to various model parameters. Results indicate that, for some model parameters, significant improvements can be achieved by the optimal strategy compared to the static control strategy. The static strategy respects the same budget constraint as the optimal strategy and has a constant value throughout the campaign horizon. This work finds application in election and social awareness campaigns, product advertising, movie promotion and crowdfunding campaigns.     

Stackelberg strategies in linear-quadratic stochastic differential games

This paper obtains the Stackelberg solution to a class of two-player stochastic differential games described by linear state dynamics and quadratic objective functionals. The information structure of the problem is such that the players make independent noisy measurements of the initial state and are permitted to utilize only this information in constructing their controls. Furthermore, by the very nature of the Stackelberg solution concept, one of the players is assumed to know, in advance, the strategy of the other player (the leader). For this class of problems, we first establish existence and uniqueness of the Stackelberg solution and then relate the derivation of the leader's Stackelberg solution to the optimal solution of a nonstandard stochastic control problem. This stochastic control problem is solved in a more general context, and its solution is utilized in constructing the Stackelberg strategy of the leader. For the special case Gaussian statistics, it is shown that this optimal strategy is affine in observation of the leader. The paper also discusses numerical aspects of the Stackelberg solution under general statistics and develops algorithms which converge to the unique Stackelberg solution.This work was performed while the second author was on sabbatical leave at the Department of Applied Mathematics, Twente University of Technology, Enschede, Holland.     

Approximations of Relaxed Optimal Control Problems

In the present paper, we investigate an approximation technique for relaxed optimal control problems. We study control processes governed by ordinary differential equations in the presence of state, target, and integral constraints. A variety of approximation schemes have been recognized as powerful tools for the theoretical studying and practical solving of Infinite-dimensional optimization problems. On the other hand, theoretical approaches to the relaxed optimal control problem with constraints are not sufficiently advanced to yield numerically tractable schemes. The explicit approximation of the compact control set makes it possible to reduce the sophisticated relaxed problem to an auxiliary optimization problem. A given trajectory of the relaxed problem can be approximated by trajectories of the auxiliary problem. An optimal solution of the introduced optimization problem provides a basis for the construction of minimizing sequences for the original optimal control problem. We describe how to carry out the numerical calculations in the context of nonlinear programming and establish the convergence properties of the obtained approximations.The authors thank the referees for helpful comments and suggestions.     

Applications of numerical optimal control to nonlinear hybrid systems

This paper develops a technique for numerically solving hybrid optimal control problems. The theoretical foundation of the approach is a recently developed methodology by S.C. Bengea and R.A. DeCarlo [Optimal control of switching systems, Automatica. A Journal of IFAC 41 (1) (2005) 11–27] for solving switched optimal control problems through embedding. The methodology is extended to incorporate hybrid behavior stemming from autonomous (uncontrolled) switches that results in plant equations with piecewise smooth vector fields. We demonstrate that when the system has no memory, the embedding technique can be used to reduce the hybrid optimal control problem for such systems to the traditional one. In particular, we show that the solution methodology does not require mixed integer programming (MIP) methods, but rather can utilize traditional nonlinear programming techniques such as sequential quadratic programming (SQP). By dramatically reducing the computational complexity over existing approaches, the proposed techniques make optimal control highly appealing for hybrid systems. This appeal is concretely demonstrated in an exhaustive application to a unicycle model that contains both autonomous and controlled switches; optimal and model predictive control solutions are given for two types of models using both a minimum energy and minimum time performance index. Controller performance is evaluated in the presence of a step frictional disturbance and parameter uncertainties which demonstrates the robustness of the controllers.