7.3.1 Основные определения

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции 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,учитываются в явном виде.

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

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