МЕТОДЫ ОПТИМИЗАЦИИ

Лектор: доцент Р. М. Ларин

6 семестр

1. Понятие о задачах оптимизации. Классификация задач конечномерной оптимизации.

2. Элементы выпуклого анализа. Выпуклые множества. Проекция точки на множество и ее свойства. Теоремы отделимости. Конус. Теорема Фаркаша. Выпуклые и строго выпуклые функции, их экстремальные свойства. Сильно выпуклые функции. Теорема о существовании и единственности оптимального решения.

3. Выпуклая условная оптимизация. Возможные направления и экстремальные свойства. Условия регулярности. Теорема о критерии оптимальности основной задачи выпуклого программирования. Седловая точка и условия ее существования. Теорема о седловой точке и равенстве минимаксов. Функция Лагранжа. Теорема Куна – Таккера. Общий случай и случай линейных ограничений.

4. Задача линейного программирования. Нормальная и каноническая форма задачи. Основные свойства задачи. Базисные решения. Существование оптимального базисного решения. Элементарные преобразования базиса. Симплекс-метод с использованием симплексных таблиц. Метод искусственного базиса для поиска базисного допустимого решения. Конечность симплекс-метода. Вырожденность. Лексикографический вариант симплекс-метода. Модифицированный симплекс-метод.

Двойственные задачи линейного программирования. Теоремы двойственности. Двойственный симплекс-метод и его лексикографический вариант.

5. Численные методы безусловной оптимизации. Понятие о скорости сходимости. Методы нулевого, первого и второго порядка. Градиентные методы. Метод наискорейшего спуска. Методы с регулировкой шага. Теоремы о сходимости градиентных методов. Метод Ньютона и его интерпретация. Теорема о квадратичной скорости сходимости. Модификация метода Ньютона.

6. Численные методы условной оптимизации. Метод возможных направлений. Теорема о сходимости метода.

Методы штрафных функций. Метод внешних штрафных функций. Теоремы о сходимости.

7. Корректные и некорректные задачи оптимизации. Нормальное решение. Метод регуляризации. Теоремы о сходимости метода.

Литература

  1. Карманов В. Г. Математическое программирование. М.: Наука, 1986.
  2. Глебов Н. И., Кочетов Ю. А., Плясунов А. В. Методы оптимизации /Учебное пособие /Новосиб. гос. ун-т. Новосибирск, 2000.
  3. Васильев Ф. П. Численные методы решения экстремальных задач. М.: Наука, 1980.

 

Программа практических занятий

1. Примеры задач конечномерной оптимизации.

2. Безусловная оптимизация. Необходимые и достаточные условия локального экстремума. Задачи о наибольшем и наименьшем значении ([1], Отдел II, § 13; Отдел VI, § 7).

3. Задачи с ограничениями–равенствами. Функция Лагранжа. Метод множителей Лагранжа. Решение задач с ограничениями–неравенствами ([1], Отдел VI, § 7).

4. Выпуклые функции и множества. Доказательство выпуклости специальных множеств и функций. Квазивыпуклые функции и их свойства ([2], Глава 1).

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

6. Задача линейного программирования. Эквивалентность различных форм задачи. Геометрическая интерпретация задачи. Базисные решения. Симплекс–таблица и критерий оптимальности ([2], Глава 4; [2], Глава 5, § 1,2).

7. Элементарные преобразования базиса. Алгоритм симплекс–метода. Геометрическая интерпретация ([2], Глава 5, § 3,4).

8. Метод искусственного базиса ([2], Глава 5, § 5).

9. Вырожденность. Зацикливание. Лексикографический вариант симплекс- метода ([2], Глава 5, § 6,7).

10. Двойственные задачи линейного программирования. Двойственный симплекс–метод. Геометрическая интерпретация ([2], Глава 6, § 1,2).

Литература

  1. Демидович Б. П. Сборник задач и упражнений по математическому анализу. М.: Наука,1972.
  2. Заславский Ю. Л. Сборник задач по линейному программированию. М.: Наука,1969.