- •Элементы выпуклого анализа.
- •Начальные сведения о численных методах оптимизации.
- •4.Сходимость методов оптимизации.
- •5.Метод покоординатного спуска.
- •6.Метод случайного поиска. Алгоритм с возвратом при неудачном шаге.
- •7. Метод случайного поиска. Алгоритм наилучшей пробы.
- •8. Метод случайного поиска. Алгоритм статистического градиента.
- •9. Метод случайного поиска. Алгоритм покоординатного обучения.
- •10. Градиентный метод. Метод с постоянным шагом.
- •11. Градиентный метод. Метод с дроблением шага.
- •12. Градиентный метод. Метод наискорейшего спуска.
- •13. Метод Ньютона
- •14. Численные методы решения задач линейного программирования. Прямой симплекс-метод. Базис и базисное решение.
- •15. Численные методы решения задач линейного программирования. Прямой симплекс-метод. Элементарные преобразования. Симплекс-таблицы.
- •16. Численные методы решения задач линейного программирования. Прямой симплекс-метод. Алгоритм симплекс-метода.
- •17. Численные методы решения задач линейного программирования. Модифицированный симплекс-метод.
- •18. Численные методы решения задач линейного программирования. Лексикографический прямой симплекс-метод
- •19. Численные методы решения задач линейного программирования. Двойственный симплекс-метод.
- •20. Численные методы решения задач линейного программирования. Двойственный симплекс-метод.
- •22. Численные методы решения задач линейного программирования. Геометрическая интерпретация задач линейного программирования
- •23. Численные методы решения задач линейного программирования. Геометрическая интерпретация прямого симплекс-метода.
- •24. Численные методы условной оптимизации. Метод возможных направлений.
- •25. Численные методы условной оптимизации. Метод Келли и метод секущих плоскостей.
- •26. Численные методы условной оптимизации. Первый (циклический) алгоритм Гомори.
- •27. Численные методы условной оптимизации. Метод ветвей и границ
- •28. Численные методы условной оптимизации. Метод ветвей и границ для решения задач нелинейного программирования
- •29. Численные методы условной оптимизации. Метод внешних штрафов
- •30.Численные методы условной оптимизации. Метод внутренних штрафов или метод барьерных функций
- •31.Муравьиный алгоритм.
- •32.Генетические алгоритмы.
- •33.Задачи классического вариационного исчисления. Постановка задачи классического вариационного исчисления
- •Сильный и слабый экстремум в задачах классического вариационного исчисления.
- •Допустимые управления и управляемые процессы в задачах оптимального управления. Оптимальные процессы
- •Элементарный вывод необходимых условий экстремума для простейших задач классического вариационного исчисления
- •Задачи оптимального управления. Постановка задачи оптимального управления
- •Формулировка принципа максимума для линейной задачи быстродействия
- •Доказательство принципа максимума для линейной задачи быстродействия.
- •Достаточность принципа максимума
Достаточность принципа максимума
Пусть X – конечномерное пространство, Y X – подпространство, A: X→X – линейное преобразование. Будем говорить, что Y – подпространство инвариантное относительно A , если A(Y) Y. Когда Y ≠X , то Y – собственное подпространство. Пусть a X . Элемент a принадлежит собственному инвариантному подпространству Y тогда и только тогда, когда вектора {a,Aa,…,Ak-1a} линейно зависимы, что очевидно, так как из независимости этой системы следует, что подпространство Y совпадает с X.
Будем говорить, что для задачи быстродействия выполнено условие общности положения, если для каждого вектора w параллельного некоторому ребру многогранника U , вектор Bw не принадлежит никакому собственному инвариантному подпространству A, то есть вектора {Bw,ABw,…,Ak-1Bw} образуют линейно зависимую систему.
Замечание 1. Множество векторов, для которых det{Bw,ABw,…,Ak-1Bw}≠0, является нигде неплотным. Следовательно, добиться выполнения условия общности положения можно всегда сколь угодно малым сдвигом. Множество называется нигде неплотным, если его дополнение всюду плотно.
Лемма 4. Пусть P(t) – нетривиальное решение сопряженной системы = - PA, a ≠0 такое, что P(τ)a=0 для всех τ (τ0 , τ1). Тогда a принадлежит некоторому собственному инвариантному подпространству относительно преобразования А.
Теорема 3. Пусть u(t) – допустимое управление, заданное на отрезке [t0, t1], x(t) – соответствующая траектория, удовлетворяющая начальным условиям x(t0)=x0 и x(t1)=0. Тогда для оптимальности управления необходимо и достаточно, чтобы оно удовлетворяло принципу максимума.
Теорема 4 (о конечности переключений). Для любого нетривиального решения P(t) сопряженной системы = - PA соотношение P(t)Bu(t) = однозначно определяет управление u(t) . Кроме того, управление u(t) оказывается кусочно-постоянным и его значениями являются лишь вершины многогранника U.
Теорема 5. Пусть U={u: aβ ≤ uβ ≤ bβ, β=1,…,r} , собственные значения матрицы A – вещественные. Тогда в оптимальном управлении u(t) =(u1(t),…,ur(t)) каждая функция uβ(t) кусочно-постоянна, принимает лишь значения aβ, bβ, и имеет не более (n-1) точек переключения.