full_book

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

Определение 4.8. Пусть y′ и y′′ — точки испытаний, тогда если при некотором p>0 отношение

при k→∞ ограничено и строго положительно, то число p будем называть порядком относительной концентрации испытаний, а функцию αk ( y′, y′′) —

относительной концентрацией (плотностью) испытаний в точке y′ по отношению к точке y′′.

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

величина ρk ( y′) , а также — моменты, когда уменьшаться будет ρk ( y′′) . Отсюда следует, что в процессе поиска относительная концентрация испытаний αk ( y′, y′′)

при k→∞ будет совершать колебания в некоторых границах. Наша цель будет состоять в том, чтобы найти зависимость границ этих колебаний для произвольно выбранных точек y′ и y′′ из D от поведения функции Q, описывающей исходную задачу.

Пример упрощенного способа оценивания относительной концентрации

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

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

~

способ получения некоторого «среднего» значения α( y′, y′′) , вокруг которого

совершает колебания относительная плотность при k→∞. Этот способ не является строгим, но позволяет лучше понять основную идею последующего формального

изложения.

~

Покажем, как можно получить значение α( y′, y′′) на примере метода

Х. Кушнера. Предположим, что порядок относительной концентрации испытаний p в (4.90) равен единице ( p=1). Тогда

ρk ( y′′) =αk ( y′, y′′)ρk ( y′) .

Для метода Х.Кушнера с функционалом (4.36), как было указано в пункте 4.3.4, для отрезка [yi–1; yi] можно вычислить характеристику

Выберем и зафиксируем произвольную точку испытания y′. Пусть на k–м

шаге она совпадает с (i-1)–й точкой в порядке возрастания координат yi–1, где i=i(k, y′). Тогда в наших обозначениях

yi − yi−1 = ρk ( y′) .

Аналогично можно рассмотреть другую точку испытания y′′, причем для j = i(k, y′′)

y j − y j−1 = ρk ( y′′) =αk ( y′, y′′) ρk ( y′) .

В процессе поиска, из-за всюду плотного характера сходимости, значения R(i(k, y′)) и R(i(k, y′′)) будут поочередно становиться то больше, то меньше одно

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

другого, поэтому «среднее» значение α~( y′, y′′) можно найти, приравнивая их друг к другу

R(i(k, y′)) = R(i(k, y′′))

с заменой в них значения αk ( y′, y′′) на «среднее» α~( y′, y′′) . Отсюда, используя

непрерывность функции f и всюду плотный характер сходимости, при k→∞ получим

Это выражение характеризует «среднее» значение вокруг которого колеблется плотность испытаний в точке y по отношению к плотности в точке глобального минимума y*.

Очевидно, что максимум в выражении (4.99) равен 1 и достигается в точках

функции f(y) отличается от глобально–оптимального. Заметим, что асимптотическое значение относительной плотности испытаний вне Y*

уменьшается с уменьшением δ = limδk . Однако, сразу выбирать очень маленькие

k→∞

δk нельзя из-за замедления выхода относительной плотности на асимптотику.

Качественный характер зависимости α~( y, y* ) от y для конкретной функции показан на рис.4.6

Рис.4.6. Зависимость «средней» концентрации испытаний в точке y по отношению к y*

)Контрольные вопросы и упражнения.

Попробуйте самостоятельно построить оценку α~( y, y* ) для метода

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

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

4.6.2. Метод аналитического оценивания относительной концентрации испытаний

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

Введем дополнительные обозначения. При N >1рассмотрим замкнутый шар

O( y, r) ={u : y −v ≤ r},

а при N =1 примем другую трактовку того же обозначения

O( y, r) =[ y; y + r] .

Пусть Uk — множество попарно различных точек из (4.76), и u Uk . Введем

обозначение для координат точки с максимальным значением функции выбора Wk(ω(Q,U k ), y), при условии, что этот максимум определяется в области в виде шара с центром в точке испытания u и радиусом, равным значению ρ(u,Uk ) , т.е.

расстоянию от u до ближайшей к ней другой точки из U k .

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

характеризующую максимальное значение функции выбора, соответствующее точке yˆ(u,Uk ) (заметьте, что в (4.101), из-за специфики структуры множества

ψ (u,r) , значение r = ρ(u,Uk ) ).

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

Пусть y′и y′′ — две фиксированные точки из D.

Предположение 4.1. Для функции Q, описывающей решаемую задачу, и

попарно различных точек, образующих в пределе всюду плотное покрытие D и включающих точки y′ и y′′, найдется такое K, начиная с которого при u=y′ ,

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

а также для u=y′′ при достаточно малом σ ≥ ρ(u,Uk ) существуют оценки для значений из (4.101)следующего вида

где функции Ai (Q,u, r) (i =1,2) не зависят от Uk, σ, некоторым образом зависят от свойств Q в точке u и строго возрастают по r.

Предположение 4.3. При достаточно малом r и некотором p>0 существуют положительные ограниченные, непрерывные по r в нуле решения βi = βi ( y′, y′′,r)

причем эти решения имеют положительные ограниченные пределыβ1( y′, y′′,0) ,

β2 ( y′, y′′,0) при r→ 0.

Теорема 4.13. Пусть метод поиска (4.75) на классе функций Φ обладает всюду плотным характером сходимости в области D, y′ и y′′ — фиксированные точки испытаний, не лежащие на границах D, а функционал Wk(ω(Q,Yk ), y) удовлетворяет предположениям 4.1–4.3. Тогда α( y′, y′′) — относительная

концентрация испытаний в точке y′ по отношению к y′′ обладает следующими свойствами.

1. Имеет порядок p.

2.Подчиняется следующей динамике. При достаточно большем k и r = ρk ( y′′) ,

если значение

αk ( y′, y′′) [ β1 ( y′, y′′,r); β2 ( y′, y′′,r)],

то оно может только приближаться к этому отрезку и за конечное число шагов попадет в него. Находясь в этом отрезке αk ( y′, y′′) может как возрастать

(не более, чем в ν1 p раз на шаге), так и убывать (не более, чем в ν раз на шаге). 3. Для любого ε > 0 найдется K, что при k >K имеют место следующие оценки

ДОКАЗАТЕЛЬСТВО приведено в [15].

Рис.4.7. Асимптотическая динамика при ν=2 и p=1

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

Асимптотическую динамику перемещения точки (ρk ( y′′); ρk ( y′)) из

нескольких начальных положений при ν=2 и значениях p=1 и p=0.5 иллюстрируют рис.4.7, 4.8

Рис.4.8. Асимптотическая динамика при ν=2 и p= 0.5

Пример оценки относительной концентрации для метода Х. Кушнера

Не проводя выкладок, укажем только окончательный результат для y′ = y, y′′ = y* . Оказывается, что для метода Х. Кушнера в (4.106)

и при этом p =1, ν = 2 , т.е. при сколь угодно малом ε > 0, начиная с некоторого шага, относительная плотность испытаний принадлежит интервалу

α k ( y , y * ) [0 .5 α~ ( y , y * ) − ε ; 2α ( y , y * ) + ε ],

где α~( y, y* ) определяется соотношением (107).

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

Напомним, что этот метод был описан в пункте 4.3.4, а вид его характеристической функции приведен в (4.86) раздела 4.5, где в качестве функции распределения F(z) использована функция

Будем предполагать, что вектор–функция Q = ( f , g1 ,..., gm ) принадлежит

классу Φ′′ , введенному при рассмотрении данного метода в разделе 4.5. Для упрощения вывода нужных нам оценок аппроксимируем все функции кусочно– постоянными из Φ′′ , т.е. рассмотрим подкласс в Φ′′ .

Опуская достаточно громоздкие, но несложные выкладки, приведем окончательный результат. Рассмотрим подобластьYεG допустимой области Y

из (4.38)

YεG = {y D : G( y) ≤ −εG },

где 0 < ε G << 1 , а G(y) — обобщенная функция ограничения, введенная в п. 4.3.5. Можно показать, что если обе сравниваемые точки допустимы с «запасом»,

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

минимума равен 1, причем в выражении (4.106) для границ колебаний относительной концентрации ν = 2 , а значения

т.е. при сколь угодно малом ε > 0, начиная с некоторого шага, относительная концентрация испытаний принадлежит интервалу

концентрации испытаний в недопустимой точке y по отношению к точке глобального минимума определяется как p = (sγ )<1. Т.е. при k → ∞ расстояние

ρk ( y* ) от y* до ближайшей к ней точки испытания является величиной более высокого порядка малости (равного 1 p >1) нежели расстояние ρk ( y) от точки y недопустимого испытания до ближайшей к ней точки другого испытания:

ρk ( y* ) = o(ρk ( y))= O((ρk ( y))1 p ).

Кроме того, в выражении (4.106) для границ колебаний относительной концентрации ν = 2 , а значения

т.е. при сколь угодно малом ε > 0, начиная с некоторого шага, относительная концентрация испытаний принадлежит интервалу

где α~( y, y* ) определяется соотношением (109).

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

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

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

Лист регистрации изменений

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

Глава 5. Фундаментальные способы редукции размерности в многоэкстремальных задачах

5.1. Многоэкстремальные задачи и методы покрытий

Рассмотрим конечномерную задачу оптимизации (задачу нелинейного программирования)

т.е. задачу отыскания экстремальных значений целевой (минимизируемой) функции f ( y) в области Y , задаваемой координатными (5.3) и

функциональными (5.2) ограничениями на выбор допустимых точек (векторов)

соответствующая нижняя и (или) верхняя границы отсутствуют, принимаются равными ai = −∞ и (или) bi = +∞ .

Довольно часто в формулировку задачи нелинейного программирования включают также ограничения в виде равенств. Однако любое равенство h( y) = 0 ,

ЭВМ точная реализуемость равенства невозможна, поэтому предполагают, что

учитывая указанные обстоятельства, можно утверждать, что (5.1)-(5.3) является формулировкой общей многомерной задачи нелинейного программирования.

Если m = 0 , т.е. функциональные ограничения отсутствуют, будем полагать Y = D . Задача (5.1)-(5.3) в этом случае будет называться задачей безусловной оптимизации.

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

допустимой области Y несколько локальных экстремумов. На сложность решения таких задач существенное влияние оказывает размерность. Например, для класса многоэкстремальных функций, удовлетворяющих условию Липшица, имеет место так называемое "проклятие размерности", состоящее в экспоненциальном росте вычислительных затрат при увеличении размерности. А именно: если в одномерной задаче для достижения точности решения ε требуется p вычислений функции, то в задаче с размерностью N для решения с той же

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

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

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

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

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

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

Другой пример. Пусть минимизируемая функция f ( y) удовлетворяет в области Y условию Липшица (4.69) с константой L , или кратко f ( y) Lip(Y ) .

В этом случае оказывается, что задача построения эффективной конечной сетки эквивалентна геометрической задаче построения оптимального покрытия области поиска [11, 45]. При ориентации на критерий априорной оптимальности (4.26) такими покрытиями являются так называемые равномерные, или переборные сетки. Из них наиболее элементарными являются кубические сетки. Методика их построения чрезвычайно проста.

которых составят кубическую сетку. На первый взгляд, точки этой сетки расположены в гиперкубе с хорошей "равномерностью". Однако, подобное утверждение справедливо лишь в одномерном случае. Уже при N = 2 кубическая решетка не очень хороша, а с увеличением размерности ее "равномерность" быстро ухудшается. Существуют сетки, реализующие более качественное покрытие области D в том смысле, что они обеспечивают меньшие значения показателей "неравномерности" размещения узлов сетки (например, сетки метода Монте-Карло). Среди этих сеток наименьшим порядком роста неравномерности при увеличении размерности обладают так называемые ЛПτ -сетки [41]

(теоретически наилучший порядок роста неравномерности неизвестен).

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

Размещение испытаний в узлах кубических, или ЛПτ -сеток, или любых

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

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

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

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

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

Простейший способ состоит в том, чтобы выбирать начальные точки по схеме метода Монте-Карло [27], т.е. случайно в соответствии с некоторым распределением в области поиска (обычно равномерным), либо использовать в качестве таких точек узлы некоторой регулярной сетки [41]. Сравнение способов выбора начальных точек приведено в [45].

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

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

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