«Нижегородский государственный университет им. Н.И. Лобачевского Методы оптимизации в примерах и задачах Учебно-методическое пособие Рекомендовано методической комиссией факультета вычислительной математики и кибернетики ...»

Для функции Q (x) общего вида метод за N итераций в точку её минимума, естественно, не попадет и будет выполнен рестарт из последней найденной точки. Кроме того, для функции общего вида очередной вектор p k может не являться направлением строгого локального убывания. Это проверяется в пункте (c). В случае нарушения данного условия выполняется рестарт из последней точки.

Метод Хука-Дживса Этот метод прямого поиска, т.е. измеряются только значения функции, а гладкость и даже непрерывность Q (x ) не предполагаются. Направление локального убывания определяется построением так называемой конфигурации.

При удачных перемещениях создается и в последующем используется шаг по образцу.

Пусть e1, e2, K, eN – координатные орты, а h – параметр конфигурации.

Алгоритм построения конфигурации x = F (z ).

(b) Для i N выполнить пункт (c); при i > N завершить построение конфигурации.

Q ( x h ei ) < Q ( x ), положить x := x h ei ; иначе сохранить прежнее x.

Увеличить номер координаты i := i + 1 и вернуться к пункту (b).

Основной алгоритм (a) Задать начальную точку x 0, параметр останова конфигурации h >>.

(c) Построить конфигурацию x k +1 = F ( z k +1 ) (e); иначе, если h <, остановить вычисления, приняв за оценку решения значение x k ; если же h >, то перейти к пункту (f).

пункту (c).

(f) Если k > 0, положить x 0 := x k, k = 0 и перейти к пункту (b); если же k = 0, то уменьшить параметр конфигурации h := h 2 и перейти к пункту (b).

4.5. Вычислительные методы решения задач с ограничениями Рассмотрим задачи общего вида (4.1)-(4.2) и приведем описание двух общих методов: метода внешнего штрафа и метода модифицированных множителей Лагранжа. Оба метода строят последовательность вспомогательных оптимизационных задач. Минимизируемые функции этих задач зависят от настраиваемых параметров. Решения исходной задачи можно получить как предельные точки последовательностей решения вспомогательных задач.

Метод внешнего степенного штрафа [8, 9, 10, 13] Функция H (x ), определенная на множестве x E, называется функцией штрафа в задаче (4.1)-(4.2), если Одним из конкретных видов функции штрафа является степенной штраф:

где c1, K, c N ; C1, K, C M - положительные нормировочные коэффициенты, а показатель степени p > 0.

Заметим, что при достаточной гладкости функций g i и h j порядок гладкости функции штрафа определяется значением p следующим образом:

(a) при 0 < p 1 негладкий штраф;

(b) при 1 < p 2 гладкость до первого порядка;

(c) при 2 < p 3 гладкость до второго порядка.

Построим вспомогательную функцию для задачи со штрафом > 0 – коэффициент штрафа. Заметим, что в допустимой области x D где функция S ( x ) = Q ( x ), а вне этой области S ( x ) > Q ( x ) за счет присутствия положительной штрафной добавки за нарушение ограничений.

Вспомогательные задачи со штрафом будут иметь вид:

где выбирается решения x k этих задач существуют и не покидают некоторой ограниченной и замкнутой области. Если E - компактно, то последнее предположение будет всегда выполнено. Можно доказать, что при непрерывности Q и H все предельные точки последовательности будут являться решениями исходной задачи (4.1)-(4.2). Структуру задачи со штрафом при некотором коэффициенте штрафа k иллюстрирует рис. 4.4.

Рис. 4.4. Пример поведения функции задачи со штрафом при гладкой функции штрафа Заметим, что при гладкости штрафа в случае положения x* (решения исходной задачи) на границе допустимой области D сходящаяся к x * подпосследовательность x k решений вспомогательных задач со штрафом в общем случае будет приближаться к x*, оставаясь вне области D. Сходимость обеспечивается лишь при k. Это приводит к ухудшению структуры функций со штрафом S k (x ) за счет усиления их «овражности», т.е.

увеличения разброса значений собственных чисел матриц Гессе в точках x k решений вспомогательных задач. Этот эффект препятствует хорошей работе вычислительных методов.

Алгоритм метода штрафов (a) Задать > 0 – параметр останова, 0 – достаточно большое начальное значение коэффициента штрафа; выбрать стратегию построения последовательности k, обеспечивающую стремление k к бесконечности при k. Выбрать степень в штрафе p, p > 1, и принять k = 0.

(b) Найти решение x k в задаче со штрафом (4.6), используя один из методов решения задач без функциональных ограничений с использованием информации о решении x k 1 предыдущей задачи.

(c) Проверить критерий останова по малости невязки Если G ( x k ), остановить вычисления и принять x k в качестве оценки решения; иначе, при G ( x k ) >, перейти на пункт (d).

(d) Выбрать, согласно принятой стратегии, обеспечивающей неограниченное увеличение k, значение k +1 > k, положить k := k + 1 и вернуться к пункту (b).

Методы модифицированных функций Лагранжа Метод ориентирован на решение задачи (4.1)-(4.2) при E = R n в случае гладкости функций Q, g i и h j до второго порядка. Для сходимости метода должны быть выполнены ещё и некоторые дополнительные условия, имеющие характер достаточных условий второго порядка наличия в x* строгого локального минимума (включающих достаточные условия регулярности области в точке x* в форме линейной независимости градиентов ограничений).

В основе метода лежит идея определения x* путём поиска седловой точки модифицированной функции Лагранжа L ( x,, ) в пространстве прямых переменных Лагранжа).

Обычная функция Лагранжа для задачи с регулярной областью, имеющая вид далеко не всегда имеет в точке Каруша-Куна-Таккера ( x *, *, * ) седловую точку по области x R n, только при выпуклости Q, g i и аффинности h j. Для задач более общего вида ее может не быть.

Если же модифицировать функцию Лагранжа, добавив к ней штрафную функцию, то при достаточно большом коэффициенте штрафа модифицированная функция Лагранжа будет иметь в точке Каруша-Куна-Таккера седловую точку.

Метод модифицированных функций Лагранжа для задач с равенствами [9, 13] Решается задача Модифицированная функция Лагранжа имеет вид Градиент этой функции по переменным Метод сочетает поиск минимума модифицированной функции Лагранжа по переменным x с процедурой градиентного поиска максимума этой функции по переменным.

Описание алгоритма (a) Задать > 0 - параметр останова, x 0, 0 - начальные значения прямых и двойственных переменных, штрафа; определить стратегию изменения последовательности k ; принять k = 0.

(b) Определить локальный минимум используя в качестве начальной точки x k.

(c) Найти новые оценки множителей Лагранжа, выполнив шаг в направлении градиента по модифицированной функции Лагранжа:

(d) Проверить критерий останова по малости невязки в условиях оптимальности:

Если эти условия выполнились, приять x k +1 в качестве оценки решения задачи с ограничениями; иначе перейти на пункт (e).

(e) Изменить k, согласно принятой стратегии, выбрав k +1 k, положить k := k + 1 и вернуться к пункту (b).

При определённых требованиях к задаче (4.7) и при достаточной малой погрешности начального приближения метод обеспечивает сходимость ( x k, k ) к ( x *, * ) - стационарной точке функции Лагранжа (эта точка одновременно является седловой для модифицированной функции Лагранжа).

При этом T 0, что Таким образом, по множителям Лагранжа сходимость будет линейной, если коэффициенты штрафа k остаются ограниченными. Если же k при k, то сходимость по будет сверхлинейная.

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

Метод модифицированных функций Лагранжа для задач с равенствами и неравенствами [9, 13] Метод ориентирован на решение гладких до второго порядка задач вида (4.1)-(4.2) при E = R n. Его правила могут быть получены из рассмотренного выше аналогичного метода для задач с ограничениями-равенствами за счёт сведения неравенств g i ( x ) 0 к равенствам g i ( x ) + zi2 = 0, включающим искусственные переменные zi. При этом в правиле (4.8) нужно будет брать минимум не только по x, но и по ( z1, K, z N ). Исключая затем zi, путём аналитического определения их значений из условия оптимальности для (4.8), можно получить приведённый ниже алгоритм, использующий следующий вид модифицированной функции Лагранжа.

Описание алгоритма (a) Задать > 0 - параметр останова, x 0, 0, 0 - начальные значения прямых и двойственных переменных, 0 - начальное значение коэффициента штрафа; определить стратегию изменения последовательности k = 0.

(b) Определить локальный минимум используя в качестве начальной точки x k.

(c) Найти новые оценки множителей Лагранжа:

(d) Проверить критерий останова по малости невязки в системе условий Каруша-Куна-Таккера:

условиях дополняющей нежёсткости. Если все условия выполнены, остановить вычисления и принять x k +1 в качестве оценки; иначе перейти к пункту (e).

(e) Выбрать k, согласно принятой стратегии k +1 k ; положить k := k + 1 и вернуться к пункту (b).

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

4.6. Методы липшицевой многоэкстремальной оптимизации Этому вопросу посвящена общирная литература (см., например, библиографию в [19], [13]).

Рассмотрим задачу поиска глобального минимума где функция Функция Q называется липшицевой в области E с константой Липшица Такие функции обладают ограниченной «скоростью» изменения. Например, sin x - липшицева с константой L 1 в R1, а функция x липшицева на [, ) при > 0 с константой L 1 ( 2 ), но не является липшицевой на [0, ). Заметим, что, кроме принимаемой нами по умолчанию евклидовой нормы многоэкстремальных функций.

Пусть выполнено k измерений функции в точках x s с результатами Qs ( s = 1, K, k ). По результатам каждого измерения можно построить, используя (4.10), верхнюю и нижнюю оценки для Q (x ) :

Учитывая результаты всех k измерений, получим (рис. 4.5) Свойство Липшица позволяет по конечному числу испытаний получить оценки положения глобальных минимумов x* и значения функции в них Q*(x) = Q(x*). Очевидно, что Qk Q* Qk, а x* Ek = x E : Qk ( x) Qk.

Многие методы липшицевой оптимизации основаны на размещении новых измерений в тех точках, где можно ожидать наименьших значений функции Q.

Метод С.А. Пиявского (1967) (a) Задать > 0 - точность решения задачи и L - константу Липшица, вычислить функцию в k0 1 произвольно выбранных начальных точках x s, запомнить значения Qs ( s = 1, K, k0 ) ; положить k = k0.

(b) Найти точку (c) Проверить выполнение критерия останова: Qk Qk ( x k +1 ).

Если условие выполнено, то точку xk, соответствующую проведенному измерению со значением Qk, принять за оценку глобального минимума; иначе перейти к пункту (d).

(d) Выполнить измерение Qk +1 = Q ( x k +1 ), положить k := k + 1 и вернуться к пункту (b).

При компактности E и липшицевости функции Q с константой L метод остановится через конечное число шагов и построенная им оценка Qk будет отличаться от глобально-оптимального значения не более чем на. В процессе своего выполнения метод строит неравномерное адаптивное покрытие области поиска E точками испытаний. Это покрытие (при весьма общих условиях) в пределе имеет в качестве точек сгущения множество глобальных минимумов решаемой задачи.

В случае, когда размерность задачи n = 1, метод С.А. Пиявского называют методом ломаных [13, 17, 19]. Пусть E = [ a, b ], тогда обычно используют k0 = 2 и принимают x1 = a, x 2 = b. После проведения нескольких испытаний упорядочим точки измерений нижним индексом в порядке возрастания координаты: a = x1 < x2 < K < xk 1 < xk = b. Будем считать, что им соответствуют результаты измерений Q1, Q2, K, Qk. Тогда в каждом из интервалов [ xi, xi +1 ] нижняя оценка будет иметь вид одного «зубца» (см. рис. 4.5) с координатами точки минимума:

Величину R i называют характеристикой интервала.

Алгоритм метода ломаных (a) Задать > 0 - точность решения задачи, L > 0 - константу Липшица, положить k = 2.

(b) Найти интервал с лучшей характеристикой (c) Если Qk Rt, остановить вычисления и принять за оценку глобального минимума точку xk, соответствующую Qk ; иначе перейти на пункт (d).

(d) Вычислить xk +1 = xt и Qk +1 = Q ( x k +1 ) ; вставить полученную пару x k +1, Qk +1 в упорядоченный по координатам набор проведенных испытаний (в отрезок с номером t ); положить Qk +1 = min { Qk, Qk +1}; увеличить k := k + и вернуться к пункту (b).

В случае неизвестной константы Липшица метод может проводить её оценку в ходе поиска. А именно, после k -го измерения можно вычислить величину являющуюся заниженной оценкой для L. Как правило, вводят коэффициент надежности r > 1 и в качестве оценки L принимают величину которую и используют в алгоритме вместо L.

Укажем на эффективный информационно-статистический метод, предложенный Р.Г. Стронгиным [19].

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

Во-первых, в соотношениях (4.11)-(4.12) изменяется способ определения характеристики (4.12). В информационно-статистическом методе она может быть представлена в виде:

Во-вторых, константа Липшица считается неизвестной и оценивается согласно (4.13)-(4.14). При вычислении характеристики Ri используется её оценка (4.14).

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

Компонентные методы В многомерном случае метод С.А. Пиявского точно не реализуем.

Для построения процедур многоэкстремальной оптимизации в многомерном случае используются несколько подходов: методы редукции (т.е.

понижения) размерности с использованием разверток Пеано-Гильберта, редукция с применением многошаговой схемы; компонентные методы [13].

Методы последней группы последовательно разделяют множество E на подобласти-компоненты P стандартной формы (чаще всего – гиперинтервалы).

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

Форма компонент P и правило размещения в ней измерений выбираются так, чтобы существовала аналитическая нижняя оценка Q (P ) наименьшего значения Q (x ) при x P. Далее на каждом шаге для последующего деления выбирается компонента P * с наименьшей нижней оценкой Q ( P * ).

Метод деления на три Метод предложен Ю.Г. Евтушенко и В.А. Ратькиным в 1987 год и использует деление исходного множества E = x Rn : ai xi bi, i = 1,K, n координатными плоскостями на гиперинтервалы P с последующим проведением по одному испытанию в геометрических центрах каждого из P (так называемая центральная схема измерений) [13]. Гиперинтервал с геометрическим центром в точке y будем обозначать как Py. Пусть Q y = Q( y ), а diam( Py ) - диаметр множества Py. Из свойства (4.10) очевидно следует, что Использование этой оценки позволяет построить метод деления на три. На рис. 4.6 показан пример возможного вида разделения множества E на компоненты и размещение точек испытаний после трех итераций метода.

Рис. 4.6. Характер возможного разбиения области поиска в методе деления на три после трех итераций (цифрами отмечены точки проведенных испытаний) Описание алгоритма (a) Задать > 0 - точность поиска и L > 0 - константу Липшица.

(b) Исходный гиперинтервал E разделить по большему ребру на три равные части P, P2, P3. В их геометрических центрах x1, x 2, x 3 выполнить измерения Q1, Q2, Q3, вычислить по формуле (4.15) нижние оценки Q ( Pi ) (i = 1,2,3) и принять их за характеристики гиперинтервалов Pi :

R ( Pi ) = Q ( Pi ). Наборы K i = (Pi, Qi, R ( Pi ) ) поместить в список K.

(c) В списке K найти лучший по характеристике R ( Pi ) набор K t (e) Если выполняется Q * Q ( Pt ), остановить вычисления и в качестве оценки глобального минимума выбрать точку испытаний с наименьшим значением функции; иначе перейти к пункту (f).

(f) Разделить Pt по его большему ребру на три равных компоненты P, P2 и P3 ; провести измерения функции в геометрических центрах крайних компонент. Значение функции в центре средней известно, и его следует извлечь из набора K t (оно равно Qt ). Вычислить для новых компонент нижние оценки функции по формуле (4.15). Исключить из списка K набор K t и включить в него три новых набора, соответствующих построенным новым компонентам.

Вернуться к пункту (с).

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

Метод деления на три для задач с ограничениями-неравенствами Метод применим к задаче где функции Q и g i липшицевы с константами LQ и Lg i,а допустимая область не пуста. Алгоритм поиска глобального минимума для задачи с ограничениями-неравенствами аналогичен рассмотренному выше, поэтому остановимся только на отличиях.

В центре каждой компоненты P вычисляются значения всех функций Q, g1, K, g N. Результаты измерения для компонента Pi обозначим Q i, g1, K, g N. Далее для гиперинтервала P вычисляются нижние оценки для каждой из функций Q, g1, K, g N по результатам их измерений в геометрическом центре P. Вид этих оценок аналогичен (4.15).

Введем новый способ вычисления характеристики компоненты P.

Может сложиться две ситуации. Если i = 1, K, N все значения g i ( P ) 0, то в компоненте P существуют допустимые точки и в качестве её характеристики примем нижнюю оценку функции Q по области P, т.е.

R ( P ) = Q ( P ). Если же для некоторого i выполняется g i ( P ) > 0, то допустимых точек в P нет и проводить дальнейшие измерения в ней нецелесообразно. Для того, чтобы такая компонента никогда не была выбрана для дальнейшего деления, формально положим для нее R (P ) = +.

Наборы K i, помещаемые в список K в пунктах (b) и (f), теперь будут включать в себя более широкую информацию: K i = Pi, Q i, g1, K, g N, R ( Pi ).

Кроме того, изменится правило вычисления значения Q* - оценки глобальнооптимального значения. Поскольку теперь не любая точка проведенного измерения допустима, следует определить наилучшее значение только по допустимым точкам, т.е. значение Q* в пункте (d) теперь будем вычислять так:

где | K | - количество элементов в списке K. Если к данному шагу ни одной допустимой точки не встретится, формально положим Q* = +.

Остальные действия, описанные в алгоритме метода деления на три при отсутствии ограничений, принципиально не изменяются и остаются такими же для метода, учитывающего ограничения-неравенства.

4.7. Контрольные задания 1. Выяснить, какой из трех пассивных M шаговых алгоритмов ( j = 1, 2, 3 ) обладает меньшим значением гарантированной погрешности d * ( ) при поиске минимума унимодальной функции Q на отрезке [0, 10].

Погрешность измеряется длиной интервала, который определяется в качестве подобласти, содержащей глобальный минимум, после проведения M измерений функции Q и применения правил отбрасывания.

Принять, что алгоритмы проводят измерения функции в точках со следующими координатами: 1 =4 :1, 3, 4, 8 ; M = 4 : 3, 4, 7, 8 ; M =5 : 2, 4, 6, 8, 9.

Для каждого алгоритма показать на рисунке подынтервал, соответствующий значению d * ( ).

2. Для класса задач оптимизации, представленных в задаче № 1, получить оптимальное пассивное размещение M = 5 точек измерений, а также -оптимальное для M = 4 и M = 6 точек.

3. Задачу поиска минимума унимодальной функции Q =| x 6 | на отрезке [0, 10] решить с точностью = 1, используя следующие последовательные методы: Фибоначчи (с параметром -оптимальности = 0.01); золотого сечения (приняв 0.62 ); дихотомии (по схеме с использованием измерения в центральной точке). Сравнить число проведенных измерений в каждом методе и реальную достигнутую точность.

Указание: для методов Фибоначчи и дихотомии вычисления провести в обыкновенных дробях.

4. Для класса строго возрастающих функций f, имеющих значения разных знаков на концах отрезка [a, b], построить последовательный M шаговый метод поиска корня, оптимальный по отношению к гарантированному значению остаточной ошибки. Изменится ли алгоритм, если использовать правило проведения измерений, оптимальное по гарантированному значению ошибки, только на один шаг вперед?

5. В условиях задачи № 4 построить метод, оптимальный на шаг вперед по гарантированному значению ошибки, если известна следующая дополнительная информация о функции:

6. Для дифференцируемой выпуклой функции Q (x ), заданной на множестве D = [0, 5]2 R 2, по измерениям градиента, выполненным в трех точках x1 = (1; 3), x 2 = ( 4; 1), x3 = (0; 2) выделить минимальное подмножество, гарантированно содержащее точку глобального минимума Q на D.

Считать, что значения градиентов Q1, Q2, Q3 в этих точках следующие:

7. Построить нижнюю оценку выпуклой функции на отрезке [0, 9] по результатам пяти ее измерений ( x k ; Qk ) : (0; 6), (1; 4), (5; 2), (8; 5), (9; 9).

8. Изучить последовательности испытаний, порожденные методами Ньютона при поиске минимума следующих функций скалярной переменной x :

(a) Q( x) = x(m +1) m, где m – нечетное число; (b) Q( x) = x 4 ; (c) Q( x) = x 2 + x 4.

Выяснить наличие сходимости, порядок сходимости, определить область сходимости. Объяснить результаты, используя условия сходимости метода.

Указание: для определения области сходимости в случае (c) используйте диаграммы Кенигса-Ламерея.

9. Исследовать поведение метода Ньютона для функции, «собранной» из двух квадратичных Q ( x1, x2 ) = max ( x1 + 1) 2 + 5 x2 ; ( x1 1) 2 + 5 x Дать объяснение обнаруженному эффекту.

10. Показать, что для метода наискорейшего градиентного поиска, примененного к функции Q ( x1, x2 ) = x1 + x2, > 0, выполнение одной итерации из точки ( x1 ; x2 ) = ( a ; a функции по закону Q k +1 = Q k q ( ), где Исследовать зависимость q от параметра итерации. Какая связь Q k +1 с Q k будет в случае использования метода Ньютона?

11. Используя соотношение Канторовича, получить оценку скорости сходимости метода наискорейшего градиентного поиска для функции 12. Для функции Q ( x1, x2 ) = x1 + 9 ( x1 + 1) + x2 исследовать применение трех алгоритмов выбора шагового множителя t k при условии, что итерация метода локальной оптимизации выполняется из точки x k = ( x1 ; x2 ) = (0; 0) в направлении d k = (1; 0). Найти t k, используя:

а) метод Армихо с параметрами b) правило Вулфа с параметрами останова = 1 80, = 1 40 и начальным пробным t = = 20, коэффициентами «экстраполяции» и «интерполяции», соответственно, 2 и 1 2.

c) метод одномерной оптимизации с параметрами останова = 1 40, основанный на использовании золотого сечения, считая, что начальный отрезок поиска [0, T ] = [0, 20]. Как изменится начальный отрезок [0, T ], если значение T выбирается алгоритмически просмотром луча xk + d k t с удваивающимся шагом h при начальном значении t = 0 и h = 2 10 ?

множество точек, в которых выполняется критерий останова Q ( x1, x2 ) 14. Построить качественный вид линий равного уровня функции Розенброка Q ( x1, x2 ) = 100 ( x2 x1 ) 2 + ( x1 1) 2. Применить метод ХукаДживса для начальной точки x k = 0 = ( 2; 2) при начальном значении шага построения конфигурации h = 1 и параметре останова сопряженных градиентов из начальной точки x 0 = ( x1 ; x2 ) = ( a ; a ), построив x k для k = 1, 2. Сколько итераций понадобится этому методу для попадания в минимум функции Q ? Сколько итераций при тех же условиях понадобится методу наискорейшего градиентного поиска, методу Ньютона?

16. В методе внешнего квадратичного штрафа исследовать влияние величины коэффициента штрафа на степень обусловленности функции S (x ) вспомогательной задачи со штрафом для задачи наибольшему из собственных чисел матрицы вторых производных функции S (x ) в точке ее минимума x.

17. Для метода внешнего штрафа доказать, что при строгом возрастании коэффициента штрафа k +1 > k в точках минимума x вспомогательных задач со штрафом значения функций штрафа H (x ) и целевой функции Q (x ) удовлетворяют соотношениям: Q ( x k +1 ) Q ( x k ), H ( x k +1 ) H ( x k ).

18. Получить оценку погрешности решения задачи по невязке в ограничении в зависимости от величины коэффициента штрафа.

Считать, что задача решается методом внешнего степенного штрафа с показателем степени p = 2. Оценить количество итераций метода штрафа для решения задачи с погрешностью если начальное значение коэффициента штрафа 0 = 2 и его значения удваиваются после каждой итерации.

19. Исследовать зависимость величины ошибки по координате от показателя степени p > 1 степенного штрафа и значения коэффициента штрафа методом внешнего штрафа.

Как изменится результат, если функцию ограничения-неравенства заменить на g ( x ) = ( x 1) 3.

20. Оценить характер сходимости по множителям Лагранжа для метода модифицированных функций Лагранжа, примененного к вырожденной задаче min { x 2 : h( x ) = x 1 = 0}. Представить процесс изменения приближения k множителя Лагранжа диаграммой Кенигса-Ламерея на плоскости ( k ; k +1 ). Выяснить влияние поведения последовательности коэффициентов штрафа на порядок скорости сходимости.

21. Выполнить исследование, аналогичное предложенному в задаче № 19, для задачи min{ x ( x + 1) : h( x ) = x = 0}, применительно к процессу поиска локального минимума в окрестности точки x* = 0.

22. Вывести итерационные соотношения метода модифицированных функций Лагранжа для задачи min {x ( x 1) : g ( x ) = x 0}, с ограничениемнеравенством используя известную форму этого метода для случая ограничений-равенств.

Указание: заменить неравенство g ( x ) 0 эквивалентным равенством h( x, z ) = g ( x ) + z 2 = 0 за счет добавления искусственной переменной z. В полученных итерационных соотношениях от переменной z следует избавиться.

23. Для функции Q (x ), липшицевой с константой L = 1 на отрезке x [0, 10], известны результаты трех измерений: x1 = 3, Q ( x1 ) = 1; x 2 = 6, Q ( x 2 ) = 2 ; x 3 = 10, Q ( x 3 ) = 1, где верхний индекс – номер измерения.

Построить по этим данным миноранту функции, получить ее графическое представление, определить нижнюю оценку глобально-оптимального значения Q ( x* ) и указать область возможного положения точек глобального минимума на отрезке [0, 10]. Как изменятся построенные оценки, если становится известным результат четвертого измерения: x 4 = 0, Q ( x 4 ) = 0 ?

24. Применить метод Пиявского (ломаных) к функции Q ( x ) = x на отрезке x [0, 16], используя в качестве константы Липшица значение L = 2 .

Первые два измерения провести в точках x1 = 0 и x 2 = 16. Определить координаты третьего и четвертого: x 3 и x 4. После проведения этих измерений, получить оценки решения как по значению функции, так и по координате.

25. Липшицева с константой L = 1 функция Q (x ) рассматривается на отрезке x [0, 18] ; имеется следующий набор измерений: x1 = 3, Q ( x1 ) = 6 ;

x 2 = 9, Q ( x 2 ) = 3 ; x 3 = 15, Q ( x 3 ) = 5, где верхний индекс – номер измерения. Сравнить нижние оценки, построенные для двумя методами: ломаных и деления на три.

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

26. Рассмотреть задачу поиска глобального минимума негладкой функции Q ( x ) = min x 2 ; 1 + ( x 5) 2 3 на отрезке [2, 8]. Используя качественные геометрические построения, показать размещение первых девяти точек испытаний в методе деления на три и в методе Пиявского. В качестве L выбрать минимально возможное для Q (x ) значение.

27. В задаче № 26 применить метод Пиявского, используя адаптивную оценку константы Липшица со значением коэффициента надежности r = 2.

Показать работу метода, выполнив качественные геометрические построения для первых семи шагов.

28. Определить погрешность оценки глобального минимума в задаче min Q ( x ), x [0, 648] при применении метода деления на три после выполнения двух итераций метода. Принять, что константа Липшица L = 2, а значения функции во всех точках испытаний, проведенных на этих итерациях, совпали со значениями функции x в этих точках.

константой L, определить выражение для нижней оценки Q (x ) в целом по параллелепипеду P (a, b ) = {x R n : ak xk bk, k = 1, K, n}, используя результат ее измерения Q y = Q ( y ) в геометрическом центре P, y = (a + b) 2.

30. Найти оценку глобального минимума многоэкстремальной функции Q (x ) на множестве x = ( x1, x2 ) [0, 108]2 с точностью по значению функции при = 24, используя метод деления на три. Определить количество необходимых испытаний. Принять, что функция Q (x ) липшицева в метрике, использованной в задаче № 29, с константой L = 2, а ее значения во всех точках проводимых испытаний совпадают со значениями функции x1 + x2.

31. Используя метод деления на три, найти оценку глобального минимума многоэкстремальной функции Q (x ) на множестве x [0, 108]2 при наличии дополнительного ограничения g ( x ) 0. Точность построения оценки должна составлять = 24 по значению функции. Принять, что Q (x ) и g (x ) липшицевы по отношению к норме x = n =1 xk с константами LQ = и Lg = 1.5, а их значения в точках испытаний, проведенных до выполнения критерия останова, совпадают, соответственно, со значениями функций x1 + x 5. Вариационное исчисление 5.1. Основные понятия Пусть I [ y ()] – интегральный функционал, заданный на некотором классе Y допустимых функций y (x). Множество Y является открытым множеством. Функция y * ( x ) из Y называется глобальным минимумом (максимумом) функционала I [ y ()], если I [ y * (.)] I [ y ()] ( I [ y * (.)] I [ y ()]) для всех y Y.

Для определения локального экстремума необходимо ввести расстояние (норму) в множестве Y. В вариационном исчислении чаще всего используют расстояние 0 ( y1, y 2 ) = max y1 ( x) y 2 ( x) (сильное расстояние) и (слабое расстояние).

Соответственно определяется 2 вида локальных экстремумов. Если существует > 0 такое, что для всех y Y таких, что 0 ( y *, y ) < y * ( x) Y достигается сильный (слабый) локальный минимум (максимум).

Поскольку 1 ( y *, y ) 0 ( y *, y ), то если на y * достигается сильный экстремум, то, тем более, достигается и слабый. Глобальный экстремум является одним из локальных.

Для получения необходимых условий экстремума функционала рассматривается произвольное однопараметрическое семейство кривых y ( x, ), удовлетворяющих тем же условиям гладкости и тем же граничным условиям, что и допустимые кривые, и такое, что кривая y0 ( x), для которой вычисляется вариация функционала, погружена в это семейство при = 0.

I [ y ( x, )] =0. Необходимым условием экстремума (любого - сильного или слабого локального, глобального) является обращение в ноль его первой вариации для любого семейства y ( x, ). Это условие аналогично необходимому условию локального экстремума дифференцируемой функции.

Кривые, удовлетворяющие этому условию, называются экстремалями.

Дополнительный теоретический материал по разделу можно найти в литературе [20, 21], а задачи в [5, 11, 15, 20, 21].

5.2. Простейшая задача с фиксированными концами и а функция F ( x, y, y ) имеет непрерывные частные производные до второго порядка включительно. Для того, чтобы на функции y (x) достигался экстремум функционала, необходимо, чтобы y (x) удовлетворяла уравнению Эйлера: F y d dx (F y ) = 0. Интегральные кривые уравнения Эйлера являются экстремалями. Свойство кривой быть или не быть экстремалью не зависит от выбора системы координат (это означает инвариантность уравнения Эйлера относительно выбора переменных).

Уравнение Эйлера — нелинейное дифференциальное уравнение второго порядка в обыкновенных производных; в общем случае оно не интегрируется.

Отметим важные частные случаи. Если F явно не зависит от y, то имеется первый интеграл F y = C ; если F явно не зависит от x, то есть первый интеграл F y F y = C ; если F не зависит от y,то уравнение Эйлера не является дифференциальным уравнением и в общем случае не существует функций, удовлетворяющих заданным граничным условиям. Если же F зависит только от y, то экстремалями являются прямые y = C1 x + C 2.

уравнение Эйлера является линейным уравнением второго порядка, поэтому, даже если у него есть первый интеграл, то удобнее решать само уравнение.

Пусть найдены кривые, удовлетворяющие уравнению Эйлера и граничным условиям y ( x0 ) = y0, y ( x1 ) = y1. Решена ли задача? Нет, поскольку выполнение уравнения Эйлера является лишь необходимым условием экстремума: «каждый понимает разницу между арестом подозреваемого и фактическим доказательством его виновности». Если не решен вопрос о существовании решения, то нет смысла и говорить о необходимых условиях.

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

Отметим роль 2 F y 2. Задачи, где эта производная отлична от нуля, называются регулярными. Условие 2 F y 2 0 исключает возможность излома экстремалей (теорема Дюбуа-Реймона). Кроме того, имеет место необходимое условие второго порядка (условие Лежандра): если на y * ( x) достигается минимум (максимум) функционала, то В точках нарушения условия регулярности (т.е. при 2 F y 2 = 0 ) экстремали могут иметь изломы, т.е. являться кусочно-гладкими.

Необходимыми условиями экстремума функционала в классе кусочногладких кривых является выполнение на каждом участке гладкости уравнения Эйлера, а в точках излома x экстремали – выполнение условий ВейерштрассаЭрдмана [20]:

Если y (x) – вектор-функция y ( x) = ( y1 ( x),..., y n ( x) ), то при аналогичных условиях для F и фиксированных граничных условиях необходимое условие экстремума состоит в выполнении системы n уравнений:

Если F = F ( x, y, y,..., y (m) ), то при аналогичных условиях для F и фиксированных граничных условиях y ( xi ) yi, y ( xi ) = y,..., y ( m 1) ( xi ) = yi( m 1), (i = 0, 1) необходимое условие экстремума первого порядка состоит в выполнении уравнения Эйлера-Пуассона:

z ( x, y ) — гладкие поверхности, удовлетворяющие на границе множества D условию z D = f ( x, y ), необходимое условие экстремума (уравнение ЭйлераОстроградского) имеет вид:

Пример 1. Задача Лопиталя о форме световых лучей Какова траектория световых лучей в атмосфере, где скорость распространения пропорциональна высоте?

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

Рассмотрим плоскую задачу. Пусть источник расположен в точке M 0 ( x0, y0 ), а наблюдатель – в точке M 1 ( x1, y1 ), y0, y1 > 0.

Запишем математическую модель этой задачи. Время распространения света из точки M 0 ( x0, y0 ) в точку M 1 ( x1, y1 ) описывается функционалом ( 1 + y2 )dx. Таким образом, Здесь = ky ( k > 0). Так как при всех k функционал достигает минимума на одной и той же кривой, то примем k = 1.

Функция F = 1 + y 2 y при y 0 имеет непрерывные частные производные до второго порядка включительно. Задача регулярна, необходимое условие Лежандра выполнено, так как при y > 0. Мы пришли к простейшей вариационной задаче: найти глобальный минимум функционала в классе гладких кривых, соединяющих точки M 0 и M 1. Уравнение Эйлера – трудное нелинейное уравнение второго порядка. Но если заметить, что F явно не зависит от x, то можно записать первый интеграл F y(F y) = C и решить существенно более простое уравнение первого порядка, которое легко интегрируется:

т.е. экстремалями являются окружности, центры которых лежат на оси Ox.

Через точки M 0 и M 1 можно провести единственную окружность данного семейства.

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

Через два века после Лопиталя А.Пуанкаре на основе этой задачи построил модель плоскости Лобачевского.

Пример 2. Задача о движении яхты против ветра Пусть на безграничном водном пространстве дует постоянный по величине и направлению ветер, вектор скорости которого параллелен вектору, направленному из точки B в точку A. Найти способ передвижения яхты, при котором она за наименьшее время сможет перейти из точки A в точку B.

Яхтсмены считают, что v = v ( y ). Требуется найти глобальный минимум этого функционала. Здесь F = 1 + y 2 = F ( y ), т.е. гладкими экстремалями в этой задаче являются прямые. На единственной прямой AB, соединяющей начало и конец движения, очевидно, не может достигаться минимум времени перехода. Отсюда следует, что поставленная задача решения в классе гладких кривых не имеет. Будем искать ее решение в классе кусочно-гладких кривых с конечным числом угловых точек. Поскольку на каждом участке гладкости искомая кривая должна удовлетворять уравнению Эйлера, то искомый путь яхты состоит из прямолинейных отрезков, т.е. яхта должна двигаться галсами.

Задача решена лишь качественно. Если мы хотим получить аналитический результат, то надо записать зависимость ( y ) и использовать условия Вейерштрасса-Эрдмана.

Найти экстремум функционала:

в классе гладких кривых, проходящих через точки В этой задаче экстремум может достигаться лишь на функциях y (x) и z (x), удовлетворяющих системе уравнений Эйлера:

Следовательно, любая допустимая кривая является экстремалью. Этот результат легко понять, если увидеть, что исследуемый функционал описывает работу силового поля 2 xyz 3 i + x 2 z 3 j + 3 x 2 yz 2 k по перемещению точки из M 0 в M 1. Это поле является потенциальным с потенциалом u = x 2 yz 3 ; в этом случае работа не зависит от пути.

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

Для плоского случая условия трансверсальности имеют вид где ( x, y ) = 0 — неявное задание кривой, по которой перемещается конец допустимой кривой.

В частности, если значения допустимых функций y (x ) на границе не подчинены никаким условиям (т.е. конец может перемещаться по прямой x = x0 или x = x1 ), то будем говорить, что это задача со свободным концом.

На свободном конце выполняется естественное граничное условие F y = 0.

Если конец движется по прямой y = const, то на нем F y F y = 0.

Если граничная кривая задана в явном виде y = f (x), то условия трансверсальности имеет форму задают условия ортогональности экстремали с граничной кривой: y f = 1.

Найти экстремали функционала в классе кусочно-гладких кривых, удовлетворяющих условию y (0) = 1.

F ( x, y, y) = y2 y 2 имеет непрерывные частные производные любого порядка, Fy y = 2 0, поэтому по теореме Дюбуа-Реймона экстремали изломов не имеют, являются дважды гладкими. Т.к. Fy y > 0, то если в данном классе допустимых кривых достигается экстремум функционала, то он является минимумом.

Необходимым условием минимума является выполнение уравнения Эйлера при 0 < x < 4, условие закрепленного конца y (0) = 1 и условие свободного конца при обращается в 0.

для экстремали откуда C2 = 1. Итак, экстремалью является кривая y = cos x + sin x.

Найти гладкую кривую OA длины l, проходящую через начало координат, кончающуюся на прямой y = h и образующую вместе с ординатой точки A и осью Ox наибольшую площадь.

В этой задаче требуется найти максимум функционала I [ y ()] = 0 1 y ( x)dx в классе гладких кривых, левый конец которых закреплен:

y (0) = 0, правый конец лежит на прямой y = h, а функционал I 0 [ y ()] = 0 1 1 + y2 dx принимает заданное значение l.

Решаем эту изопериметрическую задачу методом множителей Лагранжа.

Вводим вспомогательный функционал решаем для него задачу на безусловный экстремум. Запишем необходимые условия. Так как F1 = y + 1 1 + y 2 явно не зависит от x, то уравнение Эйлера имеет первый интеграл F y F1 y = c. Мы будем искать такое его решение, которое на левом конце удовлетворяет условию y (0) = 0, а на правом конце – условию трансверсальности, которое для горизонтальной прямой y = h имеет вид F y F1 y = 0. Таким образом, нам известно значение первого интеграла в одной точке (на правом конце). Тогда по определению первого интеграла во всех точках экстремали Это – семейство экстремалей. Неизвестные c,, x1 определяются из искомую кривую рассматривать при x > 0 (при x < 0 будет симметричное решение), то, так как окружность пересекает прямую y = h в двух точках, то конец кривой – правая из двух возможных точек пересечения:

x1 = c + c 2 h 2. Константу c, а вместе с ней и, находим из условия 1 + y 2 = y (из дифференциального уравнения экстремали). Так как y > 0 при h > 0 (при h < 0 имеется симметричное решение), то т.е. — отрицательный корень этого трансцендентного уравнения. Величина определяет положение центра искомой окружности и ее радиус.

5.4. Вариационные задачи на условный экстремум Изопериметрическая задача имеет следующую постановку: найти экстремум функционала I [ y1 (),..., yn ()] в классе гладких на [ x0, x1 ] кривых, удовлетворяющих заданным граничным условиям, при условии, что другой функционал I 0 [ y1 (),..., yn ()] принимает заданное постоянное значение:

Аналогично задаче Лагранжа изопериметрическая задача сводится к задаче на безусловный экстремум вспомогательного функционала I1 = x 1 ( F + G ) dx, где = const. При этом предполагается, что y1 ( x),..., y n ( x) не является экстремалью функционала I 0.

Задача Лагранжа ставится следующим образом: требуется найти экстремум функционала I [ y1 ()] = x 1 F ( x, y1,..., yn, y1,..., yn )dx в классе гладких на [ x0, x1 ] кривых, удовлетворяющих заданным граничным условиям и условиям связи G k ( x, y1,..., y n, y1,..., y n ) = 0, k = 1, m, m < n.

Если Gk не зависят от y1,..., y n, то связи называются голономными. В этом случае условия связи означают, что допустимые кривые лежат на поверхностях Gk = 0.

Эта задача сводится к задаче на безусловный экстремум вспомогательного функционала: если кривая y1 ( x),..., y n ( x) доставляет экстремум функционалу I при условиях Gk = 0, то существуют множители Лагранжа k (x) такие, что на этой кривой достигается безусловный экстремум функционала:

Найти геодезические линии круглого цилиндра r = R. Геодезические линии — это линии наименьшей длины, соединяющие две заданные точки поверхности. Задача сводится к нахождению глобального минимума функционала I1 = x 1 1 + y2 + z 2 dx при условии, что кривые, проходящие через точки M 0 ( x0, y0, z 0 ) и M 1 ( x1, y1, z1 ), лежат на поверхности цилиндра.

Это — задача Лагранжа с голономными связями. Задачу удобнее решать в цилиндрических координатах r,, z. Тогда функционал имеет вид:

Уравнение связи: r = R (const ).

Составляем вспомогательный функционал:

и решаем для него задачу о нахождении глобального минимума.

Необходимое условие экстремума:

Кроме того, есть уравнение связи r = R.

Экстремалями задачи являются винтовые линии. Через точки M 0 и M (при z 0 z1 ) можно провести бесчисленное множество винтовых линий, отличающихся друг от друга числом оборотов вокруг цилиндра. В этой задаче наглядно видно, что выполнение уравнения Эйлера — необходимое условие локального экстремума. Можно показать, что на каждой из этих винтовых линий достигается локальный минимум функционала; глобальный минимум реализуется на той винтовой линии, для которой 0 < 2. При 0 = это будет отрезок прямой, соединяющей точки M 0 и M 1.

Найти минимум функционала I [ y ()] = 0 y2 dx в классе гладких кривых, удовлетворяющих условиям y (0) = y (1) = 0, 0 y 2 dx = 1.

Эта изопериметрическая задача сводится к нахождению безусловного экстремума вспомогательного функционала I [ y ()] = 0 ( y2 + y 2 ) dx в классе гладких кривых, удовлетворяющих условию y (0) = y (1) = 0.

краевую задачу. При 0 она имеет только тривиальные решения, не проверять только при одном из значений t, например, при t = t1.

Если конец x 0 ( x1 ) не фиксирован, а принадлежит некоторому многообразию M, то на этом конце выполняются условия трансверсальности:

вектор * (t0 ) ( * (t1 )) ортогонален всем касательным векторам многообразия M в точке x 0 ( x1 ).

Важным классом задач являются задачи о быстрейшем попадании в начало координат по траекториям линейной системы x = Ax + Bu, где область V = M является m -мерным выпуклым многогранником, содержащим точку ноль (0 не должен быть вершиной M ), удовлетворяющим условию общности положения: если w-вектор, параллельный любому ребру многогранника M, то векторы Bw, ABw,..., A n 1Bw линейно независимы. В таких задачах принцип максимума Понтрягина для функции Гамильтона H = T ( Ax + Bu ) является не только необходимым, но и достаточным условием оптимальности, причем требование равенства нулю функции Гамильтона выполнено автоматически.

Пример 1. О наискорейшем выведении судна на курс В качестве первого примера рассмотрим задачу о быстрейшем приведении в начало координат объекта, движение которого описывается уравнением Эту задачу можно интерпретировать как задачу о быстрейшем выведении судна на курс.

Изучим случай h < 0. Вначале рассмотрим, что будет при крайних значениях управления, при u = ±1. На рис. 6.1 сплошными линиями начерчены траектории системы при u = +1, пунктиром – при u = 1. Если взять начальное состояние, расположенное вне полосы y = x < 1 h, то для него не существует допустимой траектории, ведущей в начало координат, так как никакая допустимая траектория, начинающаяся вне этой полосы, не может попасть в эту полосу при возрастании t. Это происходит потому, что никакая траектория не может пересечь траектории системы с u = +1 снизу вверх.

Верхняя граница этой полосы является траекторией системы с u = 1, а нижняя – траекторией системы с u = +1. Из точек, расположенных внутри этой полосы, можно придти в точку 0 (хотя бы по траекториям систем с u = ±1 ).

Итак, задачу об отыскании оптимального управления можно решать лишь для точек множества управляемости – полосы y < 1 h.

Рис. 6.1. Фазовые траектории системы при двух постоянных значениях управления u = ± Нетрудно показать, что в этой задаче выполняется условие общности положения. Поэтому принцип максимума Понтрягина задает необходимые и достаточные условия оптимальности.

решения сопряженной системы 1 = H x = 0, 2 = H y = 1 + h 2.

max{H : u 1} достигается при граничных значениях управления, причем знак u опт зависит от 2 : u опт = sign 2 (t ). Решая сопряженную систему, получим: 1 = c1, 2 = c1 + h 2, 2 = c2 e ht c1 h, откуда видно, что 2 (t ) может менять знак не более 1 раза. Следовательно, оптимальное управление может менять знак не более 1 раза. Мы пока знаем только качественную структуру оптимального управления и не знаем, при каких состояниях происходит перекладывание руля из одного крайнего положения в другое. Выясним этот вопрос. Целью управления является точка (0,0). В нее ведут лишь 2 траектории, удовлетворяющие принципу максимума: +1 и 1, отвечающие граничным значениям управления u. Последний участок движения должен лежать на одной из них, т.е. кривая Г, состоящая из +1 и 1, является линией переключения. Решение задачи синтеза оптимальных управлений (нахождение оптимального управления как функции состояния системы) существует лишь при x < 1 h и имеет следующий вид:

Схема переключений показана на рис. 6.2.

Рис. 6.2. Вид линии переключения и оптимальных траекторий примера 1 для области управляемости (серым тоном отмечена область неуправляемости) Пример 2.О скорейшем выведении на интервал В качестве второго примера рассмотрим задачу о быстрейшем приведении объекта, описываемого уравнением или, что то же самое, системой интерпретировать как задачу о быстрейшей остановке колебаний маятника.

Составим функцию Гамильтона H = 1 y + 2 ( x + u ), где функции 1, 2 являются решением сопряженной системы Очевидно, что максимальное значение функции Гамильтона достигается при значениях управления u 0 (t ) = sign 2 (t ). Решая сопряженную систему, получим Из условий трансверсальности следует, что если траектория приходит в момент времени T на интервал ( 1; + 1) оси OX, то вектор (T ) = ( 1 (T ), 2 (T )) должен принять одно из значений (0; 1), (0; + 1). В первом случае мы имеем систему решив которую, получим: с1 = cos T, c2 = sin T.

Таким образом, означает, что на последнем интервале времени (T 2 ; T ) значение управления равно 1, а предыдущие интервалы времени с постоянным значением управления + 1 (или 1), имеют длительность (кроме, быть может, первого интервала).

Во втором случае мы имеем систему решив которую, получим: c1 = cos T, c2 = sin T.

означает, что на последнем интервале времени (T 2 ; T ) значение управления равно +1, а предыдущие интервалы времени с постоянным значением управления 1 (или + 1), имеют длительность (кроме, быть может, первого интервала).

Далее заметим, что траекториями системы (6.2) при u = 1 являются окружности с центром в точке (1; 0), а при u = +1 - окружности с центром в точке (+1; 0). Таким образом, сверху на интервал Q могут придти только траектории системы (2) при управлении u = 1, а снизу на интервал Q могут придти только траектории системы (2) при управлении u = +1. Поскольку длительности времени соответствующей траектории системы (2), линией переключения в момент времени T 2 с управления u = +1 на u = 1 будет отрезок Q1 = {( x, y ) : x = 1,0 y 2}, а линией переключения с u = 1 на u = + будет отрезок Q+1 = {( x, y ) : x = 1,2 y 0} (рис. 6.3).

Рис. 6.3. Вид оптимальных траекторий и линии переключения в примере Отдельно решается вопрос о длительности интервала времени с постоянным значением управления u = 1 для траектории (1), приходящей в крайнюю точку (1; 0) множества Q, поскольку в этой точке любая прямая является «касательным» к множеству Q вектором. Таким образом, длительность этого интервала для траектории (1) в соответствии с принципом максимума и общим решением для 2 (t ) может теоретически быть любой от нуля до значения. С другой стороны, легко видеть, что длительность этого интервала не может быть меньше, чем 2, так как для того, чтобы пересечь дугу траектории (1), соединяющую точки (1; 2) и (1; 0), траектория системы (6.2) при Q1 = {( x, y ) : x = 1,0 y 2}, уже являющийся линией переключения с управления u = +1 на управление u = 1. Значит, заключительным участком оптимальной траектории, приходящей в точку (1; 0), может быть любая дуга траектории (1), соответствующая интервалу времени (t1, T ), где каждому значению t1 [T, T 2] соответствует точка дуги AB траектории (1), соединяющей точки A(3; 0) и B (1; 2). Рассмотрим траектории системы (6.2) при управлении u = +1 на отрезке времени [T 3 2, T 2], приходящие в момент времени T 2 в одну из точек линии переключения Q1 = {( x, y ) : x = 1,0 y 2}, а также на отрезке времени [t1,t1 ], приходящие в момент времени t1 в одну из точек дуги AB. Начала этих траекторий, соответствующие моментам времени T 3 2 и t1, образуют линию переключения с управления u = 1 на управление u = +1, составленную из отрезка Q+3 = {( x, y ) : x = 3,2 y 0} и дуги CD окружности с центром в точке (3; 0) радиуса 2, соединяющей точки C (3; 2) и D (5; 0). Заметим, что отрезок Q+3 = {( x, y ) : x = 3,2 y 0} и дуга CD получаются из отрезка Q1 = {( x, y ) : x = 1,0 y 2} и дуги AB поворотом на угол относительно точки (1; 0).

Совершенно аналогичным образом решается вопрос о структуре оптимальных траекторий, приходящих на множество заключительному интервалу времени (T 2, T ) соответствует дуга траектории системы (2) при управлении u = +1 (четверть дуги окружности с центром в точке (1; 0) ). Отрезок Q+1 = {( x, y ) : x = +1,2 y 0} будет линией переключения с управления u = 1 на управление u = +1. При этом заключительный участок траектории (1), входящей в точку (1; 0), может начинаться с любой точки ее дуги EF, соединяющей точки E (1; 2) и F (3; 0), и являющейся также частью линии переключения с управления u = 1 на управление u = +1. Начальные точки дуг траекторий системы (2) при управлении u = 1, соответствующие интервалу времени и заканчивающиеся в точках отрезка Q+1 = {( x, y ) : x = +1,2 y 0} и дуги EF, образуют линию переключения с управления u = +1 на управление u = 1.

Она будет составлена с помощью поворота на угол вокруг точки (1; 0) из отрезка Q3 = {( x, y ) : x = 3,0 y 2} и дуги MN окружности с центром в точке (3; 0) и радиусом 2, соединяющей точки M (5; 0) и N (3; 2).

Продолжая указанным выше образом процесс построения линии переключения, мы в итоге получим следующий результат. Линией переключения, с управления u = 1 на управление u = +1 будет ломаная Q2 k 1 = {( x, y ) : x = 2k 1,2 y 0} и дуг окружностей с центрами в точках ( 2k 1; 0) и радиусом 2, соединяющих точки ( 2k 1; 2) и ( 2k + 1; 0), k = 1, 2, K Линией переключения с управления u = +1 на управление u = будет ломаная непрерывная кривая, составленная из отрезков Q 2 k +1 = {( x, y ) : x = 2k + 1,0 y 2} и дуг окружностей с центрами в точках ( 2k + 1; 0) и радиусом 2, соединяющих точки (2k + 1; 2) и Дополнительный теоретический материал и задачи можно найти в литературе [21, 22], а также [5, 14].

6.2. Контрольные задания 1. Найти область управляемости и осуществить синтез оптимальных управлений в задаче о быстрейшем попадании в начало координат для линейной системы && + 2hx + kx = u (t ), где 1 u (t ) +1, в следующих случаях:

Здесь 1 и 2 — корни характеристического уравнения 2 + 2h + k = 0.

2. Оптимальное управление гармоническим осциллятором с помощью двух независимых управлений.

Рассмотрим вращающийся космический летательный аппарат с единственной осью симметрии (рис. 6.4).

Пусть x1 (t ), x2 (t ), x3 (t ) — угловые скорости (в рад/сек) относительно трех основных осей тела; I1, I 2, I 3 — моменты инерции относительно тех же осей; D1, D2, D3 — реактивные двигатели, которые жестко прикреплены к аппарату и могут развивать тягу в обоих направлениях; сила тяги этих двигателей ограничена по величине.

Требуется найти оптимальный закон управления тягой двигателей D1 и D2 так, чтобы при постоянной скорости x3 (t ) скорости x1 (t ) и x2 (t ) сделать равными нулю за наименьшее время. Осуществить синтез оптимальных управлений.

Рис.6.4. – Модель вращающегося космического летательного аппарата с единственной осью 3. Оптимальное управление демпфированным гармоническим осциллятором с помощью двух независимых управлений.

Найти оптимальный по быстродействию закон управления в начало координат для системы u1 (t ) 1, u2 (t ) 1. Осуществить синтез оптимальных управлений.

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

5. Оптимальное управление объектом третьего порядка. Для системы где u (t ) 1, найти управление, переводящее систему в начало координат за наименьшее время. Решить задачу синтеза.

6. Решить задачу о быстрейшем попадании по траекториям системы && = u (t ), u (t ) 1, на: (a) отрезок [1,+1] оси OX ; (b) на отрезок [1,+1] оси 7. Найти управление, переводящее систему && = u (t ),u (t ) 1 из начального состояния на квадратную окрестность начала координат x a, x a ? за наименьшее время. Решить задачу синтеза.

8. Решить задачу, аналогичную задаче 7, если уравнение управляемой системы имеет вид && + x = u (t ).

9. Решить задачу, аналогичную задаче 7, для круглой окрестности начала координат x1 + x2 R в двух случаях: (a) R > 1; (b) R < 1.

10. Рассмотрим одномерное управляемое движение (например, движение поезда) под действием ограниченной по величине силы тяги u (t ). Считая, что затраты энергии за время T пропорциональны 0 u dt, найти оптимальное управление, переводящее систему из начального состояния в начало координат таким образом, чтобы линейная комбинация времени перехода и энергетических затрат была бы минимальной. При решении задачи неровностью пути и сопротивлением пренебречь.

пропорциональны 0 (t ) dt, с учетом сопротивления воздуха. Найти особый режим.

пропорциональны особый режим.

13. Решить задачу об оптимальном управлении одномерной системой x = ax + u (t ) в начало координат, минимизирующем квадратичный функционал 0 u 2 (t )dt.

14. Задача об оптимальном управлении тягой ракеты. Пусть газы из сопла ракеты вылетают с постоянной скоростью C. Сопло подвешено на оси, и направление выброса газов можно регулировать. В предположениях, что движение ракеты является плоским, происходит в безвоздушном пространстве и вектор ускорения свободного падения g является постоянным, найти оптимальное управление тягой ракеты максимизирующее: а) дальность полета ракеты; б) высоту подъема ракеты.

Здесь (t ) – угол между горизонтом и прямой, вдоль которой происходит выброс газов в момент времени t.

15. Задача о мягкой посадке при минимальном расходе горючего.

Посадить космический корабль на планету с нулевой скоростью, используя минимальное количество горючего. Управлением является сила тяги двигателя u (t ), 0 u (t ) A. Гравитационное ускорение вблизи планеты считаем постоянным.

16. Решить задачу 14 с учетом сопротивления. Найти особый режим управления.

Литература 1. Неймарк Ю.И. Динамические системы и управляемые процессы. – М.:

Наука, 1978.

2. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. – М.: Наука, 1965.

3. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. – М.: Высшая школа, 1979.

4. Арис Р. Дискретное динамическое программирование. – М.: Мир, 1969.

5. Сборник задач по математике для втузов. Часть 4. Методы оптимизации.

Уравнения в частных производных. Интегральные уравнения. – М.:Наука, 1990.

6. Чжун К. Однородные цепи Маркова. – М.: «Мир», 1964.

7. Ховард Р.А. Динамическое программирование и марковские процессы. – М.: Советское радио, 1964.

8. Карманов В.Г. Математическое программирование. - М.: Физматлит, 2000.

9. Измайлов А.Ф., Солодов М.В. Численные методы оптимизации. – М.:

Физматлит, 2003.

10. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы.

– М., Мир, 1982.

11. Галлеев Э.М. Оптимизация: теория, примеры, задачи. Учебное пособие. – М.: Элиториал УРСС, 2000.

12. Методические указания (сборник задач) для самостоятельной работы студентов. / Сост. Коротченко А.Г. – Н. Новгород: ННГУ, 1991.

13. Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремальная оптимизация. – Н.Новгород: ННГУ, 2007.

14. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. – М.:Наука, 1984.

15. Васильев О.В. Методы оптимизации в задачах и упражнениях. – М.:

Физматлит, 1999.

16. Оптимизация функций и динамических процессов. / Сост. Городецкий С.Ю., Павлюченок З.Г., Савельев В.П. – Н.Новгород: ННГУ, 2001.

17. Васильев Ф.П. Численные методы решения экстремальных задач. – М.:

Наука, 1988.

18. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. -– М.: Мир, 1985.

19. Стронгин Р.Г. Численные методы в многоэкстремальных задачах (информационно-статистические алгоритмы). – М.: Наука, 1978.

20. Краснов М.Л., Макаренко Г.И., Киселев А.И. Вариационное исчисление. – М.:Наука, 1973.

21. Ванько В.И., Ермошина О.В., Кувыркин Г.Н. Вариационное исчисление и оптимальное управление. – М.: МГТУ им. Баумана, 1999.

22. Болтянский В.Г. Математические методы оптимального управления. – М.:

Наука, 1969.

МЕТОДЫ ОПТИМИЗАЦИИ

В ПРИМЕРАХ И ЗАДАЧАХ

Светлана Анатольевна Григорьева и др.

Учебно-методическое пособие Государственное образовательное учреждение высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского»

603950, Нижний Новгород, пр. Гагарина, Бумага офсетная. Печать офсетная. Гарнитура Таймс.

Отпечатано в типографии Нижегородского госуниверситета 603600, г. Нижний Новгород, ул. Большая Покровская,