full_book

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

множества базовых точек производится отбор l < L "лучших" точек, т.е. таких, в которых значения функции минимальны и точки не слишком близки друг к другу. Эти l точек и служат начальными точками локального поиска. Существует множество вариантов этой схемы. Например, семейство базовых точек может модифицироваться в процессе поиска – туда могут добавляться новые точки. Также в процессе реализации этой схемы может изменяться схема отбора точек с учетом вновь поступившей информации и т.п.

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

{y k } , порождаемой алгоритмом, и, следовательно, для непрерывной функции

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

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

По сравнению с редукцией к локальным задачам более плодотворным является подход, основанный на идеях редукции размерности, т.е. построение таких схем, когда решение многомерной задачи сводится к решению одной или нескольких одномерных подзадач. Известны две эффективные схемы такого рода: многошаговая схема оптимизации [7, 9, 42] и редукция размерности на основе кривых, заполняющих пространство (кривых Пеано) [7, 9].

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

Вторая из указанных схем основана на известном фундаментальном факте, согласно которому N -мерный гиперпараллелепипед (5.3) и отрезок [0, 1]

вещественной оси являются равномощными множествами и отрезок [0, 1] может

быть однозначно и непрерывно отображен на гиперпараллелепипед (5.3) [29]. Отображения такого рода обычно называют кривыми, или развертками Пеано.

Пусть y(x), x [0 ,1], есть кривая Пеано и функция f ( y) из (5.1) непрерывна. Тогда из непрерывности f ( y) и y(x) и равенства

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

D = {y(x) : 0 ≤ x ≤1}

следует, что

т.е. решение многомерной задачи минимизации f ( y) сводится к минимизации одномерной функции f ( y(x)) .

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

5.3. Многошаговая схема редукции размерности

Рассмотрим в качестве исходной задачу (5.1)-(5.3) в варианте, когда все

Последняя функция тождественно равна нулю в области Y . Введем обозначения

определенных в соответствующих проекциях

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

множества D из (5.3) на координатные оси y1 ,..., yi , причем по определению

DN = D .

В силу непрерывности функции G N ( y) ≡ G( y) и компактности области D функция G N −1 (uN −1 ) существует и непрерывна в DN −1 , что влечет существование

инепрерывность функции G N −2 (uN −2 ) и т.д. определяет существование и

непрерывность всех функций семейства (5.11). Справедлива следующая

Лемма 5.1. Справедливо соотношение

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

проекции Πi+1 (ui ) в смысле определения (5.10).

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

1. Докажите, что сечение Si+1 (ui ) не пусто тогда и только тогда, когда

Gi (ui ) ≤ 0 .

определенных на соответствующих проекциях Yi . Тогда имеет место основное соотношение

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

Эта задача является одномерной задачей минимизации по y2 , т.к. y1 фиксировано.

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

при фиксированном uN −1 .

Окончательно решение задачи (5.1) – (5.3) сводится к решению семейства "вложенных" одномерных подзадач

где фиксированный вектор ui−1 Yi−1 .

Решение исходной многомерной задачи (5.1) – (5.3) через решение системы взаимосвязанных одномерных подзадач (5.26) называется многошаговой схемой редукции размерности.

Заметим, что если в задачах (5.26) по некоторым координатам yi искать не

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

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

Пример 5.1. Рассмотрим двумерную задачу (5.1) – (5.3), в которой

Рис. 5.1. Иллюстрация к примеру на метод редукции по многошаговой схеме

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

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

В этой задаче функция G 2 ( y) = ( y1 −1)2 + ( y2 −1)2 −1, а функция

G1 ( y) = min{G 2 ( y1 , y2 : y2 [0,2]} = ( y1 −1)2 −1,

областей задаются корнями указанных функций, принадлежащими отрезку [0,2]. Для функции G1 ( y1 ) такими корнями являются значения 0 и 2, поэтому

Π1 = [0,2] .

Функция G 2 ( y) = ( y2 −1)2 −α 2 , где α = 1 − ( y1 −1)2 ≤1, имеет корни 1 ±α , очевидно принадлежащие отрезку [0,2], и неположительна между этими корнями,

поэтому

f ( y* ) = 3 − 2 2 . На рисунке координата оптимума помечена точкой на соприкосновении границы допустимой области с одной из линий уровня.

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

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

функций Gi (ui ) . Вместе с тем можно указать более наглядный "геометрический" способ построения проекций Πi+1 (ui ) . Собственно, этот способ вытекает из

определений (5.9) и (5.10) и состоит в том, что необходимо построить сечения области Y плоскостями ui = const и затем установить границы этих сечений по

координате yi+1 .

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

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

Πi+1 (ui ) .

Для иллюстрации рассмотрим следующий Пример 5.2. Пусть область оптимизации (или интегрирования) задается как

Ее вид показан на рис. 5.2.

Серый цвет, как и ранее, помечает допустимую область. Сплошная прямая y1 = const на пересечении с допустимой областью формирует сечение S1 ( y1 ) , а

его проектирование на ось y2 определяет проекцию Π2 ( y1 ) . Данная проекция в виде двух отрезков на оси y2 , а также проекция Π1 на оси y1 отмечены на рисунке утолщенными линиями.

Рис. 5.2. Иллюстрация к построению проекций

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

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

2. Решите аналитически задачу минимизации функции f ( y) = y12 + y22 в области (5.29).

Рассмотренные примеры являются достаточно простыми в том смысле, что нам удалось в явном виде выписать границы областей одномерного поиска – проекций Πi - и аналитически решить одномерные задачи (5.18). Реальные

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

Обратим внимание, что при анализе одномерных подзадач многошаговой схемы возникают две проблемы:

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

Πi (ui−1 ) ;

б) требуется обеспечить минимизацию одномерных функций f i (ui−1 , yi ) в

областях Πi (ui−1 ) .

Структура и сложность проекций Πi (ui−1 ) полностью определяются сложностью многомерной допустимой области Y . Сложность второй проблемы зависит от характеристик функций f i (ui ) , на которые влияют как свойства целевой функции f ( y) , так и особенности области поиска Y , определяемые ограничениями (5.2), (5.3).

5.4. Свойства одномерных подзадач многошаговой схемы

5.4.1. Структура допустимых областей одномерного поиска

Для анализа структуры областей Πi (ui−1 ) используем результаты Леммы

5.3, которая установила эквивалентность определения (5.10) и представления (5.17). Дело в том, что (5.17) дает конструктивный аппарат построения области

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

j=1

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

Рис. 5.3. Различные способы порождения областей неположительности непрерывной функции

В системе (5.31) число q отрезков может быть бесконечным. В качестве примера подобной ситуации приведем функцию

Таким образом, в случае непрерывной функции G( y) проекция из (5.26) есть множество вида (5.31), т.е.

qi

Πi (ui−1 ) = U[aij , bij ]

(аналитические) выражения для величин qi , aij , bij как функций ui−1 Yi−1 , тогда

область Y называется областью с вычислимой границей. Образцы таких областей приведены в примерах 5.1 и 5.2. Для построения данных областей необходимо

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

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

в которой корни g(x) являются точками глобального минимума. Для решения

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

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

Практически важным частным случаем задачи (5.1) – (5.3) является случай Y = D , когда функциональные ограничения (5.2) отсутствуют. В данной ситуации

где ai , bi - константы.

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

Определение 5.1. Функция g( y) называется выпуклой (вниз) в выпуклой области