Глава 3. Многомерная оптимизация с ограничениями 43

3.1 Классическая задача на условный экстремум 43

Рассмотрим задачу 43

(3.1) 43

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

Рассмотрим обобщенную функцию Лагранжа: 43

(3.2) 43

(3.3) 43

. Если в этой точке , то точка является точкой условного локального минимума. 44

3.2 Нелинейное программирование 44

Рассмотрим задачу 44

(3.5) 44

44

Перейдем от неравенств к равенствам, применив прием Валлентайна: 44

44

Рассмотрим обобщенную функцию Лагранжа 44

(3.6) 44

(3.7) 44

(3.8) 44

44

Из последнего соотношения, имеем 44

(3.9) 44

Из 3.8 и 3.9 получаем так называемые условия дополняющей нежесткости: 45

(3.10) 45

(3.11) 45

3.3 Классификация численных методов многомерной оптимизации при наличии ограничений 45

Снова рассмотрим задачу 45

(3.5) 45

45

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

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

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

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

В рамках единой методологии можно выделить несколько подходов. 46

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

Определение 19. Последовательность называется последовательностью внешних штрафных функций, если: 46

1. 46

2. 46

3. 46

4. 47

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

Определение 20. Последовательность называется последовательностью внутренних штрафных функций(барьерных функций), если: 47

1. 47

2. 47

3. 47

Где - все внутренние точки множества , а - граница множества. 47

3.4 Метод внешних штрафных функций 48

(3.5) 48

48

/ (3.12) 48

1.Задать: начальную точку ;точность ;;; 48

2. Составить вспомогательную функцию , где 48

49

3.5 Метод барьерных функций 50

1.Задать: начальную точку внутри области ;точность ;;;; 51

2.Составить вспомогательную функцию , где 51

или 51

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

(3.5) 52

52

Данный метод является комбинацией двух предыдущих: для ограничений типа равенств применяется метод внешних штрафных функций, а для ограничений неравенств – метод барьерных функций. 52

. 52

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

1.Задать: начальную точку так, чтобы ;точность ;;;; 53

2.Составить вспомогательную функцию , где 53

или 53

4. Справедливы замечания для внешних штрафных функций и для барьерных функций. 54

3.7 Метод множителей. 54

(3.5) 54

54

Данный метод аналогичен методу внешних штрафных функций, но штраф добавляется не к целевой функции, а к классической функции Лагранжа. 54

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

(3.18) 54

(3.19) 54

1. Задать: начальную точку точность ;;;; ит начальные значения параметра 54

2. Составить модифицированную функцию Лагранжа. 55

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

3.8 Метод точных штрафных функций 56

(3.5) 56

56

1. Задать: начальную точку точность ;- число решаемых задач безусловной минимизации.; ;;; 57

2. Составить вспомогательную функцию , где 57

для недифференцируемых штрафных функций или для дифференцируемых штрафных функций. 57

3.9 Метод проекции градиента 58

Хотя метод проекции градиента применяется в задачах поиска условного экстремума как для равенств, так и для неравенств, мы рассмотрим применение этого метода только в случае ограничений типа равенств: 58

(3.22) 58

а 58

1. Задать: начальную точку ; точность ;; 58

2. Если то ;конец;иначе 58

Литература 61