Методы одномерной оптимизации

О.К. МУРГА

ЧИСЛЕННЫЕ МЕТОДЫ

ОПТИМИЗАЦИИ

Учебное пособие

Казань 2004

УДК 519.6

Мурга О.К. Численные методы оптимизации: Учебное пособие. Казань: Изд-во Казан. гос. техн. ун-та, 2004, 59 с.

ISBN

Пособие содержит подробное описание основных численных методов оптимизации, алгоритмов их реализации, необходимые методические указания для выполнения лабораторных работ. Предназначено для студентов, обучающихся по направлению “Информатика и вычислительная техника”, учебные планы которых предусматривают изучение дисциплины “Методы оптимизации”.

Табл. 3 Ил. 4 Библиогр.: 4 назв.

Рецензенты: кафедра математического анализа ( Казанский государствен-

ный педагогический университет);

канд. техн. наук А.Н. Козин (Академия управления

"ТИСБИ").

Рекомендовано к изданию Учебно-методическим центром

КГТУ им.А.Н. Туполева

ISBN С Изд-во Казан. гос.техн. ун-та, 2004.

С Мурга О.К., 2004.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.. 5

1. МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ.. 6

1.1. МЕТОДЫ ПЕРЕБОРА.. 7

1.1.1. Метод равномерного поиска. 7

1.1.2. Метод поразрядного поиска. 7

1.2. МЕТОДЫ ИСКЛЮЧЕНИЯ ОТРЕЗКОВ.. 8

1.2.1. Метод дихотомии. 8

1.2.2. Метод золотого сечения. 9

1.3. СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ОДНОМЕРНОГО ПОИСКА.. 11

1.4. ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ... 11

1.5. ЗАДАНИЯ ДЛЯ ЛАБОРАТОРНОЙ РАБОТЫ. 12

2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ.. 13

2.1. ПРЯМЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ.. 13

2.1.1. Поиск по правильному симплексу. 14

2.1.2. Поиск по деформируемому многограннику. 15

2.1.3. Типовой пример. 19

2.1.4. Порядок выполнения лабораторной работы.. 20

2.1.5. Задания для лабораторной работы.. 21

2.2 МЕТОДЫ ПОКООРДИНАТНОГО СПУСКА.. 21

2.2.1 Метод циклического покоординатного спуска. 21

2.2.2. Метод Зейделя. 23

2.2.3. Метод Хука-Дживса. 24

2.2.4. Метод Пауэлла. 25

2.2.5. Типовые примеры.. 25

2.2.6. Порядок выполнения лабораторной работы.. 28

2.2.7. Задания для лабораторной работы.. 29

2.3. ГРАДИЕНТНЫЕ МЕТОДЫ... 29

2.3.1. Метод градиентного спуска. 30

2.3.2. Метод наискорейшего спуска. 31

2.3.4. Порядок выполнения лабораторной работы.. 33

2.3.5. Задания для лабораторной работы.. 34

3. МЕТОДЫ ОПТИМИЗАЦИИ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ.. 35

3.1. МЕТОДЫ ПОСЛЕДОВАТЕЛЬНОЙ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ.. 36

3.1.1. Метод штрафных функций. 36

3.1.2. Метод барьерных функций. 37

3.1.3. Комбинированный метод штрафных функций. 38

3.1.4. Типовой пример. 38

3.1.5. Задание для лабораторной работы.. 39

3.2. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ.. 40

3.2.1. Постановка задачи выпуклого программирования. 40

3.2.2. Описание метода возможных направлений. 40

3.2.3. Построение начального приближения. 41

3.2.4. Выбор наилучшего подходящего направления. 43

3.2.5. Определение длины шага. 46

3.2.6. Типовой пример. 46

3.2.7. Задания для лабораторной работы.. 48

3.3. МЕТОД СЛУЧАЙНОГО ПОИСКА.. 48

3.3.1. Поиск с возвратом при неудачном шаге. 49

3.3.2. Алгоритм наилучшей пробы.. 50

3.3.3. Алгоритм статистичекого градиента. 50

3.3.4. Порядок выполнения работы.. 51

3.3.5. Задания для лабораторной работы.. 51

4. ПРИБЛИЖЁННОЕ РЕШЕНИЕ ЗАДАЧИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ.. 53

4.1. ПОСТАНОВКА ЗАДАЧИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ.. 53

4.2. ГРАДИЕНТНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ.. 53

4.2.1. Описание градиентного метода в функциональном пространстве. 53

4.2.2. Алгоритм метода. 55

4.2.3. Порядок выполнения лабораторной работы. 57

4.2.4. Задания для лабораторной работы. 58

СПИСОК ЛИТЕРАТУРЫ... 59

ВВЕДЕНИЕ

Пособие предназначено в помощь студентам, обучающимся по специальностям направления “Информатика и вычислительная техника“, при изучении ими дисциплины “Методы оптимизации”. Целью изучения данной дисциплины является практическое усвоение основных численных методов оптимизации, формирование умения и навыков их алгоритмической и программной реализации, анализа и исследования эффективности вычислительных процедур поиска решения.

В пособии приводится достаточно полное описание основных численных методов оптимизации и алгоритмов их реализации, подробно разбираются типовые примеры. Для усвоения материала предполагается выполнение лабораторных работ по изучаемым методам.

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

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

МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

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

Решить задачу одномерной оптимизации

min {f(x) | a £ x £ b} (1.1)

т.е. найти число x*[a ;b], такое что f(x*)  f(x), x[a;b].

Здесь a, b – заданные числа, причем a  b; функция одной переменной f(x) унимодальна на отрезке [a;b].

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

(x) = 0, (1.2)

находятся все стационарные точки на интервале (a;b). В найденных стационарных точках проверяется достаточное условие и выделяются из них точки локального минимума, в которых выполнилось условие

f " (x) > 0 . (1.3)

Далее сравниваются значения функции f(x) в выделенных точках и на концах отрезка [a,b]. Наименьшему из этих значений и будет соответствовать точка глобального минимума функции f(x) на отрезке [a,b].

Однако, даже если функция f(x) задана аналитически и производная (x) найдена, то решение уравнения (1.2) зачастую вызывает затруднения. Кроме того, вычисление производных может быть весьма трудоемко или же функция f(x) может быть задана не аналитически. Поэтому классический метод имеет ограниченное применение и для решения задачи (1.1) на практике, как правило, применяют приближенные методы.

Начнём изучение с простейших приближённых методов, позволяющих найти решение задачи (1.1) с необходимой точностью в результате определения конечного числа значений функции f(х) в некоторых точках отрезка [a ;b]. Такие методы называют прямыми методами одномерного поиска.

МЕТОДЫ ПЕРЕБОРА

Метод равномерного поиска

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

Отрезок [a ;b] разбивается на n равных частей точками деления

x_i = a + i×(b-a)/n, i=0,...,n. (1.4)

Сравнением значений функции f(x) во всех точках xi, , находится точка хk: 0  k  n, для которой

f(x_k)=min { f(x₀), f(x₁),… f(x_n)}. (1.5)

Полагая х^*xk , ff(xk), получается решение задачи (1.1) с погрешностью, не превосходящей величины

e_n= . (1.6)

Для того, чтобы обеспечить требуемую точность  определения точки x*, число n отрезков разбиения необходимо выбирать из условия n  , т.е. назначить

n ³ . (1.7)

Метод поразрядного поиска

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

Очевидно, если окажется, что f(x_i+1)  f(x_i), то отпадает необходимость вычислять f(x) в точках x_i+2, x_i+3,…, x_n, т.к. в силу унимодальности функции f(x) x*x_i+1. Кроме того, целесообразно сначала грубо определить отрезок, содержащий x^*, т.е. найти точку x^* с небольшой точностью, а затем искать её на этом отрезке с меньшим шагом, повышая точность. Реализация этих возможностей улучшения метода перебора и приводит к методу поразрядного поиска.

В методе поразрядного поиска перебор точек отрезка предлагается выполнять сначала с достаточно большим шагом h=x_i+1 - x_i ( например, h=(b - a)/4 ) до тех пор, пока не выполнится условие f(x_i+1)  f(x_i) или пока очередная точка не совпадет с концом отрезка. После этого шаг уменьшается и перебор точек с новым шагом производится в противоположном направлении до тех пор, пока значения функции снова не перестанут уменьшаться или пока очередная точка не совпадет с другим концом отрезка. Описанный процесс завершается, когда перебор в данном направлении закончен, а использованный при этом шаг h не превосходит .

Таким образом получается следующий алгоритм метода поразрядного поиска.

Шаг 0. Задать параметр точности   0, выбрать начальный шаг h=(b - a)/4, положить x₀=a, вычислить f(x₀).

Шаг 1. Найти очередную точку x₁= x₀+h, вычислить f(x₁).

Шаг 2. Сравнить значения функции f(x₀) и f(x₁). Если f(x₀)f(x₁), то перейти к шагу 3, иначе – к шагу 4.

Шаг 3. Положить x₀= x₁ и f(x₀)=f(x₁). Проверить условие x₀Î(a ;b ). Если

a<x₀<b, то перейти к шагу 1, иначе – к шагу 4.

Шаг 4. Проверить условие окончания поиска | h | £ e. Если оно выполняется, то вычисления завершить, положив х^*»x₀ , f^*»f(x₀), иначе–перейти к шагу 5.

Шаг 5. Изменить направление и шаг поиска, положив h=-h /4, x₀=x₁, f(x₀)=f(x₁). Перейти к шагу 1.