Обобщенный алгоритм решения задач НЛП

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

x^k+1 = x^k + h_k r(x^k), k = 0,1,.... (1)

Здесь

k - номер итерации;

x^k - решение на k-ой итерации;

r(x^k) - направление, в котором изменяется значение x^k;

h_k - переменная, показывающая величину изменения (длину шага) вектора x^k в направлении r(x^k); h_k ≥ 0.

В алгоритмах подобного типа необходимо анализировать (доказывать) сходимость (и скорость сходимости) последовательности {x^k, k=0,1,...} к оптимальному решению x*. Критерием окончания итерационного процесса служит выполнение неравенства

║ x^k – x*║ ≤ e,

Поскольку значение x^*, как правило, заранее не известно, то часто используется критерий

║ x^k+1 – x^k║ ≤ e, или ║ r(x^k)║ ≤ e, или h_k ≤ e,

Таким образом, для реализации итерационного процесса (1) необходимо:

а) задавать начальное значение x^o;

б) на каждом k-ом шаге уметь вычислять направление r(x^k), и величину шага h_k;

в) задавать критерий окончания итерационного процесса e.

С точки зрения области применимости алгоритма различают универсальные (широкоспециализированные) и специализированные (узкоспециализированные) алгоритмы.

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

С п е ц и а л и з и р о в а н н ы е алгоритмы в той или иной степени учитывают специфику функций, описывающих множество допустимых альтернатив и целевой функции. Прежде всего, такая специфика выражается в линейности этих функций. Так, например, если ограничения задают выпуклый многогранник (описываются линейными уравнениями), т.е. имеют вид: A x ≤ b, x ≥ 0, то в зависимости от вида целевой функции различают задачи:

– к в а д р а т и ч н о г о программирования; целевая функция имеет вид:
f(x) = c^тx + x^тDx , где D — неположительно определенная матрица;

– б и л и н е й н о г о программирования; целевая функция имеет вид:
f(x) = c^тx + d^тy + x^тG y;

– д р о б н о - л и н е й н о г о программирования; целевая функция имеет вид:

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

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

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

2) алгоритмы прямого решения исходной задачи;

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