full_book

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

Определение 4.5. T – представимый метод назовем Const – нормальным, если для всякого Uk из (4.76) и y D при ρ( y,Uk ) ≥ R > 0 выполняется условие

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

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

f * −δ0 − f max < 0 , где f max — верхняя оценка f на [a,b], существующая в силу

непрерывности f, а знаменатели при ρ(y,Uk )≥ R больше R>0. Отсюда вытекает, что

Wk (ω( f ,Uk ), y)≥ M = −(f max − f * +δ0 )R >W * = −∞.

Таким образом, метод Х.Кушнера является К– нормальным.

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

Покажите, что при определенных дополнительных требованиях на класс функций Q=(f,g) метод условной глобальной оптимизации на основе адаптивных стохастических моделей, определяемый функционалом (4.86), будет Const – нормальным. Укажите эти требования.

Теорема 4.7. (критерий всюду плотной сходимости). На функциях класса

Φ Φ′ в задачах с неизвестным индикатором множества решений, описанных в пункте 4.5.1, Const – нормальный метод поиска обладает всюду плотным типом сходимости тогда и только тогда, когда он принадлежит Const – типу, т.е. W *( y, Q( y) ) = const.

НЕОБХОДИМОСТЬ непосредственно вытекает из теоремы 4.6. ДОСТАТОЧНОСТЬ. Пусть W *( y, Q( y) ) ≡ c, но y′ D, не являющаяся

предельной для последовательности испытаний Y∞ . Тогда найдется R>0, что для всех k ρ( y, Yk )≥ R. Из (4.87) следует, что M, что k

Wk (ω(Q,Yk ), y′)≥ M > c .

Но т.к. D — компакт, в D существует по крайней мере одна предельная точка y′′ для Y∞ . На сходящейся к ней подпоследовательности yik при k→∞

Wik −1 (ω(Q,Yik −1 ), yik )→ c .

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

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

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

быть существенно различной в различных подобластях области поиска и даже иметь различный порядок малости при k→ ∞ . Соответствующие оценки относительной концентрации будут получены в разделе 4.6.

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

известным, например, в тех задачах глобальной оптимизации, к которым сводятся задачи поиска решений систем совместных уравнений и неравенств. Таким задачам адекватны T – представимые методы δ – типа.

Введем понятие δ – нормальности, аналогичное по смыслу Const – нормальности из определения 4.5, но ориентированное на применение к методам δ – типа.

Определение 4.6. T – представимую процедуру поиска назовем δ – нормальной,

где M может зависеть от Q, R и y , но не зависит от k .

Изучим условия сходимости второго типа.

Теорема 4.8. (достаточные условия сходимости второго типа). Если на классе функций Φ метод поиска является δ – нормальным и относится к δ – типу, то он порождает для задач с непустым замкнутым множеством решений Y * последовательности поисковых испытаний, все предельные точки которых принадлежат Y *. Если же Y * = , метод порождает всюду плотную в пределе последовательность испытаний.

ДОКАЗАТЕЛЬСТВО. Если Y * = , то δ – нормальный метод δ – типа является в гиперпараллелепипеде D Const – нормальным методом константного типа. Поэтому, из доказательства теоремы 4.7 вытекает его всюду плотная сходимость.

Пусть теперь Y * замкнуто и непусто. Если бы никакая точка y′ из Y * не была предельной для последовательности испытаний, то рассуждая аналогично тому, как это было сделано в доказательстве теоремы 4.7, получили бы, что в области D \ Y * точки испытаний располагались в пределе всюду плотно. Но в этом случае найдутся граничные точки Y *, являющиеся предельными для последовательности испытаний. Однако в силу замкнутости Y * это противоречит первоначальному

Следовательно, ни одна из точек y′′ D \ Y * не может быть предельной, т.к. иначе на сходящейся к ней подпоследовательности yik при k→∞ из (4.78) имели бы

Wik −1 (ω(Q,Yik −1 ), yik )→η(0) ,

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

но это вместе с (4.89) противоречит правилу выбора точек испытаний (4.75). Теорема доказана.

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

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

Впервые эти свойства были выявлены и исследованы Р.Г.Стронгиным [7] для конкретных информационно–статистических алгоритмов глобального поиска, а затем в работах В.А.Гришагина теоретически обобщены для класса характеристических алгоритмов оптимизации (см. раздел 4.4).

Более общие результаты в предположении непрерывности целевой функции f в задаче (4.90) формулирует следующая теорема.

Теорема 4.9. ( необходимые и достаточные условия свойства приоритета)

Для того, чтобы T – представимый метод поиска минимума в задаче (4.90) для скалярных непрерывных в компакте D функций f порождал поисковую последовательность со свойством приоритета, достаточно принадлежности метода строго монотонному типу (SM – типу), а на классе методов непрерывного типа ( C – типа) — необходимо, чтобы метод поиска относился к монотонному типу ( M – типу).

ДОСТАТОЧНОСТЬ. Пусть y′ и y′′ — предельные точки последовательности испытаний Y∞ и f(y′) ≠ f(y′′ ), например, f(y′) < f(y′′ ). Из строго монотонного типа метода следует, что y D W * ( y, f ( y)) = µ( f ( y)) и µ( f(y′) ) > µ( f(y′′ ) ). Из

(4.77), (4.79) и непрерывности µ(z) и f(y) сразу получаем, что при достаточно малом ε >0 найдется точка испытания yk* , достаточно близкая к y′, что k > k*

Wk (ω( f ,Yk ), yk* ) >W * ( y′, f ( y′)) −ε >W * ( y′′, f ( y′′)) ,

но тогда y′′ не может быть предельной для множества точек испытаний. Полученное противоречие доказывает, что f(y′) = f(y′′ ).

В силу компактности области D у последовательности точек испытаний Y∞ существует хотя бы одна предельная точка y′. Рассмотрим значение f(y′). Из-за свойства приоритета f(y′) ≤ f(y 1). Но, по построению функции, f(y ) ≥ f(y 1) y D,

может быть предельной для Y∞ . Поскольку это невозможно, метод должен быть монотонен. Таким образом, доказательство завершено.

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

Заметим, что из условий теоремы 4.9 и ранее проведенного анализа следует, что информационно–статистический метод и метод С.А. Пиявского обладают свойствами приоритета на классе липшицевых функций, а метод Х.Кушнера этим свойством не обладает.

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

Следствие 4.9.1. Если T – представимый метод поиска решения задачи (4.90) на компакте D сходится, то для непрерывных в D функций f из выполнения свойства приоритета следует конечность числа испытаний, размещаемых методом в

любой подобласти со значениями f ( y) ≥ f ( y* ) +ε при ε > 0 .

ДОКАЗАТЕЛЬСТВО. В самом деле, если процедура сходится (в смысле понятия сходимости, введенного в начале пункта 4.5.3), то в Y * имеются предельные точки последовательности Y∞ . Отсюда и из свойства приоритета очевидно следует отсутствие предельных точек последовательности Y∞ в замкнутых

подобластях, не содержащих точек из Y * , т.е. конечность числа точек испытаний в таких подобластях. Доказательство завершено.

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

ДОКАЗАТЕЛЬСТВО. Если конечных минорант для f не существует, то глобальный минимум может располагаться в любой точке, не совпадающей с точками проведенных испытаний. Тогда для его определения необходимо всюду плотное в пределе размещение испытаний. Но это противоречит следствию 4.9.1.

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

Рассматривая вопрос на содержательном уровне, можно сказать, что функционал Wk (.) должен позволять идентифицировать наличие не содержащих

точек испытаний подобластей Dy , когда точка y , принадлежащая границе Dy ,

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

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

набор Γ пар ( A; y) , где A — множество, y ∂A ( ∂A — граница A ) и рассматривать указанное выше свойство, заменяя Dy на A Dy .

Определение 4.7. Пусть Γ — некоторая совокупность пар (A; y), где y D, а A —

нормальным (относительно класса функций Φ и класса Γ пар (A; y) ), если для любых f Φ и y D таких, что существует пара (A; y) Γ с A D y из (4.92), для произвольной последовательности U∞ , имеющей y в числе своих предельных

точек и такой, что U∞ ∩ Dy = , начиная с некоторого k выполняется

При этом M может зависеть от f и (A; y), но не зависит от k.

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

Теорема 4.10. ( условия локальной сходимости со свойством приоритета)

Пусть f Φ Φq из (4.91), число локальных минимумов f в D конечно, метод поиска решения задачи (4.90) относится к строго монотонному типу (SM –типу) с W * ( y, f ( y)) = µ( f ( y)) и является M – нормальным относительно Φ и класса

пар Γ. Тогда справедливы следующие утверждения.

А. Если y′— предельная точка последовательности испытаний Y∞ , то для любого k≥ 1 f ( y′) ≤ f ( yk ) и либо точка y′ является локальным минимумом f на

D, либо для y′ в классе Γ не существует пар (A; y′) Γ со сколь угодно малыми значениями диаметра diam(A) и A Dy′ .

В. Если y′′ — любая другая предельная точка последовательности испытаний Y∞ ,

то f ( y′′ )=f ( y′).

ДОКАЗАТЕЛЬСТВО. Справедливость утверждения В и первой части утверждения А непосредственно следует из теоремы 4.9. Доказательство остальных утверждений читатель сможет найти в работе [15].

Анализ характера сходимости к локально–оптимальным точкам

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

Теория T – представимых методов позволяет проанализировать характер этого приближения. Для возможности такого анализа рассмотрим семейства множеств Kε ( v,ϕ ), являющихся пересечениями ε – окрестностей Oε (0) точки 0 с конусами Kε ( v,ϕ ) следующего вида

K (v,ϕ) = {y R N : (v, y) > y cosϕ},

где v =1.

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

Введем также класс Ψ(y, Kε (v,ϕ)) последовательностей Uk попарно различных точек испытаний из (4.76), что y будет предельной для U∞ и

Kε (v,ϕ)IU∞ = .

Определение 4.8. Пусть выбрано фиксированное ϕ* (0, π2] . T – представимый

метод решения задачи (4.90) с функцией f из класса Φ назовем ϕ – нормальным, со значением ϕ =ϕ* на классе Φ, если для всякой внутренней по отношению к D локально–оптимальной точки y o задачи (4.90) v с v =1, ε >0 и произвольной

последовательности точек испытаний U∞ Ψ( yo , Kε (v,ϕ)) , удовлетворяющей

дополнительному требованию, что u k U∞ : f( u k )≥ f( yo), начиная с некоторого шага k (возможно, зависящего от U∞ ) выполняется следующее неравенство

sup{ Wk (ω( f ,Uk ),u): u yo + Kε (v,ϕ) }≥ M ( f , y) >W * (y, f ( y)). (4.94)

Необходимые результаты представлены в следующей теореме.

Теорема 4.11 ( условия «сходимости» по секторам). Пусть T – представимый метод решения задачи (4.90) с функцией f из класса Φ относится к строго монотонному типу (SM – типу) и при некотором ϕ = ϕ* (0, π2] является

ϕ – нормальным на классе Φ. Тогда, если некоторая внутренняя, по отношению к области D, локально–оптимальная точка y o будет предельной для

последовательности испытаний, то для любого направления v ( v =1) в

коническом секторе y o + K( v,ϕ*) с угловым размером 2ϕ* и ориентацией v найдется подпоследовательность испытаний, сходящаяся к y o.

ДОКАЗАТЕЛЬСТВО. Пусть внутренняя для D локально–оптимальная точка y o является предельной для последовательности испытаний Y∞ , но утверждение теоремы для нее не верно. Тогда найдется конический сектор y o + K( v,ϕ*) с угловым размером 2ϕ* и ориентацией v ( v =1), что (yo + K(v,ϕ* ))IY∞ = .

Поскольку метод строго монотонен, то по теореме 4.9 для него выполнено свойство приоритета, т.е., в частности, для любой точки испытания y k выполнено f(y o)≤ f(y k) (k=1,2,..).

Таким образом, для последовательности испытаний Y∞ выполнены все условия, накладываемые на множества U∞ в определении 4.8 и, следовательно,ε > 0 последовательность Y∞ принадлежит классу Ψ( yo , Kε (v,ϕ* )) .

kS

в силу (4.78),

WkS −1 (ω( f ,YkS −1 ), ykS )→W * ( yo , f ( yo )) = µ( f ( yo )) ,

и ε : 0 < ε < 0.5 (M ( f , yo ) − µ(f ( yo ))) при некотором достаточно большом ks и дополнительном условии ks > k(ε) окажется, что

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

WkS −1 (ω( f ,YkS −1 ), ykS )<W * ( yo , f ( yo )) +ε <WkS (ω( f ,YkS ), yε ),

но это противоречит правилу выбора точек испытаний (4.75). Таким образом, теорема верна.

Исследование сходимости только к глобально-оптимальным точкам

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

Теорема 4.12 ( условия глобальной оптимальности предельных точек). Пусть f Φ Φq из (4.91), число локальных минимумов f в D конечно, T –

представимый метод поиска решения задачи (4.90) относится к строго монотонному типу (SM – типу) с W * ( y, f ( y)) = µ( f ( y)) . Тогда справедливы

то все предельные точки поисковой последовательности принадлежат множеству глобальных минимумов Y *.

где M(.) не зависит от k но может зависеть от R, f и y, то предельными точками последовательности испытаний являются все точки множества глобальных минимумов Y * и только они.

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

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

Самостоятельно докажите утверждения А и В теоремы 4.12.

Пример. Проиллюстрируем применение теорем 4.10–4.12 к анализу свойств метода С.А. Пиявского. Рассмотрим его на классе липшицевых функций для размерности N >1. Этот случай интересен тем, что его нельзя проанализировать с позиций теории характеристически представимых алгоритмов, поскольку область ее применимости ограничивается задачами с одним переменным и сводимыми к ним.

Ранее было показано, что при N ≥ 1 метод С.А. Пиявского, определяемый

оценка константы Липшица L выбрана так, что L ≥ L .

ПРОВЕРКА УСЛОВИЯ M – НОРМАЛЬНОСТИ. В качестве класса Γ выберем

всевозможные пары (A;y), где A — произвольные открытые односвязные множества, а y ∂ A. Рассмотрим точку, не являющуюся локальным минимумом f на D, тогда D y из (4.92) не пусто и существует (A;y) Γ, что A D y .

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

Рассмотрим произвольную точку u A . Поскольку она для A внутренняя, то в условиях определения 4.7 R > 0 , что k ρ(u,Uk ) ≥ R > 0 . Из условия Липшица

Таким образом, доказана М – нормальность по отношению к введенному классу пар Γ.

Заметим, что рассматриваемый класс пар содержит пары (A; y) с множествами A сколь угодно малого диаметра. Поэтому из строгой монотонности метода, доказанной M – нормальности и теоремы 4.10 следует, что процесс поиска

возможность выполнения для метода С.А. Пиявского оценки (4.94). Рассмотрим произвольную точку y o внутреннего локального минимума f на D и некоторое направление v. Вначале выберем последовательности U∞ из класса Ψ(y, Kε (v,ϕ)),

включающие только такие точки измерений uk, которые располагаются на прямой y o+v t, t R 1 вне промежутка (0;ε ) по t. При достаточно больших номерах шагов для них, с учетом существования в U∞ подпоследовательности точек, сходящейся к y o, возможна (при достаточно малых δ > 0) оценка

последовательностей U∞ в качестве «худшей» в значении sup{…} можно принять точку u = u = yo + v ∆ .

Нетрудно понять, что нижняя оценка для Wk (ω( f ,Uk ),u ) не понизится, если в U∞ добавить произвольные точки uk (yo + K(v,ϕ)), но uk Oε ( y0 ) .

Отсюда следует, что справедливость (4.94) можно теперь установить, оценивая снизу в выбранной точке u точную нижнюю грань значения Wk (ω( f ,Uk ),u ) по всем последовательностям U∞ , имеющим предельную точку

в y o и не пересекающимся с открытым коническим множеством yo + K (v,ϕ) .

Нетрудно видеть, что проверка выполнения (4.94) в указанных условиях эквивалентна доказательству того, что при соответствующем выборе β = tg(ϕ)

значение минимума в задаче

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

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

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

ρ2 (1−1α 2 )− 2 t ∆ + ∆2 = 0 ,

не должна иметь пересечений с границей допустимой области t = ρ γ . Таким образом, задача сводится к обеспечению отрицательности дискриминанта

гарантировать, что при сходимости подпоследовательности испытаний к

подпоследовательность измерений, целиком лежащая в этом конусе. Видно, что при α → ∞ угловой размер 2ϕ* соответствующих конусов стремиться к нулю.

РОВЕРКА УСЛОВИЙ ГЛОБАЛЬНОЙ СХОДИМОСТИ. Очевидно, что при ~ ≥ для

П L L

метода С.А. Пиявского выполнено условие (4.95), для которого в (4.91) можно принять

q(ω( f ,Yk ), y)= max{f ( yi ) − L y − yi : yi Yk }.

В силу теоремы 4.12 отсюда следует, что при ~ ≥ все предельные точки

L L

последовательности испытаний принадлежат множеству глобальных минимумов

Y *.

Если с некоторого шага оценка константы Липшица ~ > , то выполнено

L L

усиленное условие (4.96), где при ρ( y,Yk ) ≥ R > 0

Таким ~ > множество предельных точек последовательности образом, при L L

испытаний метода С.А. Пиявского совпадает с Y *. Рассмотрение примера закончено.

Итак, мы познакомились с теорией сходимости Т – представимых методов и проиллюстрировали ее положения на примере нескольких методов многоэкстремальной оптимизации.

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

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

4.6. Анализ относительной плотности размещения испытаний при всюду плотной сходимости

Аналитические методы анализа относительной плотности размещения испытаний являются необходимым инструментом исследования методов со всюду плотным характером сходимости. Сам факт всюду плотной сходимости ничем не отличает обладающие такой сходимостью методы от тривиального равномерного перебора, однако опубликованные результаты экспериментального исследования таких методов показывают их высокую эффективность [28, 33, 51]. Теория аналитического вывода оценок относительной плотности предложена в [15]. В этом разделе излагаются основы подхода на примере метода Х.Кушнера, а затем в обзорном плане — общая методика и результаты ее применения для ряда алгоритмов.

4.6.1. Необходимые понятия и обозначения

Воспользуемся еще раз определенным в (4.76) усечением U k последовательности U∞ произвольных попарно различных точек испытаний из D. Для y′ Uk введем для N >1 функцию ρ( y′,Uk ) расстояния от y′ до ближайшей

точки из U k не совпадающей с y′. В случае же размерности N=1 под ρ( y′,Uk ) будем понимать расстояние от y′ Uk до ближайшей справа точки из U k . Если

которая ниже будет часто применяться.

Эти обозначения иллюстрирует рис. 4.5, где жирными точками для N=2 и вертикальными штрихами для N=1 отмечены элементы множества Yk. Показано различие в трактовке обозначения ρ( y) для разных размерностей.

Для всюду плотно сходящихся процедур величины ρk ( y), y Yk являются бесконечно малыми при k→∞.

Рис. 4.5. Значения ρk ( y′) и ρk ( y′′) для размерности N=2 и N=1