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.     

Numerical methods for solving applied optimal control problems

For an optimal control problem with state constraints, an iterative solution method is described based on reduction to a finite-dimensional problem, followed by applying a successive linearization algorithm with the use of an augmented Lagrangian. The efficiency of taking into account state constraints in optimal control computation is illustrated by numerically solving several application problems.     

Optimal control synthesis for the constrained bilinear biquadratic regulator problem

Optimal process control with control constraints is a challenging task related to many real-life problems. In this paper, a single input continuous time constrained linear quadratic regulator problem, is defined and fully solved. The constraints include both bilinear inequality constraints and customary control force bounds. As a first step, the problem is reformulated as an equivalent constrained bilinear biquadratic optimal control problem. Next, Krotov’s method is used to solve it. To this end, a sequence of improving functions suitable to the problem’s new formulation is constructed and the corresponding successive algorithm is derived. The required computational steps are arranged as an algorithm and proof outlines for the convergence and optimality of the solution are given. The efficiency of the suggested method is demonstrated by numerical example.     

Optimal discrete-valued control computation

In this paper, we consider an optimal control problem in which the control takes values from a discrete set and the state and control are subject to continuous inequality constraints. By introducing auxiliary controls and applying a time-scaling transformation, we transform this optimal control problem into an equivalent problem subject to additional linear and quadratic constraints. The feasible region defined by these additional constraints is disconnected, and thus standard optimization methods struggle to handle these constraints. We introduce a novel exact penalty function to penalize constraint violations, and then append this penalty function to the objective. This leads to an approximate optimal control problem that can be solved using standard software packages such as MISER. Convergence results show that when the penalty parameter is sufficiently large, any local solution of the approximate problem is also a local solution of the original problem. We conclude the paper with some numerical results for two difficult train control problems.     

Value-Estimation Function Method for Constrained Global Optimization

A novel value-estimation function method for global optimization problems with inequality constraints is proposed in this paper. The value-estimation function formulation is an auxiliary unconstrained optimization problem with a univariate parameter that represents an estimated optimal value of the objective function of the original optimization problem. A solution is optimal to the original problem if and only if it is also optimal to the auxiliary unconstrained optimization with the parameter set at the optimal objective value of the original problem, which turns out to be the unique root of a basic value-estimation function. A logarithmic-exponential value-estimation function formulation is further developed to acquire computational tractability and efficiency. The optimal objective value of the original problem as well as the optimal solution are sought iteratively by applying either a generalized Newton method or a bisection method to the logarithmic-exponential value-estimation function formulation. The convergence properties of the solution algorithms guarantee the identification of an approximate optimal solution of the original problem, up to any predetermined degree of accuracy, within a finite number of iterations.     

A penalty function-based random search algorithm for optimal control of switched systems with stochastic constraints and its application in automobile test-driving with gear shifts

Practical industrial process is usually a dynamic process including uncertainty. Stochastic constraints can be used for industrial process modeling, when system sate and/or control input constraints cannot be strictly satisfied. Thus, optimal control of switched systems with stochastic constraints can be available to address practical industrial process problems with different modes. In general, obtaining an analytical solution of the optimal control problem is usually very difficult due to the discrete nature of the switching law and the complexity of stochastic constraints. To obtain a numerical solution, this problem is formulated as a constrained nonlinear parameter selection problem (CNPSP) based on a relaxation transformation (RT) technique, an adaptive sample approximation (ASA) method, a smooth approximation (SA) technique, and a control parameterization (CP) method. Following that, a penalty function-based random search (PFRS) algorithm is designed for solving the CNPSP based on a novel search rule-based penalty function (NSRPF) method and a novel random search (NRS) algorithm. The convergence results show that the proposed method is globally convergent. Finally, an optimal control problem in automobile test-driving with gear shifts (ATGS) is further extended to illustrate the effectiveness of the proposed method by taking into account some stochastic constraints. Numerical results show that compared with other typical methods, the proposed method is less conservative and can obtain a stable and robust performance when considering the small perturbations in initial system state. In addition, to balance the computation amount and the numerical solution accuracy, a tolerance setting method is also provided by the numerical analysis technique.     

SQP-methods for solving optimal control problems with control and state constraints: adjoint variables, sensitivity analysis and real-time control

Parametric nonlinear optimal control problems subject to control and state constraints are studied. Two discretization methods are discussed that transcribe optimal control problems into nonlinear programming problems for which SQP-methods provide efficient solution methods. It is shown that SQP-methods can be used also for a check of second-order sufficient conditions and for a postoptimal calculation of adjoint variables. In addition, SQP-methods lead to a robust computation of sensitivity differentials of optimal solutions with respect to perturbation parameters. Numerical sensitivity analysis is the basis for real-time control approximations of perturbed solutions which are obtained by evaluating a first-order Taylor expansion with respect to the parameter. The proposed numerical methods are illustrated by the optimal control of a low-thrust satellite transfer to geosynchronous orbit and a complex control problem from aquanautics. The examples illustrate the robustness, accuracy and efficiency of the proposed numerical algorithms.     

Parametric continuation method with correction and its applications

The article discusses the parametric continuation method for nonlinear equations. A continuation algorithm with correction is proposed, an approximation accuracy theorem is proved, and issues of efficient numerical implementation are considered. An approach is described to the application of the continuation method for seeking the Pontryagin extremal solution in the optimal control problem. Algorithms developed by the author are applied to optimal control problems nonlinear in control, to problems with a nonsmooth control region, and to affine problems with mixed constraints. Translated from Prikladnaya Matematika i Informatika, No. 30, 2008, pp. 55–94.     

Project prioritization under policy restrictions. A combination of MCDA with 0–1 programming

Multiple Criteria Decision Aid methods are increasingly used in financial decision making in order to capture the multifaceted character of modern enterprises activated in a complex and versatile market environment. This paper presents a multiple criteria approach for the selection of firms applying for financial support from public funds. Besides the budget constraint, the specific decision situation imposes the consideration of additional policy constraints that prevent from directly exploiting rankings provided by a multiple criteria method. In such a case the problem solution is to find a set of alternatives satisfying the constraints and at the same time maximizing a measure of global performance. The proposed procedure relies on the PROMETHEE V method which belongs to the well-known PROMETHEE family of multiple criteria outranking methods and is combined with an integer programming formulation capable to effectively deal with the problem’s combinatorial character. This method is modified in order to avoid any bias in the selection of the optimal set that may arrive because of the apparent contradiction between the rate of resources consumption and the coefficients of the alternatives in the additive objective function.     

Fast automatic differentiation as applied to the computation of second derivatives of composite functions

A technique for deriving formulas for the second derivatives of a composite function with constrained variables is proposed. The original system of constraint equations is associated with a linear system of equations, whose solution is used to determine the Hessian of the function. The resulting formulas are applied to discrete problems obtained by approximating optimal control problems with the use of Runge-Kutta methods of various orders. For a particular optimal control problem, the numerical results obtained by the gradient method and Newton’s method with the resulting formulas are described and analyzed in detail.     

Connections between the covector mapping theorem and convergence of pseudospectral methods for optimal control

In recent years, many practical nonlinear optimal control problems have been solved by pseudospectral (PS) methods. In particular, the Legendre PS method offers a Covector Mapping Theorem that blurs the distinction between traditional direct and indirect methods for optimal control. In an effort to better understand the PS approach for solving control problems, we present consistency results for nonlinear optimal control problems with mixed state and control constraints. A set of sufficient conditions is proved under which a solution of the discretized optimal control problem converges to the continuous solution. Convergence of the primal variables does not necessarily imply the convergence of the duals. This leads to a clarification of the Covector Mapping Theorem in its relationship to the convergence properties of PS methods and its connections to constraint qualifications. Conditions for the convergence of the duals are described and illustrated. An application of the ideas to the optimal attitude control of NPSAT1, a highly nonlinear spacecraft, shows that the method performs well for real-world problems. The research was supported in part by NPS, the Secretary of the Air Force, and AFOSR under grant number, F1ATA0-60-6-2G002.     

A partitioning and bounded variable algorithm for linear programming

An interesting new partitioning and bounded variable algorithm (PBVA) is proposed for solving linear programming problems. The PBVA is a variant of the simplex algorithm which uses a modified form of the simplex method followed by the dual simplex method for bounded variables. In contrast to the two-phase method and the big M method, the PBVA does not introduce artificial variables. In the PBVA, a reduced linear program is formed by eliminating as many variables as there are equality constraints. A subproblem containing one ‘less than or equal to’ constraint is solved by executing the simplex method modified such that an upper bound is placed on an unbounded entering variable. The remaining constraints of the reduced problem are added to the optimal tableau of the subproblem to form an augmented tableau, which is solved by applying the dual simplex method for bounded variables. Lastly, the variables that were eliminated are restored by substitution. Differences between the PBVA and two other variants of the simplex method are identified. The PBVA is applied to solve an example problem with five decision variables, two equality constraints, and two inequality constraints. In addition, three other types of linear programming problems are solved to justify the advantages of the PBVA.     

Epsilon-ritz method for solving optimal control problems: Useful parallel solution method

Using Balakrishnan's epsilon problem formulation (Ref. 1) and the Rayleigh-Ritz method with an orthogonal polynomial function basis, optimal control problems are transformed from the standard two-point boundary-value problem to a nonlinear programming problem. The resulting matrix-vector equations describing the optimal solution have standard parallel solution methods for implementation on parallel processor arrays. The method is modified to handle inequality constraints, and some results are presented under which specialized nonlinear functions, such as sines and cosines, can be handled directly. Some computational results performed on an Intel Sugarcube are presented to illustrate that considerable computational savings can be realized by using the proposed solution method.     

Second order sufficient conditions and sensitivity analysis for the optimal control of a container crane under state constraints

Stability and sensitivity analysis of parametric control problems has recently been elaborated for optimal control problems subject to pure state constraints. This paper illustrates the numerical aspects of sensitivity analysis for a complex practical example: the optimal control of a container crane with a state constraint on the vertical velocity. The multiple shooting method is used to determine a nominal solution satisfying first order necessary conditions. Second order sufficient conditions are checked by showing that an associated Riccati equation has a bounded solution. Sensitivity differentials of optimal solutions an computed with respect to variations in the swing angle     

A method for solving a general multi-valued complementarity problem

We propose an extended version of Chandrasekaran’s method for general complementarity problems with multi-valued weakly off-diagonally antitone costmappings. It allows one either to construct a sequence converging to a solution or to recognize that the problem has no solutions. We also propose versions of Jacobi’s methods for multi-valued inclusions subject to one- and two-side constraints.     

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.     

Noether’s theorem of nonholonomic systems in optimal control

In this paper, we extend Noether’s theorem to nonholonomic constraints systems in optimal control. We present a systematic way to calculate conserved quantities along the Pontryagin extremals for optimal control problems with nonholonomic constraints, which are invariant under the parameter groups of infinitesimal transformations that change all (time, state, control) variables. Meanwhile, the Noether equalities corresponding to the conservation laws are given. Then, we obtain a new version of Noether’s theorem to optimal control systems. An example is given to illustrate the application of these results.     

Anchoring Points and Cones of Opportunities in Interior Multiobjective Linear Programming

This paper presents a modification of one variant of Karmarkar's interior-point linear programming algorithm to Multiobjective Linear Programming (MOLP) problems. We show that by taking the variant known as the affine-scaling primal algorithm, generating locally-relevant scaling coefficients and applying them to the projected gradients produced by it, we can define what we refer to as anchoring points that then define cones in which we search for an optimal solution through interaction with the decision maker. Currently existing MOLP algorithms are simplex-based and make their progress toward the optimal solution by following the vertices of the constraints polytope. Since the proposed algorithm makes its progress through the interior of the constraints polytope, there is no need for vertex information and, therefore, the search for an optimal solution may prove less sensitive to problem size. We refer to the class of MOLP algorithms resulting from this variant as Affine-Scaling Interior Multiobjective Linear Programming (ASIMOLP) algorithms.     

On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke’s method

Affine generalized Nash equilibrium problems (AGNEPs) represent a class of non-cooperative games in which players solve convex quadratic programs with a set of (linear) constraints that couple the players’ variables. The generalized Nash equilibria (GNE) associated with such games are given by solutions to a linear complementarity problem (LCP). This paper treats a large subclass of AGNEPs wherein the coupled constraints are shared by, i.e., common to, the players. Specifically, we present several avenues for computing structurally different GNE based on varying consistency requirements on the Lagrange multipliers associated with the shared constraints. Traditionally, variational equilibria (VE) have been amongst the more well-studied GNE and are characterized by a requirement that the shared constraint multipliers be identical across players. We present and analyze a modification to Lemke’s method that allows us to compute GNE that are not necessarily VE. If successful, the modified method computes a partial variational equilibrium characterized by the property that some shared constraints are imposed to have common multipliers across the players while other are not so imposed. Trajectories arising from regularizing the LCP formulations of AGNEPs are shown to converge to a particular type of GNE more general than Rosen’s normalized equilibrium that in turn includes a variational equilibrium as a special case. A third avenue for constructing alternate GNE arises from employing a novel constraint reformulation and parameterization technique. The associated parametric solution method is capable of identifying continuous manifolds of equilibria. Numerical results suggest that the modified Lemke’s method is more robust than the standard version of the method and entails only a modest increase in computational effort on the problems tested. Finally, we show that the conditions for applying the modified Lemke’s scheme are readily satisfied in a breadth of application problems drawn from communication networks, environmental pollution games, and power markets.