Основные определения. Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах (в дальнейшем

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах (в дальнейшем без ограничения общности будут рассматриваться задачи поиска минимального значения функции):

f(x) min(7.34)

при ограничениях:

g_i(x) 0, i 1, ..., k;

h_j(x) 0, j 1, .., m;(7.35)

a x b.

Здесь x, a, b — векторы-столбцы:

, , (7.36)

Оптимизируемую функцию f(x) называют целевой функцией. Каждая точка x в n-мерном пространстве переменных x₁, ..., х, в которой выполняются ограничения задачи, называется допустимой точкой задачи. Множество всех допустимых точек называется допустимой областью G . Будем считать, что это множество не пусто. Решением задачи считается допустимая точка х*, в которой целевая функция f(х) достигает своего минимального значения. Вектор х* называют оптимальным. Если целевая функция f(x) и ограничения задачи представляют собой линейные функции независимых переменных х₁, ..., х_n, то соответствующая задача является задачей линейного программировании, в противном случае - задачей нелинейного программирования. В дальнейшем будем полагать, что функции f(x), g(x), i 1, ..., k , h_j(x), j 1, …, m, - непрерывные и дифференцируемые.

В общем случае численные методы решения задач нелинейного программирования можно разделить на прямые и непрямые. Прямые методы оперируют непосредственно с исходными задачами оптимизации и генерируют последовательности точек {x[k]}, таких, что f(х[k+1]) f(x[k]). В силу этого такие методы часто называют методами спуска. Математически переход на некотором k-м шаге (k. 0, 1, 2, ...) от точки х[k]к точке x[k+1] можно записать в следующем виде:

x[k+l]x[k] + a_kp[k], (7.37)

где р[k] — вектор, определяющий направление спуска; а_k — длина шага вдоль данного направления. При этом в одних алгоритмах прямых методов точки х[k] выбираются так, чтобы для них выполнялись все ограничения задачи, в других эти ограничения могут нарушаться на некоторых или всех итерациях. Таким образом, в прямых методах при выборе направления спуска ограничения, определяющие допустимую область G, учитываются в явном виде.

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

Рассмотрим некоторые алгоритмы прямых методов.