Зачет по оптимизации

Материалы:

• Список вопросов
• Методичка

Оглавление:

• Зачет по оптимизации
  • 9. Матрица Гессе и ее применение для решения задач оптимизации.
  • 10. Методы оптимизации нулевого порядка.
  • 11. Условная оптимизация.
  • 12. Градиент и его применение для решения задач оптимизации.
  • 13. Генетические алгоритмы
  • 14. Аппроксимация как задача оптимизации.
  • 15. Золотое соотношение и его применение для решения задач оптимизации.
  • 16. Условия Каруша-Куна-Таккера.

9. Матрица Гессе и ее применение для решения задач оптимизации.

Матрица Гессе — симметрическая квадратичная формы, описывающая поведение функции во втором порядке. Матрица этой квадратичной формы образована вторыми частными производными функции. Если все производные существуют, то она определяется следующим образом:

Определитель этой матрицы называется определителем Гессе, или просто гессианом. Матрицы Гессе используются в задачах оптимизации методом Ньютона. Полное вычисление матрицы Гессе может быть затруднительно, поэтому были разработаны квазиньютоновские алгоритмы, основанные на приближённых выражениях для матрицы Гессе. Наиболее известный из них — алгоритм Бройдена — Флетчера — Гольдфарба — Шанно. В методичке он называется BFGS (страница 64).

Если градиент

$f$ (её векторная производная) равен нулю в некоторой точке

$x_0$, то эта точка называется критической. Достаточным условием существования экстремума в этой точке является знакоопределённость гессиана

$f$ (понимаемого в данном случае как квадратичная форма), а именно:

• если гессиан положительно определён, то
  $x_0$ точка локального минимума функции
  $f(x)$
• если гессиан отрицательно определён, то
  $x_0$ точка локального максимума функции
  $f(x)$
• если гессиан не является знакоопределённым (принимает как положительные, так и отрицательные значения) и невырожден
  $detH(f)\ne 0$ то
  $x_0$ – седловая точка
  $f(x)$

10. Методы оптимизации нулевого порядка.

• метод дихотомии
• метод фибоначи
• метод золотового сечения
• метод квадратичной интерполяции

11. Условная оптимизация.

Условная оптимизация — метод поиска максимума или минимума функции при заданных ограничениях на ресурсы системы и выбранных критериях оптимизации. Если ограничения отсутствуют, то метод оптимизации называется безусловным.

Методы условной оптимизации:

• Аналитические
  1. Метод Лагранжа
• Численные
  2. Метод штрафных функций
  3. Метод барьерных функций

12. Градиент и его применение для решения задач оптимизации.

Градиент (от лат. gradiens, род. п. gradientis «шагающий, растущий») — вектор, своим направлением указывающий направление наибольшего возрастания некоторой величины

$\phi$, значение которой меняется от одной точки пространства к другой (скалярного поля), а по величине (модулю) равный скорости роста этой величины в этом направлении.
Имеет два варианта обозначения:

$grad\phi$ ,

$\mathrm{\nabla }\phi$.

Допустим есть некоторая функция:

$$\phi =\phi (x,y,z)$$

Градиент данной функции будет равен:

$$\mathrm{\nabla }\phi =\frac{d\phi }{dx}i+\frac{d\phi }{dy}j+\frac{d\phi }{dz}k$$

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

• Градиентный спуск, включая модификации
• Метод Чебышева
• Метод сопряженных градиентов
• Метод Нестерова
• Стохастический градиентный спуск

Подробное описание всех перечисленных методов можно найти тут.

13. Генетические алгоритмы

Методичка страница, 64.

Генетические алгоритмы (ГА), так же как другие численные алгоритмы
оптимизации являются итерационными.
Основным объектом, над которым производятся операции в ГА являются особи
(или иначе хромосомы). Каждая хромосома представляет собой набор
значений некоторых параметров, которые можно менять для того, чтобы получить
идеальную особь.

Каждая итерация генетического алгоритма включают в себя три этапа:

1. Скрещивание. Случайным образом выбираются две хромосомы, на их основе получают новую хромосому. В различных ГА используют разные способы скрещивания: вычисление среднего, обмен частями хромосом и другие.
2. Мутация. С достаточно малой вероятностью происходит случайное изменение некоторой хромосомы.
3. Отбор. Производится упорядочивание хромосом в соответствии с функцией пригодности, после чего хромосома с самой низким значением пригодности удаляется.

Работа алгоритма завершается, когда все хромосомы станут «похожи», или когда будет выполнено достаточное число итераций, или когда будет достигнуто нужное значение функции пригодности.

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

$n$ вещественных переменных и могут быть решены с помощью единого
алгоритма.

• Одним из самых известных генетических алгоритмов вещественной оптимизации является алгоритм дифференциальной эволюции (Differential Evolution (DE)).

14. Аппроксимация как задача оптимизации.

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

(серег мб это)
1.Задать целевую ф-ию и началльное положение х0
2.Построить апроксимрующую ф-ию f*(x) примерно равную f(x)
3.Найти экстремум x1, для f*
4.Проверить точности, если больше, то шаг 2

15. Золотое соотношение и его применение для решения задач оптимизации.

Метод золотого сечения — метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации. Впервые представлен Джеком Кифером в 1953 году.

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

Золотое сечение (золотая пропорция, деление в крайнем и среднем отношении, гармоническое деление) — соотношение двух величин a и b, при котором бо́льшая величина относится к меньшей, так же, как сумма величин к бо́льшей, то есть:

$$\frac{a}{b}=\frac{a+b}{a}$$

Золотое сечение имеет множество представлений, например непрерывной дробью:

ЗОЛОТОЕ СООТНОШЕНИЕ - содерижтся в методе золотого сечения, когда мы делим отрезок в отношении U(типо фи). ПРи этом свойства золотого сечения гарантируют, что на следующем шаге новая точка в центре отрезка также будет делить его в том же соотношении (это из конспекта)

16. Условия Каруша-Куна-Таккера.