Анализ методов решения задач оптимального управления.

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

Существует достаточно большое количество численных ме­тодов оптимизации.

Основные из них классифицируются следующим образом:

1. По размерности решаемой задачи: одномерные и многомер­ные.

2. По способу формирования шага многомерные методы де­лятся на следующие виды:

2.1.Градиентные.

· по способу вычисления градиента: с парной пробой и с центральной пробой;

· по алгоритму коррекции шага;

· по алгоритму вычисления новой точки: одношаговые и многошаговые.

2.2. Безградиентные: с поочередным изменением переменных и с одновременным изменением переменных.

2.3. Случайного поиска: с чисто случайной стратегией и со смешанной стратегией.

3. По наличию активных ограничений.

3.1. Без ограничений (безусловные).

3.2. С ограничениями (условные):

· с ограничениями типа равенств;

· с ограничениями типа неравенств;

· смешанные.

1. Методы одномерной оптимизации являются базой для не­которых «многомерных» методов. К данному методу относятся

1)метод деления пополам, который основан на делении текущего отрезка [a, b] на две равные части с последующим выбором одной из половин, в которой локализуется максимум в качестве следующего текущего отрезка.

2)метод золотого сечения, который основан на делении текущего отрезка [a, b] на две неравные части, подчиняющиеся правилу золотого сечения. Для определения следующего отрезка, содержащего максимум.

2. Многомерная безусловная градиентная оптимизация.

При отыскании экстремумов функции R(x) используются методы без активных ограничений, а величина шага в рекуррентном соотношении x_i+1=x_i+ i вычисляется с использованием градиента целевой функции R(x), т.е. i=f(grad R(x_i)). При этом шаг может определяться с использованием градиента в одной (текущей) или двух (текущей и предыдущей) точках. Направление градиента показывает направление наискорейшего возрастания функции, а его модуль – скорость этого возрастания. К методам данной оптимизации относится метод наискорейшего спуска и метод сопряженных направлений.

3. Многомерная безусловная безградиентная оптимизация.

В данных численных методах опти­мизации величина и направление шага к оптимуму формируются однозначно по определенным детерминированным функциям в зависимости от свойств критерия оптимальности в окрестности текущей точки без использования производных (т.е. градиента). Все алгоритмы имеют итерационный характер и выражаются формулой
x _i+1 =x _i+f [R(x_i)].

Основная особенность рассматриваемой группы методов — отсутствие вычисления градиента критерия оптимальности. Ряд методов прямого поиска базируется на последовательном применении одномерного поиска по переменным или по другим задаваемым направлениям, что облегчает их алгоритмизацию и применение. К методам данной оптимизации относится метод Зейделя – Гаусса

4. Многомерная безусловная случайная оптимизация.

В методах случайного поиска шага при построении улучшающей последовательности x _i+1 =x_i + _i формируется случайным образом. Поэтому в одной и той же ситуации шаг может быть различен в отличие от регулярных методов.

В целом случайные методы поиска предпочтительнее регу­лярных в задачах высокой размерности n>10 и вдали от оптиму­ма. Методы этой группы позволяют в среднем быстрее выходить в район оптимума. Эффективны данные методы и при поиске глобального оптимума. Кроме того, случайные методы имеют ту осо­бенность, что даже при одних и тех же неформально задаваемых параметрах они дадут различные траектории поиска.

5. Многомерная условная оптимизация.

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

Допустимая область может формироваться автономными ог­раничениями x_imin x_i x_imax, связями f_j(x₁, x₂, …x_n)=0 (j=1, 2, …m) и ограничениями f_j(x₁, x₂, …x_n)>0, для j = 1,..., р.

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