9,10. Необхідні і достатні умови одновимірної оптимізації.

Необхідні і достатні умови багатовимірної оптимізації.

Рассмотрим n-мерную задачу оптимизации без ограничений min F(X)=F(X*) (XэR^n) (1)

По аналогии с одномерной задачей, для того, чтобы точка X0 являлась минимумом функции F(X) необходимо выполнение условия стационарности функции F(X) в точке X0 или, что то же самое, необходимо, чтобы точка X0была стационарной точкой функции F(X): дельтаF(X0)=0 (2).

Положим, что функции F(X) дважды непрерывно дифференцируема в окрестности точки X0. Для поиска достаточного условия достижения этой функцией в точке X0 минимума, разложим F(X) в окрестности точки X0 в ряд Тейлора:

F(X0+дельтаX)-F(X0)=(дельтаX^T)*дельтаF(X0)+1/2*(дельтаX^T)*H(X0)*дельтаX+… (3)

Здесь n-мерный вектор-столбец достаточно малых величин дельтаX={дельта x, i=1..n}, H(X)-(n*n) -матрица Гессе.

По аналогии с одномерной задачей, для того, что в точке X0 достигался минимум функции F(X), необходимо, чтобы разность F(X0+дельтаX)-F(X0) была положительной. Поскольку (дельтаF(X0)=0), то из (3) следует, что для выполнения этого условия необходимо, чтобы матрица Гессе H(X) была положительно определена в точке X0.

Таким образом, справедлива

Теорема 1. Если функция F(X) дважды непрерывно дифференцируема в окрестности точки X0эR^n, то необходимыми и достаточными условиями минимума этой функция в точке X0 являются условия:

(дельтаF(X0)=0) (4),

H(X0)- положительно определена.

Таким образом, теорема 1 определяет необходимые и достаточные условия минимума в многомерной задаче безусловной оптимизации.

Заметим, что условие (4) является только необходимым условием минимума в многомерной задаче безусловной оптимизации.

По аналогии с одномерной задачей точками, в которых функция F(X) достигает своего наименьшего значения, могут быть либо ее стационарные точки функции, либо критические точки функции (точки недифференцируемости).

Поэтому так же, как в одномерной задаче, точку, в которой функция F(X) принимает наименьшее значение нужно искать, сравнивая значения этой функции во всех стационарных и критических точках.

11. Класифікація методів оптимізації. Классификация методов оптимизации

Общая запись задач оптимизации задаёт большое разнообразие их классов. От класса задачи зависит подбор метода (эффективность её решения). Классификацию задач определяют: целевая функция и допустимая область (задаётся системой неравенств и равенств или более сложным алгоритмом)^[1].

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

• Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.

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

Существующие в настоящее время методы поиска можно разбить на три большие группы:

1. детерминированные;

2. случайные (стохастические);

3. комбинированные.

По критерию размерности допустимого множества, методы оптимизации делят на методы одномерной оптимизации и методы многомерной оптимизации.

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

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

• В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:

  • если и  — выпуклые функции, то такую задачу называют задачей выпуклого программирования;

  • если , то имеют дело с задачей целочисленного (дискретного) программирования.

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

• прямые методы, требующие только вычислений целевой функции в точках приближений;

• методы первого порядка: требуют вычисления первых частных производных функции;

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

Помимо того, оптимизационные методы делятся на следующие группы:

• аналитические методы (например, метод множителей Лагранжа и условия Каруша-Куна-Таккера);

• численные методы;

• графические методы.

В зависимости от природы множества X задачи математического программирования классифицируются как:

• задачи дискретного программирования (или комбинаторной оптимизации) — если X конечно или счётно;

• задачи целочисленного программирования — если X является подмножеством множества целых чисел;

• задачей нелинейного программирования, если ограничения или целевая функция содержат нелинейные функции и X является подмножеством конечномерного векторного пространства.

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

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

Способ нахождения экстремума полностью определяется классом задачи. Но перед тем, как получить математическую модель, нужно выполнить 4 этапа моделирования:

• Определение границ системы оптимизации

  • Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается

• Выбор управляемых переменных

  • «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)

• Определение ограничений на управляемые переменные

  • … (равенства и/или неравенства)

• Выбор числового критерия оптимизации (например, показателя эффективности)

  • Создаём целевую функцию