Global optimization of polynomial-expressed nonlinear optimal control problems with semidefinite programming relaxation

In this paper, we propose a new deterministic global optimization method for solving nonlinear optimal control problems in which the constraint conditions of differential equations and the performance index are expressed as polynomials of the state and control functions. The nonlinear optimal control problem is transformed into a relaxed optimal control problem with linear constraint conditions of differential equations, a linear performance index, and a matrix inequality condition with semidefinite programming relaxation. In the process of introducing the relaxed optimal control problem, we discuss the duality theory of optimal control problems, polynomial expression of the approximated value function, and sum-of-squares representation of a non-negative polynomial. By solving the relaxed optimal control problem, we can obtain the approximated global optimal solutions of the control and state functions based on the degree of relaxation. Finally, the proposed global optimization method is explained, and its efficacy is proved using an example of its application.     

Error Estimates for the Approximation of a Class of Optimal Control Systems Governed by Linear PDEs

This paper deals with a class of optimal control problems in which the system is governed by a linear partial differential equation and the control is distributed and with constraints. The problem is posed in the framework of the theory of optimal control of systems. A numerical method is proposed to approximate the optimal control. In this method, the state space as well as the convex set of admissible controls are discretized. An abstract error estimate for the optimal control problem is obtained that depends on both the approximation of the state equation and the space of controls. This theoretical result is illustrated by some numerical examples from the literature.     

Optimality conditions for state constrained nonlinear control problems

The problem of optimal control of nonlinear control and state constrained control problems, where the state constraint may involve differential operators and the cost functionals may be nonsmooth, is studied. For this class of problems, necessary optimality conditions using techniques from infinite dimensional optimization theory adapted to the framework of control problems are derived. It is shown that the underlying structure admits a considerable relaxation of the classical constraint qualifications. The theory then is applied to examples of various nonlinear elliptic equations and state constraints.     

An LP approach to dynamic programming principles for stochastic control problems with state constraints

We study a class of nonlinear stochastic control problems with semicontinuous cost and state constraints using a linear programming (LP) approach. First, we provide a primal linearized problem stated on an appropriate space of probability measures with support contained in the set of constraints. This space is completely characterized by the coefficients of the control system. Second, we prove a semigroup property for this set of probability measures appearing in the definition of the primal value function. This leads to dynamic programming principles for control problems under state constraints with general (bounded) costs. A further linearized DPP is obtained for lower semicontinuous costs.     

Necessary Optimality Conditions for Some Control Problems of Elliptic Equations with Venttsel Boundary Conditions

In this paper we derive a necessary optimality condition for a local optimal solution of some control problems. These optimal control problems are governed by a semi-linear Vettsel boundary value problem of a linear elliptic equation. The control is applied to the state equation via the boundary and a functional of the control together with the solution of the state equation under such a control will be minimized. A constraint on the solution of the state equation is also considered.     

Time optimal control computation with application to ship steering

An efficient computational scheme for solving a general class of linear time optimal control problems, where the target set is a compact and convex set with nonempty interior in the state space, is presented. The scheme is applied to solve the ship steering control problem, and excellent results are obtained.     

An Efficient Approximation Technique for Solving a Class of Fractional Optimal Control Problems

In this paper, we discuss a class of fractional optimal control problems, where the system dynamical constraint comprises a combination of classical and fractional derivatives. The necessary optimality conditions are derived and shown that the conditions are sufficient under certain assumptions. Additionally, we design a well-organized algorithm to obtain the numerical solution of the proposed problem by exercising Laguerre polynomials. The key motive associated with the present approach is to convert the concerned fractional optimal control problem to an equivalent standard quadratic programming problem with linear equality constraints. Given examples illustrate the computational technique of the method together with its efficiency and accuracy. Graphical representations are provided to analyze the performance of the state and control variables for distinct prescribed fractions.     

A transformation technique for optimal control problems with partially linear state inequality constraints

This paper considers optimal control problems involving the minimization of a functional subject to differential constraints, terminal constraints, and a state inequality constraint. The state inequality constraint is of a special type, namely, it is linear in some or all of the components of the state vector.A transformation technique is introduced, by means of which the inequality-constrained problem is converted into an equality-constrained problem involving differential constraints, terminal constraints, and a control equality constraint. The transformation technique takes advantage of the partial linearity of the state inequality constraint so as to yield a transformed problem characterized by a new state vector of minimal size. This concept is important computationally, in that the computer time per iteration increases with the square of the dimension of the state vector.In order to illustrate the advantages of the new transformation technique, several numerical examples are solved by means of the sequential gradient-restoration algorithm for optimal control problems involving nondifferential constraints. The examples show the substantial savings in computer time for convergence, which are associated with the new transformation technique.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-76-3075, and by the National Science Foundation, Grant No. MCS-76-21657.     

Parametric optimization for a hyperbolic equation in divergence form with a pointwise state constraint: I

We consider an optimal control problem with a pointwise state constraint of inequality type and with dynamics described by a linear hyperbolic equation in divergence form with the homogeneous Dirichlet boundary condition. The state constraint contains a functional parameter that belongs to the class of continuous functions and occurs as an additive term. We study the properties of solutions of linear hyperbolic equations in divergence form with measures in the input data and compute the first variations of functionals on the basis of a so-called two-parameter needle variation of controls.     

Null space conditions and thresholds for rank minimization

Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in machine learning, control theory, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-hard, and for most practical problems there are no efficient algorithms that yield exact solutions. A popular heuristic replaces the rank function with the nuclear norm—equal to the sum of the singular values—of the decision variable and has been shown to provide the optimal low rank solution in a variety of scenarios. In this paper, we assess the practical performance of this heuristic for finding the minimum rank matrix subject to linear equality constraints. We characterize properties of the null space of the linear operator defining the constraint set that are necessary and sufficient for the heuristic to succeed. We then analyze linear constraints sampled uniformly at random, and obtain dimension-free bounds under which our null space properties hold almost surely as the matrix dimensions tend to infinity. Finally, we provide empirical evidence that these probabilistic bounds provide accurate predictions of the heuristic’s performance in non-asymptotic scenarios.     

Parametric optimization for a hyperbolic equation in divergence form with a pointwise state constraint: II

On the basis of the results of the first part of the paper, we consider necessary conditions for minimizing sequences in an optimal control problem with a pointwise state constraint of inequality type and with dynamics described by a linear hyperbolic equation in divergence form with the homogeneous Dirichlet boundary condition. The state constraint contains a function parameter that belongs to the class of continuous functions and occurs as an additive term. For the parametric optimization problem, we also consider regularity and normality conditions stipulated by the differential properties of its value function.     

Superconvergence and $L^{\infty}$-Error Estimates of RT1 Mixed Methods for Semilinear Elliptic Control Problems with an Integral Constraint

In this paper, we investigate the superconvergence property and the $L^{\infty}$-error estimates of mixed finite element methods for a semilinear elliptic control problem with an integral constraint. The state and co-state are approximated by the order one Raviart-Thomas mixed finite element space and the control variable is approximated by piecewise constant functions or piecewise linear functions. We derive some superconvergence results for the control variable and the state variables when the control is approximated by piecewise constant functions. Moreover, we derive $L^{\infty}$-error estimates for both the control variable and the state variables when the control is discretized by piecewise linear functions. Finally, some numerical examples are given to demonstrate the theoretical results.     

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.     

Application of the method of multipliers to state space constrained optimal control problems with discrete time

The paper deals with convergence conditions of multiplier algorithms for solving optimal control problems with discrete time suggested by J. Bjbvonek in some earlier papers. In this approach the original state space constrained problem is converted into a control-constrained problem by introducing an additional control variable and an equality constraint which is taken into consideration by a multiplier method. Convergence conditions for the multiplier Iteration of global and local nature are given for exact and inexact solution of the subproblems.     

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.     

Rigorous filtering using linear relaxations

This paper presents rigorous filtering methods for continuous constraint satisfaction problems based on linear relaxations, designed to efficiently handle the linear inequalities coming from a linear relaxation of quadratic constraints. Filtering or pruning stands for reducing the search space of constraint satisfaction problems. Discussed are old and new approaches for rigorously enclosing the solution set of linear systems of inequalities, as well as different methods for computing linear relaxations. This allows custom combinations of relaxation and filtering. Care is taken to ensure that all methods correctly account for rounding errors in the computations. The methods are implemented in the GloptLab environment for solving quadratic constraint satisfaction problems. Demonstrative examples and tests comparing the different linear relaxation methods are also presented.     

Control the Fibre Orientation Distribution at the Outlet of Contraction

A two dimensional model of the orientation distribution of fibres in a paper machine headbox is studied. The goal is to control the fibre orientation distribution at the outlet of contraction by changing its shape. The mathematical formulation leads to an optimization problem with control in coefficients of a linear convection-diffusion equation as the state problem. Then, the problem is expressed as an optimal control problem governed by variational forms. By using an embedding method, the class of admissible shapes is replaced by a class of positive Radon measures. The optimization problem in measure space is then approximated by a linear programming problem. The optimal measure representing optimal shape is approximated by the solution of this linear programming problem. In this paper, we have shown that the embedding method (embedding the admissible set into a subset of measures), successfully can be applied to shape variation design to a one dimensional headbox. The usefulness of this idea is that the method is not iterative and it does not need any initial guess of the solution.      

Optimal control problems with unbounded constraint sets

We consider in this paper optimal control problems in which some of the constraint sets are unbounded. Firstly we deal with problems in which the control set is unbounded, so that ‘impulses’ are allowed as admissible controls, discontinuous functions as admissible trajectories. The second type of problem treated is that of infinite horizons, the time set being unbounded. Both class of problems are treated in a similar way. Firstly, a problem is transformed into a semi-infinite linear programming problem by embedding the spacesof admissible trajectory-control pairs into spaces of measures. Then this is mapped into an appropriate nonstandard structure, where a near-minimizer is found for the non-standard optimization; this entity is mapped back as a minimizer for the original problem. An appendix is including introducing the basic concepts of nonstandard analysis

Numerical methods are presented for the estimation of the minimizing measure, and the construction of nearly optimal trajectory-control pairs. Examples are given involving multiplicative controls     

On differentiability with respect to parameter of solutions to convex optimal control problems subject to state space constraints

A family of convex optimal control problems that depend on a real parameterh is considered. The optimal control problems are subject to state space constraints.It is shown that under some regularity conditions on data the solutions of these problems as well as the associated Lagrange multipliers are directionally-differentiable functions of the parameter.The respective right-derivatives are given as the solution and respective Lagrange multipliers for an auxiliary quadratic optimal control problem subject to linear state space constraints.If a condition of strict complementarity type holds, then directional derivatives become continuous ones.