Нелинейное программирование. 
Методы поиска минимума функции многих переменных

Нелинейное программирование [nonlinear programming] — раздел математического программирования, изучающий методы решения экстремальных задач с нелинейной целевой функцией и (или) областью допустимых решений, определенной нелинейными ограничениями[7].

Задачи с нелинейной целевой функцией и линейными ограничениями называют задачами нелинейного программирования с линейными ограничениями. Оптимизационные задачи такого рода можно классифицировать на основе структурных особенностей нелинейных целевых функций. Если f (x) — квадратичная функция, то имеем дело с задачей квадратичного программирования; если f (x) есть отношение линейных функций, то соответствующая задача носит название задачи дробно-линейного программирования, и т. д. Деление оптимизационных задач на эти классы представляет значительный интерес, поскольку специфические особенности тех или иных задач играют важную роль при разработке методов их решения[3].

В краткой форме задачу нелинейного программирования можно записать так: F (x) > max при условиях g (x)? b, x? 0, где x — вектор искомых переменных; F (x) — целевая функция; g (x) — функция ограничений (непрерывно дифференцируемая); b — вектор констант ограничений (выбор знака? в первом условии здесь произволен, его всегда можно изменить на обратный).

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

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

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

Такой подход называется методом кусочно-линейных приближений, он применим, однако, лишь к некоторым видам нелинейных задач. Нелинейные задачи в определенных условиях решаются с помощью функции Лагранжа: найдя ее седловую точку, тем самым находят и решение задачи.

Среди вычислительных алгоритмов нелинейного программирования большое место занимают градиентные методы. Универсального же метода для нелинейных задач нет и, по-видимому, может не быть, поскольку они чрезвычайно разнообразны. Особенно трудно решаются многоэкстремальные задачи [7].

В начале 60-х годов И. М. Гельфондом и М. Л. Цетлиным был дескриптивно задан класс невыпуклых функций многих переменных. Элементы класса характеризуются следующей структурой: в любой точке некоторого подмножества области определения функции существует такой базис, что все независимые переменные можно разделить на две группы. Первая группа состоит из тех аргументов, изменение которых приводит к значительному изменению целевой функции (в [4] они названы несущественными переменными). Изменение переменных второй группы (существенных переменных) приводит к незначительному изменению функции. При этом для любой точки подмножества вторая группа содержит лишь небольшое число параметров. Функция, допускающая такое разбиение переменных в некоторой области, называется хорошо организованной (овражной) функцией в этой области, а число существенных переменных определяет размерность оврага [4]. Характерное свойство овражной функции — скорость изменения функции существенно зависит от направления, вдоль которого производится измерение скорости, и от точки, в которой производится измерение[1].

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