Методы одномерной оптимизации в алгоритмах задач МП. Общий подход к определению оптимального шага

Решение оптимизационных задач в общем случае – это итерационная процедура в результате которой отыскивается минимум целевой функции. При этом необходимо задать правило (закон) изменения итерационных переменных в соответствии с общепринятой формулой.

,

,

где – это направление изменения переменных,

– это шаг по указанному направлению.

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

Непосредственное определение оптимального шага на основе общего подхода.

На начальном этапе необходимо знать интервал на котором находится экстремум функции.

Для функции одной переменной внутри интервала, функция непрерывна и дифференцируема.

Направление изменения переменных связанно с изменением координат оси. Необходимо найти величину шага, который приведёт к экстремуму (рисунок 2).

Рисунок 2

,

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

,

Пусть имеем начальное значение переменных и начальное значение интервала локализации функции .

Выразим функцию в явном виде от шага:

,

Воспользовавшись экстремумом, получим:

. (1)

Решая это уравнение получим наилучшее значение шага на предыдущем значении функции.

Пусть , тогда при a=2, b=3, c=4 начальное значение будет:

.

Пусть известно , выразим функцию в явном виде от шага.

Решая выражение (1) с первой независимой:

.

Далее получим значение функции с этим шагом:

.

.

Представим функцию двух переменных:

.

Решая данное уравнение выше, получим оптимальный шаг перемещения с которым в заданном направлении даст координаты минимума функции.

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

Для функции отличающейся от тривиальной определение шага затрудненно.

Трансындентная функция: . Такой общий подход является трудно реализуемым.