Среди численных методов поиска экстремума нелинейных функций можно выделить [24]:

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

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

В Scilab реализованы методы поиска оптимума, которые применимы как для решения задачи одномерной, так и многомерной оптимизации для условной и безусловной нелинейной оптимизации [13].

Безусловная оптимизация нелинейных функций использует два базовых алгоритма: Квази-Ньютоновские алгоритмы и алгоритмы Нелдера-Мида.

Квази-Ньютоновские алгоритмы, применяют смешанную процедуру поиска с использованием квадратичного или кубического полиномов и алгоритм BFGS для аппроксимации и корректировки Гессиана (матрицы вторых частных производных). Квази-Ньютоновские методы оптимизации основаны на накоплении информации о кривизне целевой функции по наблюдениям за изменением градиента, и принципиально отличаются от Ньютоновскихметодовтем,что Квази-Ньютоновские методы исключают явное формирование матрицы Гессе, заменяя её приближением, исходя из сделанных до этого шагов.

Метод BFGS – итерационный метод численной оптимизации, предназначенный для нахождения локального минимума нелинейной функции без ограничений. Также существуют модификация этого метода: метод с ограниченным использованием дополнительной памяти (L-BFGS), который предназначен для решения нелинейных задач с большим количеством неизвестных, а также метод с ограниченным использованием памяти в многомерном кубе
(L-BFGS-B). Этот метод находит минимум любой дважды непрерывно дифференцируемой выпуклой функции. Несмотря на эти теоретические ограничения, BFGS хорошо справляется и с невыпуклыми функциями.

Алгоритм Нелдера-Мида, также известен как метод деформируемого многогранника или симплекс-метод. Этот алгоритм является алгоритмом прямого поиска и использует только значения функции (не требует производные), а поэтому легко применим к негладким и/или зашумленным функциям. Здесь регулярным симплексом называется множество (n+1)-й равноудаленной точки в n-мерном пространстве. В двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве – правильный тетраэдр.

Алгоритм, построенный на основе метода Нелдера-Мида, заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума. Идея метода состоит в сравнении значений функции в (n+1) вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. Существуют несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных, если n<6. В различных модификациях метода симплекс может перемещаться с помощью трех основных операций: отражения, растяжения и сжатия.

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

Основными программными средствами оптимизации в Scilab являются [13]:

· optim– решатель, предназначенный для задач нелинейной оптимизации как без ограничений, так и с ограничениями, основанный на Квази-Ньютоновских методах и использующий внешнюю функцию cost, которая позволяет свести к минимуму проблемы, связанные с вычислением производных и их градиентов, в тех случаях когда их сложно получить в явном виде;

· Neldermead – набор объектно-ориентированных инструментальных средств, который поддерживает прямой поиск оптимума, основанный на методах Нелдера-Мида.

Они могут использоваться, если:

o нет необходимости или невозможно получить производные целевых функций;

o количество параметров невелико (не более 6);

o могут существовать границы и/или нелинейные ограничения.

В наборе инструментальных средств Neldermeadпредоставлены

следующие решатели:

o neldermead– решатель, который реализует различные варианты алгоритмов Нелдера-Мида и может управлять ими для установки их компонент, таких, например, как способы вычисления начальных симплексов, критерии завершения процесса оптимизации и многие другие;

o fminsearch – решатель, который реализует упрощенный алгоритм Нелдера-Мида, в котором заранее заданы конкретные установки критериев прекращения оптимизации, начальные симплексы и вспомогательные установки.

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

Вспомогательными классами и методами для этих решателей являются:

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

o optimset –метод, который может создавать или обновлять значения структур данных оптимизации для изменения поведения методов и результатов оптимизации;

o optimget – метод, который запрашивает текущие значения структуры данных оптимизации;

o optimplotfunccount, optimplotx и optimplotfval – методы, которые осуществляют управление возможностями вывода результатов для решателей.

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

Рассмотрим использование некоторых упомянутых выше решателей более подробнее.