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

Общая запись задач оптимизации задаёт большое разнообразие их классов. От класса задачи зависит подбор метода (эффективность её решения). Классификацию задач определяют: целевая функция и допустимая область (задаётся системой неравенств и равенств или более сложным алгоритмом).
Методы оптимизации классифицируют в соответствии с задачами оптимизации:
  1. Локальные методы: сходятся к локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.
  2. Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.
Существующие в настоящее время методы поиска можно разбить на три большие группы:
  1. Детерминированные;
  2. Случайные (стохастические);
  3. Комбинированные.
По критерию размерности допустимого множества, методы оптимизации делят на:
  1. Методы одномерной оптимизации ;
  2. Методы многомерной оптимизации.

Термины и определения

Градиент функции f(x1,x2,…,xn) определяется как вектор Градиент функции
Матрица, составленная из вторых производных функции, называется матрицей Гессе. Матрица Гессе (гессиан) для функции f(x1,…,xn) есть симметрическая матрица порядка nxn:

Норма вектора (норма матрицы), S(x1,x2)

Онлайн калькуляторы по методам оптимизации

В данном разделе представлены онлайн сервисы следующих направлений.

Функция одной переменной

  1. Наибольшее и наименьшее значение функции одной переменной.
  2. Интервалы выпуклости и вогнутости функции.
  3. Полное исследование функции.

Методы поиска нулей функции

  1. Метод Ньютона (Метод касательных)
  2. Метод хорд
  3. Комбинированный метод
  4. Метод итераций
  5. Метод секущих

Методы минимизации функций

Функция одной переменной

  1. Метод Свенна
  2. Одномерный поиск
  3. Метод Ньютона
  4. Метод деления отрезка пополам
  5. Метод Фибоначчи
  6. Метод золотого сечения
  7. Метод Пауэлла
  8. Интервалы возрастания и убывания функции. Точки перегиба (интервалы выпуклости и вогнутости).

Функция двух переменных

  1. Матрица Гессе. . Позволяет ответить на вопрос является ли функция выпуклой или вогнутой, а также определить тип экстремума (минимум или максимум).
  2. Производные второго порядка
  3. Экстремум функции двух переменных.

Методы прямого поиска

  1. Метод Хука–Дживса
  2. Метод сопряженных направлений (метод Пауэлла). Найти минимум целевой функции методом сопряженных направлений: f(x)=3x1 – x13 + 3x22 + 4x2. x0=(0.78;1)

Градиентные методы

  1. Метод наискорейшего спуска (метод Коши).
  2. Метод Ньютона
  3. Метод Марквардта. Найти минимум функции: y=x12+4x22+x1x2+1-5x2 методом Марквардта с начальной точкой (10;10) и εxy= ε|f(x)|=0.5. Предельное число итераций равно M=5.
  4. Метод сопряженных градиентов (метод Флетчера-Ривса, метод Миля-Кентрелла, метод Поллака-Рибьера)
  5. Метод Бройдена–Флетчера–Гольдфарба–Шанно (квазиньютоновские методы).

Линейное программирование

  1. Графический метод решения задач линейного программирования.
  2. Задача линейного программирования сводится к приведению к канонической форме, а затем к стандартной форме ЗЛП.
  3. Симплекс-метод.
  4. Двойственный симплекс-метод (P-метод).
  5. Составление и решение двойственной задачи.
  6. Метод Гомори.
  7. Задачи параметрического программирования.

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

Прямые методы

  1. Метод множителей Лагранжа. В задачах 301-320 используя метод множителей Лагранжа найти точки экстремума функции z=f(x,y) при заданном условии: z=xy+7x, 2x+y=1
  2. Условия Куна-Таккера.

Градиентные методы

  1. Метод проекции градиента.
  2. Метод условного градиента.

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

  1. Метод непосредственной линеаризации.
  2. Метод допустимых направлений Зойтендейка.

Итерационные методы решения СЛАУ

  1. Метод простой итерации
  2. Метод Зейделя

Прямые методы решения СЛАУ

  1. Метод Гаусса
  2. Метод LU-разложения

Численное интегрирование функций

  1. Формула прямоугольников
  2. Формула трапеции
  3. Формула Симпсона

Вычисление определителей

  1. Вычисление определителя матрицы методом декомпозиции
  2. Нахождение определителя правилом Саррюса.
  3. Определитель методом Гаусса.
  4. Расчет определителя через алгебраические дополнения.

Многокритериальная оптимизация

  1. Метод идеальной точки.
загрузка...