full_book

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

Рис. 5.13. Разбиение области по схеме Я.Д. Сергеева и вид адаптивной диагональной кривой

Поскольку кривая может иметь самопересечения (например, T1 = T7 , T18 =T6 , T11 = T16 ), то реализация метода требует организации такой системы хранения

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

Использование адаптивных диагональных кривых является одним из перспективных направлений в области глобальной оптимизации.

5.7.4. Компонентные методы, основанные на триангуляции области поиска

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

Триангуляционные методы, предложенные в [19], используют адаптивное разбиение области D на многогранники Si с (N+1)-вершинами, образующими симплексы и порождающими триангуляцию области. Особенностью подхода является то, что множество вершин всех многогранников Si совпадает с Yk — множеством точек всех проведенных испытаний. Характеристика R(i) для каждой компоненты Si вычисляется при использовании совокупности размещенных в вершинах Si (N+1)-го испытания функции f, что позволяет более полно учитывать поисковую информацию.

Поскольку точки используемых в Si измерений образуют N-мерные симплексы, то такие методы можно назвать симплекс–методами многоэкстремальной оптимизации или SM-методами.

SM–методы построены для двух классов целевых функций f: класса липшицевых функций Ф=Lip(D) и класса дифференцируемых функций с липшицевой производной по направлениям

y`≠ y`` D и v = (y`– y``)/|| y`– y``||: | ∂Q(y`)/∂v – ∂Q( y``)/∂v |≤ L*|| y`– y``||. (5.77)

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

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

ПРИНЦИПИАЛЬНАЯ СХЕМА АЛГОРИТМА

ШАГ 1. Задаются параметры метода k. Начальные испытания проводятся во всех вершинах D, его геометрическом центре и, в зависимости от размерности задачи N и выбранного вида начальной триангуляции, — в центрах граней D определенных размерностей. Строится начальное разбиение, определяющее триангуляцию D. Вершины компонент Si симплекс–разбиения размещаются в точках проведенных испытаний. Запоминается k — количество выполненных испытаний и nk — количество симплексов разбиения.

ШАГ 2. Для каждой из компонент Si оценивается константа класса L, получается ее локальная оценка l(Si). Вычисляется глобальная (общая) оценка константы класса

l*k = max{ l(Si): i=1,..,nk }

и ее завышенная оценка L*k, лежащая в пределах γ2*l*k/γ1≤ L*k ≤ γ2*l*k при l*k>0 и равная 1 при l*k=0 (1<γ1<γ2). По этим характеристикам определяется локализованная оценка L(Si) константы класса, используемая для компоненты Si при вычислении ее приоритета.

L(Si)=max{ L*, Li},

где L*>0 — вычисляемая по всем l(Si) заниженная общая оценка константы класса, а Li – скорректированное взвешенное среднее между завышенной локальной оценкой γ2* l(Si) / γ1 и завышенной глобальной L*k. Весовые коэффициенты зависят от диаметра d(Si) компоненты Si и заданного порогового значения d* для этого диаметра: Li=L*k, при d(Si)>d*, а в противном случае,

Li=(γ2*l(Si)/γ1)(1–d(Si)/d*) + + L*k (d(Si)/d*).

ШАГ 3. Для всех компонент Si симплекс–разбиения с использованием L(Si), — локализованных оценок констант класса, вычисляются характеристики R(i)=R(Si)

компоненты St так, что делит его в пропорции ν, где 0< ν*≤ ν ≤ (1–ν*), ν* —

заданный параметр метода (0<ν*≤ 0,5).

ШАГ 5. Проводится испытание в выбранной точке, пополняется множество

точек испытаний и их результатов Yk+1=Yk {yk+1}, ωk+1=ωk {(f,yk+1)}, компонента Stkk разделяется на две новые с помощью точки yk+1. Определяются

все остальные компоненты Si разбиения, содержащие ребро rt (это можно сделать без полного перебора компонент). Выполняется их разделение на две части с использованием в качестве их новой вершины точки выполненного последнего испытания. Предпринимаются дополнительные действия, описанные в [19], по обеспечению условия Rmin(Si)/Rmax(Si)>β, где 0<β<<1 — параметр метода, а Rmin, Rmax — длины наибольшего и наименьшего ребра многогранника Si (их отношение характеризует степень вырождения Si). Возникает новое разбиение области D. Далее полагается k=k+1, корректируется число компонент и выполняется переход на шаг 2.

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

)Замечание.

1.В алгоритм обычно встраивается дополнительное адаптивное преобразование функции решаемой задачи, улучшающее ее свойства [19].

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

Приведенная принципиальная схема требует конкретизации способа вычисления локальных оценок параметров класса функций, а также способа подсчета характеристик компонент R(i). Эти две части метода существенно зависят от свойств класса функций. Здесь они будут кратко описаны для липшицевых функций (класс Lip(D) ). Читателей, интересующихся учетом измерений градиента в SM–методах при оптимизации функций из класса (5.77) адресуем к работе [20].

Итак, рассмотрим класс функций Lip(D). Одну из компонент разбиения обозначим через S, ее вершины — через v0,…,vN, а результаты испытаний — через f 0,…,f N. Локальную оценку константы L для S обозначим через l(S), а локализованную — через L(S). Способы вычисления локализованных оценок по локальным приведены в описанной выше принципиальной структуре алгоритма.

Локальная оценка определяется согласно соотношению

l(S) = max { | f i – f j | / || vi – vj ||: i=0,…,N-1; j=i+1,…,N }.

Значение функции приоритета будем строить как оценку минимума миноранты

f –s(y) =max{f j – L(S)||v j – y||: v j S}

функции f в S, по результатам испытаний f в вершинах S. Для вычисления характеристики R(S) компоненты S вводится функция

В [19] описан вычислительный метод решения (5.78), основанный на сведении к линейной системе. Решения обозначим через C(S) и y(S). В [19] доказано, что для

класса Lip(D) при y(S) S выполняется: C(S)=min{ f –s(y) : y S}. Эта ситуация показана на рис.5.14 слева.

Рис.5.14. Нижние оценки функции по измерениям в вершинах симплекса S

Если же y(S) S, то для уже вычисленных C(S) и y(S) методами квадратичного программирования определяется значение Ψ –(S) = min{ Ψ( v, C(S), y(S) ): v S }, а

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

также определяется f –r(S) — минимум миноранты f –s(y) на ребрах S. Окончательно получим следующее правило вычисления характеристики компоненты

Геометрическая иллюстрация для двух случаев приведена на рис.5.14.

Вычислительные иллюстрации

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

y1, y2 [–2;2].

решенная SM–методом при следующих параметрах γ1=1.2, γ2=1.8, d*=0.1 diam(D),

εx=0.01.

На правом рисунке показано размещение точек при решении задачи

Рис.5.15. Размещение точек испытаний SM–методом

На рис.5.16 показана триангуляция области D, построенная SM–методом на некотором промежуточном шаге в процессе решения задачи (5.80) с двумя глобальными минимумами.

Рис.5.16. Триангуляция области, построенная SM–методом в задаче (5.80)

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

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

На рисунке видно, как процесс триангуляции адаптируется к структуре решаемой задачи.

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

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

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

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

В разделе 1.3 второй главы были введены понятия решений по Парето и Слейтеру (см. определение 1.4) для задач (1.21)–(1.23) с векторным критерием.

Напомним, что в пунктах 1.3.2–1.3.6 рассматривались различные схемы компромисса и было показано, что их использование приводит к параметрической скаляризации векторной задачи с использованием некоторой функции свертки. При заданных параметрах используемого метода скаляризации из решения возникающей вспомогательной оптимизационной задачи находится одно из эффективных y* или слабо эффективных yo решений исходной задачи. Изменяя значения параметров, можно последовательно (поочередно) определять оценки

различных решений из множеств Y* или Yo.

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

Материал лекции, в основном, опирается на результаты, приведенные в работах Евтушенко Ю.Г. и Потапова М.А. (см. [24], а также более подробный вариант изложения в [25]), работах Городецкого С.Ю.[17,18], а также Маркина Д.Л. и Стронгина Р.Г. [30].

Далее будет описано несколько близких подходов, представленных в этих работах:

•метод неравномерных покрытий Евтушенко Ю.Г. и Потапова М.А.,

позволяющий строить ε – оптимальные оценки всего множества эффективных точек Y*;

•метод построения перестраиваемого семейства непараметрических

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

семейство одношагово–оптимальных методов для оценивания множества Yo в целом (результат Городецкого С.Ю.);

•метод построения непараметрической свертки, порождающей скалярную задачу, множество точек глобальных минимумов которой совпадает с множеством слабо эффективных точек исходной задачи (результат Маркина Д.Л., Стронгина Р.Г.).

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

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

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

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

Напомним некоторые из ранее использованных обозначений, а также добавим новые. Пусть F = f(Y) = {z = f(y): y Y} — множество возможных векторных оценок, Yk = {y j: y j Y (j = 1,…k)} — множество точек выполненных измерений вектор–функции f, а Fk = f(Yk) = {z j = f(y j): y j Yk} — множество результатов этих измерений. В пункте 1.3.2. были использованы операторы P и S, определенные на множествах оценок и выделяющие из них подмножества Парето и Слейтера. При этом P(F) и S(F) — будут множествами Парето и Слейтера исходной задачи, а их прообразы при отображении f (обозначаемые через

Y* и Yo) —множествами эффективных и слабо эффективных точек в пространстве параметров. Кроме того, P(Fk), S(Fk) — будут аппроксимациями множеств Парето и Слейтера, построенными по конечному набору вычисленных векторных оценок Fk, а прообразы этих множеств, порождаемые какой–либо однозначной ветвью

отображения f –1(обозначим их через Yk*, Yko), — будут текущими оценками множеств Y*, Yo.

Приведем алгоритм построения таких оценок на примере Yko.

РЕКУРРЕНТНЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ОЦЕНОЧНЫХ МНОЖЕСТВ Yko.

ШАГ 0. Вначале полагается Yko = {y1}, k = 1

ШАГ 1. Появляется результат очередного измерения f k+1, выполненного в точке

y k+1.

ШАГ 2. Если y j Yko (0< j≤ k), что f k+1< f j, то все такие точки y j исключаются из Yko, а точка y k+1 включается в Yko, затем полагается Y ok+1=Yko. Иначе, если y j Yko

(0< j≤ k), что f j < f k+1, то полагается Y ok+1=Yko, иначе y k+1 добавляется к Yko, т.е.

Y ok+1=Yko {y k+1}.

ШАГ 3. Принимается k:=k+1 и выполняется переход на шаг 1.

6.1. Основные принципы непараметрической скаляризации

В пункте 1.3.7 было дано определение 1.6 множества Yε* — ε – оптимальных (по Парето) решений задачи. Приведем его незначительную модификацию, необходимую для дальнейшего изложения, и дополним определением ε – оптимального решения по Слейтеру.

Определение 6.1. Пусть e Rn, e>0 и ||e||=1, ε >0. Множество Y*ε Y будем

называть ε – оптимальным по Парето решением задачи (6.1), еслиy* Y* yε* Yε*, что f(yε*)≤ f(y*)+ε e и в Yε* нет двух разных точек yε*1, yε*2, что

Множество Yεo Y будем называть ε – оптимальным по Слейтеру решением

задачи (6.1), если yo Yo yεo Yεo, что f(yεo)≤ f(yo)+ε e, и в Yεo нет двух разных точек yεo1≠ yεo2, что f(yεo1)= f(yεo2) или f(yεo1)< f(yεo2).

6.1.1. Метод сведения к скалярной задаче с перестраиваемой целевой функцией

Рассмотрим идею построения ε – оптимального решения, следуя работам

[24, 25].

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

Пусть ~ n — некоторое замкнутое множество точек в пространстве

R

Z

оценок. Введем специальную функцию

Ей можно дать следующую геометрическую интерпретацию. Рассмотрим введенное в разделе 1.3.5. множество

параллельным сдвигом на вектор –Ce, будет совпадать с геометрическим местом

точек, где ρ ~ = (рис. 6.1).

C

)

Z

,

z

(

Рис.6. 1. Структура изолиний функции ρ ~ (z, Z )

~

Используем теперь в качестве Z конечное слейтеровское подмножество S(Fk) результатов выполненных измерений. Рассмотрим семейство поверхностей

показанных на рис.6.2.

Рис.6. 2. Вид оценок P(Fk ) и S(Fk ) и область «улучшения» на величину от 0 до C

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

Имеют место несколько очевидных свойств.

Свойство 6.1. Пусть z j Fk . При этом z j S(Fk ) тогда и только тогда, когда

ρ( z, S(Fk ))=0, т.е. z j ∂ C=0.

Свойство 6.2. Если для точки y Y значение ρ( f(y), S(Fk ))=C >0, то включение в Fk дополнительного значения z=f(y) приведет к смещению участка поверхности ∂ C=0 на величину C вдоль направления ( – e).

Описанная в свойстве 6.2 ситуация эквивалентна соответствующему улучшению текущей оценки множества Слейтера S(Fk ).

)Замечание. Функцию ρ( z, S(Fk )) можно трактовать как меру улучшения оценки множества Слейтера S(Fk ) за счет учета результата z=f(y) очередного измерения векторного критерия.

Введем непараметрическую функцию свертки

уменьшение значений которой эквивалентно соответствующему увеличению значения меры ρ(.).

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

рекуррентному алгоритму построения оценочных множеств (см. алгоритм перед разделом 6.1), являлось ε –оптимальным (по Слейтеру) решением задачи (6.1) необходимо и достаточно, чтобы zo S(F )

НЕОБХОДИМОСТЬ. Пусть Yko — ε–оптимальное по Слейтеру решение. Возьмем произвольное zo S(F ). При этом найдутся yo Yo, что zo=f(yo). По определению 6.1, для yo Yo yko Yko, что f(yko)≤ f(yo)+ε e и, следовательно,

i =1,..., n ( fi ( yko ) − fi ( yo ) )ei ≤ ε .

Отсюда следует, что

ρ(zo , f (Yko ))= min max((fi ( y) − fi ( yo )) ei )≤ ε .

y Yko 1≤ i ≤n

Далее, поскольку для zo=f(yo) S(F ) не существует точки y Y, что f(y)< f(yo), тоy Y выполнится неравенство

max((fi ( y) − fi ( yo )) ei )≥ 0 .

1≤ i ≤n