ISSN 1817-2172, рег. Эл. № ФС77-39410, ВАК

Differential Equations and Control Processes
(Differencialnie Uravnenia i Protsesy Upravlenia)

Piecewise Linear Approximation Method for Solving Optimal Control Problems



Russia, 630090, Novosibirsk,
Ave. of acad. Koptyug, 4,
S.L.Sobolev Institute of Mathematics, Siberian
Branch of the Russian Academy of Sciences,


The paper is aimed to present systematically the author's late publications on numerical methods of solving optimal control problems. The basis for the study is the special mapping piecewise linear approximation method (simplex method) appropriate to the problems in which necessary conditions are imposed on the control to make it optimal according to Pontrjagin principle of the maximum. For linear systems it involves the following. Let it be required to minimize the pseudoconvex functional defined on the set of final states of the controlled system. On the strength of Pontrjagin principle of the maximum an "extremal" relation of boundary condition of the adjoint system to extreme points of the system attainability set is established. Let there be (n+1)-th extreme point of the attainability set. In that case special mapping of this sort is linearly interpolated at the convex hull of the extreme points (at the simplex). With the simplex method running, the sequence of simplices is generated, final state function minimizator, local relative to the simplex, being found for every simplex. The simplex method produces strictly decreasing sequence of the functional values. For nonlinear systems the simplex algorithm is based on piecewise linear approximation of the function on triangulation which makes the algorithm suitable for solving boundary problems.
The paper consists of preface and three sections.
In Section 1 dealing with the problem of minimizing pseudoconvex function on convex compact set, belonging to the class of problems of nonlinear programming, its solution (exact) simplex algorithm (algorithm 1.1) is described.
Algorithm 1.1 generates sequence of simplices. For every of them the minimum (exact) of objective function is computed, the procedure being an auxiliary task (Algorithm 1.2). Two versions of approximate simplex algorithm (Algorithm 1.3) are described in which instead of seeking local minimum its reasonably rough approximation is determined. Proving convergence of the simplex algorithm is given. For the problem of minimizing pseudoconvex functional defined on the set of final states of linear controlled system an algorithm is described that is used for computing optimal control in the form of convex combination of extremal controls in Mayer linear auxiliary tasks.
In Section 2 the problem of minimizing convex functional on the final state set is solved for linear controlled system under linear terminal constraints. The simplex algorithm is used to obtain efficient solutions to auxiliary extremal tasks which present themselves when the method of modified Lagrangian function and the method of parametrizing objective function should be applied. The procedure of forming promptly realizable controls is given by means of which linear system is moved from an initial point to the final one under additional constraints or without them. These controls are formed as linear combinations of the controls computed before the control process.
In Section 3 an algorithm is described that represents combination of the fixed point method and the quasi-Newtonian method. The algorithm is used for solving boundary nonlinear problems when Pontrjagin principle of the maximum is required to be applied. Use of piecewise linear approximation of function on triangulations enables the range of the algorithm efficiency to be widened for boundary problems to be solved.
In each section the data resulted from computing are summarazed in the tables.

Full text (pdf)