MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

Optimization Toolbox 2.2 Руководство пользователя

А.Г.Трифонов. Стандартные алгоритмы

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

Данный раздел включает в себя следующие пункты.

Обзор методов оптимизации.

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

Оптимизация без наличия ограничений

Обсуждается применение квазиньютоновского метода и метода линейного поиска для оптимизации без ограничений. Так же приводятся детали выполнения коррекции матрицы Гессе и этапов линейного поиска в квазиньютоновском алгоритме применительно к функции fminunc.

Оптимизации методом наименьших квадратов

Обсуждается применение метода Ньютона-Гаусса и метода Левенберга-Маркварда для нелинейной оптимизации с применением метода наименьших квадратов (LS). Так же приводятся детали реализации методов Ньютона-Гаусса и Левенберга-Маркварда применительно к подпрограмм нелинейной оптимизации методом наименьших квадратов при использовании функций lsqnonlin и lsqcurvefit

Системы нелинейных уравнений

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

Оптимизации при наличии ограничений

Обсуждается применение уравнений Куна-Таккера (KT) как некой базы метода Последовательного Квадратичного Программирования (SQP). Так же приводятся детали реализации методов корректировки матрицы Гессе, решения задач квадратичного программирования, а так же линейного поиска и этапы расчета по алгоритму SQP применительно к функциям fmincon, fminimax, fgoalattain иfseminf

Многоцелевая оптимизация

Приводится введение в многоцелевую оптимизацию, а также обсуждаются стратегии обращения с конкурирующими целями. Кроме того приводятся детали реализации метода Достижения цели и предлагается их посдедующее улучшение посредством SQP метода применительно к данной задаче.

Избранная библиография

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

Примечание. Термин средней размерности не является общестандартным термином и используется только как для введения отличия используемых алгоритмов от алгоритмов большой размерности, представленных в разделе "Алгоритмы большой размерности".

Обзор методов оптимизации

Методы оптимизации используются для того, что бы найти некий набор параметров х={x1, х2, … хn} которые в некотором смысле могут быть определены как оптимальными. В узком смысле это может быть поиск минимума или максимума некой функции как параметра от х={x1, х2, … хn}. В более широком смысле эта формулировка представляет собой минимизацию или максимизацию целевой функции, f(x), при наличии ограничений в форме

Равенств

или неравенств

а также и/или ограничений ,

на пределы изменения параметров.

Общая формулировка (GP) задачи параметрической оптимизации представляется следующим образом: следует найти вектор х={x1, х2, … хn}, обеспечивающий

(3-1)

при условии

где х - вектор оптимизируемых параметров (), f(x) - скалярная целевая функция (критерий) векторного аргумента (), G(x) - также некоторые скалярные функции векторного аргумента как некие функции от х () (при этом задача максимизации может сводиться к задаче минимизации при замене f(x) на -f(x)).

Эффективность и точность решений данной задачи зависит как от числа параметров и ограничений, так и от вида целевой функции. При линейных ограничениях и линейной целевой функции приведенная задача оптимизации называется задачей линейного программирования (LP). Задача квадратичного программирования (QP) представляет собой минимизацию или максимизацию квадратичной (по аргументам) целевой функции при наличии ограничений линейного вида. Постановки задач типа (LP) и (QP) представляют собой достаточно реалистически достижимыми задачами. Более сложной является обобщающая задача нелинейного программирования ( NP), когда целевая функция и ограничения представляют собой некие нелинейные функции от исходных аргументов. ( NP), в общем случае, решается с помощью итерационных методов с коррекцией направления поиска на каждой итерации. Такая постановка задачи обычно решается через решение отдельных промежуточных задач ( LP) и (QP)/

Оптимизация без наличия ограничений

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

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

Градиентные методы используют информацию о наклоне функции для выбора направления поиска экстремума. В одном из таких методов - наискорейшего спуска - на каждой итерации движение к точке минимума осуществляется в направлении (где - вектор-градиент целевой функции f(x). Этот метод весьма неэффективен в ситуациях, когда поверхность целевой функции имеет узкие "овраги", как, например, у известной функции Розенброка

(3-2)

Минимальное значение данной функции, как нетрудно видеть, равно нулю при . Графическое представление изолиний данной функции приведено на Рис. 3, где также представлено траектория продвижения по направлению к точке минимума согласно метолу наискорейшего спуска из начальной точки [-1.9,2].

Рис. 3-1: Метод наискорейшего спуска для функции Розенброка (уравнение 3-2).

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


Поиск по сайту:

Система Orphus

Яндекс.Метрика