<<
>>

§ 4. ПРИНЦИПЫ ПОСТРОЕНИЯ ЧИСЛЕННЫХ МЕТОДОВ ПОИСКА БЕЗУСЛОВНОГО ЭКСТРЕМУМА

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

1. Целевая функция /(х) может не иметь непрерывных производных до

второго порядка включительно.

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

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

Подавляющее большинство численных методов оптимизации относится к классу итерационных, т.е. порождающих последовательность точек в соответст­вии с предписанным набором правил, включающим критерий окончания. При заданной начальной точке х° методы генерируют последовательность х^х^х2,....Преобразование точки хк в xk+l представляет собой итерацию.

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

/(*’) = min f(x). (4.1)

' ' xeR?

Численное решение задачи (4.1), как правило, связано с построением по­следовательности |х*| точек, обладающих свойством

/(х*+1)lt;/(**)gt; *=0,1............................................. (4.2)

Общее правило построения последовательности |x*j имеет вид

хк+{ =х*+/*lt;/*, * = 0,1,..., (4.3)

где точка х° - начальная точка поиска; dk - приемлемое направление перехода

из точки хк в точку х*+1, обеспечивающее выполнение условия (4.2) и называе­мое направлением спуска\ tk - величина шага.

Начальная точка поиска х° задается, исходя из физического содержания решаемой задачи и наличия априорной информации о положении точек экстре­мума.

Приемлемое направление спуска dk должно удовлетворять условию

(?/(**),lt;/*)lt; О, к = 0,1,...

, (4.4)

обеспечивающему убывание функции /(х). Примером приемлемого направления

является направление вектора антиградиента: dk = -V/(x*).

Величина шага tkgt; 0 выбирается либо из условия (4.2), либо из условия минимума функции вдоль направления спуска:

/(х*+lt;*lt;/*)-gt; 1ШП. (4.5)

Выбор шага tk из условия (4.5) делает спуск в направлении dk наискорейшим.

Определение 4.1. Последовательность {x*J называется минимизирующей,

если lim /(х*] = /*, т.е. последовательность сходится к нижней грани

к^юо V /

f'= inf f(x). xeRn

Определение 4.2. Последовательность jx*j называется сходящейся к точке минимума х*, если || хк -х*|| -#9658; 0 при к со.

Сходимость последовательности jx*J при выборе приемлемого направле­ния dk и величины шага tk из условия (4.2) или (4.5) зависит от характера функции f(x) и от выбора начальной точки х°.

Пример 4.1. Классифицировать согласно определениям 4.1 и 4.2:

( \ х2

а) последовательность хЧ = к для функции /(х) =--------------

[ } 1 + х4

б) последовательность {**}, заданную правилом хк+{ = хк -“V/(x*) для

функции /(х) = х,2 + х\.

? Воспользуемся определениями 4.1 и 4.2:

X2 (

а)--------------------------------------- для функции /(х) = последовательность \хк\ = к, к - 1,2,... явля-

1+ х4 1 ]

ется минимизирующей, так как lim /(amp;) = 0 = /*, однако она не сходится

к —#9658; со

к точке минимума х* = 0;

б) для функции /(х) = х2 + х| последовательность хк+х = хк -“V/(x*) яв-

Г

2

\ Н)-1 2xf'
,4) 2 12*2* J

ляется не только минимизирующей, но и сходящейся к точке х* =(0,0)4

/(**) = /' = О, так как V/(x*) = (2xf,2xf) и Х|л+,

\х2

В зависимости от наивысшего порядка частных производных функции /(х), используемых для формирования ^ и численные методы решения за­дачи безусловной минимизации (4.1) принято делить на три группы.

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

2. Методы первого порядка, использующие информацию о первых произ­водных функции /(х).

3. Методы второго порядка, требующие для своей реализации знания вто­рых производных функции /(х).

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

Рассмотрим последовательность , сходящуюся к х*. Предположим, что

все ее элементы различны и ни одна из точек хк не совпадает с х*.

Наиболее эффективный способ оценивания скорости сходимости состоит в сопоставлении расстояния между хк+{ и х* и расстояния между хк их*.

Определение 4.3. Последовательность (хМ называется сходящейся с поряд­

ком г , если г - максимальное число, для которого

Поскольку величина г определяется предельными свойствами |х*|, она на­зывается асимптотической скоростью сходимости.

Определение 4.4. Если последовательность сходящаяся с порядком г ,

то число

с = Пт к-юо

называется асимптотическим параметром ошибки.

Определение 4.5. Если г = 1, с lt; 1, то сходимость линейная\ если г = 2, то сходимость квадратичная; если г gt; 1 или г - 1, с = 0, то сходимость сверхлинейная.

Линейная сходимость является синонимом сходимости со скоростью гео­метрической прогрессии.

Пример 4.2. Определить порядок сходимости последовательности

хк = д(2 ), к = 0,1,2,... , где 0lt; а lt; 1.

? Каждый следующий член этой последовательности равен квадрату пре­дыдущего, а ее предел равен нулю. По определению 4.4

поэтому г = 2 и сходимость квадратичная. Квадратичная сходимость, грубо гово­ря, означает, что с каждым шагом число правильных цифр у хк удваивается. Первые четырнадцать членов последовательности с параметром а = 0,99 приве­дены во втором столбце табл. 4.1. Заметим, что удвоение числа правильных цифр начинается не сразу, а, точнее, при к gt; 7. #9632;

Таблица 4.1 bgcolor=white>
к хк / *
0 0,99
1 0,9801 1,4832397 Ю
2 0,96059601 1Д178833 0,25
3 0,92274469 1Д035775 0,03703704
4 0,85145777 1,0505130 0,00390625
5 0,72498033 1,0249453 0,00032
6 0,52559649 1,0123958 0,00002143
7 0,27625167 1,0061788 0,00000121
8 0,07631498 1,0030847 0,0000000596
9 0,00582398 1,0015411 0,0000000026
10 0,00003392 1,0007703
11 ОД 1515 х 10quot;8 1,0003851 -
12 ОД 3236 х 10'17 1,0001925 -
13 ОД 7519 X 10'36 1,0000963 -
14 0,30692 х 10quot;72 1,0000481 -

Пример 4.3.

Определить порядок сходимости последовательностей:

(2“М

а) ук = а' ', к = 0,1,... , где а gt; 0;

б) ук =1 + 2Л А: = 0,1,... .

? Воспользуемся определениями 4.3 - 4.5:

а) каждый следующий член этой последовательности является квадратным корнем предыдущего. Ее предел при любом а gt; 0 равен 1, причем

и1п ,----------------------------------------

к-gt;00 к-*со д2-lt;*+|) + | 2

Поэтому г = 1 и сходимость линейная. Первые четырнадцать членов этой после­довательности при а = 2,2 приведены в третьем столбце табл. 4.1.

Замечания 4.1.

r у*+1-1 1

lim ---------------- =-- -.

к —gt; oo y* _ j 2

Поэтому r = 1 и сходимость линейная. #9632;

? Предел |г*} равен нулю и

Так как г = 1 и с = 0, то сходимость сверхлинейная. Первые девять членов этой последовательности приведены в четвертом столбце табл. 4.1. #9632;

1. На практике линейная сходимость может быть медленной, в то время как квадратичная или сверхлинейная сходимость является довольно быстрой. Ре­альное поведение итерационного процесса зависит от константы с , например, линейная сходимость с константой с = 0,001, вероятно, является вполне удовле­творительной, а с константой с = 0,9 - нет.

2. Одним из критериев сходимости, часто используемым при сравнении алгоритмов, является их способность эффективно минимизировать квадратич­ные функции. Это объясняется тем, что вблизи минимума квадратичная функ­ция может быть достаточно хорошей аппроксимацией целевой функции. Таким образом, алгоритм, который не дает хороших результатов при минимизации квадратичной функции, вряд ли может быть с успехом использован в случае об­щей нелинейной функции, когда текущая точка находится в окрестности мини­мума.

Излагаемые далее численные методы решения задачи (4.1) иллюстрируются решениями примеров, связанных с минимизацией квадратичной функции двух переменных. В [42] приведены примеры Применения этих методов и минимиза­ции функций, имеющих специальную структуру линий уровня, и сделана попыт­ка анализа эффективности этих методов в зависимости от характера целевой функции /(*).

Задачи для самостоятельного решения

1. Классифицировать последовательность

Для функции /(х) = 5Х]2 -15*! + х2 -х2 + Зх32 + 6х3 +10.

к точке минимума х[4] = (1,5; 0,5;- 1)Т.

2. Классифицировать последовательность

х\ (гк)

х\

О

о

8х]* +16'
у к+1 х2 = V к х2 - о

о

6х2* +18
.у к+1

ХЪ

\ /

у к

[ХЪ J

1» » Я) 2х3* -4

\ /

для функции /(*) = 4х2 +16*! + Зх22 +18*2 + *з2 ~ 4хг + 16 •

Ответ: последовательность является минимизирующей и сходящейся к точке минимума х* = (-2,-3,2)г.

3. Определить порядок сходимости последовательности

хк =1 + 3-*, к = ОД,...

Ответ: последовательность сходится к х* = 1 линейно при с = ^ .

4. Определить порядок сходимости последовательности

х*=1 + 2-2‘, *=0,1,...

Ответ: последовательность сходится к х* = 1 квадратично при с = 1 .

5. Классифицировать последовательность

** = -3 + Тquot;~Гgt; * = 0,1,... к +1

для функции /(*) = х2 + 6х +12.

Ответ: последовательность минимизирующая и сходится к точке х* = -3 минимума функции.

6. Классифицировать последовательность

хк+1 = хк _1удх*), Л = 0gt;1)

О

для функции /(х) = 4х2 - 8х + 7.

Ответ: последовательность минимизирующая и сходится к точке х* = 1 минимума функции.

7. Классифицировать последовательность

* = 0,1,...

V * + 1 - 1 V к *1 --pound;*2 8’

<< | >>
Источник: Пантелеев А. В., Летова Т. А.. Методы оптимизации в примерах и задачах: Учеб. посо- бие/А. В. Пантелеев, Т. А. Летова. — 2-е изд., исправл. — М.: Высш. шк.,— 544 с.: ил.. 2005

Еще по теме § 4. ПРИНЦИПЫ ПОСТРОЕНИЯ ЧИСЛЕННЫХ МЕТОДОВ ПОИСКА БЕЗУСЛОВНОГО ЭКСТРЕМУМА:

  1. Задача о замене оборудования
  2. § 4. ПРИНЦИПЫ ПОСТРОЕНИЯ ЧИСЛЕННЫХ МЕТОДОВ ПОИСКА БЕЗУСЛОВНОГО ЭКСТРЕМУМА
  3. § 8. ПРИНЦИПЫ ПОСТРОЕНИЯ ЧИСЛЕННЫХ МЕТОДОВ ПОИСКА УСЛОВНОГО ЭКСТРЕМУМА