full_book

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Перепишем величину fk− как

fk− = min{ψ ( yi* ) :1 ≤ i ≤ k +1},

где

ψ ( yi* ) = min{ fk− ( y) : y [ yi−1 , yi ]},1 ≤ i ≤ k +1.

Из условия Липшица и определения миноранты fk− ( y) yi* = ( yi−1 + yi ) / 2 −(zi − zi−1 ) /(2L), 2 ≤ i ≤ k,

где ∆i = yi −yi−1, 1 ≤ i ≤ k +1.

Погрешность определения минимального значения целевой функции на отрезке [ yi−1 , yi ] не превосходит величины

является наихудшей и W (s* ) = L(b − a) . 2K

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

оптимальность метода перебора.

Что касается байесовых методов поиска экстремума, то Й.Б.Моцкусом [32] показано, что задача их построения может быть сведена к решению некоторой системы рекуррентных уравнений. Однако и в этом случае задача остается настолько сложной, что оптимальные байесовы методы точно не реализуемы.

Формулировка критериев оптимальности в виде (4.26), (4.27) ориентирована на использование только априорной информации и не учитывает одной важной особенности организации вычислительного процесса поиска минимума, а именно, возможности учета получаемой в процессе поиска (апостериорной) информации о функции. Это приводит для критерия (4.26) к ориентации на худший, а для критерия (4.27) – на "типичный" (наиболее вероятный) случай, хотя оптимизируемая функция может существенно отличаться от худшей, либо типичной. При минимаксном подходе в классе липшицевых функций оказывается, что вследствие ориентации на худший случай, которым является функция-константа, многие оптимальные алгоритмы представляют собой метод перебора по равномерной сетке. В связи с этим А.Г.Сухарев ввел понятие последовательно-оптимального алгоритма как метода, который являясь минимаксным, вместе с тем на каждом шаге поиска наилучшим образом использует апостериорную информацию о минимизируемой функции (строгое определение можно найти в [45]). Понятие последовательной оптимальности можно применить и к байесовским методам поиска [7]. Более экономные последовательно-оптимальные алгоритмы удалось построить А.Г.Сухареву для некоторых подклассов липшицевых функций.

4.3. Одношагово-оптимальные методы оптимизации

Трудности конструирования оптимальных в смысле (4.28) алгоритмов поиска привели к использованию более простых понятий оптимальности. Одним из таких понятий является так называемая одношаговая оптимальность [7, 9, 11, 45], когда алгоритм размещает очередное испытание наилучшим образом, предполагая, что оно является последним.

4.3.1. Принцип одношаговой оптимальности

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

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

Приведем формальное описание одношагово-оптимального метода поиска экстремума [7, 9]. С этой целью вернемся к формальной схеме метода оптимизации (4.9) и для любого возможного ωk из (4.11) определим класс Φ(ωk )

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

из (4.12), т.е. множество функций из Φ , допускающих реализацию данного ωk . В исходном множестве алгоритмов S выделим подкласс S(ωk ) таких методов, которые для любой функции f Φ(ωk ) после первых k испытаний реализуют данное ωk . Введем последовательность функций Vk +1 (ωk , y, z) , определяющих

эффективность проведения очередного испытания в точке y и получения результата z=f(y) для f Φ(ωk ) .

Тогда алгоритм s может быть описан набором

называемую функцией гарантированного результата. Выбор операции sup/inf определяется тем, как введена функция эффективности (случай sup соответствует варианту "чем меньше Vk +1 (ωk , y, z) , тем лучше").

определяющее функцию средней эффективности, где P(zk+1 /ωk , yk +1 ) -

условное по отношению к результатам испытаний распределение вероятностей, то метод, определяемый соотношением (4.32), будет называться байесовским одношагово-оптимальным алгоритмом, или методом, одношагово-оптимальным в среднем.

Приведем примеры одношагово-оптимальных алгоритмов.

4.3.2. Метод ломаных как одношагово-оптимальный алгоритм

Классическим примером минимаксного одношагово-оптимального алгоритма является метод С.А.Пиявского. Данный метод предполагает, что минимизируемая функция одного аргумента f(y) удовлетворяет на отрезке [a,b] условию Липшица с константой L>0, т.е. f ( y) Lip[a,b] .

Идея метода геометрически проста: предлагается проводить очередное испытание в точке минимума кусочно-линейной миноранты fk− ( y) . Можно

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

Vk +1 (ωk , y, z) = min{ fk* ; z}− min{ fk− (u); z − L y −u } ,

u [a,b]

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

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

4.3.3. Информационно-статистический метод Р.Г.Стронгина

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

Итак, пусть на отрезке [a,b] определена функция f(y). Будем минимизировать данную функцию на конечной равномерной сети точек

a = y(0) < y(1) < y(2) <... < y(n −1) < b = y(n)

(n +1) -мерного евклидова пространства Rn+1 . Тогда возможный способ описания априорных предположений о минимизируемой функции f Rn+1 состоит в задании плотности ϕ( f ) распределения вероятностей на пространстве Rn+1 .

Если плотность ϕ( f ) положительна и непрерывна, то с вероятностью

единица минимум оптимизируемой функции достигается в единственной точке, поэтому для его оценки достаточно подсчитать вероятности η(α) расположения

минимума в точках α , совпадающих с узлами сетки. Более того, после проведения испытаний в некоторых узлах сетки и получения поисковой информации ωk возможно получение условных (апостериорных) вероятностей

η(α /ωk ) , обеспечивающих текущие оценки экстремума.

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

описания апостериорных вероятностей η(α /ωk ) с помощью введения

дополнительной дискретной случайной величины α , распределение вероятностей ξ(α) которой на узлах сетки связано с априорным вероятностным описанием

ϕ( f ) с помощью разложения

ϕ( f ) = ∑ϕ( f /α)ξ(α)

α Yn

где Yn - множество узлов сетки. Введение такого разложения позволяет

установить основанные на методе малого параметра условия близости апостериорных вероятностей η(α /ωk ) и ξ(α /ωk ) и тем самым перейти к

вычислению условных вероятностей состояния природы, которые существенно проще.

В качестве конкретного примера применения информационностатистического подхода рассмотрим вероятностное описание, в котором априорная плотность ϕ( f ) представлена разложением ϕ( f /α), 0 ≤α ≤ n, где

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

этой функции в точке y(0) при любом фиксированном α являются реализациями независимых случайных величин, подчиненных нормальному закону со

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

равномерной непрерывности.

Кроме того, априорное математическое ожидание

значений fi функции f при фиксированном α имеет единственный локальный

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

a = y0 < y1 < y2 < ... < yk < b = yk +1

и получена информация ωk . Тогда апостериорные вероятности состояния природы могут быть выражены как

ξ(α /ωk ) = B h(ωk ,α)ξ(α) ,

где B - константа, а для любого α из отрезка ys−1 ≤α ≤ ys , is−1 J , is J , 1 ≤ s ≤ k,

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

исходные состояния природы равновероятны, и параметр m удовлетворяет условию

характеристикой интервала, максимальна, и совпадает с наивероятнейшей точкой расположения минимума.

Более того, точка αt* будет одношагово-оптимальной точкой, если в качестве функций потерь Vk +1 (ωk , y, z) , описывающих эффективность

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

k

Vk +1 (ωk , y, z) = ∑zs

s=0 .

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

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

Построенный метод легко распространяется на функции с непрерывно изменяющимся аргументом. Для этого достаточно устремить число точек равномерной сетки к бесконечности (n→∞ ) так, чтобы в пределе был получен конечный интервал D=[a,b]. При этом полученные расчетные формулы для характеристики интервала R(s) и наилучшей точки измерения на нем αs* не

изменятся. Координату точки измерения на s–м интервале в дальнейшем вместо

С использованием (4.34) правило выбора точки очередного испытания в информационно-статистическом методе может быть записано в виде

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Wk +1 ( yk +1 ) = max{Wk +1 ( y) : y D =[a;b]}.

4.3.4.Одношагово-оптимальный байесовский метод Х.Кушнера

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

ϕ(x2 ) −ϕ(x1 ) распределено по нормальному закону с нулевым средним и

дисперсией вида σ x2 − x1 , т.е. пропорциональной приращению аргумента. Их

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

Введем функцию оптимальности на шаге следующим образом. Будем считать, что y — точка планируемого (k+1)-го испытания, а z=f(y) — пока еще не известное нам значение целевой функции в этой точке. С учетом планируемого

измерения ωk +1 =ωk U{( y; z)}. Выберем вид функции эффективности таким образом, чтобы Vk +1 ( f ,ωk +1 ) зависела от функции f только через посредство

т.е. потери постоянны и равны единице, если значение функции в точке очередного испытания меньше текущего минимального после k-го шага значения

fk* с "запасом", который задается величиной параметра δk > 0 , и равны нулю в противном случае.

При вычислении функции средней эффективности Wk +1 ( y) для винеровской

модели поведения целевой функции используется функция условного распределения с гауссовой плотностью p(z /ωk , y) , вид математического

ожидания и дисперсии которой приведен в (1.57), (1.58) главы 1 и проиллюстрирован на рис.1.22. С учетом (4.35) получим

Wk +1 ( y) = ∫−+∞∞Vk +1 (ωk , z) p(z /ωk , y)dz = P( f ( y) ≤ fk* −δk ωk ) .

Согласно принципу одношаговой оптимальности в среднем, выбор точки очередного испытания определяется правилом

т.е. yk +1 находится из условия максимизации вероятности вычисления в точке yk +1 значения целевой функции меньшего достигнутого минимального значения fk* по крайней мере на δk > 0 .

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Если предположить, что проведены испытания в точках (4.24), то можно

где математическое ожидание и дисперсия определяются соотношениями (1.57), (1.58). Это выражение достигает своего максимума в точке

Теперь в качестве точки очередного испытания достаточно выбрать ту точку ~yi , которой соответствует максимальная величина R(i) .

)Замечания.

1. При программной реализации метода Х.Кушнера параметр δk обязательно

должен адаптивно изменяться в ходе поиска решения задачи (как правило, убывать), оставаясь отделенным от нуля некоторым малым положительным значением 0 <δ <<1: δk ≥δ > 0 .

2. Настройка параметраδk может выполняться с помощью специального алгоритма, аналогичного приведенному ниже в (4.43). Применение алгоритма

σk = (1(b − a))∑i=2 (f ( yi ) − f ( yi−1 )) .

4.3.5. Одношагово–оптимальный метод на основе адаптивных вероятностных моделей для задач с ограничениями

Понятие одношаговой оптимальности естественным образом встраивается в общую теорию конструирования алгоритмов на основе адаптивных вероятностных (стохастических) моделей, введенных в пункте 1.4.2.3 [14, 16, 17, 18].

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

Итак, рассмотрим задачу с ограничениями–неравенствами

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

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

Для того, чтобы при построении метода упростить учет набора ограничений, будем использовать функцию обобщенного ограничения (1.66), введенную в

пункте 1.4.2.3 главы 1. Она имеет вид

G( y) = max{g1 ( y),..., gm ( y)} .

Предположим, что накоплена поисковая информация ωk , включающая измерения набора функций Q( y) = ( f ( y), g1 ( y),..., gm ( y) ) , описывающего поставленную задачу. Таким образом, имеем ωk =ωk (Q) =ωk ( f , g) , что позволяет

выделить отдельно поисковую информацию, накопленную о функции f, т.е. ωk ( f ) , и поисковую информацию о значениях функции g, т.е. ωk (g) .

Будем считать, что для произвольно взятой точки y из D неизвестные

(1.67)–(1.70) из пункта 1.4.2.3 первой главы. Совокупность этих распределений образует адаптивную вероятностную модель решаемой задачи.

Следует обратить внимание на то, что модель поведения функции G, определяемая функцией распределения F G , строится не по измерениям функции G, а по результатам ωk (g) измерений исходного набора функций ограничений

g1 ,..., gm . Существующие здесь отличия иллюстрируются на рис.1.25.

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

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

Теперь аналогично (4.35) введем функцию эффективности, зависящую от накопленной поисковой информации ωk ( f , g) , а также от результатов z f и zG измерений функций f и G в точке планируемого испытания y.

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

измерения оказывается допустимой с «запасом» εG > 0 , а текущую оценку решения fk* удается улучшить, по крайней мере, на величину δk > 0 . Функция средней эффективности определяется соотношением

Wk +1 ( y) = ∫−+∞∞ ∫−∞+∞Vk +1 (ωk ( f , g), z f , zG )dF f (z f ωk ( f ), y)dF G (zG ωk (g), y),

которое, как нетрудно видеть, может быть записано в виде

ННГУ. Учебный курс «Модели и методы конечномерной оптимизации». Часть 2. Нелинейное программирование и многоэкстремальная оптимизация.

Согласно принципам одношаговой оптимальности очередное испытание должно проводиться в точке yk +1 , для которой

Wk +1 ( yk +1 ) = max{Wk+1 ( y) : y D}.

В этой точке достигает максимума произведение вероятности вычисления значения f(y), улучшающего fk* не менее чем на δk , на вероятность выполнения в этой точке ограничений в усиленной форме.

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

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

Заметим, что входящий в функцию эффективности параметр δk

существенно влияет на поведение построенного метода. Для его эффективной работы параметр δk должен постепенно адаптивно уменьшаться до некоторого

малого значения 0 <δ ≤ ε f , где ε f — заданная точность по значению целевой функции. Возможный алгоритм настройки этого параметра состоит в следующем.

Зададим пороговую величину β (0<β<<0.5) для значения вероятности Wk +1 ( yk +1 ) .

использованием метода максимального правдоподобия. Например, на шаге k определить численно значение σkf из приближенного решения вспомогательной задачи поиска максимума

)Замечание. Рассмотренный метод следует рассматривать как некоторую теоретическую схему, поскольку его нельзя точно вычислительно реализовать. Однако он допускает приближенные вычислительные реализации с использованием либо приближенных методов максимизации функции (4.42) либо компонентного подхода, примеры применения которого рассматриваются в разделе 5.7.