Zhadan_lektsii_6_semestr

В.Г.Жадан

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

(учебное пособие)

ЧастьIII

1.ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ

где как допустимое множество X,так и множество оптимальных решений X X предполагаются непустыми.Найти решение задачи(1)аналитически,применяя условия оптимальности или используя геометрический подход,удается лишь в очень немногих простых случаях.Как правило,это возможно только тогда,когда целевая функция и допустимое множество выпуклы.Но в подавляющем большинстве случаев,особенно в практических приложениях,где зачастую размерность вектора x большая и функция f(x) имеет сложный вид,решение задачи аналитически становится невозможным.Поэтому приходится обращаться к численным методам, т.е.к специальным процедурам,которые находили бы решение задачи(быть может приближенное).Численные методы строятся с использованием специфики задачи,а именно,учитывают к какому классу относится целевая функция f(x) и каким об - разом задается допустимое множество X.Выделяют численные методы отыскания локальных и глобальных решений.Их так и называют методы локальной и глобаль-

ной оптимизации.

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

1

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

Итерационный численный метод генерирует последовательность точек x0, x1, x2,

. . .,которая,вообще говоря,является бесконечной.При этом начальная точка x0 задается,а последующие точки вычисляются по предыдущим по определенным правилам.Точка xk называется k-м приближением к решению , а вся совокупность точек

{xk} траекторией.

Переход от xk к точке xk+1 называется шагом или итерацией метода.Способ этого перехода и составляет суть метода,поэтому часто метод записывается виде итерационной схемы:

Приведенная схема(2)является одношаговой, так как в ней для определения после - дующего приближения xk+1 используется только предыдущее приближение xk.

Иногда рассматривают многошаговые схемы,в которых при рассчете xk+1 кроме xk используются и другие приближения xk−1, xk−2 и т.д.Например,в двухшаговых схемах используются xk и xk−1.Тогда надо перед началом вычислений помимо x0 задать и x1, а итерационная схема (2) заменяется на xk+1 = Φk(xk, xk−1).

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

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

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

Определение1. Метод называется сходящимся к решению x X (из точки x0),если

lim xk = x .

k→∞

2

Иногда метод генерирует последовательность {xk}, которая не является сходя - щейся,но содержит сходящиеся подпоследовательности.Определение1в этом случае переформулируется следующим образом.

Определение2. Метод называется сходящимся к множеству решений X (из точки x0),если

lim ρ(xk, X ) = 0,

k→∞

где ρ(x, X) расстояние от точки x до множества X.

В том случае , когда множествоX есть компакт,из сходимости метода к X следует существование сходящихся подпоследовательностей у последовательности {xk}.

Определение3. Последовательность {xk} называется минимизирующей,если

В случае,когда выполняется(3),говорят,что метод сходится по функционалу. Может оказаться так,что метод сходится по функционалу,но сходимости по x нет. В качестве примера приведем следующую задачу

в которой f = 0, X = {0}.Последовательность {xk} с xk = k + 1, k ≥ 0 является минимизирующей для этой задачи,однако она не сходится к решению задачи точке

x = 0.

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

Пусть последовательность {xk} сходится к точке x , являющейся решением зада -

чи(1).

Определение4. Метод сходится к x с линейной скоростью , если можно ука - зать такую константу 0 < C < 1 и K0 ≥ 0, что

xk+1 − x ≤ C xk − x

для любых k ≥ K0.

3

Определение5. Метод сходится к x со сверхлинейной скоростью,если

xk+1 − x ≤ Ck xk − x ,

где Ck > 0 и Ck → 0 при k → ∞.

Определение6. Метод сходится к x с квадратичной скоростью , если можно указать такую константу C > 0 и K0 ≥ 0, что

xk+1 − x ≤ C xk − x 2,

для любых k ≥ K0.

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

Определение7. Пусть можно указать такие C0 > 0, 0 < q < 1 и K0 ≥ 0, что

xk − x ≤ C0qk

при k ≥ K0. Тогда говорят , что метод сходится со скоростью геометрической прогрессии,где q знаменатель прогрессии .

Определения,аналогичные(4) Ð (6),могут быть даны и касательно сходимости по функционалу.В них только xk заменяется на f(xk), а x на f .Например,линейная скорость сходимости по функционалу означает,что

|f(xk+1) − f | ≤ C|f(xk) − f |

для некоторого 0 < C < 1 и при всех k ≥ K0.

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

Пусть ε1, ε2 и ε3 некоторые параметры требуемой точности.Тогда процесс прерывается,если выполняется какое-нибудь из неравенств:

1)xk+1 − xk ≤ ε1;

2)|f(xk+1) − f(xk)| ≤ ε2;

Если функция f(x) дифференцируемая,то можно проверять следующее условие 3) fx(xk) ≤ ε3,указывающее на то,с какой точностью выполняется необходимое

условие оптимальности в задаче.

4

Правила 1) и 2) основаны на использовании абсолютных изменений соответственно аргумента и значений целевой функции.Гораздо более обосновано использование их относительных изменений:

4)xk+1 − xk ≤ ε1 (1 + xk+1 );

5)|f(xk+1) − f(xk) ≤ ε2 (1 + |f(xk+1|).

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

1.2.Методы одномерной минимизации

Одной из наиболее простой,но часто встречающейся в приложениях,является задача минимизации функции одного аргумента на отрезке:

где x R, X = [a, b].При этом считаем,что a < b и функция f(x) непрерывна на

[a, b].

Алгоритмы решения задачи(4)существенным образом зависят от свойств функции f(x).Мы здесь в этом разделе ограничимся рассмотрением функций,которые получили название унимодальных.Приведем это определение в общем случае для произвольных функций f(x),не предполагая их непрерывность.

Определение8. Функция f(x) называется унимодальной на [a, b], если суще -

ствует такая точка x [a, b], что f(x1) > f(x2) для любых a ≤ x1 < x2 < x , и f(x1) < f(x2) для любых x < x1 < x2 ≤ b 1.

Если на [a, b] унимодальная функция f(x) достигает своего минимума,то она достигает его именно в точке x .Для непрерывных функций свойство унимодальности означает обязательное наличие у функции f(x) единственного локального минимума на [a, b],который одновременно является и глобальным минимумом.Можно показать,что для непрерывных функций одного аргумента свойство унимодальности на отрезке [a, b] равносильно ее строгой квазивыпуклости на [a, b].

Утверждение1. Пусть f(x) унимодальная на отрезке [a, b] функция,достигающая своего минимума в точке x [a, b]. Пусть , кроме того , имеются две точки x1 [a, b] и x2 [a, b] такие,что x1 < x2. Тогда :

1. если f(x1) ≤ f(x2), то x [a, x2];

1Известны также другие определения унимодальных функций и их обобщений,см.,например, [].Приведенное здесь определение взято из[].

5

2.если f(x1) ≥ f(x2), то x [x1, b].

Доказательство. Докажем только первое утверждение.От противного,предположим,что f(x1) ≤ f(x2), но x > x2. Тогда x1 < x2 < x и в силу унимодальности функции f(x) должно выполняться неравенство: f(x1) > f(x2).Мы пришли к противоречию.

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

Делается это таким образом,что каждый из отрезков [ak, bk] содержит точку x , причем в качестве начального отрезка [a0, b0],как правило,берется сам исходный отрезок [a, b].Длины ∆k = bk − ak отрезков [ak, bk] образуют монотонно уменьшающуюся последовательности чисел

∆0 > ∆1 > ∆2 > á á á > ∆k > á á á ,

стремящихся к нулю.

Если построен отрезок [ak, bk], то в качестве приближенного решения задачи(4) берется произвольная точка xk из отрезка [ak, bk].Обычно в качестве такой точки целесообразно брать середину отрезка точку

2

Тогда для оценки точности такого приближенного решения(4)получаем

|xk − x | ≤ ∆2k .

В общем случае,при выборе произвольной точки xk из отрезка [ak, bk], имеем только

|xk − x | ≤ ∆k.

Для прерывания процесса построения отрезков(5)задаются точностью решения задачи (4) параметром ε.Под точностью в таких методах понимают оценку расстояния между точным решением x задачи(4)и найденным приближенным решением xk, т . е . величину|xk − x |.Процесс прерывают,когда выполняется неравенство |xk − x | ≤ ε.Если в качестве точки xk согласно(8)берется середина отрезка [ak, bk], то для этого достаточно совершить N итераций,где N наименьшее из целых неотрицательных чисел,для которого выполняется условие ∆N ≤ 2ε.

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

6

отрезков [ak, bk] или,говоря более точно,конкретными способами перехода от отрезка [ak, bk] к следующему отрезку [ak+1, bk+1].При этом все эти методы существенным образом используют то обстоятельство,что минимизируемая функция f (x) является унимодальной функцией на [a, b].

Метод дихотомии(метод деления отрезка пополам) является одним из наиболее простых и интуитивно понятных методов решения задачи(4).Идея метода заключается в поиске на каждом шаге такого отрезка [ak+1, bk+1] внутри отрезка [ak, bk],который имел бы вдвое меньшую длину по сравнению с длиной отрезка

[ak, bk].

Начальная итерация.Полагаем a0 = a, b0 = b, c0 = (a0 + b0)/2 и вычисляем f (c0).Полагаем k = 0.

Общая k-я итерация.

Шаг 1. Берем точку yk = (ak + ck)/2 и вычисляем f (yk). Возможны два случая :

а). Если f (yk) ≤ f (ck), то полагаем

ak+1 = ak, bk+1 = ck, ck+1 = yk

В качестве очередного приближения к решению задачи точке x берут любую точку из отрезка [ak+1, bk+1], в частности , точкуck+1, определяемую согласно (7).

7

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

Пусть позволяется сделать самое большое N вычислений значений функции f(x), причем для простоты считаем,что N нечетное число . Тогда методом дихотомии

Как видим,погрешность уменьшает не медленнее,чем со скоростью геометрической прогрессии со знаменателем q ≈ 0.707.

Применяя формулу(8),можно оценить также количество итераций K, которое необходимо проделать методом,чтобы добиться заданной точности ε.Имеем

где символом a обозначено наименьшее целое,аппроксимирующее число a сверху. Существуют также другие варианты метода дихотомии,например,разбивают текущий отрезок [ak, bk] на два равных отрезка и в качестве следующего отрезка

[ak+1, bk+1] берут тот отрезок,который содержит решение задачи точку x .

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

Пусть имеется отрезок [a, b].Предположим,что точка,которая делит отрезок в пропорции золотого сечения ( обозначим ееy),находится ближе к левому концу отрезка точке a.Тогда для нее выполняется соотношение

Если,напротив,эта точка находится ближе к правому концу отрезка,то для этой

8

точки(обозначим ее z) вместо (10) имеет место соотношение

5 − 1 (b − a) a + 0.618 (b − a) . 2

Точка y(a, b) носит название меньшей золотой точки отрезка [a, b], точка z(a, b)

большей золотой точки отрезка [a, b].Если ввести величину

√

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

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

Утверждение2. Пусть y и z меньшая и большая золотые точки отрезка

2.y большая золотая точка отрезка [a, z], а z меньшая золотая точка отрезка [y, b].

Опишем теперь сам алгоритм метода золотого сечения.

Начальная итерация.Полагаем a1 = a, b1 = b, y1 = y(a, b), z1 = z(a, b) и

вычисляем f (y1).Полагаем k = 1.

Общая k-я итерация.

Вычисляем то из значений f (yk) или f (zk),которое еще не вычислено.Если f (yk) ≤ f (zk), то полагаем

9

После этого увеличиваем номер итерации на единицу k := k + 1 и переходим на начало итерации.

Согласно утверждению2на каждой k-й итерации

yk+1 = y(ak+1, bk+1), zk+1 = z(ak+1, bk+1),

а согласно утверждению 1

x [ak+1, bk+1] .

Поэтому в качестве приближения xk+1 к решению задачи можно брать любую точку из отрезка [ak+1, bk+1]. Отметим также , что в методе золотого сечения на каждой итерации требуется вычислять значение целевой функции f(x) лишь в одной точке.

Если позволяется вычислить значение функции f(x) лишь в N точках,то можно сделать K = N − 1 шагов методом золотого сечения и получить следующую оценку для близости точки xN к x :

|xN − x | ≤ bN − aN = 1 N−1 (b − a) ≈ 0.618N−1 (b − a) .

τ

Данная оценка лучше,чем получаемая в методе дихотомии.Для получения точности ε, как видно из (12), следует провести количество итераций

ln b−a

K ≥ ln τε + 1,

где символом a обозначена целая часть числа a.

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

При этом первые два числа полагаются равными: F0 = F1 = 1. Тогда для последую - щих чисел Фибоначчи согласно(13)получаем

F2 = 2, F3 = 3, F4 = 5, F5 = 8, . . . .

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

10