МО-Лекции

Министерство образования и науки Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Б. Ю. ЛЕМЕШКО

МЕТОДЫ

ОПТИМИЗАЦИИ

Утверждено Редакционно-издательским советом университета

в качестве конспекта лекций

НОВОСИБИРСК

2009

УДК 519.852(075.8)

Л 442

Рецензенты: д-р техн. наук, проф. А.А. Попов; д-р физ.-мат. наук, проф. В.А. Селезнев

Работа подготовлена на кафедре прикладной математики для студентов III курса ФПМИ (направление 010500 – Прикладная математика и информатика, специальности 010503 – Математическое обеспечение и администрирование информационных систем)

Лемешко Б.Ю.

Л 442 Методы оптимизации : конспект лекций / Б.Ю. Лемешко. – Новосибирск : Изд-во НГТУ, 2009. – 156 с.

ISBN 978-5-7782-1202-2

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

2

4

сурсом. Но все-таки с задачами без ограничений сталкиваются. Это бывает в условиях «неограниченных» ресурсов или в условиях, не накладывающих ограничений на переменные задачи. В таком случае мы имеем безусловную задачу, задачу без ограничений:

q j ( x ) , определяющих допустимую область. Функции могут быть ли-

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

Например, если функции f ( x ) и q j ( x ) линейны, имеем задачу ли-

нейного программирования и можем использовать для поиска решения методы линейного программирования (варианты симплекс-метода).

Если функции f ( x ) и q j ( x ) нелинейны, используем методы нели-

нейного программирования. Если при этом минимизируем выпуклую f ( x ) при выпуклых функциях q j ( x ) , то знаем, что задача одно-

экстремальна (выпуклое нелинейное программирование).

Если q j ( x ) линейна, а минимизируемая f ( x ) представляет собой

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

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

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

Если система ограничений отсутствует и f ( x ) представляет собой

нелинейную функцию, то для решения задачи (3), т. е. для определения минимума или максимума этой функции, используются различные алгоритмы поиска. В зависимости от информации о функции f ( x ) , ис-

6

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

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

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

Методы второго порядка при поиске решения используют информацию о самой функции и о ее производных первого и второго порядка. Сюда относятся метод Ньютона и его модификации.

1. МЕТОДЫ ОДНОМЕРНОГО ПОИСКА

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

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

1.1. МЕТОД ДИХОТОМИИ

Предполагается, что минимизируемая функция f ( x) унимодальна на отрезке [a0 , b0 ] , и необходимо найти минимум этой функции на

7

Рис. 1.1. Метод дихотомии

Затем сокращаем интервал неопределенности и получаем интервал

Далее по аналогичным формулам на этом интервале вычисляем

8

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

практически в два раза (при малых ).

1.2. МЕТОД ЗОЛОТОГО СЕЧЕНИЯ

Этот метод позволяет найти минимум унимодальной функции на заданной области [a0 , b0 ] , как правило, с меньшими вычислительными

затратами, чем метод дихотомии.

На первой итерации находим две точки по следующим формулам:

и вычисляем значения функции f (x1) и f (x2 ) .

Рис. 1.2. Методы золотого сечения, дихотомии и Фибоначчи

Обратим внимание, что на первой итерации находим две точки и дважды вычисляем f ( x) .

Сокращаем интервал неопределенности.

9

x1 x2 .

На последующих итерациях производим расчет только той точки и значение функции в ней, которые необходимо обновить: в случае 1)

На i -й итерации интервал неопределенности сокращается до величины 0.618 003 399(bi 1 ai 1) . Это меньше, чем в два раза, но зато всего один раз вычисляем значение f ( x) в новой точке.

1.3. МЕТОД ФИБОНАЧЧИ

Последовательность чисел Фибоначчи подчиняется соотношению:

Из этой формулы видно, что при больших значениях n выполняет-

10