Все выпуски

В статье рассматривается аппроксимация функции цены антагонистической дифференциальной игры с критерием, задаваемым условием минимизации некоторой величины вдоль реализовавшейся траектории, решениями стохастических игр с непрерывным временем и моментом остановки, управляемым одним из игроков. Отметим, что если в качестве вспомогательной игры выбрана стохастическая дифференциальная игра, то ее функция цены задается параболическим уравнением второй степени в частных производных с дополнительными ограничениями в форме неравенств, в то время как для случая вспомогательной игры с динамикой, задаваемой марковской цепью, функция цены определяется системой обыкновенных дифференциальных уравнений с дополнительными ограничениями. Развиваемый в статье метод аппроксимации основан на концепции стохастического поводыря, впервые предложенном в работах Н.Н. Красовского и А.Н. Котельниковой.

The paper is concerned with the approximation of the value function of the zero-sum differential game with the minimal cost, i.e., the differential game with the payoff functional determined by the minimization of some quantity along the trajectory by the solutions of continuous-time stochastic games with the stopping governed by one player. Notice that the value function of the auxiliary continuous-time stochastic game is described by the Isaacs–Bellman equation with additional inequality constraints. The Isaacs–Bellman equation is a parabolic PDE for the case of stochastic differential game and it takes a form of system of ODEs for the case of continuous-time Markov game. The approximation developed in the paper is based on the concept of the stochastic guide first proposed by Krasovskii and Kotelnikova.

Изучаются свойства дискретной вариационной задачи динамической аппроксимации в комплексном евклидовом (L + 1)-мерном пространстве E. Она обобщает известные задачи среднеквадратической полиномиальной аппроксимации функций, заданных своими отсчетами в конечном интервале. В рассматриваемой задаче аппроксимация последовательности y = {y_i}_L⁰ отсчетов функции y(t) ∈ L²[0, T], T = Lh на сетке I_h осуществляется решениями однородных линейных дифференциальных или разностных уравнений заданного порядка n с постоянными, но, возможно, неизвестными коэффициентами. Тем самым показано, что в последнем случае задача аппроксимации включает в себя и задачу идентификации. Анализ ее особенностей - основная тема статьи. Ставится задача нахождения вектора коэффициентов  разностного уравнения Σ_n⁰ ŷ_i+k α_i = 0, где k = 0,L − n. Оптимизируются коэффициенты  и начальные условия переходного процесса y этого уравнения. Цель оптимизации - наилучшая аппроксимация исследуемого динамического процесса y ∈ E. Критерий аппроксимации  минимум величины ||y − ŷ||²_E. Показано, что изучаемая вариационная задача сводится к задачам проектирования в E вектора y на ядра разностных операторов с неизвестными коэффициентами α ∈ ω ⊂ S ⊂ Eⁿ⁺¹. Здесь α - направление, S - сфера или гиперплоскость. Показана связь изучаемой задачи с задачами дискретизации и идентифицируемости. Тогда координаты вектора y ∈ E есть точное решение дифференциального уравнения на сетке I_h и y = ŷ. Дано сравнение изучаемой задачи вариационной идентификации с алгебраическими методами идентификации. Показано, что ортогональные дополнения к ядрам разностных операторов всегда имеют теплицев базис. Это приводит к быстрым проекционным алгоритмам вычислений. Показано, что задача нахождения оптимального вектора α сводится к задаче безусловной минимизации функционала идентификации, зависящего от направления  в Eⁿ⁺¹. Предложена итерационная процедура его минимизации на сфере с широкой областью и высокой скоростью сходимости. Изучаемую вариационную задачу можно применять при математическом моделировании в управлении и научных исследованиях. При этом на конечных интервалах может использоваться, в частности, возможность кусочно-линейной динамической аппроксимации сложных динамических процессов разностными и дифференциальными уравнениями указанного типа.

Some properties of the discrete variational problem of the dynamic approximation in the complex Euclidean (L + 1)-dimensional space are studied here. It generalizes familiar problems of the mean square polynomial approximation of the functions given on the finite interval in accordance with their references. In the problem under consideration sequence approximation y = {y_i}_L⁰ of the references of the function y(t) ∈ L²[0, T], T = Lh on the lattice I_h is achieved by solving homogeneous linear differential equations or difference equations of the given order n with constant but possibly unknown coefficients. Thus, it is shown that in the latter case the approximation problem also includes the identification problem. The analysis of its properties is the main subject of the article. The problem is set to find vector of coefficients  of difference equation Σ_n⁰ ŷ_i+k α_i = 0, where k = 0,L − n. Coefficients  and initial conditions of the transient process by of this equation are optimized. The optimization purpose is to achieve the best approximation of the dynamic process y ∈ E being considered here. The approximation criterion is a minimum of the quantity ||y − ŷ||²_E. The variational problem under study is shown to be reduced to the problem of projecting vector y in E on the kernels of the difference operators with unknown coefficients  α ∈ ω ⊂ S ⊂ Eⁿ⁺¹, where  is a direction, S is a sphere or a hyperplane. The problem under study is shown to be related to the problems of the discretization and identifiability. In this case vector coordinates y ∈ E is an exact solution of differential equation on the lattice I_h and y = ŷ. The problem of the variational identification is compared with algebraic methods of identification. The orthogonal complement to the kernels of the difference operators are shown to always have Toeplitz basis. This results in fast projecting algorithms of computation. The problem of finding optimal vector α is shown to be reduced to the problem of the absolute minimization of the identification functional depending on the direction  in Eⁿ⁺¹. The iterative procedure of its minimization on a sphere with wide domain and high speed of convergence is presented here. The variational problem considered here can be applied in mathematical modeling for control problem and research purposes. On the finite intervals, for example, it is possible to use piecewise-linear dynamic approximations of the complex dynamic processes with difference and differential equations of the specified type.

Для задачи оптимального управления системой обыкновенных дифференциальных уравнений с поточечным фазовым ограничением типа равенства и конечным числом функциональных ограничений типа равенства и неравенства формулируется устойчивый секвенциальный, или, другими словами, регуляризованный, принцип максимума Понтрягина в итерационной форме. Его главное отличие от классического принципа максимума Понтрягина заключается в том, что он, во-первых, формулируется в терминах минимизирующих последовательностей, во-вторых, имеет форму итерационного процесса в пространстве двойственных переменных и, наконец, в-третьих, устойчиво к ошибкам исходных данных оптимизационной задачи порождает в ней минимизирующее приближенное решение в смысле Дж. Варги, т.е. представляет собою регуляризирующий алгоритм. Доказательство регуляризованного принципа максимума Понтрягина в итерационной форме опирается на методы двойственной регуляризации и итеративной двойственной регуляризации.

The stable sequential Pontryagin maximum principle or, in other words, the regularized Pontryagin maximum principle in iterative form is formulated for the optimal control problem of a system of ordinary differential equations with pointwise phase equality constraint and a finite number of functional equality and inequality constraints. The main difference between it and the classical Pontryagin maximum principle is that, firstly, it is formulated in terms of minimizing sequences, secondly, the iterative process occurs in dual space and, thirdly, it is resistant to errors of raw data and gives a minimizing approximate solution in the sense of J. Warga. So it is a regularizing algorithm. The proof of the regularized Pontryagin maximum principle in iterative form is based on the methods of dual regularization and iterative dual regularization.

Для задачи оптимального управления линейным параболическим уравнением с распределенным, начальным и граничным управлениями и с операторным полуфазовым ограничением типа равенства формулируется устойчивый секвенциальный, или, другими словами, регуляризованный, принцип максимума Понтрягина в итерационной форме. Его главное отличие от классического принципа максимума Понтрягина заключается в том, что он, во-первых, формулируется в терминах минимизирующих последовательностей, во-вторых, имеет форму итерационного процесса в пространстве двойственных переменных и, наконец, в-третьих, устойчиво к ошибкам исходных данных оптимизационной задачи порождает в ней минимизирующее приближенное решение в смысле Дж. Варги, т.е. представляет собой регуляризирующий алгоритм. Доказательство регуляризованного принципа максимума Понтрягина в итерационной форме опирается на методы двойственной регуляризации и итеративной двойственной регуляризации. Приводятся результаты модельных расчетов при решении конкретной задачи оптимального управления, иллюстрирующих работу алгоритма, основанного на регляризованном итерационном принципе максимума Понтрягина. В качестве конкретной оптимизационной задачи рассмотрена задача поиска минимальной по норме тройки управлений при операторном ограничении-равенстве в финальный момент времени, или, другими словами, обратная задача финального наблюдения по поиску ее нормального решения.

The stable sequential Pontryagin maximum principle or, in other words, the regularized Pontryagin maximum principle in iterative form is formulated for the optimal control problem of a linear parabolic equation with distributed, initial and boundary controls and operator semiphase equality constraint. The main difference between it and the classical Pontryagin maximum principle is that, firstly, it is formulated in terms of minimizing sequences, secondly, the iterative process occurs in dual space, and thirdly, it is resistant to error of raw data and gives a minimizing approximate solution in the sense of J. Warga. So it is a regularizing algorithm. The proof of the regularized Pontryagin maximum principle in iterative form is based on the dual regularization methods and iterative dual regularization. The results of model calculations of the concrete optimal control problem illustrating the work of the algorithm based on the regularized iterative Pontryagin maximum principle are presented. The problem of finding a control triple with minimal norm under a given equality constraint at the final instant of time or, in other words, the inverse final observation problem of finding a normal solution is used as a concrete model optimal control problem.

Рассматривается регуляризация принципа Лагранжа (ПЛ) в выпуклой задаче условной оптимизации с операторным ограничением-равенством в гильбертовом пространстве и конечным числом функциональных ограничений-неравенств. Целевой функционал задачи не является, вообще говоря, сильно выпуклым, а на множество ее допустимых элементов, которое также принадлежит гильбертову пространству, не накладывается условие ограниченности. Получение регуляризованного ПЛ основано на методе двойственной регуляризации и предполагает использование двух параметров регуляризации и двух соответствующих условий согласования одновременно. Один из регуляризирующих параметров «отвечает» за регуляризацию двойственной задачи, другой же содержится в сильно выпуклом регуляризирующем добавке к целевому функционалу исходной задачи. Основное предназначение регуляризованного ПЛ — устойчивое генерирование обобщенных минимизирующих последовательностей, аппроксимирующих точное решение задачи по функции и по ограничениям, для целей ее непосредственного практического устойчивого решения.

We consider the regularization of the Lagrange principle (LP) in the convex constrained optimization problem with operator constraint-equality in a Hilbert space and with a finite number of functional inequality-constraints. The objective functional of the problem is not, generally speaking, strongly convex. The set of admissible elements of the problem is also embedded into a Hilbert space and is not assumed to be bounded. Obtaining a regularized LP is based on the dual regularization method and involves the use of two regularization parameters and two corresponding matching conditions at the same time. One of the regularization parameters is «responsible» for the regularization of the dual problem, while the other is contained in a strongly convex regularizing addition to the objective functional of the original problem. The main purpose of the regularized LP is the stable generation of generalized minimizing sequences that approximate the exact solution of the problem by function and by constraint, for the purpose of its practical stable solving.

На примере известной задачи о прокладке трассы изучаются возможности численного решения сосредоточенных задач оптимального управления методом параметризации управления с помощью линейной комбинации $\mu$ функций Гаусса. Напомним, что функция Гаусса (называемая также квадратичной экспонентой) - это функция вида $\varphi(x)=\dfrac{1}{\sigma\sqrt{2\pi}}\exp\left[-\dfrac{(x-m)^2}{2\sigma^2}\right]$. Основу метода составляет сведение исходной бесконечномерной задачи оптимизации к конечномерной задаче минимизации целевого функционала по параметрам аппроксимации управления с последующим применением численных методов конечномерной оптимизации. Данная статья опирается на исследование, проведенное автором ранее и касавшееся возможностей аппроксимации функций одного переменного на конечном отрезке линейной комбинацией функций Гаусса, и является его непосредственным продолжением. Прежде всего, мы доказываем утверждение об аппроксимации на любом конечном отрезке материнского вейвлета «мексиканская шляпа» линейной комбинацией двух квадратичных экспонент. Отсюда получаем теоретическое обоснование возможности эффективной аппроксимации функций одного переменного на любом конечном отрезке линейными комбинациями функций Гаусса. После этого мы проводим сравнение качества аппроксимации указанного вида с аппроксимацией по Котельникову на базе численных экспериментов. Затем приводится постановка задачи о прокладке трассы, а также результаты ее численного решения при различных способах параметризации управления, наглядно демонстрирующие преимущества предлагаемого способа, в частности устойчивость численного решения к погрешности вычисления параметров аппроксимации оптимального управления даже при использовании малого количества этих параметров.

On the example of well known problem of a road construction we study the opportunities of numerical solution for lumped optimal control problems by the method of control parametrization with the help of a linear combination of $\mu$ Gaussian functions. Recall that a Gaussian function (named also as quadratic exponent) is one defined as follows $\varphi(x)=\dfrac{1}{\sigma\sqrt{2\pi}}\exp\left[-\dfrac{(x-m)^2}{2\sigma^2}\right]$. The method is based on reduction of an original infinite dimensional optimization problem to finite dimensional minimization problem of a cost functional with respect to control approximation parameters. This paper is guided by the former author's research concerned the opportunities of approximation of one variable functions on a finite segment by a linear combination of $\mu$ Gaussian functions, and is to be regarded as its direct continuation. First of all, we prove an assertion concerning approximation on any finite segment for mother wavelet Mexican hat by a linear combination of two Gaussian functions. Hence, we obtain theoretical justification of the opportunity of an effective approximation for one variable functions on any finite segment with the help of linear combinations of Gaussian functions. After that, we give a comparison by quality of the approximation under study with the approximation in the style of Kotelnikov by means of numerical experiments. Then we give the road construction problem formulation and also the results of numerical solution for this problem which demonstrate obviously the advantages of our approach, in particular, a stability of numerical solution with respect to evaluation error of the approximation parameters for an optimal control, even with usage of small count of such parameters.

Рассматривается регуляризация классических условий оптимальности (КУО) — принципа Лагранжа и принципа максимума Понтрягина — в выпуклой задаче оптимального управлении с функциональными ограничениями типа равенства и неравенства. Управляемая система задается линейным функционально-операторным уравнением второго рода общего вида в пространстве $L^m_2$, основной оператор правой части уравнения предполагается квазинильпотентным. Целевой функционал задачи является сильно выпуклым. Получение регуляризованных КУО в итерационной форме основано на использовании метода итеративной двойственной регуляризации. Основное предназначение получаемых в работе регуляризованных принципа Лагранжа и принципа максимума Понтрягина в итерационной форме — устойчивое генерирование минимизирующих приближенных решений в смысле Дж. Варги. Регуляризованные КУО в итерационной форме формулируются как теоремы существования в исходной задаче минимизирующих приближенных решений. Они «преодолевают» свойства некорректности КУО и являются регуляризирующими алгоритмами для решения оптимизационных задач. В качестве иллюстративного примера рассматривается задача оптимального управления, связанная с гиперболической системой дифференциальных уравнений первого порядка.

We consider the regularization of the classical optimality conditions (COCs) — the Lagrange principle and the Pontryagin maximum principle — in a convex optimal control problem with functional constraints of equality and inequality type. The system to be controlled is given by a general linear functional-operator equation of the second kind in the space $L^m_2$, the main operator of the right-hand side of the equation is assumed to be quasinilpotent. The objective functional of the problem is strongly convex. Obtaining regularized COCs in iterative form is based on the use of the iterative dual regularization method. The main purpose of the regularized Lagrange principle and the Pontryagin maximum principle obtained in the work in iterative form is stable generation of minimizing approximate solutions in the sense of J. Warga. Regularized COCs in iterative form are formulated as existence theorems in the original problem of minimizing approximate solutions. They “overcome” the ill-posedness properties of the COCs and are regularizing algorithms for solving optimization problems. As an illustrative example, we consider an optimal control problem associated with a hyperbolic system of first-order differential equations.

Изучаются аппроксимирующие конечномерные задачи математического программирования, возникающие в результате кусочно-постоянной дискретизации управления (в рамках техники параметризации управления) при оптимизации распределенных систем достаточно широкого класса. Устанавливается непрерывность по Липшицу градиентов функций аппроксимирующих задач; приводятся соответствующие формулы градиентов, использующие аналитическое решение исходной управляемой системы и сопряженной к ней системы и тем самым обеспечивающие возможность алгоритмического разделения проблемы оптимизации и проблемы решения управляемой начально-краевой задачи. Применение к численному решению задач оптимизации иллюстрируется на примере задачи Коши-Дарбу, управляемой по интегральному критерию. Приводятся результаты численного решения соответствующей аппроксимирующей задачи в системе MatLab с помощью программы fmincon, а также авторской программы, реализующей метод условного градиента. Кроме того, рассматривается задача безусловной минимизации, получаемая из аппроксимирующей задачи с ограничениями методом синус-параметризации. Приводятся результаты численного решения указанной задачи в системе MatLab с помощью программы fminunc, а также авторских программ, реализующих методы наискорейшего спуска и BFGS. Результаты численных экспериментов подробно анализируются.

We study approximating finite-dimensional mathematical programming problems arising from piecewise constant discretization of the control (in the framework of control parametrization technique) in the course of optimization of distributed parameter systems of a rather wide class. We establish the Lipschitz continuity for gradients of approximating problems. We present their formulas involving analytical solutions of an original controlled system and their adjoint one, thereby giving the opportunity for algorithmic separation of the optimization problem itself and the problem of solving a controlled system. Application of the approach under study to numerical optimization of distributed systems is illustrated by example of the Cauchy-Darboux system controlled by an integral criterion. We present the results of numerical solving the corresponding approximation problem in MatLab with the help of the program fmincon and also an author-developed program based on the conditional gradient method. Moreover, the unconstrained minimization problem is investigated that arises from the constrained approximation problem with applying the sine parametrization method. We present the results of numerical solving this problem in MatLab with the help of the program fminunc and also two author-developed programs based on the steepest descent and BFGS methods, respectively. The results of all numerical experiments are analyzed in detail.