full_book

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

Возьмем два произвольных вектора ui′,ui′′ Yi . Тогда существуют вектора

vi′, vi′′ такие, что y′ = (ui′,vi′), y′′ = (ui′′,vi′′) Y . Но тогда для любого α [0,1] вектор

αy′ + (1 −α) y′′= (αu′+ (1−α)u′′,αv′+ (1−α)v′′) Y , т.е. вектор αu′+ (1−α)u′′ Yi . 3). Покажем, что функция (5.6) выпукла в D .

Для любой точки αy + (1 −α)z , α [0,1], y, z D , существует номер s такой, что

G( αy + (1−α)z ) = gs (αy + (1−α)z) ≤αgs ( y) + (1−α)gs (z) ≤ ≤α max{g1 ( y),..., gm ( y)}+ (1−α) max{g1 (z),..., gm (z)} =

=αG( y) + (1−α)G(z)

= αGi (ui′) + (1 −α)Gi (ui′′)

5). Так как функция Gi+1 (ui+1 ) выпукла по совокупности переменных ui+1 , то

функция G~i+1 (ui+1 ) выпукла и непрерывна как функция максимума от двух

выпуклых непрерывных функций. Из выпуклого анализа известно [5], что множество оптимальных точек выпуклой функции на выпуклом множестве также выпукло. В одномерном случае выпуклое множество – это отрезок или

~i+1

(полу)интервал. Так как функция G (ui+1 ) непрерывна по yi+1 , то множество ее оптимальных точек на [ai+1 ,bi+1 ] является отрезком.

Теорема доказана.

Проекции Πi+1 (ui ) могут являться отрезками (5.37) не только в случае

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

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

Определение 5.2. Пусть h(γ ) = (h1 (γ ),..., hN (γ )),γ [0,1] , есть параметризованная

кривая, соединяющая две точки гиперпараллелепипеда D . Эта кривая называется монотонной, если каждая ее координатная функция hi (γ ) является

монотонной (одномерной) функцией аргумента γ [0,1] .

Определение 5.3. Функция g( y) называется монотонно унимодальной в D , если

для любых двух точек из D существует монотонная кривая h , соединяющая эти точки и такая, что неотрицательная функция

g+ (γ ) = max{0; g(h(γ ))}, λ [0,1] ,

либо является унимодальной (вниз), либо она тождественно равна нулю в подынтервале [γ1 ,γ 2 ] [0,1] и строго монотонна на отрезках [0,γ1 ] и [γ 2 ,1], убывая на первом из них и возрастая на втором.

Определение 5.4. Ограничения (5.2) называются монотонно унимодальными в D

Примеры.

1.Любая унимодальная (вниз) функция является монотонно унимодальной.

2.Любая выпуклая функция является монотонно унимодальной в D . В качестве кривой h(γ ) можно взять отрезок. Более того, любой набор выпуклых на

Dфункций будет монотонно унимодальным в совокупности.

3.Пусть

D = {y R2 : yi [0,1],i =1,2} .

Рассмотрим два ограничения: g1 ( y) = y12 + y22 − 0.81 и g2 ( y) = 0.25 − y12 − y22 .

Данные ограничения, являясь монотонно унимодальными в совокупности, порождают в (5.2) невыпуклую допустимую область Y .

фиксированном ui−1 , и для решения подзадач (5.26) определяющим является характер зависимости функции f i от переменной yi .

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

т.е.

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

f( y) = ∑ fi ( yi ) ,(5.38)

i=1N

а функциональные ограничения g j ( y) отсутствуют, т.е. Y = D . Тогда, как следует из (5.19), (5.38),

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

положительный.

Рассмотрим следующий пример. Пусть в задаче (5.1) – (5.3) целевая функция f ( y) удовлетворяет условию Липшица (5.39), а область Y имеет вид

Следующая теорема [7] устанавливает достаточные условия липшицевости функций f i (ui ) .

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

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

Комментарии к теореме.

1.Представление граничных пар в виде (5.40), (5.41) имеет место, если область является выпуклым многогранником.

2.Если область Y является гиперпараллелепипедом, то все вектора αiν , βiν

нулевые, и поэтому Li = L , 1 ≤ i ≤ N .

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

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

Наконец, случай нелинейных ограничений может вообще привести к потере липшицевости.

5.5. Редукция размерности на основе кривых Пеано

Рассмотрим кривую Пеано y(x), x [0 ,1], отображающую однозначно и

непрерывно отрезок вещественной оси на многомерный гиперпараллелепипед

(5.3), т.е.

Вместе с тем эта возможность может быть реализована только при наличии алгоритмического способа реализации развертки y(x) . Рассмотрим одну из схем

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

Указанное построение формирует непрерывное и однозначное отображение

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

Предлагаемое построение приведено, например, в [7] и состоит в следующем.

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

1. Сначала гиперкуб D из (5.45) , длина ребра которого равна 1, разделяется координатными плоскостями на 2N гиперкубов так называемого первого разбиения (с длиной ребра, равной ½), которые занумеруем числами z1 от 0 до

2N −1, причем гиперкуб первого разбиения с номером z1 условимся обозначать

через D(z1 ) .

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

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

числами z2 от 0 до 2N −1, причем гиперкуб второго разбиения с номером z2 , входящий в D(z1 ) , условимся обозначать черезD(z1 , z2 ) .

Продолжая указанный процесс, можно построить гиперкубы любого p -го разбиения с длиной ребра, равной (1/ 2) p , которые условимся обозначать через

D(z1 ,..., z p ) , причем

D(z1 ) D(z1 , z2 ) ... D(z1 ,..., z p ) и 0 ≤ z j ≤ 2N −1, 1 ≤ j ≤ p .

2. Теперь осуществим деление отрезка [0,1] на 2N равных частей, каждую из которых в свою очередь также разделим на 2N равных частей и т.д., причем элементы каждого разбиения будем нумеровать слева направо числами z j ( j -

номер разбиения) от 0 до 2N −1. При этом интервалы p -го разбиения условимся обозначать как d(z1 ,..., z p ) , где, например, d (z1 , z2 ) обозначает интервал второго разбиения с номером z2 , являющийся частью интервала d (z1 ) первого разбиения с номером z1 . Заметим, что

d(z1 ) d(z1 , z2 ) ... d(z1 ,..., z p )

и длина интервала d(z1 ,..., z p ) равна (1/ 2) pN .

Предполагается, что интервал d(z1 ,..., z p ) содержит свой левый конец; он содержит правый конец тогда и только тогда, когда

x d(z1 ,..., z p ) → y(x) D(z1 ,..., z p ) .

Построенное соответствие y(x) является однозначным.

4. Для любого x d(z1 ,..., z p ) справедливо, что

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

Следовательно, если представить x в виде двоичного числа с фиксированной запятой, т.е.

i=0 , (5.47)

где αN j−i из (5.46). Таким образом, точка y(x) может быть оценена с точностью (1/ 2) p+1 по каждой координате, если известно (5.47).

5. Чтобы построенное отображение было вдобавок непрерывным, наложим

Введенное отношение устанавливает совершенный строгий порядок на множестве различных векторов z p . Минимальным элементом при этом является вектор (0 , . . . , 0), а максимальным - вектор ( 2N −1, . . . , 2N −1). Порядок данного вида фактически задает лексикографическое упорядочение векторов z p .

где p - символ отношения предшествования.

Рис. 5.4. Нимерация гиперкубов при построении первых двух приближений кривой Пеано

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

Для непрерывности построенного отображения достаточно выбрать такую нумерацию, чтобы смежные гиперкубы любого p -го разбиения ( p ≥1) имели

общую грань. Тогда, устремляя p к бесконечности, в пределе получим непрерывную кривую Пеано, заполняющую гиперкуб D .

Существуют различные способы требуемой нумерации, детальное описание которых можно найти, например, в [7]. Продемонстрируем на примере, взятом из [11], один из вариантов такой нумерации (рис. 5.4, 5.5).

Рис. 5.5. Следующее приближение кривой Пеано

Построенное отображение Пеано не обеспечивает взаимно однозначное соответствие между отрезком [0,1] и N -мерным гиперкубом (5.45), потому что точка y D ={y(x) : x [0,1]} может иметь несколько прообразов в отрезке [0,1],

но не более, чем 2N . Кратность точек y D при соответствии y(x) является

фундаментальным свойством, отражающим сущность понятия размерности: отрезок [0,1] и гиперкуб D являются равномощными множествами, первое из них можно однозначно отобразить на второе, но если такое отображение непрерывно, то оно не может быть взаимно однозначным. При этом размерность N гиперкуба

определяет возможную кратность ( 2N ) для отображения y(x) . Если вернуться к использованию разверток для целей оптимизации, то это означает, что точка y* глобального минимума функции f ( y) в гиперкубе D может порождать несколько точек xs* глобального минимума функции f ( y(x)) в отрезке [0,1] таких, что y* = y(xs* ) .

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

Теорема 5.4. [7] Пусть f ( y) есть липшицева с константой L функция, определенная в области D из (5.45). Тогда функция f ( y(x)), x [0,1], где y(x)

есть непрерывное однозначное отображение со свойствами 1-5, удовлетворяет условию

характеристические алгоритмы, ориентированные на минимизацию липшицевых функций, заменив в их решающих правилах "евклидово" расстояние x′− x′′ на

расстояние (5.51). Так, для информационно-статистического алгоритма глобального поиска АГП его модификация – многомерный обобщенный алгоритм глобального поиска (МОАГП) – содержит характеристику

Точка очередного испытания в МОАГП вычисляется согласно выражению

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

Нетрудно показать, что МОАГП удовлетворяет условиям теорем 4.1, 4.4, а при m >16L N и достаточным условиям сходимости теоремы 4.5.

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

Пеаноподобная развертка. Сначала остановимся на кусочно-линейной развертке из [7]. Согласно выполненной ранее схеме построения 2 pN центров y(z1 ,..., z p ) гиперкубов p -го разбиения D(z1 ,..., z p ) образуют равномерную

ортогональную сетку H ( p, N ) в гиперкубе D из (5.45). Шаг этой сетки (по любой

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

хуже 2− p по каждой координате к кривой Пеано. На рис. 5.6 изображен образ отрезка [0,1] при соответствии q(x) для двухмерного пространства и разбиения 3

порядка.

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

Рис. 5.6. Образ отрезка [0,1] при отображении пеаноподобной разверткой при разбиении третьего порядка

Введенное отображение q(x) сопоставляет минимизируемой многомерной

и приближенное решение многомерной задачи сводится к решению задачи одномерной, где функция f (q(x)) удовлетворяет обобщенному условию

Липшица в метрике (5.51) (доказательство аналогично доказательству Теоремы 5.4). Из этого следует, что для решения одномерной задачи можно использовать обобщенные на метрику (5.51) алгоритмы типа алгоритма МОАГП (5.52), (5.53).

Простые кусочно-линейные развертки. Наряду с пеаноподобной кусочно-

линейной разверткой можно рассмотреть более простые непрерывные развертки, покрывающие сетку H ( p, N ) , для которых остается в силе соотношение (5.56). В

качестве таких разверток можно взять, например, так называемую "телевизионную" кривую или спиральную развертку (см. рис. 5.7).

Рис. 5.7. Примеры простых кусочно–линейных разверток

Вместе с тем простые кусочно-линейные развертки t(x) имеют один

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

покрывающие большое число (до 2 p ) узлов сетки H ( p, N ) . Это приводит к тому,