Лекция 10-11 ОАП (1077348), страница 2
Текст из файла (страница 2)
В многих случаях целевая функция может быть определена алгоритмически, т.е. получена из решения математической модели объекта. Для этого используют так называемую процедуру поисковой оптимизации (см ниже), т.е. последовательного приближения выходных параметров ТО к оптимальным значениям (целевая функция приближается к оптимальной заданной точке). На представленном ниже рисунке,- алгоритм схемы расчета целевой функции, определенной из математической модели:
|
|
|
§5.3Методы одномерной оптимизации
Все методы одномерной оптимизации строятся в предположении, что целевая функция имеет на интервале [a, b] минимум. Этот интервал называется интервалом неопределенности. Сущность всех методов одномерной оптимизации состоит в последовательном сокращении интервала неопределенности до малой величины Точка x*, попавшая в считается точкой экстремума.
Известные методы уменьшения интервала неопределенности на каждом (k-ом) шаге оптимизации сводятся к выбору двух новых точек x1k и x2k внутри интервала [ak, bk ], затем определению в этих точках значений целевой функции и выбору нового интервала неопределенности согласно алгоритму
При использовании нижеизложенных методов достигается экономия времени и вычислительных ресурсов.
Метод половинного деления
На каждом шаге делаются две пробные точки, равноотстоящие от середины интервала
|
| Алгоритм уменьшения интервала неопределенности аc = cb Если F(c-)<F(c+ ) то x*[c-, b] иначе x*[a, c+ ] Условие прекращения поиска Если ab < то x* = min(F(a),F(b)) |
Метод золотого сечения
Идея метода в сокращении количества пробных точек на шаге и использовании пробных точек предыдущего шага. Золотым сечением отрезка называется точка с, делящая отрезок [a, b] в соотношении 
На каждом следующем шаге требуется определять значение функции только в одной новой точке, поскольку одна из внутренних точек отрезка с предыдущего шага уже является точкой золотого сечения для нового интервала неопределенности
|
| Алгоритм уменьшения интервала неопределенности akck=dkbk=0.3819…akbk Если F(ck)<F(dk) то x*cb иначе x*ad dk+1bk+1=ckdk0.382ak+1bk+10.382ckbk Условие прекращения поиска Если ab< то x*=min(F(a),F(b)) |
Метод полиномизации
Идея метода - в замене функции на интервале неопределенности полиномом (параболой) и отыскания минимума этого полинома аналитическими методами. Если целевая функция - парабола, то решение отыскивается за один шаг.
|
| Алгоритм уменьшения интервала неопределенности с - произвольная точка внутри интервала. Строим полином P(x)=a0+a1x+a2x2 по трем точкам a,F(a); b,F(b); c,F(с) Определяем точку экстремума x*P=-a1/2a2=d Если F(ck)<F(dk) то x*cb иначе x*ad Условие прекращения поиска Если F(x*P)= P(x*P), то x*=x*P Если ab< то x*=min(F(a),F(b)) |
§5.4 Методы многомерной (безусловной) оптимизации
Классификация задач параметрической оптимизации.
1. По размерности пространства управляемых параметров: одномерные, т.е. оптимизация по одной переменной; многомерные;
2. По типу пространства управляемых параметров: дискретные - пространство управляемых параметров дискретно, например параметры - только целые числа, непрерывные;
3. По типу экстремума целевой функции: глобальный и локальный;
4. По наличию ограничений управляемых параметров: условные и безусловные;
5. По характеру целевой функции и ограничений: задачи линейного программирования или задачи нелинейного программирования;
6. По способу выбора направления следующего шага оптимизации: нулевого порядка ( не используют производные F(x)), первого порядка - используют F’(x); второго порядка - используют F’’(x).
Под безусловной оптимизацией понимается оптимизация на всем пространстве управляющих параметров, т.е. без ограничений. Часто задачу условной оптимизации сводят к задаче безусловной оптимизации.
Различают методы 0, 1 и 2 порядков по использованию при поиске оптимума соответствующих производных. Чем выше порядок метода, тем выше его сходимость. Однако, реальные целевые функции обычно не выражаются через аналитические функции, их алгоритмические аналоги приходится искать путем решения систем алгебраических уравнений. В этом случае производные вычисляются приближенными численными методами, что снижает эффективность методов высших порядков.
Методы нулевого порядка
Метод сканирования. В области допустимых значений выбирается некоторое множество точек, в которых вычисляется целевая функция. Та точка, в которой она принимает минимальное значение, считается оптимумом. Чем меньше шаг между точками, тем больше точность, однако, с ростом количества точек и размерности пространства управляемых параметров, затраты вычислительных ресурсов растут очень быстро.
|
| Количество проб N=kn, где k- количество точек по каждой управляемой переменной, n- число управляемых переменных. В то же время - это единственный метод, который можно применять как для безусловной, так и для условной оптимизации, и он дает гарантию определения глобального экстремума при k |
Метод покоординатного спуска. Заключается в последовательном применении методов одномерной оптимизации вдоль каждого из координатных направлений. Смена направления происходит в точке касания траектории движения и поверхности равного уровня. Метод плохо работает для овражных целевых функций в том случае, если направление оврага не совпадает ни с одним из координатных направлений - приходится очень часто менять направления поиска. В то же время очень хорошо работает, когда ось оврага параллельна координатному направлению.
|
| x1 - точка экстремума вдоль направления параллельного 1 координатной оси из точки x0 x2 - точка экстремума вдоль направления параллельного 2 координатной оси из точки x1 Поиск прекращается, если из точки x* нельзя сделать ни одного шага hmin так, чтобы F(x*+hmin)<F(x*). Здесь hmin- малое наперед заданное число. |
Методы первого порядка
Называются градиентными. Известно, что направление градиента является направлением наибольшего возрастания функции. Таким образом направление противоположное вектору градиента - направление наибольшего убывания функции. Вектор-градиент функции в точке рассчитывают по формуле:
Метод градиента
В каждой точке делается шаг h в антиградиетнтом направлении, xk+1=xk‑hg, где h - шаг поиска. Если новый шаг не дает улучшения и h<hmin, то точка xk считается точкой минимума.
|
| Недостатки:
|
Метод наискорейшего спуска. Снижает количество точек, в которых необходимо вычислять производные.
|
| Движение из начальной точки также производится в направлении антиградиента до тех пор, пока значение целевой функции уменьшается. В этой точке вычисляют новое направление антиградиента и продолжают движение уже в новом направлении |
Методы второго порядка.Основаны на разложении в ряд Тейлора необходимого условия экстремума функции F(x) в окрестности экстремальной точки.
ограничившись двумя членами ряда получим
откуда
матрица Гессе
Гессе
Метод Ньютона
Основан на последовательном применении полученной формулы на каждом шаге:
В чистом виде практически не применяется, поскольку надежных алгоритмов быстрого вычисления матрицы Гессе, а тем более обратной ей матрицы нет. Теоретически дает возможность найти минимум квадратичной функции за один шаг.
Метод Флетчера-Пауэла
О
снован на методе Ньютона. В этом методе производится одномерная оптимизация вдоль направления sk , вычисленного на основе приближенного определения матрицы Гессе
|
|
|
Методы условной оптимизации
Сведение задачи условной оптимизации к задаче безусловной оптимизации
Для ограничений типа неравенств
Метод штрафных функций
Идея состоит в замене целевой функции F(x) на новую (x), максимально приближенную к F(x) в области допустимых значений и существенно большую вне области допустимых значений.
|
|
Ф(x)=F(x)+(x) (x) функция штрафа часто |
Метод барьерных функций
Функцию штрафа выбирают таким образом, чтобы при приближении к границе она стремилась к бесконечности (барьер)
|
|
Ф(x)=F(x)+(x) (x) барьерная функция часто |
Для ограничений типа равенств
минимум всегда находится на гиперповерхности ограничений
Метод проекции вектор-градиента
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
