Стохастическое линейное программирование

Бывает много практических ситуаций, когда коэффициенты целевой функции, коэффициенты в матрице коэффициентов, коэффициенты ограничений - являются случайными величинами. В этом случае сама целевая функция становится случайной величиной, и ограничения типа неравенств могут выполняться лишь с некоторой вероятностью. Приходится менять постановку самих задач с учётом этих эффектов и разрабатывать совершенно новые методы их решения. Соответствующий раздел получил название стохастического программирования.

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

Задача нелинейного программирования это задача на условный минимум с ограничениями типа неравенств. Пусть на определены функции f(x), f1(x), f2(x), ... fm(x). Обозначим D = {x: , fi(x) 0, i=1,..,m, xj 0, j=1,..,n}={x: , F(x) 0, x 0}, где F(x) = (f1(x), ..., fm(x)). Множество D называется допустимой областью. Задача минимизации функции f на множестве D называется задачей нелинейного программирования. Таким образом, решением задачи нелинейного программирования являются вектор и число f* такие, что .

Определение 1.   Точка называется точкой условного (глобального) минимума функции f на множестве D, если .

Определение 2.   Точка называется точкой локального условного минимума функции f на множестве D, если существует число , такое, что неравенство выполняется для таких , что .

Квадратичное программирование

Под квадратичным программированием понимаются задачи следующего вида (в матричных обозначениях)

где -симметричная матрица размерности . Задачи линейного программирования являются частным случаем этих задач - они получаются при =0. Способы решения этих задач во многом определяются видом матрицы : если - положительно определённая матрица, то целевая функция будет выпуклой и любой её локальный минимум будет глобальным. Если - отрицательно определённая матрица, то может быть несколько локальных минимумов, но глобальный минимум, если он существует, достигается обязательно на вершине допустимой области. В общем случае, когда собственные числа матрицы имеют разные знаки, задача очень сильно усложняется, так как глобальный минимум может достигаться где угодно - и внутри области и на её границе.

Выпуклое программирование

Под задачей выпуклого программирования понимают задачу вида

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

Для решения задач этого типа разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, в основном связанные с понятием градиента целевой функции и основной идеей о том, что функция наиболее быстро убывает, если двигаться в направлении, противоположном градиенту. К ним относятся метод градиентного спуска, метод сопряженных градиентов и т.д. Но есть и методы, основанные на других идеях ¾ метод штрафных функций, многочисленные варианты метода случайного поиска и т.д.