Методы решения выпуклых задач оптимизации и управления системами с сосредоточенными параметрами Карюкина Юлия Геннадьевна

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Карюкина Юлия Геннадьевна. Методы решения выпуклых задач оптимизации и управления системами с сосредоточенными параметрами : диссертация ... кандидата физико-математических наук : 05.13.01.- Москва, 2006.- 107 с.: ил. РГБ ОД, 61 06-1/1224

Содержание к диссертации

Введение

Глава 1. Двойственный регуляризованный конечношаговыи метод в выпуклых задачах оптимизации .

1.1 Общие и вспомогательные утверждения 27

1.2 Описание метода и сходимость 31

Глава 2. Регуляризованные конечношаговые методы проекции и условного градиента в выпуклых задачах оптимизации .

2.1 Вспомогательные утверждения 35

2.2 Аппроксимация множеств для ограничений типа неравенств 39

2.3 Конечношаговые методы проекции и условного градиента 43

2.4 Регуляризованный метод для двойственной задачи 47

Глава 3. Задача оптимального управления для одной экономической модели .

3.1 Постановка задачи. Свойства параметров модели 50

3.2 Определение вида множества достижимости 54

3.3 Исследование задачи оптимального управления 70

Приложение.

4.1 Некоторые классы выпуклых задач оптимального управления 77

4.2 Результаты вычислительных экспериментов для выпуклых задач оптимизации 87

4.3 Результаты вычислительных экспериментов для экономической модели 95

Заключение 98

Литература

Общие и вспомогательные утверждения
Описание метода и сходимость
Вспомогательные утверждения
Постановка задачи. Свойства параметров модели

Введение к работе

Характерной особенностью современной научно-технической революции является стремительный рост объема потоков различных видов информации: научной, технической, экономической, политической и др.; усложнение и расширение спектра общественных, коллективных и индивидуальных информационных потребностей, возрастание ценности информации, которая превращается в один из важнейших ресурсов социально-экономического и научно-технического прогресса.

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

Теория управления представляет собой довольно обширную область науки. Она находит применение в различных сферах человеческой деятельности, начиная с управления конкретными объектами и кончая управлением в области политики и общественных отношений. Во всех этих сферах работают свои законы, определяющие динамику соответствующих систем. Взаимодействие материальных точек и системы твердых тел описываются законами механики, которые достаточно хорошо изучены. Известны также законы молекулярного и атомного взаимодействия. Во многих случаях они выражаются четкими математическими соотношениями. Тогда основные понятия теории управления и свойства управляемых систем можно сформулировать в математических терминах и на этой основе получать новые закономерности в достаточно общем виде (см., например [37, 54, 31]). Гораздо сложнее ситуация в сфере экономики и общественных отношений. Математические зависимости в этой сфере человеческой деятельности удается получить лишь в отдельных случаях. Тем не менее, основные понятия теории управления (управляемость, наблюдаемость, оптимальность и т.д.) здесь используются достаточно широко.

Развитие рыночной экономики ставит вопрос о разработке методов управления микроэкономическими системами и, таким образом, представляет новую область применения теории систем управления. Вместе с тем экономические системы представляют, как правило, нелинейные объекты со специфическими нелинейностями, требующими разработки специальных методов.

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

Многие процессы важные для современной техники и экономики управляемы, то есть, эти процессы могут протекать различными способами в зависимости от воли человека. В связи с этим возникает вопрос, как управлять процессом наилучшим образом (оптимально), как применять для этих целей математические методы. Математически сформулированные вопросы являются задачами оптимального управления. Поданной тематике опубликовано множество работ (см., например, [2, 5,10, 12, 38, 52, 72, 74, 76, 77, 79, 83, 84]).

При моделировании, разработке методов и численном решении прикладных задач оптимального управления, как и в других областях вычислительной математики, возникает проблема построения эффективных и обоснованных численных методов. При этом важно априори знать, является ли рассматриваемая задача устойчивой по отношению к возмущениям, и иметь оценки скорости сходимости уклонения решений. Основы теории и методов устойчивости и аппроксимации экстремальных задач заложены в работах Б.М.Будака, Ф.П.Васильева, В.В.Васина, Р.Ф.Га-басова, А.Дончева, А.И.Егорова, Ю.М.Ермольева, Ю.Г.Евтушенко, В.Г.Карманова, М.М.Потапова, А.З.Ишмухаметова, Ф.М.Кирилловой, В.Б.Колмановского, П.С.Краснощекова, А.Б.Куржанского, Ж.Л.Лионса, П.Ж.Лорана, Н.Н.Моисеева, Ю.С.Осипова, В.И.Плотникова, А.Н.Тихонова, В.М.Тихомирова и многих других (см. [13-15, 19-25, 28, 33, 50, 60, 66, 69, 80, 81]). По данной тематике опубликованы монографии и большое число научных статей отечественных и зарубежных авторов, среди которых [1, 7, 42, 44, 47, 58, 59, 62, 67, 82].

В теории оптимизации, в частности, в задачах математического программирования при разработке численных методов актуальными являются вопросы их практической реализуемости, эффективности и доведения их до алгоритмов. К таким вопросам относятся разработка методов, алгоритмов без бесконечных внутренних вычислительных процедур, поиск и формулировка критериев, правил останова. Отметим, что данной проблеме посвящено большое количество работ. Библиографию по этим работам можно найти, например, в [6, 8, 18, 29, 50, 63, 75, 85, 87, 88].

Предлагаемые в данной работе методы направлены на решение этих вопросов. Они построены на основе метода регуляризации (см., например, [3, 21, 35, 36, 42, 68, 69]), методов проекции, условного градиентов и двойственного метода [18, 29, 43, 50]. Для них получены критерии останова, доказаны оценки скорости сходимости по функционалу, сходимость по аргументу ко множеству оптимальных элементов и к нормальному оптимальному элементу. Они в абстрактном, для бесконечномерных гильбертовых пространств предложены в [41, 46]. В конечномерных задачах они имеют свои особенности, в частности, это связано с эквивалентностью слабой и сильной топологий, отсутствием конечномерных аппроксимаций, присущей для бесконечномерных задач. Кроме того отметим, что обоснование методов проводится при условии непрерывности градиентов целевой и функций ограничений и рассматриваются случаи, когда параметр регуляризации можно положить равным нулю, т.е. при отсутствии регуляризации. Предлагаемые методы эффективны для решения задач с квадратичными целевыми функциями и с квадратичными функциями, задающих ограничения на допустимые элементы; выпуклыми целевыми функциями и с квадратичными функциями-ограничений [56]. В этом случае методы сводятся к последовательному решению систем линейных алгебраических уравнений.

Также в данной работе рассматривается динамическая модель управления производством, хранением и сбытом товаров повседневного спроса. Модель потенциально позволяет учитывать особенности рыночной экономики при производстве потребительских товаров. Также показывается, что для адекватного описания процессов необходимо учитывать их динамический характер, поскольку только в этом случае можно дать правильную интерпретацию особенностей наблюдаемых явлений и выбрать правильную стратегию производства и развития. Описан способ реализации стратегии производства, обеспечивающей его максимальную доходность. Разработанная модель, в некотором смысле, является базовой: на ее основе могут строиться новые модели, учитывающие влияние других факторов. Отметим работы в этом направлении [26, 27, 70].

Диссертация состоит из введения, трех глав и приложения.

Во введении приведена общая характеристика представленной диссертации, обоснована актуальность темы исследования и сформулированы результаты работы.

В главе 1 для решения конечномерных выпуклых задач с ограничениями типа неравенств с условием Слейтера, и в которых сумма целевой функции и функций ограничений является строго равномерно выпуклой, предложен и обоснован численный метод, основанный на решении двойственной к исходной регуляризовашюй задачи. Для этого метода получены условия сходимости, оценки сходимости по функционалу, по аргументу ко множеству оптимальных элементов и к g - нормальному решению. В первом параграфе данной главы даются общие и вспомогательные утвреждения, а именно: в евкли- довом пространстве Е^п со скалярным произведением и нормой соот- ветственно (a,b) = Yl^ai^i и ||а||² = ^2^а1 рассматривается выпуклая г=1 г=1 задача минимизации J(u) - inf, и 6 U С Е^п, (1) где U - выпуклое, ограниченное, замкнутое множество, J (и), и Є Е^п - выпуклая, непрерывно дифференцируемая функция.

Обозначим решения задачи (1) нижнюю грань функционала J* = inf J(u) и множество оптимальных элементов U* = {и Є U : J(u) =

Будем рассматривать случай ограничений типа неравенств: U = {и Є Е^п : _ді{и) < О, і Є I}, I = {1,..., m}, (2) где gi{u), и Є Eⁿ, і Є І - выпуклые, непрерывно дифференцируемые функции и для множества U выполняется условие Слейтера, т.е. существует элемент и_с Є U такой, что ді(и_с) < О, г Є I. Будем использовать также класс строго равномерно выпуклых функций. А именно: функция (f(u), и Є V строго равномерно выпукла, если для V (Зє[0,1]иУщуЄУ <р((3и + (1 - 0)v) < /ЭД«) + (1 - 0)tp{v) - 0(1 - %(||т* - «И), где модуль строгой выпуклости //() удовлетворяет условиям //(0) = 0, n(t) > 0, 0 < * < diam V = sup ||u - v\\. u,v&V

Вводятся функции S{u) = J{u) + g{u), g(u) = &(«), ti Є V. (3)

Тогда справедливо утверждение о существовании решений в задаче (1), (2), а именно: если в задаче (1), (2) функция S(u), и Є V строго равномерно выпукла, то U* Ф 0 выпукло, замкнуто и ограничено в Е^п.

Функция S(u) рассматривается с учетом следующего предположения.

Предположение 1. Функция S(u), и Є V строго равномерно выпукла с модулем выпуклости //() и д* = inf д(и) > —оо.

Для задачи (1), (2) вводится регулярная функция Лагранжа L{u,X) = J(u) + 53Ai,^(«), ueV, (4)

А Є Л = {А_г-^ О, г = 1,2,..., га}.

Пусть множество (2) удовлетворяет условию Слейтера, тогда, сог ласно известной теореме Куна-Таккера, для выполнения включения и* Є U* в задаче (1), (2) необходимо и достаточно существование множителя Лагранжа А* Є Л такого, что ₍ L{u*,\*)^L{u,\*) V, ueV \*_9i{u*) = 0, я(и*)<0, і = 1,2,..., га. Определяется двойственная к (1), (2) задача:

Х(А) = inf L(u, А) -> sup, А Є Л, где х* = supx(A), Л* = {А Є Л : х(А) = X*} - ^ее решения, а

Л / = {1,2,...,т},

IV) = {і Є 7 : a-(ti) < 0}, 1{и) = {і Є І: &(«) = 0}, Л₀ = {А: А; >0, г' = 1,2,...,т}, Лі = {А Є Л : х(А) > -co}, {А} = тіп(1, А_ь ..., А_т). Приводятся некоторые свойства функции х(А) и определятся структура введенных множеств Лі и Л*.

Во втором параграфе данной главы вводятся следующие рег-уляризованные задачи T_N{u) = J(u) + a_Ng(u)^in{, ueU, N=1,2,..., (5) адг > О, N = 1,2,..., a_N -> О, N -* со. определяются задачи двойственные к (5)

Х(А) = inf L(u, X) = L(u(X), X) -> sup, (6)

А Є Лдг = {A; ^ a_N, і = 1,2,...,m,}, N = 1,2,.... и их решения _X*_N = supx(A) = x№), X*_NeA*_N = {XGA_N: _X(A) = _X*n), ^ = 1,2, - An при этом X*_Nigi(u*_N) = aN9i{u*_N), г = 1,2,..., m и u*_N = u(X*_N). Описывается поиск элементов Ajv Є Ajv, N = 1,2,... - являющихся приближенным решением задач (6), в смысле: max | (X_N - P_N{X_N + g(u_N)))i \= (7) = max | max{ajv — Xm', ^'(wjv)} К n ~ 0, N —> со, где Pjv - оператор проектирования на An : (РдгА)і = тах{адг; Aj}, і = 1,2,..., m,aujsf = и^(Х^). Для поиска Ajv используется следующий вариант метода проекции градиента. Пусть произвольно А? Є Л₀. Следующие А^,к = 0,1,...,K{N), N = 1,2,... ищем как: X^k_N⁺¹ = X^k_N + (3^k_Np^k_N, Pn = PN(X^k_N + я№)) - АІг = = {тах[алг - X^k_Ni; gi(u_N(X^k_N))], і Є I}, где шаг (3ff Є (0,1] вычисляется, например, конечным алгоритмом Армийо. При переходе к следующей (N+ 1)-й итерации можно положить Ajy₊₁ = Лдг = Ад/ '. Показывается, что этот процесс будет сходящимся и через конечное число шагов приведет к выполнению условия (7).

При выполнении предположения 1 существует единственный g-оптимальный элемент и** 6 U* : д(и») = Г = mf д(и) = miS(u) -Г = д(п**) - Г.

Соответсвенно приходим к следующей теореме:

Теорема 1. Пусть в задачах (1), (2) функции J(u), ді{и),и Є V, і = 1,2,...,т дифференцируемы, выполняется условие Слейтера, предположение 1 и множество U ограничено. Тогда верно следующее.

1. Значения Xjsi —» Л*, N —> со, элементы и^ —» U*, N —> со и справедливы оценки N ^ xjv(Ajv) - J* ^ О, ajvд* - Civ < Tn{un) - J* ^ Сє^, olnT + n ^ Jn{un) - J* < -ВДҐ + С^лг.

2. В случае iv/ajv —> 0, iV —> оо элементы w^r —* w**, N -+ оо.Таким образом, рассматривается двойственный регуляризован- ный метод и исследуются вопросы сходимости, а именно: для задачи (1), (2) рассмотривается метод, связанный с решением двойственных к исходным регуляризованным задачам, где в качестве регуляриз-ирующей функции берется сумма функций, задающих ограничения (3). На каждой итерации метода регуляризации в двойственной задаче определяется критерий останова и доказывается сходимость метода.

Во второй главе для решения выпуклых конечномерных задач минимизации с ограничениями типа неравенств при выполнении условия Слейтера предлагаются два метода с конечношаговыми внутренними вычислительными процедурами. Эти методы построены на основе метода регуляризации, методов проекции и условного градиентов, а также двойственного метода. В предлагаемых методах использованы критерии останова, получены оценки сходимости по функционалу, сходимость по аргументу ко множеству оптимальных элементов икО- нормальному оптимальному элементу. В первом параграфе данной главы даются вспомогательные утверждения, а именно: рассматривается выпуклая задача минимизации J (и) -+ inf, ueUcEⁿ, (8) где U - выпуклое, ограниченное, замкнутое множество, J (и), и Є Е^п - выпуклая, непрерывно дифференцируемая функция. Пусть єдг ^ О, sjv —> О, N —» oo,aujv Є U - некоторая последовательность приближенных решений. Вводятся следующие два условия приближенности: \\u_N - wnH єлг, w_N = РиЫ - J'(u_N)), N = 1,2,..., (9)

О < (J'K W - <4К 4, (10) w]f Є U : {J'(uN),w}f-UN) =min (J'(u_N),v -u_N), N = 1,2,....

Здесь Рц - оператор проектирования на множество U. Эти условия являются приближениями для соответствующих критериев оптимальности и* = Pu(u*-J'(u*)),-mm {J'(u*),v-и*) = 0.

Для последовательностей, удовлетворяющих (9) или (10), имеют место следующие утверждения о сходимости к решениям (8):

Теорема 2. Для последовательности им Є U, N = 1,2,..., удовлетворяющей в задаче (8) условию (9) или (10), справедливы следующие утверждения:

0 ^ J{u_N)-r ^ (D+\\J'{u_N)\\)e_N, N = 1,2,...; p(u_N; U*) -+ 0, JV -+ со.

Здесь D - диаметр множества U : D = diam U = sup ||u — v||; u,veU p(u; U*) - расстояние от точки и до множества U* : р(щ U*) = inf \\и — v\\.

Для (8) вводятся регуляризирующие задачи: T_N(u) = J(u) + a_NQ(u) -> inf, и Є U, N = 1,2,..., (11) где q;jv > О, N = 1,2,..., адг — О, N —» со. Для этих задач определяется последовательность и^ U, N = 1,2,..., удовлетворяющая аналогичным (9) и (10) соответственно условиям: \Wn - w_N\\ ^ e_N, w% - Pu{un - T'_N(u_N)); (12) о<(т;ы,%-4)^4, (із) (T'_N(u_N),w^l_N -u_N) = min {T'_N(u_N),v - u_N), N = 1,2,...

Для этой последовательности имеют место следующие утверждения о сходимости к решениям задачи (8).

Теорема 3. Для последовательности un Є U, N = 1,2,..., удовлетворяющей в задачах (11) условиям (12) или (13), при є^/а^ —» 0, N —» со имеет место сходимость ||ujv — и**\\ — О, N —> со и справедливы следующие оценки по функционалу a_NQ* ^T*_N-J*^ a_NQ(u*), T_N = miT_N(u); a_Ntl* ^ T_N{u_N) - J* < a_NQ(u*) + C(e_N/a_N)^1/2; 0 < J(u_N) - Г < «лгРМ - ГЦ + C{e_N/a_N)^1/2,

Т;=іпі:ЗД, и* - произвольный элемент из U*, а константа С = С (и*) не зависит отіУ.

В данном случае для построения сходящейся к определенному элементу и* Є U*, последовательности un Є U, N = 1,2,... ипользо-ван метод регуляризации Тихонова. Здесь С1(и), и Є Е^п - сильно выпуклая, дифференцируемая функция, причем О,'(и), и Є U удовлетворяет условию Липшица, a Q* = inf Q,(u), и** Є U* — Q - нормальное решение, т.е. и** [/* — Q - нормальное решение, если ft(u**) = fi„ = inf Q{u).

Во втором параграфе данной главы рассматриваются регуляриз-ирующие аппроксимации и для задач на этих множествах доказываются утверждения аналогичные теоремам 2 и 3. Вводятся следующие аппроксимации для множества (2): U_N = {и Е^п : g_Ni(u) = gi{u) + а^^(и) < 0, і Є /}, (14) где a^l_N ^ о;^₊₁ > 0, iV = 1,2,..., a^l_N — 0, iV -> со, a ф(и), и Є Е^п, і Є І - неотрицательные, сильно выпуклые и дифференцируемые функции. Для аппроксимирующих задач J_N(u) -> inf, и Є U_N, N = 1,2,... , (15) где д(и) = (gi(u),...,g_m(u)), g_N(u) = (дт(и),...,дыт(и)), Pn - оператор проектирования на Un, a ujv Є Un, N = 1,2,... - некоторая последовательность, удовлетворяющая условию \\^UN - W%\\ < S_N, W% = P_N{U_N - J'_N(U_N)) (16) или условию

О < (J'_N(u_N),u_N - w^l_N) ^ e_N, (17) (J'n{un), w_n - un) = min {J'_N{u_N), v-u_N). показывается, что эти приближенные решения сходятся к решению задачи (1), (2).

Теорема 4. Для последовательности un Є Un, N = 1,2,..., удовлетворяющей в задачах (14), (15) условиям (16) или (17) имеет место сходимость p(u_N;U*)->0,N->oo и справедлива оценка по функционалу

О ^ J(u_N) -J*^(D + \\J'(u_N)\\)(e_N + Cmaxajv).

Кроме того, рассматриваются регуляризованные задачи на множествах [/дг: T_N(u) = J(u) + a_NQ(u) -> inf, и Є U_N, a_N > О, N = 1,2,..., (18) где а —> О, N —» со и м/у Є /#, iV = 1,2,... - последовательность, удовлетворяющая условию \Wn - w_N\\ ^ s_N, w_N = Pn{un - T'_N(u_N)), (19) или условию (T^(ujv), w^ - u_N) - min (Tx(u_N),v- u_N).

Эти приближенные решения также сходятся к решению задачи (1),(2).

Теорема 5. Для последовательности ujv Є Un, N = 1,2,..., удовлетворяющей в задачах (14) (18) условиям (19) или (20) при тахадг/адг —> 0, sn/c^n —> 0, N —> оо, имеет место сходимость ||uj\r-u || -+0, iV -+00 и справедливы следующие оценки cwft* ^Tx-J*^ a_Nn{u*) + Cmaxajv, TjJ = inf Щи); іЄІ Un maxajy + (е^/алг)¹^² a_NQ, ^ T_N(u_N) - J* ^ a_NQ{u*) + С 0 < J{u_N) -J*^ a_N[tl{u*) - fij + С где и* - произвольный элемент из U*, а С = С (и*) - константа, независящая от N.

В третьем параграфе второй главы конкретизируется построение последовательностей и^ Є Un, N = 1,2,..., а именно: в задачах (14),(15), удовлетворяющих условиям (16) или (17) (случай отсутствия регуляризации, т.е. при ац = О, N = 1,2,...) и в задачах (14),(18), удовлетворяющих условиям (19) или (20) (случай наличия регуляризации: адг > 0, N = 1,2,...). Определяется следующий итерационный, релаксационный процесс UjV,fc+l = U_N:k + @N,kPN,k, к = 0, 1, ..., V Un,0 Є Un, ?№PN,k Є Е^п, \\pN,k\\ = ¹ - направление спуска, т.е. (T_N(u_N,_k),p_N)k) < О, а шаг /Зм,к > 0 будем считать выбирается по условию минимума Tn{un,1c + pN,kPN,k) = min Тх(им,к + PPNJc) или по конечношаговому алгоритму Армийо. Выбор направления спуска связан с приближениями по методу проекции градиента или по методу условного градиента. А именно: PN,k = {wN,k - WjV.fcJHwjV.fc - WjV.fcU^- ) где Wff_tk Є Eⁿ выбирается по условию близкому к методу проекции градиента \\wN,k - W%_tk\\ < ejv/2, W_N,k = ^РмЫ,к - T'_N(u_N)k)) или по условию близкому к методу условного гардиента 0 < {T'_N(u_N>k),WN,k - wjffi) < 4r/2, (T'_N{u_N>k), w_Nk - u_Ntk) = mm(T'_N(u_N)k), v - u_N,_k). ' vUn

Для последовательности w^,k вводится дополнительное условие: иы,к + P(wN,k - UN,k) U_N, (З Є (0,1).

Для предлагаемых методов справедливы теоремы 4 и 5. Т.о. показываются оценки скорости сходимости по функционалу, сходимость по аргументу ко множеству оптимальных элементов и к О, - нормальному оптимальному элементу.

В четвертом параграфе второй главы построен регуляризованный метод для двойственной задачи, а именно: рассматривается вопрос

ВЫЧИСЛеНИЯ ЭЛемеНТОВ WN,k При QfjV > О, N = 1,2,... .

Для вычисления приближенных элементов WN_fk, связанных с приближениями к Wff_k, w^l_Nk в методах проекции и условного градиента, используется описанный в главе 1 двойственный, регуляризованный метод. Для этого определяются задачи \\w - (u_N)k - T'_N(u_N>k))\\² -* inf, wGU_N, (T'_N(u_Njk), w - u_Nik) -> inf, w Є U_N, а также двойственные задачи XN,kW = inf L_N,_k(w, A) = L_N,_k(w_N,_k{\), A) -> sup, А Є Л. (21) иЄЕ^п где Ьдг^(гу, А) - соотсветствующие функции Лагранжа: LN,k(w, A) = \\w - (wjv,jfc - T'_N(u_N,k))\\² + ^2\^lgm(w), LN,k{w, A) = (T^(ujv,fc), w - u_N,_k) + ^2 ^9Ni(w), w Є Eⁿ, А Є Л = {А Є E^m : Л* ^ 0, г Є 1}

Пусть решения двойственных задач (21) х%к ~ ^m3bXXN,k(.ty,h*_Nk = {А Є Л : хлгДА) = X*Nk}- Д^ля ^ЭТИХ ^заД^ач используется метод проекции градиента, аналогичный описанному в главе 1, без регуляризации целевых функций, т.е. для задачи (21): AjV,fc,s+l = ^N,k,s + CTN,k,sQN,k,s, V Ajv,fc,0 Є Л, QN,k,s - P\{^N,k,s + 9N,k(^N,k,s)) - ^N,k,s, S = 0, 1,..., где P\ - оператор проектирования на множество Л, который в данном случае имеет простой вид: P\b = (maxjOjb¹}, ...,max{0;6^m}), V 6 Є Е^т, а шаг ак,к,з определяется конечношаговым алгоритмом Армийо. Показывается выполнение условий при которых обеспечена сходимость метода.

В третьей главе даной работы для экономической задачи, связанной с производством, хранением и сбытом товара доказывается теорема существования оптимальных управлений, рассматривается вид множества достижимости, а также возможность наличия особого режима, при котором неособые участки содержит бесконечное количество точек переключения.

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

В рассматриваемой модели используются следующие обозначения переменных и параметров: и - темп производства, количество товара выпускаемое в единицу времени; х\ - количество товара на рынке;

Х2 - количество товара у потребителей (не потребленного); жз - доход (разность между выручкой и затратами на единицу времени); Y > 0—const, потенциальный спрос (полное количество товара, способное мгновенно удовлетворить спрос в условиях отсутствия ажиотажного спроса); k\ — const, темп потребления товара (относительный коэффициент потребления купленного товара в единицу времени); к₂ — const, плата за хранение единицы товара;

О 1 - цена товара; п(с) - коэффициент скорости продаж.

За время dt прирост произведенного товара равен udt, продается n(c)(Y — x₂)x\dt (см. [26, 27]) единиц товара, скорость прироста товара на рынке равна dxi/dt = и — n(c)(Y — 2)21

Прирост товара dx2 у потребителей за время dt равен количеству проданного товара минус количество k^dt потребленного товара, так что dx₂/dt = n(c)(Y - #2)^1 — fa^x2 Доход dx$ за время dt составляет: dx^/dt = cn(c)(Y — 2)^1 — и — &2#i

Последнее уравнение показывает, что доход в единицу времени складывается из выручки от продаж n(c)(Y — 2)^1 единиц товара по цене с, расходов на производство и и затрат на хранение к₂\ все в единицу времени.

Все эти уравнения образуют динамическую модель, где параметры управления есть u(t) и с ' dx\ - = u(t) — U_C(Y — X2)X\, X\{ti) = x\ > 0, dt da —- = n_c(Y - x₂)xi - kix₂, x₂(0) - x\ > 0, — = cn_c(Y - x₂)xi - u(t) - k₂x_h ж₃(0) = x₃ > 0,1(u) = x_z(T) -> max, 0<щ^и^и₂, te [0,T].

Считаем, что цена с товара постоянна, поэтому n(c) = const. Пусть п(с) = п_с, время Т фиксировано и х₂ < Y.

Показывается, что траектория {х\(), x₂(t)) системы уравнений (22) за конечный промежуток времени может находиться только на ограниченном интервале. Кроме того, оптимальное управление и* (t) и отвечающая ему траектория {xl(t),x₂{t)) при t Є [0;Т] - существуют, поскольку система (22) линейна по управлению, функционал не зависит от управления и множество управлений является выпуклым компактом [84].

Во втором параграфе третьей главы проводятся исследования множества достижимости. Рассматривается задача, связанная с изменением количества товара на рынке и у потребителей. Для этого рассматриваются первые два уравнения системы (22): х\ = u(t) — n_c(Y — x₂)xi, ^i(O) = #1 > О < х₂ = n_c(Y - x₂)xi - kix₂, х₂{0) = x^Q₂ > 0 (23)

0<щ^и^и₂, te[0,T]

Определение. Множество точек, в которые можно перейти к моменту времени т по траекториям системы (23), исходящим в начальный момент времени to из точки xq = (х^х), используя всевозможные допустимые управления, называется множеством достижимости.

Доказывается тот факт, что если точка принадлежит границе множества достижимости, то отвечающее ей управление кусочно-постоянно и имеет не более одного переключения. В итоге получаем, что множество достижимости при определенных значениях параметров может быть как выпуклым так и не выпуклым. Задача рассматривается при таких значениях параметров, при которых множество достижимости является выпуклым. Кроме того, в данном параграфе устанавливается существование решения задачи и приводится доказательство того, чтожі(^) > 0, 0 < X2(t) < У, t Є [0;Т]. Причем я<У

В третьем параграфе данной главы исследуется задача оптимального управления для выбранной экономической модели. Задача (22) рассматривается при условии, при котором особый режим является допустимым: 1)/ < п_с(с — 1)Y 2)щ ^ к\ п_с(с-1)_ Поскольку уравнение для х$ не содержит эту переменную в правой части, то задача (22) сводится к следующей задаче оптимального управления: х\ = u(t) — n_c(Y — #2)^1, #i(0) = я? > О #2 = n_c(Y - Xq)X\ - к\Х2, ^2(0) = X₂ > 0

0<щ^и^и₂, te[0;T] (24)

I(u) = x₃(T) = x₁(T)+ + J (—(c — l)n_c(Y — ^2)2:1 + k2X\)dt —> min 0

Показывается что в задаче (24) может иметь место особый режим и на основании работы [11] получаем, что неособый участок, отвечающий управлению щ либо щ должен содержать бесконечное число точек переключения.

В приложении данной работы доказывается выпуклость некоторых задач и для них даются результаты вычислительных экспериментов основанных на регуляризованном копечношаговом методе проекции градиента.

Рассматриваются некоторые задачи оптимального управления с ограничениями типа неравенств. В качестве функциий ді(и),и Є Н,г Є I берутся квадратичные функционалы вида: _{9М = Ы\ь} _{-я?,я.-ек.}

Вводится функционал вида: J(u) = \\x{T;u)-y\\^p,p>l,pN, uUcH,te[t₀,T]

I. Линейные системы. Доказывается, что данный функционал является выпуклым для следующей задачи: \x(t) = A(t)x(t) + B(t)u(t) + f{t), \x(t₀) = Xq\ где х Є Е^п, Л(і)-матрица [nxn], #()-матрица [n x m], /(і)-столбец высоты n,UeUcH,te [to,T\.

П. Билинейные системы. Рассмотрим указанный функционал при р — 2, т.е: J(u) = \\x(T;u)-y\\\ у - фиксированный вектор из Е^п. Показывается, что данный функционал является выпуклым для следующей задачи: ix{t) = (Ли + Е?=іМ^і(і)) x(t) = A(t)x(t), yx(t₀) = x₀] щехЄЕ^п,иєи С Я,і Є [t₀,T\.

Для решения данных задач был организован численный эксперимент, реализующий конечношаговые алгоритмы минимизации функционалов, построенный на регуляризованном методе проекции градиентов. Был реализован механизм следующего вида: размерности пространств Е^п и пространства управлений соответственно п и га могут задаваться произвольными натуральными числами, ограничением может лишь служить лимит процессорного времени для решения конкретной задачи. Исходя из указанных значений п и т задаются виды матриц A{t), B(t) и столбец f(t), также значение числового вектора #о ^и значение То, тем самым польностью определяя постановку указанных задач. Задание же вектора у и R для ограничений полностью исчерпывает тот объем начальных данных, который необходим для решения уже конкретной задачи оптимального управления.

В качестве Q(u),u Є U С Н использваны функционалы вида: Щи) = \\и\\²,и Є Я, а в качестве последовательности ajv > 0, N = 1,2,...,o/v —* 0, N —» со берется последовательность {jj}-

Поскольку численное моделирование возможно только для сеточных функций, то для исследуемых объектов вводятся их сеточные дискретыне предстваления, а именно: исследуемый фукционал имеет вид: J(u) = \\xq - у\\^р -> inf, где xq = x(t;u),x_q = x(to + Atq;u) = x(t_q;u),t_q = t₀ + Atq,q = 0..(5, t + AtQ = Т. Учитывая данные обозначения, линейная система примет вид: {^X-^^ = A(t_q)x_q + B(t_qy + f(t_q), |ж(*о) = х₀; где жо-заданный вектор, a u^q - значение вектора управления в точке

Соответственно ограничения для дискретной задачи примут вид:

5>}|²Д*)<4і = 1..т.

Значение функционала 0,(и) в регуляризованной задаче будет: го / Q \ ад=Е вкі^2д*) j=l \q=0 )

В численно решенных задачах шаг по времени At берется равным 0.001, таким образом, для отрезка [^о, ^"], равного, например [0,1] количество точек разбиения составляет порядка 10³. В качестве условий остановки и проверки сходимости итерационных процессов — и**\\ —> 0, N —» со используется величина є ~ Ю^-4. Начальное значение управление произвольное и задается в виде ^un (0 ~ ft + ^С)І ⁼ l-^m> с М. В случае, если сгенеренное таким образом управление не является допустимым, то оно пересчитывается по правилу: u³_N (t)\_mw = \u^]_N (t) ^

Кроме того, был реализован поиск вида множества достижимости для экономической модели производства, хранения и сбыта товара.

Основные результаты данной работы состоят в следующем:

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

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

Сі - нормальному оптимальному элементу.

Исследована одна экономическая задача, для нее построена динамическая модель, позволяющая учитывать особенности рыночной экономики при производстве потребительских товаров, доказано существование решений, установлен факт наличия особого режима, и возможность наличия бесконечного числа моментов переключения на неособых участках.

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

Результаты, полученные в данной работе осбуждались на семинаре отдела методов нелинейного анализа ВЦ, на 13-ой Байкальской международной школе-семинаре в Иркутске и на "Понтрягинских чтениях - XVII"Воронежской весенней математической школы.

Основные результаты диссертации содержатся в работах [4, 33, 47, 48, 50].

Автор выражает д.ф.м.н. зав. отдела методов нелинейного анализа А.З.Ишмухаметову признательность за руководство данной работой и благодарит к.ф.м.н. Е.Н.Хайлова за постановку конкретной экономической задачи и обсуждение результатов исследований. Автор также выражает благодарность участникам семинара отдела методов нелинейного анализа галвному научному сотруднику, проффе-сору Е.А.Гребеникову, профессору В.В.Дикусару и другим.

Общие и вспомогательные утверждения

В евклидовом пространстве Еп со скалярным произведением и п п нормой соответственно (a, b) = аД- и а2 — а1 рассмотрим г =1 i=i выпуклую задачу минимизации J (и) - inf, ueUcEn, (1.1.1) где U - выпуклое, ограниченное, замкнутое множество, J (и), и Є Еп - выпуклая, непрерывно дифференцируемая функция. Обозначим решения задачи (1.1) нижнюю грань функционала J = inf J(u) и множество оптимальных элементов: U = {ueU: J (и) = Г}. Будем рассматривать случай ограничений типа неравенств: и = {иЄЕп:ді{и) 0,ІЄ /}, I = {1,..., m}, (1.1.2) где gi(u), и Є Еп, і Є I - выпуклые, непрерывно дифференцируемые функции и для множества U выполняется условие Слейтера, т.е. существует элемент ис Є U такой, что ді(ис) 0, і Є I. Будем использовать также класс строго равномерно выпуклых функций. А именно: функция (р(и), и Є V строго равномерно выпукла, если для Vj3e{0,l]HVu,vGV р{ри + (1 - /ЗД fo{u) + (1 - 0)ф) - /3(1 - ДМИ« - t/), где модуль строгой выпуклости /І(-) удовлетворяет условиям //(0) = 0, fi(t) 0, 0 t diam V = sup u - v. u,vV Свойства строго равномерно выпуклых функций изложены, например, в [18, 40, 41, 53, 55]. Введем функции т S(u) = J{u)+g(u), д(и) = ] #(и), uGV. Тогда справедливо следующее утверждение о существовании решений в задаче (1.1.1), (1.1.2) [41]. Теорема 1.1. Пусть в задаче (1.1.1), (1.1.2) функция S(u), и Є V строго равномерно выпукла. Тогда U ф 0 выпукло, замкнуто и ограничено в Еп. Доказательство. Пусть S = infyS(u) = S(v ),v Є V. Тогда fi(\u — v \o) J (и) — S(v ),Vu Є U. Поэтому множества Лебега М(и) = {и Є U : J (и) С} выпуклы, замкнуты и ограничены. По теореме Веерштрасса U ф 0, причем оно выпукло, замкнуто и ограничено. Введем следующее Предположение 1.1. Функция S(и), и Є V строго равномерно выпукла с модулем выпуклости fi(-) и д = inf д(и) —со. Для задачи (1.1.1), (1.1.2) регулярная функция Лагранжа имеет вид m L(u,X) = J(u) + J2xi,9i{u), ueV, (1.1.3) Л 6 Л = {ЛІ 0, і = 1,2,..., m}. Пусть множество (1.1.2) удовлетворяет условию Слейтера, т.е. существует точка й Є Еп такая, что ді(ІЇ) О, і = 1,2, ...,m. Тогда, согласно известной теореме Куна-Таккера (см., например, [18, 43]), для выполнения включения и Є U в задаче (1.1.1), (1.1.2) необходимо и достаточно существование множителя Лагранжа Л Є Л такого, что L(u ,\ ) L(u,\ ) V, ueV І9і(и ) = О, gi(u ) К 0, і = 1,2,..., m. Определим двойственную к (1.1.1), (1.1.2) задачу х(А) = inf L(w, Л) — sup, Л Є Л. Пусть х = supx(A), Л = {Л 6 Л : %(Л) = % } - ее решения. Обоз л начим / = {1,2,..., т}, І\и) = {ІЄІ: ді{и) 0}, 1{и) = {і Є І: д{(и) = 0}, Л0 = {А: А; 0, і = 1,2,...,ш}, Лі = {Л Є Л : х(А) -оо}, {А} = min(l, А1?..., Ат). При строгой равномерной выпуклости функции S(u), и (zV справедливы соотношения рЬ(щ А) + (1 - P)L{v, А) - Щи + (1 - P)v, А) = = pJ(u) + (1- (3)J(v) - J((3(u) + (1- p)v)+ m ЧРФ) + (1- Р)ф) - 9i{pu +(1- /3)«)] t=l {A}[/?S(u) + (1- 0)S(t/) - 5(/ +(1- /9)i/] 0(1-/3){Л}/І(ІІ-І/),УАЄЛО. Поэтому функция L(u, А) при фиксированном Л Є Ло строго равномерно выпукла на V с модулем выпуклости {А}//(-) и достигает нижней грани V Л Є Ло, т.е. Ло С Лі. Отметим, некоторые свойства функции х(А), Л Є Лі и опишем структуру множества Л 1. Множество Лі выпукло, а х(А), Л Є Лі вогнута, полунепрерывна сверху, причем непрерывна во внутренних (в относительной топологии множества Л) точках А\. Докажем эти утверждения. Из теоремы Куна-Таккера, ЗА Є Л С Лі, т.е. Л , Лі ф 0. Умножая неравентсва х(Х) J(u)+ Х,д(и) , х(Х) J{u)-\- Х,д(и) ,Vu Є V,VA, А Є Лі, соответсвенно на а и (1 — а),\/а Є [0,1], складывая, получаем выпуклость Лі и вогнутость х{Х),Х Є Лі. Для А, А0 Лі из неравенства х(Л) J{u)+ Х,д(и) о + А—Х,д(и) о, Vu Є V при А — А0 вытекает полунепрерывность сверху. Непрерывность во внутренних точках Лі, следует согласно [41].

2. Если множество Лебега Мс = {X Є А\ : х{Х) С}, С Є R непусто, то оно выпукло замкнуто и ограничено.

Выпуклость множества Мс следует из выпуклости Лі и вогнутости х(А),А є Ль Пусть А -» А0,Л Є Мс- Из неравенств С х(А) J(u)+ X - Х,д(и) + Х,д(и) ,Vu Є V следует, что А0 Є Лі и Ао Мс- Так как при А — +оо, А Є Мс получаем, что С х(Х) «7(й)+ А,#(й) о- —оо, то Мс ограничено. 3. Множество Л ф 0 выпукло, замкнуто и ограничено. Это свойство вытекает из предыдущего при С = х Определим отображение и (А) : Ло — V, где и (А) - единственный элемент такой, что %(А) = L(u(X),X),V X Є Ло. Будем рассматривать метод, связанный с вычислением элементов и(Х), X Є Ло- Их нахождение во многих случаях является более простой задачей. В зо частности, при квадратичности функций J(u), ді(и), і = 1,2,...,m, элементы и(Х) - решения линейных задач: L u{u, А) = 0. Обозначим J(A) = J(u(X)), д(Х) = д(и(\)), V А Є Ло. Справедливо следующее утверждение (см., например, [41]). Лемма 1.1. Пусть J(u), ді(и), і = 1,2,..., m дифференцируемы на V, причем S(u), и V строго равномерно выпукла. Тогда отображение и(Х) : Ло — V и д(Х), J(X), А Є Ло непрерывны, а х(А), А Є Ло непрерывно дифференцируема, причем х ( ) — 9(ty Є Ло 1.2. Описание метода и сходимость. Для задачи (1.1.1), (1.1.2) рассмотрим метод, связанный с решением двойственных к исходным регуляризованным задачам, где в качестве регуляризирующей функции берется сумма функций, задающий т ограничений: д(и) = ] #(и), и Є Еп. На каждой итерации метода регуляризации в двойственной задаче определим критерий останова и докажем сходимость метода. Введем следующие регуляризованные задачи TN(u) = J{u) + aNg(u) m{, uU, N = 1,2,..., (1.2.1) aN 0, N = 1,2,..., aN -+ 0, N - со. Обозначив u N Є U : TN(U N) = Т = infT(u), N = 1,2,..., воспользуемся двойственным методом. Заменив Аг- + ам на А , і = 1,2,..., т, запишем двойственные к (1.2.1) задачи Х(А) = inf L(u, A) = L(u(X), А) - sup, (1.2.2) А Є AN = {Аг- aN, і = 1,2,..., m,}, iV = 1,2,.... Пусть XN = supx(A) = х(Алг), А Є Л; = {A G Ajy : %W = Aw X N},N = 1,2,... - решения задач (1.2.2). Отметим, что X Nigi(u N) = aN9i(u N), і = 1,2,..., m и u N = u(X N). зі Пусть Лдг Є AJV, N = 1,2,... - приближенные решения задач (1.2.2) в следующем смысле: max (AJV - PN{XN + дЫШ = (1-2.3) = max I max{ajv — \т] І( ЛГ)} JV — 0, N — oo, где PJV - оператор проектирования на Лдг: (РДГЛ)І = max{a/v;Aj}, г = 1,2,...,m, а идт = и (Х ). Это условие приближенной оптимальности эквивалентно следующим условиям: 9i(uN) jv, і Є / = {г: адт Ajvi N + JV}, І І( ЛГ) JV, г Є IlN = {г : адг + N XNi}.

Описание метода и сходимость

В евклидовом пространстве Еп со скалярным произведением и п нормой соответственно (а, Ь) = ЩЬІ п и а2 = 2 а1 будем рассматривать выпуклую задачу минимизации г=1 J(u) -»inf, и Є U С Еп, (2.1.1) где U - выпуклое, ограниченное, замкнутое множество, J(w), и Є Еп - выпуклая, непрерывно дифференцируемая функция. Обозначим решения задачи (2.1.1), а именно: нижнюю грань функционала J = inf J(u) ueU и непустое множество оптимальных элементов U = {и Є U : J(u) = Г}. Пусть дг 0, єлг —» О, N — со, а и Є U - некоторая последовательность приближенных решений. Введем следующие два условия приближенности: IK -«&II N, wN = РиЫ - J (uN)), N = 1,2,..., (2.1.2) 0 {J (uN),uN - wlN) 4» (2-1-3) wjf eU : (J (UJV),IUL- — WJV) = min (J (u ),v — w#), N = 1,2,.... Здесь Py - оператор проектирования на множество U. Эти условия являются приближениями для соответствующих критериев оптимальности u = Pu(u -J (u )), mm(J (u ),v-u ) = 0. Отметим, (см. [46]) что так как из свойства оператора проектирования P\jv — v,u — P\jv 0, Vv Є Еп, Vu = int U из соотношений J (u),Pu{u-J (u))-u = u-Pu{u-J (u)),Pu(u-J\u))-u + + Pv{u - J (u)) -(u- J (u),), Pv(u - J\u) -u \\Ри(и-Г(и))-и\\2 следуют неравенства (J (и),и- w1) (J (и),и- w) \\w - u\\2, V и Є U, (2.1.4) где w = Ри(и- J {u)), (J (u), w1 — и) = min (J {u), v — u). Поэтому veU из (2.1.3) следует (2.1.2). Для последовательностей, удовлетворяющих (2.1.2) или (2.1.3), имеют место следующие утверждения о сходимости к решениям (2.1.1) (см., например, [43], теорема 1). Теорема 2.1. Для последовательности w/y Є U, N = 1,2,..., удовлетворяющей в задаче (2.1.1) условию (2.1.2) или (2.1.3), справедливы следующие утверждения: 0 J(uN)-r (D+\\J {uN)\\)sN, N = 1,2,... ; p(uN; U ) -» 0, iV - oo. Если J(u),u Є t/ сильно выпукла, то U состоит из единственной точки и и имеет место оценка \\uN - и \\2 (D+ J (uN)\\)sN/», N = 1,2,... Здесь D - диаметр множества U : D = dmra С/ = sup w — v; р u,vGU - константа сильной выпуклости функции J{u) р(и; U ) - расстояние от точки и до множества U : p{u-,U )=M\\u-v\\. vU Доказательство. Используя свойства выпуклых функций для V и Є U запишем следующие соотношения 0 J(uN)-J (J (UN),UN-U ) = (uN-Pu(uN-J (uN)),uN-u )+ +{PU{UN - J (uN)) -uN + J (UN), UN - u ) = = (uN - Pu(uN - J (uN)),uN - u )+ +{PU{UN - J M) - (uN - J (uN)),uN - PU(UN - J (UN)))+ +(PU{UN - J (uN)) - (uN - J (uN)), Pu(uN - J {uN)) - Puu ). Так как, в силу свойства проекций последнее слагаемое здесь неположительно, то, с учетом оценки (2.1.4), получаем 0 J(UJV) - J {uN - PN{UN - J {uN)),uN - u ) -\\PN{UN - J {uN)) - uN\\2 + {J (uN),uN - PU{UN J {UN))) (D+\\J (uN)\\)eN. Пусть v - предельная точка к г дг. Тогда в силу непрерывности J (и) и замкнутости U, получаем v Є С/ . Для построения, сходящейся к определенному элементу и Є U , последовательности и Є U, N = 1,2,... можно воспользоваться методом регуляризации Тихонова [80]. Пусть fi(w), и Є Еп - сильно выпуклая, дифференцируемая функция, причем fi (u), и Є U удовлетворяет условию Липшица. Обозначим через fi = inf Q(u), и Є U — Q - нормальное решение: Q(u ) — О = inf 1(и) и введем для (2.1.1) регуляризирующие задачи TN(u) = J(u) + aNQ(u) -+ inf, и U, N = 1,2,..., (2.1.5) где адг 0, iV = 1,2,..., Q;JV — 0, JV — оо. Обозначим их точные решения: u NeU: TN(u N) =TN= miTN{u),N = 1,2,..., кЄІ/ а также приближенные решения в виде: uN Є [/ : TN TN{uN) = Г; = TN + eN,N = 1,2,..., где JV 0, iV = 1,2,..., є/v — 0, iV — со. Для этих решений известны утверждения о сходимости по функционалу TJV(WJV) — J ,iV — со; слабой сходимости UJV — 7 ,iV — со и сильной сходимости по аргументу и„ — и \\ — 0, iV — со (см., например [46]). В приближенных решениях, определенных данном образом, содержатся неизвестные величины Тдг, iV = 1,2,... Это обстоятельство делает более предпочтительными условия приближенности решений, не содержащие неизвестные величины, связанными с точными решениями. В связи с этим определим условия приближенности решений следующим образом: определим последовательность UJV U, N = 1,2,..., удовлетворяющую аналогичным (2.1.2) и (2.1.3) соответственно условиям: \\ris - wN\\ eN, w% = Pu{uN - T N(uN)); (2.1.6) 0 (T N{uN), uN - wjf) 4, (2-1-7) wlNeU : (T N(uN), wlN - uN) = min (T N(uN), v-uN), N = 1,2,... veU Для этой последовательности имеют место следующие утверждения о сходимости к решениям задачи (2.1.1) [46].

Теорема 2.2. Для последовательности и Є U, N = 1,2,..., удовлетворяющей в задачах (2.1.5) условиям (2.1.6) или (2.1.7), при N/&N - 0 N -» со имеет место сходимость Цмдг — w -»О, N — оо и справедливы следующие оценки по функционалу ajvft TN{uN) - J aNn(u ) + C(sN/aN)1/2; 0 J{uN) -J aN[V(u ) - fij + C(eN/aN)1/2, где т; = іпіад, w - произвольный элемент из U , а константа С = С (и ) не зависит от N. 2.2. Аппроксимация множеств для ограничений типа неравенств. Пусть задача (2.1.1) является задачей с ограничениями типа неравенств, тогда множество U задается в виде (1.1.2), т.е. и = {иЄЕп:ф) 0, і ЄІ}, / = {l,...,m}, где 7i(u), и Є Еп, і Є І - выпуклые, непрерывно дифференцируемые функции. Будем предполагать, что U ограничено и выполняется условие Слейтера. Введем следующие аппроксимации для множества (1.1.2): UN = {и Є Еп : gNi(u) = 9і{и) + о Щи) О, г Е /}, (2.2.1) где a N a N+1 О, N = 1,2,..., агм -» О, JV - со, а ПІ (и), и Є i?n, і Є I - неотрицательные, сильно выпуклые и дифференцируемые функции. Отметим, что имеют место включения UN С C/jv-f-i С С/, iV = 1,2,..., а из непустоты U при малых ajy вытекает непустота множеств UN, И выполнение для них условия Слейтера. Обозначим д(и) = (gi{u),...:gm(u)),gN(u) - (gm(u),...,gNm{u)), PN - оператор проектирования на f/jv и определим аппроксимирующие задачи JN(u) - inf, uGUN, N = 1,2,... . (2.2.2) Пусть WJV Є t/jv, N = 1,2,... - некоторая последовательность, удовлетворяющая условию \WN - wN\\ N, WN - PN(UN J N(UN)) (2.2.3) или условию О ЙЫ, uN - w}f) 4, (2.2.4) WN (J N{UN), W1N - UN) = min (J N(uN), v-uN). veUN Покажем, что эти приближенные решения сходятся к решению задачи (2.1.1), (1.1.2). Для этого предварительно отметим следующее вспомогательное утверждение, доказанное в [46]. Лемма 2.1. Для множеств (1.1.2), (2.2.1) при достаточно малых а]у, і = 1,2,..., N = 1,2,... справедлива оценка \\PNU — и\\ Стаха , V и Є U, ІЄІ где константа С = С(и) 0 не зависит от N. Теорема 2.3.

Вспомогательные утверждения

Теперь, когда доказана выпуклость некоторых задач оптимального управления, для их решения был организован численный эксперимент, реализующий конечношаговые алгоритмы минимизации функционалов, построенный на регуляризованном методе проекции градиентов. Для рассмотренных в параграфе 4.1 выпуклых задач реализован механизм следующего вида: размерности пространств Еп и пространства управлений соответственно пит могут задаваться произвольными натуральными числами, ограничением может лишь служить лимит процессорного времени для решения конкретной задачи. Исходя из указанных значений пит задаются виды матриц A(t), B(t) и столбец /(і), также значение числового вектора XQ И значение То, тем самым польностью определяя постановку задач (4.1.3) или (4.1.7). Задание же вектора у и R для ограничений полностью исчерпывает тот объем начальных данных, который необходим для решения уже конкретной задачи оптимального управления.

В качестве Q(u),u Є U С Я для (2.1.5) используются функционалы вида: Q,(u) = \\u\\2,u Є Я, а в качестве последовательности ан Q,N = 1,2,...,аі# — О, JV —» со берется последовательность

Поскольку численное моделирование возможно только для сеточных функций, для фукционала (4.1.2) можно выписать его сеточное дискретное представление: J(u) = \\XQ — у\\р — inf, где XQ = x(t;u),xq = x(to + Atq;u) = x(tq;u),tq = to + &tq,q = O..Q, + AtQ = Т. Учитывая данные обозначения, система (4.1.3) примет вид: /й1зг =4«.) «+ («.)«+/(«. (421) a; (to) = яо; где rco-заданный вектор, a uq - значение вектора управления в точке tq. Соответственно ограничения (4.1.1) для дискретной задачи примут вид: т q=0 Значение функционала Q(u) в регуляризованной задаче (2.1.5) будет: т / Q j=\ \q=0 Аналогично можно записать для сопряженной системы: Фд - Фч-1 -ЛТ{ія)фд, Фя = P\\XQ - y\\p 2(xQ - у); гррфд = ф(Ьд),д = 0..д Значение градиента, необходимое при численном решении: J (uq) = 2Вт{ія)фг

В численно решенных задачах шаг по времени At брался равным 0.001, таким образом, для отрезка [о,Т], равного, например [0,1] количество точек разбиения составляло порядка 103. В качестве условий остановки (2.3.8) и (2.4.5) и проверки сходимости итерационных процессов \\ujsf — и \\ — 0,iV — оо и (2.3.3) использовалась величина є 10 4. Поскольку для процесса (2.3.1) начальное значение управление произвольное и должно лишь удовлетворять условию u/v Є l/jv, то для решаемых задач оно задавалось в виде UN ( ) І + С)І — 1-П , с Є R. В случае, если сгенеренное таким образом управление не являлось допустимым, то оно пересчитывалось по правилу: u3N [t)\ = \v?N (t) old I. Линейные задачи вида (4.1.2) (4.1.3). Пример 1. Размерности: т = 1,п = 1. Временной отрезок: [to,T] = [1,2]. A(t) = (t2)lxhB{t) = {t2)lxhf{t) = (-3f)ixi Доп. параметры: у = 1,р = 2,R = (4,48)ixi-Рис.4 представляет параметры модели. ..., .,,. Размерность . f -, Jsji ш Пр-во управлений Пр-ео траекторий 1 1 Cancel - --,.- Ограничения jytal OK R1 )4.480 R2 0.000 Cancel R3 П ППП R4 0.000 Начальное управление Начальная точка траектории Терминальная точка Точка начала отсчета времени Точка конца отсчета времени DK и 1 — Cancel 1.000 2.000 Рис. 4: Параметры модели. Рис.5 показывает управление (левый график) и траекторию (правый график), соответствующие начальным условиям. Так же на графике для траектории указана точка у расстояние до которой минимизируется в момент времени Т. .S!) л» Рис. 5: Управление и траектория соответствующие начальным данным. На Рис.6 изображена уже решенная задача. На левом графике получено допустимое управление, удовлетворяющее условию окончания счета (2.3.8), а на правом графике соответствующая этому управлению траектория. При этом значение функционала: J = Ю-6. Согласно теореме 2.6, полученное таким образом управление, является решением поставленной задачи оптимального управления с заданной точностью. « А Рис. б: Решение задачи. Пример 2. Размерности: т = 2, п = 2. Временной отрезок: [to, Т] = [1,2]. 3t U - 1 t - 2 / \ -3t Доп. параметры: Рис.7 представляет параметры модели. Размерность 1а ы #Ограничения Пр-во управлений р R1 )2.500 OK DO 1 9ПП Пр-во траекторий І2 пі. l.iUU Cancel R3 0 000 OK Cancel R4 0.000 Параметры модели ИЙ Начальное управление І(М) OK Начальная точка траектории 1 Cancel Т ерминальная точка 1 Точка начала отсчета времени 1.000 Точка конца отсчет эвр 3Mef ш 2.000 Рис. 7: Параметры модели. Рис.8 показывает сразу две компоненты управления (левый график), соответствующие различным начальным данным и две компоненты траектории (правй график), соответствующие начальным управлениям согласно условиям (4.2.1). Так же на графике для траектории указана точка у расстояние до которой минимизируется в момент времени Т.

Постановка задачи. Свойства параметров модели

Управление и траектория соответствующие начальным данным. На Рис.9 изображена уже решенная задача. На левом графике получены допустимые управления, с начальными данными Рис.7, удовлетворяющие условию окончания счета (2.3.8), а на правом графике соответствующие этим управлениям траектории. При этом значение функционала: J 10_6. Согласно теореме 2.6, полученное таким образом управление является решением поставленной задачи оптимального управления с заданной точностью. "р Рис. 9: Решение задачи. II. Билинейные задачи вида (4.1.2) при р = 2 (4.1.7). Пример 3. Размерности: т = 1,п = 1. Временной отрезок: [to,T] = [1,2]. A(t) = Міхі,Я(і) = (Оіхь/W = ( 3t)ixi Доп. параметры: у — 0,p = 2,R= (З.З)іхі-РисЮ. представляет параметры модели. J& Размерность -.[[ПІЦ Ограничения лЛДІЬД OK Пр-во управлений 11 R1 (3.300 R2 0.000 Cancel Пр-во траекторий І1OK Cancel R3 In плп R4 0.000 Рис. 10: Параметры модели. Рис.11 показывает управление (левый график) и траекторию (правый график), соответствующие начальным условиям. Так же на графике для траектории указана точка у расстояние до которой минимизируется в момент времени Т. А» Ах Рис. 11: Управление и траектория соответствующие начальным данным. На Рис.12 изображена уже решенная задача. На левом графике получено допустимое управление, удовлетворяющее условию окончания счета (2.3.8), а на правом графике соответствующая этому управлению траектория. При этом значение функционала: J 10 6. Основные результаты данной работы состоят в следующем:

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

2. Для решения выпуклых конечномерных задач минимизации с ограничениями типа неравенств при выполнении условия Слейтера разработаны два метода с конечношаговыми внутренними вычислительными процедурами. Эти методы построены на основе метода регуляризации, методов проекции и условного градиентов, а также двойственного метода. В предлагаемых методах использованы критерии останова, получены оценки сходимости по функционалу, сходимость по аргументу ко множеству оптимальных элементов и к Q - нормальному оптимальному элементу.

3. Исследована одна экономическая задача, для нее построена динамическая модель, позволяющая учитывать особенности рыночной экономики при производстве потребительских товаров, доказано существование решений, установлен факт наличия особого режима, и возможность наличия бесконечного числа моментов переключения на неособых участках.

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

Результаты, полученные в данной работе осбуждались на семинаре отдела методов нелинейного анализа ВЦ, на 13-ой Байкальской международной школе-семинаре в Иркутске и на "Понтрягинских чтениях - ХУН"Воронежской весенней математической школы.