Методы оптимизации в АСКТП
Основные принципы управления. Идентификация объектов управления, алгоритмы их оптимизации. Численные, градиентные, квазиньютоновские, комбинированные методы оптимизации. Аналитические методы исследования невыпуклых задач. Сущность проблемы нелокальности.
| Рубрика | Математика |
| Вид | курс лекций |
| Язык | русский |
| Дата добавления | 07.04.2015 |
| Размер файла | 1,7 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
где - малые константы.
Методы минимизации 0-го порядка.
Эти методы оперируют только со значениями .
Метод дихотомии.
Итак, необходимо найти с точностью в предположении, что унимодальна на .
Это значит, что если - точное решение задачи минимизации на , а - приближенное, то
Суть метода заключается в последовательном уменьшении отрезка, покрывающего точку минимума.
Рассмотрим один шаг метода.
Точкой делим отрезок пополам, поскольку унимодальна, то и , однако точка минимума может оказаться как в левой, так и в правой части отрезка .
На рисунке представлены две унимодальные функции, имеющие точку минимума в разных половинах отрезка .
Следовательно, по значению функции в средней точке отрезка нельзя сузить отрезок неопределенности.
Внутри отрезка выберем две точки:
;
где - параметр метода, .
Выбор малых констант должен быть согласован с машинной точностью, то есть не должны быть меньше машинной точности.
В силу унимодальности точка минимума попадет либо в отрезок , либо в .
Если , то не может в этом случае попасть в отрезок , так как нарушилась бы унимодальность .
Если , то .
Если , то . Но часто этот случай не выделяют отдельно, а включают знак равенства в один из выше рассмотренных случаев.
Таким образом, после первого шага метода постановка задачи осталась прежней с уменьшенным отрезком неопределенности, в котором находится точка минимума.
Многократное применение описанной выше процедуры приведет к тому, что отрезок неопределенности сузится до желаемого. Поскольку алгоритм работает в условиях леммы о вложенных отрезках, сходимость метода гарантирована.
На рисунке ниже представлена блок-схема метода дихотомии.
Поскольку задача решается с точностью , то необходимое число шагов метода должно удовлетворять неравенству:
Или
Таким образом, заранее по постановке задачи мы можем узнать число шагов метода.
Замечание 1.
Из последней оценки видим, что число шагов метода не зависит от вида.
Замечание 2.
Этот метод можно применять для минимизации функций, не являющихся унимодальными, однако, без гарантии, что будет найден обязательно глобальный минимум.
Пример.
Найти минимум на отрезке c
Решение.
Предварительно оценим, сколько шагов для этого потребуется. Выберем .
.
Поскольку - целое, то потребуется 7 шагов. Осуществим их.
1-й шаг.
.
2-й шаг.
;
.
3-й шаг.
;
.
4-й шаг.
;
.
5-й шаг.
;
.
6-й шаг.
; .
7-й шаг.
;
.
Следовательно, действительно, только 7 шагов приводят к решению с заданной точностью. В качестве принимаем -0,01.
На следующем рисунке проиллюстрировано уменьшение отрезка неопределенности по шагам.
Метод Фибоначчи.
Часто в вычислительных процедурах существенные трудности возникают в связи с вычислениями значений. Например, вычисляется в процессе эксперимента, либо задана сложной формулой.
К методам, в которых при ограничениях на количество вычислений значений достигается в определенном смысле наилучшая точность, относятся методы Фибоначчи и золотого сечения.
Как и в методе дихотомии, процедура будет заключаться в последовательном уменьшении отрезка неопределенности на основании анализа значений функции в двух внутренних точках отрезка с существенным отличием от предыдущего, состоящего в том, что одна из внутренних точек последующего отрезка неопределенности совпадет с одной из двух внутренних точек предыдущего отрезка неопределенности.
Определение.
Последовательность чисел называется последовательностью Фибоначчи.
Зададимся некоторым и выпишем последовательность чисел Фибоначчи.
Итак, необходимо найти минимум на отрезке с точностью .
Опишем 1-й шаг метода Фибоначчи.
Как и в предыдущем методе найдем на отрезке :
;
Из формул видно, что симметричны относительно середины отрезка .
Дальнейшая процедура уменьшения отрезка неопределенности совпадает с методом дихотомии. Итак, основное отличие метода Фибоначчи от метода дихотомии состоит в выборе точек на каждом шаге.
В силу свойств последовательности Фибоначчи, на каждом шаге, кроме 1-го и предпоследнего, вычисляется одно новое значение функции, другое значение используется из предыдущего шага. Только на 1-м шаге значение вычисляется дважды, а на предпоследнем, когда совпадает с , известно из предыдущего шага. Можно показать, что на -м шаге совпадут, этим завершится процедура деления отрезка неопределенности. Для получения окончательного результата необходимо вычислить и , где - малая величина, параметр метода.
Если , то полагают, что , в противном случае .
Посмотрим, как уменьшается отрезок неопределенности
;
Таким образом, -й шаг метода Фибоначчи обеспечивает уменьшение длины отрезка неопределенности в раз.
Для решения задачи минимизации с заданной точностью необходимо решить неравенство относительно , получить последовательность чисел Фибоначчи и использовать ее с конца.
Замечание 1.
Теоретически достаточно найти первую точку метода , остальные точки можно получать, используя свойство их симметрии относительно центра отрезка, однако в этом случае быстро накапливается погрешность. Чтобы избежать накопления погрешности, следует пересчитывать точки по соответствующим формулам.
Замечание 2.
Поскольку определяется сначала как функция от , алгоритм не позволяет получить более точный результат путем продолжения счета. Для обеспечения другой точности необходимо реализовать новую вычислительную процедуру.
Блок-схема метода Фибоначчи
Пример.
Найти минимум на отрезке c . Начнем с определения :
Для решения поставленной задачи потребуется 9 шагов по методу Фибоначчи, при этом понадобится 9 раз вычислять . Заметим, что для решения этой же задачи методом дихотомии мы проделали 7 шагов, то есть вычисляли 14 раз.
1-й шаг.
;
.
2-й шаг.
.
3-й шаг.
;
.
4-й шаг.
;
.
5-й шаг.
;
.
6-й шаг.
;
.
7-й шаг.
.
8-й шаг.
;
.
9-й шаг.
;
.
Замечание.
Вычисления проводились с 5 знаками после запятой, поэтому точки последующего и предыдущего шага совпадают не полностью.
Метод золотого сечения.
В теории чисел показано, что существует предел отношения соседних чисел Фибоначчи
показывает, как соотносятся длины отрезков неопределенности при применении метода Фибоначчи.
С другой стороны, рассмотрим следующую задачу. Возьмем отрезок , найдем внутри этого отрезка , образующие золотое сечение.
Для этого необходимо выполнение следующих условий:
Найдем ,при котором возможны равенства
,
,
,
Поскольку
Отсюда видно, что золотое сечение можно рассматривать как предельный случай деления отрезка по методу Фибоначчи при большом k. Метод золотого сечения состоит в том, что начиная с 1-го шага отрезок делится точками в пропорции золотого сечения. При каждом шаге отрезок неопределенности уменьшается в раз.
Если - заданная точность, то число шагов метода золотого сечения следует находить как решение неравенства
Замечание.
Метод золотого сечения немного медленнее сходится, чем метод Фибоначчи.
С другой стороны, при необходимости, для получения более точного результата, есть возможность его продолжить.
При шагах метода золотого сечения вычисляется раз, так как на 1-м шаге вычисляется дважды, а на последующих шагах по одному разу, так же как и в методе Фибоначчи одна из внутренних точек отрезка неопределенности последующего шага совпадает с одной из точек предыдущего шага.
Блок-схема метода золотого сечения
Пример.
Найти минимум на отрезке c
Предварительно определим, сколько потребуется шагов метода золотого сечения.
Итак, потребуется 8 шагов метода золотого сечения, при этом значения придется вычислять 9 раз, то есть трудоемкость такая же, как была в методе Фибоначчи.
1-й шаг.
;
.
2-й шаг.
;
.
3-й шаг.
;
.
4-й шаг.
;
.
5-й шаг.
;
.
6-й шаг.
;
.
7-й шаг.
;
.
8-й шаг.
;
.
Лекция 4. Методы одномерной минимизации
Методы с использованием производных.
В методах прямого поиска при вычислении значений минимизируемой функции f(x) неизбежно возникают погрешности, к которым чувствительны алгоритмы прямого поиска, основанные на сравнении значений функции в отдельных точках.
Пусть f(x) -- дважды непрерывно дифференцируемая функция в окрестности точки х* строгого локального минимума, значения которой вычисляются с абсолютной погрешностью, не превышающей . Оценим абсолютную погрешность Д*, с которой может быть найдена точка х* с применением метода прямого поиска. Для представления функции f(x) в окрестности точки х* воспользуемся формулой Тейлора с учетом равенства :
,
где о -- точка, лежащая между точками x* и x. Имея в виду, что вычисления проводятся в достаточно малой окрестности точки x*, положим . Тогда для приближенно вычисляемых значений получим
Из этих неравенств вытекает, что можно гарантировать выполнение неравенства, если .
Это приводит к приближенной оценке абсолютной погрешности нахождения точки х* методом прямого поиска:
. (1)
Заданная точность е* нахождения точки х* не должна быть меньше Д*, так как иначе эту точность нельзя достичь методом прямого поиска. Из (1) также следует, что при нахождении точки х* происходит потеря примерно половины верных значащих цифр, с которыми можно вычислить приближенное значение минимизируемой функции.
Если унимодальная функция f(x) непрерывно дифференцируема на отрезке минимизации, то точку х* наименьшего значения функции можно вычислять как корень уравнения с помощью тех или иных методов численного решения нелинейных уравнений. В этом случае на точность решения задачи решающее влияние оказывает погрешность вычисления производной функции.
Если абсолютная погрешность вычисления производной не превышает , то для нижней оценки абсолютной погрешности вычисления корня х* уравнения f(x) = 0 имеем
.
Таким образом, при нахождении этого корня можно сохранить все верные значащие цифры, с которыми можно вычислить значение производной.
Рассмотрим некоторые методы одномерной минимизации, основанные на использовании производной минимизируемой функции.
Итерационный метод Ньютона-Рафсона
Метод Ньютона относится к методам 2-го порядка и рекомендуется с применению в том случае, когда задача минимизации достаточно хорошо локализована.
Обычно это имеет место в том случае, когда на начальном этапе применяется один из методов 0-го порядка, а затем осуществляется переход к методу Ньютона. Для этого необходимым условием является гладкость , существование не равных нулю , , для .
Тогда если - k-е приближение к точке минимума, то расчетной формулой метода Ньютона будет формула
. (правило Ньютона-Рафсона)
Если целевая функция не является квадратичной, то понадобится несколько итераций до тех пор, пока не будет удовлетворен критерий останова.
Существенным преимуществом алгоритма является то, что требуется только одна точка, и то, что для квадратичной функции достаточно одной итерации. Однако имеются и недостатки:
- если первая и вторая производные оцениваются приближенно по конечным разностям, то эффективность алгоритма снижается не только из-за ошибок округления, но и из-за неточности аппроксимации. Это особенно верно в окрестности точки минимума, где первая производная становится существенно малой;
- не различаются точки минимумов, максимумов и перегибов. Уже стартовая точка должна выбираться как можно ближе к искомому минимуму;
- если целевая функция имеет порядок выше второго, то итерации метода Ньютона-Рафсона могут не сойтись. Условием сходимости является положительность второй производной для всех точек, встречающихся в процессе оптимизации.
Метод Ньютона минимизации функции является обобщением известного метода Ньютона отыскания корня уравнения, где- скалярная функция скалярного аргумента x. Минимизация основывается на использовании квадратичной аппроксимации функции f(x) в точке xk:
Таким образом,
(правило Ньютона-Рафсона)
Итерационный процесс строит последовательность точек, которая при определенных условиях квадратично сходится к некоторой стационарной точке x* функции f(x), т. е. к точке, в которой. Процесс останавливается, когда- заранее заданное малое число.
Существенными недостатками метода Ньютона являются: 1) сложность задания начального приближения x1 в малой окрестности искомого минимума x*; 2) необходимость вычисления вторых производных минимизируемой функции.
Метод Ньютона имеет высокую скорость сходимости: , где - точка минимума; С - некоторая положительная константа.
На следующем рисунке приведена блок-схема алгоритма.
Блок - схема метода Ньютона
Пример.
Найти минимум на отрезке c точностью.
Зададимся , например, возьмем середину отрезка :
Пусть
Для данного примера расчетной формулой метода Ньютона будет
1-й шаг.
2й шаг.
Решение.
Замечание.
Число сохраняемых знаков после округления определяется заданной точностью .
Оптимизация с использованием аппроксимирующих полиномов.
В методах прямого поиска мы не имели никакой информации о минимизируемой функции за исключением ее значений в выбранных нами точках и предположения, что она непрерывна и является унимодальной функцией на рассматриваемом отрезке. Если функцию в некоторой окрестности точки ее минимума можно достаточно точно заменить (аппроксимировать) многочленом, то для ее минимизации целесообразно использовать так называемые методы полиномиальной аппроксимации. Используется несколько значений функции в определенных точках для аппроксимации функции обычным полиномом, по крайней мере в небольшой области. Затем положение минимума функции аппроксимируется положением минимума полинома, поскольку последний вычислить проще. При этом характер поведения оптимизируемой функции учитывается при выборе вида полинома и при его построении.
Метод линейной интерполяции (метод секущих или regula falsi)
Хорошо известный метод секущих отыскания нуля функции первоначально назывался методом regula falsi или regula falsorum. Этот метод правильно предсказывает положение нуля функции, если она зависит линейно от своего аргумента.
Метод секущих предлагает заменить вторую производную в ньютоновской формуле ее линейной аппроксимацией
Тем самым очередное приближение к стационарной точке x* задается формулой вида
Легко видеть, что - точка пересечения с осью абсцисс секущей прямой, проходящей через точки xk и.
В отличие от метода Ньютона метод секущих гарантирует сходимость точек {xk} к стационарной точке x*, однако сходимость метода достигается ценой потери быстродействия. Как правило, метод дихотомии оказывается эффективнее метода секущих, хотя последний и получен из более быстродействующей схемы.
Начальный этап. Пусть методом Свенна получен интервал неопределенности [a1, b1], границы которого удовлетворяют неравенству. Задать - погрешность вычисления минимума и принять k = 1.
Основной этап.
Шаг 1. Найти очередное приближение xk + 1 к минимуму x* и проверить условие окончания поиска:
если то остановиться.
Шаг 2. Уменьшить интервал поиска минимума:
если в противном случае принять
положить и перейти к шагу 1.
Метод работает надежно только в случае, если функция почти линейна или хотя бы строго выпукла. Кроме того, стартовые точки должны быть выбраны в окрестности точки минимума. Иначе процедура может выдать в качестве ответа точку максимума, так как при движении к нему производная тоже будет уменьшаться.
Модификации метода Ньютона обладают только локальной сходимостью, т.е. сходятся, если начальная точка выбрана в некоторой окрестности точки минимума функции. Если же начальная точка расположена слишком далеко от точки минимума, то подобный метод может расходиться или “зацикливаться”. В некоторых случаях целесообразно сочетать различные модификации метода Ньютона, чередуя их применение в зависимости от номера шага.
Рассмотрим метод квадратичной аппроксимации минимизируемой функции , в котором график этой функции приближенно заменяют параболой, проходящей через три известные точки , i = 1,2,3, где .
Метод квадратичной интерполяции
Итак, найти с точностью .
Выбираем .
Через точки проводим параболу, то есть строим интерполяционный многочлен 2-й степени:
Находим вершину параболы из условия ,
.
Если , то необходимо выяснить или нет.
Если , то по трем точкам строится следующая парабола.
Если , то следующая парабола строится по точкам:
В случае, если соответствующим образом подбирается очередная тройка чисел, через которые проводится парабола.
Каждая новая вершина параболы принимается за очередное приближенное решение.
На рисунке представлена блок-схема метода парабол, в которой итерационный процесс заканчивается как только абсциссы вершины последующей и предыдущей параболы разнятся менее, чем на .
Блок-схема метода квадратичной интерполяции
Описанная процедура квадратичной интерполяции называется методом Пауэлла и является частным (но наиболее часто используемым) случаем так называемого интерполяционного метода Лагранжа, который предусматривает аппроксимацию целевой функции полиномами любого порядка (а не только второго). Наиболее эффективна эта процедура при оптимизации квадратичных или близких к ним функций. В других случаях этот метод может быть не столь эффективным.
Метод квадратичной аппроксимации удобно применять после локализации точки минимума методом золотого сечения или методом Фибоначчи. Это объясняется тем, что для дважды дифференцируемой функции многочлен второго порядка достаточно хорошо аппроксимирует функцию в окрестности точки минимума.
Для оптимизации неквадратичных функций предложена модификация этого метода, состоящая в том, что для интерполяции выбираются не три, а четыре точки. При этом две внутренние точки используются по очереди с крайними точками для построения двух аппроксимаций точки минимума, выполняемых по алгоритму Пауэлла. Затем их взвешенная средняя выбирается для новой итерации. Такая процедура повышает надежность определения точки минимума для функций, не являющихся квадратичными.
Пример.
Найти минимум на отрезке c точностью
Пусть
1-й шаг:
по трем точкам (-1, 1), (0.5, 0.25), (1, 1) строим параболу и находим ее вершину
,
Требование по точности не выполнено, поэтому необходимо продолжить вычисления
,
, следовательно, следующую параболу строим по трем точкам: и находим
,
Вычисления завершены, в качестве приближенного решения получили .
Нетрудно убедится в том, что является точным решением задачи. Это совпадение объясняется тем, что есть многочлен 2-й степени, построенные интерполяционные многочлены, естественно, полностью совпали с .
Замечание.
В описанном алгоритме предполагалось, что унимодальна.
В случае, если этот метод применять для неунимодальной , алгоритм может зациклиться.
Чтобы избежать возможного зацикливания, целесообразно перед построением очередной параболы проводить проверку выпуклости трех выбранных точек. Значение функции в средней точкой должно быть меньше значений на концах рассматриваемого отрезка.
Метод кубической интерполяции
Суть алгоритма заключается в том, что на каждой итерации функция f(x) аппроксимируется кубическим полиномом F(x), точка минимума x(*) которого берется в качестве текущего приближения к искомому минимуму х*. Алгоритм предполагает вычисления в каждой очередной точке значений функции f(x) и ее производной f '(x).
Начальный этап. Задать , x1, h1 - параметры метода, имеющие общепринятый смысл. Методом Свенна установить начальный интервал [a, b]:
(1) изменить направление поиска h1 = -h1, если;
(2) вычислять fk в точках при до тех пор, пока не продвинемся в точку xm, такую, что;
(3) если, то положить, иначе.
Основной этап.
Шаг 1. Найти аппроксимирующий минимум:
(1) вычислить параметр
(2) принять аппроксимирующий минимум
,
и
Шаг 2. Проверить критерий окончания поиска: eсли поиск окончить. Иначе вернуться к шагу 1, используя новый интервал если, либо интервал если
При решении реальных задач редко приходится иметь дело с функциями одной переменной. Однако методы одномерной оптимизации важны при многомерной оптимизации, которая выполняется в основном по следующему правилу: зафиксировать некоторую точку, выбрать подходящее направление, выполнить одномерную оптимизацию из выбранной точки в выбранном направлении. Поэтому методы интерполяции полезны для выполнения линейного поиска при оптимизации функций многих переменных.
Рассмотренный метод кубической интерполяции является одним из интерполяционных методов Эрмита, приспособленным специально для оптимизации. Этот метод требует знания производных функций и используется в основном в так называемых квазиньютоновских методах многомерной оптимизации, которые и сами по себе используют производные.
Вообще говоря, надежность и скорость сходимости всех интерполяционных алгоритмов существенно зависит от того, насколько целевая функции соответствует модельной функции, положенной в основу метода. В некоторых случаях методы деления интервала оказываются лучше, чем интерполяционные. Например, поиск Фибоначчи эффективнее кубической интерполяции в случае логарифмической функции и в случае полинома высокой степени. Поэтому разрабатываются новые и более сложные схемы одномерной оптимизации, базирующиеся, в основном, на всевозможных комбинациях интерполяционных подходов и методов деления отрезка.
Пример.
Рассмотрим функцию, найдем точку ее минимума x* на отрезке
1-й шаг:
Вычисляем и по формуле получаем Находим , и
Так как , то поиск точки x* продолжаем на отрезке , где и, причем
2-й шаг:
и
Теперь искомая точка x* находится в интервале и
3-й шаг:
Итак, пришли к значению , у которого четыре верных знака после запятой совпадают с точным значением
Численные методы минимизации многоэкстремальных функций.
До сих пор рассматривались унимодальные функции, имеющие на отрезке единственную точку минимума. Если функция на отрезке многоэкстремальна (то есть существует несколько минимумов функции ), то возникает задача отыскания глобального минимума функции .
Пример такой функции, где - точка глобального минимума
Ограничимся рассмотрением функций, удовлетворяющих условию Липшица на отрезке :
,
где M - константа Липшица.
Существует несколько методов определения глобального минимума таких функций. Остановимся на двух из них: методе перебора и методе ломаных.
Метод перебора.
Суть метода перебора состоит в следующем: в точках отрезка
,
вычисляются значения функции и в качестве минимального значения принимается значение .
Погрешность метода не превосходит величины . Это легко показать, так как если точка глобального минимума, то очевидно, найдется такая точка , , что .
Тогда с учетом условия Липшица
Таким образом, задаваясь необходимой величиной погрешности можно определить требуемое количество точек на отрезке :
Блок-схема метода перебора приведена ниже.
Метод ломаных.
На отрезке выбирают точек
В каждой точке вычисляется значение функции и строится миноранта для функции, представляющая собой ломаную:
определяется точка x, в которой достигает минимума, и она принимается в качестве дополнительной точки для исследования функции на минимум
.
С введением точки миноранта преобразуется в миноранту и далее процесс введения следующей точки повторяется.
В качестве приближения к искомому значению минимума после вычислений значений функции принимается величина .
Очевидно, что погрешность метода не превосходит величины - .
Значение может быть задано или же будет определяться, исходя из требуемой точности вычисления значения минимума функции . Во втором случае вычисления прекращаются, как только -
При реализации обоих методов требуется знать значение константы Липшица . На практике значение часто неизвестно. В этом случае в качестве можно использовать оценку
,
Лекция 5. Методы многомерной безусловной минимизации
Постановка задачи и классификация методов.
Под задачей многомерной безусловной оптимизации будем понимать задачу нахождения минимума,- вектор n - мерного евклидова пространства; - компоненты вектора . Обычно эта задача записывается как
.
Метод, использующий для своей реализации значения , а также ее производных до m-го порядка включительно, называется методом m-го порядка.
Рассмотрим наиболее применяющиеся методы:
0 - го порядка, использующие только значения ;
1 - го порядка, использующие значения , а также значения ее первых производных;
2 - го порядка, использующие значения , а также значения ее первых и вторых производных.
Все рассматриваемые методы характеризуются тем, что строится некоторая последовательность векторов , имеющая для всех методов, кроме метода случайного поиска, вид
,
k - номер члена последовательности или номер итерации.
Вектор определяет направление -го шага минимизации, - длину этого шага.
Последовательность сходится к точке минимума , если , а метод, реализующий такую последовательность, называется сходящимся.
Естественно, что не всегда метод будет сходящимся, поэтому вопросу сходимости при рассмотрении конкретных методов уделяется одно из центральных мест.
Установление факта сходимости и оценка скорости сходимости дает существенную информацию о выбранном методе минимизации.
Поскольку речь идет о численных методах решения, необходимо задавать точность, с которой ищется решение. Приближение имеет точность , если ,
означает норму вектора B. В основном будем использовать норму , где - - я компонента вектора B. В случае использованию других норм будут сделаны специальные оговорки.
Итак, если применяется сходящийся численный алгоритм, необходимо выработать критерии остановки вычислительного процесса, гарантирующие выполнение требования по точности.
Обычно на практике применяются следующие критерии остановки:
1.
2.
3. ,
где - малые константы;
- градиент функции , вычисленный в точке .
Градиентом функции в точке называется вектор, компоненты которого есть частные производные по компонентам вектора , вычисленные в точке .
Обычно используется либо один критерий, либо два из предложенных, либо все три критерия.
Градиентные методы.
Известно, что функция многих переменных наиболее сильно убывает в направлении антиградиента функции в этой точке, то есть в направлении вектора .
Это локальное свойство положено в основу целой серии методов, называемых градиентными и задаваемых отношением
,
- вектор начального приближения;
- шаг метода.
Метод наискорейшего спуска.
Если на каждом шаге выбирать как значение, обеспечивающее , то мы и получим метод наискорейшего спуска, то есть на каждой итерации необходимо решать задачу одномерной минимизации, которая в основном решается численно.
Итак, для того чтобы использовать метод наискорейшего спуска, необходимо задать правила вычислений , (предварительно продифференцировав ), выбрать метод одномерной минимизации.
На рисунке 5.1 представлена укрупненная блок-схема такого алгоритма, где критерием окончания счета выбрана близость градиента нулю.
Пример. Найти минимум
Методом наискорейшего спуска вычисления будут производится по расчетной формуле
Как и в предыдущих случаях в качестве начального приближения возьмем .
на каждой итерации находится классическим методом, то есть приравниванием производной нулю.
Блок-схема метода наискорейшего спуска
Результаты вычислений по итерациям
|
Номер итерации |
||||
|
0 |
0,06097 |
0 |
0 |
|
|
1 |
0,2778 |
1,09756 |
-0,36585 |
|
|
2 |
-0,06 |
0,60976 |
-1,82928 |
|
|
3 |
0,322 |
1,0312 |
-1,96977 |
|
|
4 |
0,0592 |
0,8504 |
-2,6332 |
|
|
5 |
0,3218 |
1,0098 |
-2,6766 |
|
|
6 |
0,05578 |
0,95303 |
-2,8847 |
|
|
7 |
0,3782 |
1,00293 |
-2,8976 |
|
|
8 |
0,04596 |
0,98646 |
-2,975 |
|
|
9 |
0,99766 |
-2,9773 |
Как показано выше, точным решением этой задачи является , проведенные 9 итераций не обеспечили получение приближенного решения с точностью .
Ломаная траектории метода наискорейшего спуска имеет характерные особенности.
Изменим немного вид исходной функции. Пусть
.
Нетрудно показать, что точкой минимума и этой функции будет . Применим метод наискорейшего спуска, начав с точки .
Расчетная формула метода имеет вид
,
Найдем из условия
Отсюда , то есть за один шаг попали в точку минимума.
Чем же разнятся эти задачи, дающие разные по трудоемкости вычислительные процедуры?
Представим линии уровня каждой из функций.
Для
линиями уровня будут кривые
Получили каноническое уравнение эллипса, из которого видно, что одна из полуосей в 3 раза меньше другой, то есть эллипс вытянут вдоль оси .
Для линиями уровня будут концентрические окружности с центром в точке .
На рисунке с нанесенными на плоскость линиями уровня представлена траектории движения из точки в точку , соответствующая методу наискорейшего спуска для функции
На рисунке 5.3 то же проделано для функции
Траектория движения из точки в точку функции
Траектория движения из точки в точку функции
Чем больше вытянуты линии уровня, тем сильнее будет эффект «зигзага» траектории. В этом случае функция имеет так называемый «овражный» характер, то есть небольшое изменение переменной приводит к резкому изменению значений функции, а по переменной функция меняется незначительно. В процессе реализации градиентного метода очередные приближения будут прыгать со склона на склон, что может сильно замедлить сходимость метода. Этой проблеме уделяется достаточно серьезное внимание, в настоящее время существуют специальные методы.
Градиентный метод с дроблением шага.
В методе наискорейшего спуска на каждом шаге необходимо решать задачу одномерной минимизации, для чего используется один из методов одномерной минимизации, предполагающих наличие одного минимума внутри некоторого отрезка, в чем не всегда бывает уверенность. Поэтому широко используется градиентный метод без одномерной минимизации, основанный на пошаговой корректировке коэффициента . По-прежнему расчетной будет формула
,
задаемся некоторым . Полагаем . Если при этом , то удваиваем шаг: . Процесс удвоения продолжаем до тех пор, пока убывание не прекратится.
Если , то полагаем: , если при этом не произошло уменьшение значения функции, то процесс дробления продолжаем до тех пор, пока не наступит убывание.
Эта логика работает на каждом шаге.
Этот метод сойдется, если выпукла и не является «овражной».
Метод сопряженных градиентов
Метод сопряженных градиентов отличается от градиентных методов более высокой скоростью сходимости, которая при определенных предположениях относительно целевой функции, приближается к скорости сходимости метода Ньютона.
Рассмотренные выше градиентные методы отыскивают точку минимума функции в общем случае лишь за бесконечное число итераций. Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции. Это существенно увеличивает скорость их сходимости и позволяет, например, минимизировать квадратичную функцию
с симметрической положительно определенной матрицей Н за конечное число шагов п, равное числу переменных функции. Любая гладкая функция в окрестности точки минимума хорошо аппроксимируется квадратичной, поэтому методы сопряженных градиентов успешно применяют для минимизации и неквадратичных функций. В таком случае они перестают быть конечными и становятся итеративными.
По определению, два n-мерных вектора х и у называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение. Здесь Н - симметрическая положительно определенная матрица размером пхп.
Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента в направление -сопряженное с ранее найденными направлениями. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.
Направления р[k] вычисляют по формулам:
.
Величины вk-1 выбираются так, чтобы направления были H-сопряженными:
В результате для квадратичной функции
,
итерационный процесс минимизации имеет вид
,
где р[k] - направление спуска на k-м шаге; аk - величина шага. Последняя выбирается из условия минимума функции f(х) по а в направлении движения, т. е. в результате решения задачи одномерной минимизации:
Для квадратичной функции
Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.
1. В точке х[0] вычисляется
2. На k-м шаге по приведенным выше формулам определяются шаг аk. и точка
3. Вычисляются величины
4. Если, то точка является точкой минимума функции f(х). В противном случае определяется новое направление из соотношения
и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за n шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после й итерации процедуры 1-4 циклически повторяются с заменой на а вычисления заканчиваются при , где - заданное число.
Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис. 5.4). Из заданной начальной точки осуществляется спуск в направлении В точке определяется вектор-градиент Поскольку является точкой минимума функции в направлении , то ортогонален вектору Затем отыскивается вектор, H-сопряженный к . Далее отыскивается минимум функции вдоль направления и т. д.
Траектория спуска в методе сопряженных градиентов
Методы сопряженных направлений являются одними из наиболее эффективных для решения задач минимизации. Однако следует отметить, что они чувствительны к ошибкам, возникающим в процессе счета. При большом числе переменных погрешность может настолько возрасти, что процесс придется повторять даже для квадратичной функции, т. е. процесс для нее не всегда укладывается в п шагов.
Метод тяжелого шарика
Общий вид метода тяжелого шарика:
где L - параметр условия Лившица которому должна удовлетворять оптимизируемая функция. На практике обычно выбирают
Это разностное уравнение, полученное из дифференциального уравнения, которое описывает движение шарика, катящегося по некоторой поверхности с постоянным трением. Введение инерции увеличивает скорость сходимости.
Метод тяжелого шарика при и сходится со скоростью геометрической прогрессии со знаменателем .
Если теперь сравнить знаменатели и , характеризующие скорости сходимости градиентного метода и метода тяжелого шарика, соответственно, то для плохо обусловленных функций, т. е. для функций с , очевидно, . Поэтому для уменьшения погрешности в e » 2.718 раз градиентный метод с постоянным оптимальным шагом требует итераций, а метод тяжелого шарика . Для больших m это весьма значительный выигрыш, поскольку объем вычислений в методе тяжелого шарика почти не отличается от объема вычислений в градиентном методе.
Лекция 6. Методы второго порядка многомерной безусловной минимизации
Методы второго порядка.
Методом второго порядка называется метод, использующий значения минимизируемой функции, а также значения ее первых и вторых производных. Отсюда следует, что для использования методов второго порядка необходимым условием является дважды дифференцируемость
Метод Ньютона.
Центральное место среди методов второго порядка занимает метод Ньютона. Этот метод основан на квадратичной аппроксимации . Матрица вторых производных должна быть невырожденной.
Пусть - k - е приближение к точке минимума. Покажем, как, зная его, можно получить следующее приближение .
Разложим в ряд Тейлора в окрестности точки , оставляя члены разложения не выше второго:
В этой формуле использовано традиционное обозначение скалярного произведения векторов a и b как (a,b).
- матрица вторых производных , вычисленных в приближении .
Разложение в ряд Тейлора используется для того, чтобы через него определить следующее приближение как точку минимума , удовлетворяющую соотношению
Или
,
Откуда
Такая формула носит название формулы Ньютона.
Если начальное приближение выбрано достаточно близко к точке минимума, а - сильно выпуклая функция, метод Ньютона будет сходится с квадратичной скоростью сходимости, то есть
Можно показать, что для любой квадратичной функции с положительно определенной матрицей вторых производных метод Ньютона дает точное решение независимо от начального приближения за одну итерацию. На рисунке 6.1 представлена блок-схема метода Ньютона. Итак, метод Ньютона как метод второго порядка имеет быструю сходимость, если начальное приближение близко к точке минимума, однако, он может работать плохо или даже отказать вдали от точки минимума. Нелегкой задачей является процедура нахождения матрицы вторых производных. Обычно метод Ньютона используется на заключительном этапе, когда на начальном этапе работают другие методы. На практике находят широкое применение модификации метода Ньютона, направленные на то, чтобы, сохраняя основное достоинство метода - его быструю сходимость, уменьшить трудоемкость и ослабить требования на выбор начального приближения.
Блок - схема метода Ньютона
Пример.
Найти точку минимума с точностью .
Решение.
По критерию Сильвестра матрица является положительно определенной.
Согласно критерию Сильвестра матрица положительна определена, если , а также определители всех миноров второго, ...., n - го порядка, окаймляющих этот элемент положительны.
Для этой задачи расчетная формула метода Ньютона будет иметь вид:
Введем критерии остановки:
В качестве начального приближения возьмем
Делаем первую итерацию по формуле Ньютона:
Проверяем критерий остановки:
следовательно, необходимо продолжить вычисления.
Делаем вторую итерацию по методу Ньютона:
Второе приближение совпало с первым, кроме того,
то есть, выполнены все итерации остановки и решением поставленной задачи будет
Методы Ньютона с регулировкой шага.
Эти методы еще называют методами Ньютона -- Рафсона, или демпфированными методами Ньютона. Они строятся по аналогии с градиентными методами с переменным шагом. Общий вид их таков
Длина шага может выбираться с помощью алгоритма дробления шага, требуя, например, выполнения неравенства
или, как в методе наискорейшего спуска полагая
Можно показать, что методы Ньютона -- Рафсона для сильно выпуклых функций глобально квадратично сходятся (по крайней мере для описанных выше алгоритмов выбора шага), причем вдали от точки минимума они сходятся линейно.
Метод Левенберга--Маркардта.
Этот метод основан на следующей идее. Чтобы избежать расходимости приближений метода Ньютона, вызванных неудачным выбором начального приближения, можно попытаться запретить следующей итерации быть слишком далеко от предыдущей. Для этого следующую итерацию ищут из условия
где ln -- некоторый параметр (вообще говоря, свой на каждом шаге). Первые три слагаемых в определении функции j представляют собой квадратичную аппроксимацию функции f, а последнее слагаемое -- "штраф", не позволяющий точке xn+1 уходить далеко от точки xn (с идеями метода штрафов мы еще столкнемся ниже).
(6.1)
Последняя формула и есть метод Левенберга--Маркардта.
Очевидно, что если ln = 0, то (6.1) представляет собой метод Ньютона, а если ln велико, то (поскольку [f ўў(xn) + lnI]-1 » (ln)-1I при больших ln) формула (6.1) близка к градиентному методу. Поэтому, подбирая значения параметра ln, можно добиться, чтобы метод (6.1), во-первых, сходился глобально, и во-вторых, квадратично. Можно, например, выбирать ln из следующих соображений: угол между направлениями шага и антиградиента должен быть острым, а значение функции на каждом шаге должно квалифицировано убывать. В этом случае ln должно удовлетворять следующим условиям (здесь мы обозначаем "антинаправление" шага [f ўў(xn) + lnI]-1f ў(xn) через yn)
где e1 О (0, 1) и e2 О (0, 1/2) -- параметры.
Модифицированный метод Ньютона.
В некоторых задачах более существенным недостатком метода Ньютона является его большая вычислительная трудность: на каждом шаге требуется вычисление оператора (матрицы) и его (ее) обращение, что при больших размерностях стуит в вычислительном плане очень дорого. Один из способов обхода этих трудностей состоит в "замораживании" оператора -- использовании на каждом шаге взамен:
(6.2)
Геометрическая интерпретация модифицированного метода Ньютона
Можно показать, что при естественных ограничениях модифицированный метод Ньютона сходится лишь линейно (это плата за уменьшение объема вычислений). Можно также не замораживать оператор навсегда, а обновлять его через определенное число шагов, скажем k:
(6.3.)
здесь [a] в верхнем индексе обозначает целую часть числа a. Можно доказать, что если функция f сильно выпукла и f ўў удовлетворяет условию Липшица, то
т. е. за k шагов порядок погрешности уменьшается в k + 1 раз, что соответствует следующей оценке погрешности на каждом шаге:
Другими словами, метод (6.3) является методом -го порядка сходимости. Таким образом, метод (6.3) занимает промежуточное положение между методом Ньютона (k = 1) и модифицированным методом Ньютона (6.2) (k = Ґ) как по скорости сходимости, так и по объему вычислений.
Квазиньютоновские методы. (Методы первого порядка)
Эти методы можно рассматривать как определенную модификацию метода Ньютона, заключающуюся в аппроксимации матрицы
Расчетной формулой квазиньютоновских методов будет следующая формула:
,
- шаг в выбранном направлении;
- матрица k-го порядка, аппроксимирующая матрицу
Длина шага часто выбирается из условия минимизации целевой функции вдоль выбранного направления, то есть решения на каждой итерации задачи одномерной минимизации функции по параметру .
Иногда параметр выбирается на каждой итерации путем дробления шага: шаг устраивает нас, если при таком шаге уменьшается, в противном случае уменьшается(дробится) до тех пор, пока не будет достигнуто уменьшение , либо будет сделан вывод о невозможности уменьшения значения в этом направлении.
Рассмотрим вопрос о нахождении матрицы .
Заметим, что если дважды дифференцируема, то для производной (исходя из применения формулы Тейлора) справедливо следующее соотношение:
Отсюда с точностью до членов более высокого порядка, чем , имеем:
Заметим, что для квадратичной функции эта формула точна. Для матрицы , которая будем аппроксимировать , потребуем выполнения условия:
Такое условие называется квазиньютоновским.
Методы минимизации, для которых на каждом шаге выполняется квазиньютоновское свойство, называются квазиньютоновскими.
Будем искать в виде .
Для этого перепишем квазиньютоновское свойство:
Только этому условию удовлетворяет большое число матриц.
Поскольку матрица Гессе симметрична, будем пытаться сохранить эту симметрию. Кроме того, потребуем от единичного ранга (Алгоритм Бройзена)(существуют варианты, когда у предполагается более высокий ранг).
При сделанных нами предположениях определяется единственным образом:
где
В качестве , если нет никаких специальных соображений, удобно выбирать единичную матрицу.
Пример 2.
Найти точку минимума с точностью .
Решение
В качестве выберем единичную матрицу
Положим
(Заметим, что эту же задачу мы решали методом Ньютона).
найдем как параметр, минимизирующий классическим методом, то есть приравниванием производной нулю
.
Тогда
Вычисления производятся с 5 знаками после запятой.
удовлетворяет следующему соотношению:
Отсюда
Делаем вторую итерацию
Ранее эта задача была решена, и мы видим, что в пределах точности последнее решение совпадает с точным. Матрица совпадает с обратной матрицей вторых производных. Квазиньютоновские методы всегда сходятся к точному решению за n шагов.
Формально эти методы относятся к методам первого порядка, однако, их сходимость выше сходимости указанных методов в силу хорошей аппроксимации обратной матрицы вторых производных, что обеспечивает их широкую применимость.
Интересным является тот факт, что рассмотренный выше квазиньютоновский метод (метод 1-го порядка) обеспечивает для той же задачи получение точного решения за 2 шага, в то время, как метод наискорейшего спуска требует существенно большего числа итераций.
На рисунке 6.2 для трех рассмотренных выше методов представлены траектории движения из начальной точки в точку минимума .
Сплошная линия соответствует методу наискорейшего спуска, пунктирная - квазиньютоновскому методу (Бройзена), пунктирная с точками - методу Ньютона.
Траектория движения из точки в точку минимума функции
Известные формулы перерасчета.
Формула пересчета Девидона-Флетчера-Пауэлла (DFP):
(6.4)
Формула пересчета Бройзена-Флетчера-Гольдфарба-Шанно (BFGS):
,
.
Однопараметрическое семейство формул объединяет в себе две предыдущие формулы (6.4), (6.5) :
Формулу (1.8) можно представить в виде:
,
Где
, (6.8)
Лекция 7. Методы нулевого порядка многомерной безусловной оптимизации
Методы нулевого порядка.
В практических задачах нередки случаи, когда минимизируемая функция либо не обладает нужной гладкостью, либо является гладкой, но вычисление производных с нужной точностью является слишком трудоемким. В таких случаях применяют методы минимизации, которые требуют лишь вычисления значений функций, то есть методы 0-го порядка.
Метод покоординатного спуска.
Суть метода состоит в том, что задав начальное приближение выбирается направление движения по одной из покоординатных осей, причем, на последующих шагах идет циклический перебор направлений по координатным осям.
Наиболее распространенным является метод покоординатного спуска с дроблением шага.
Обозначим - единичный координатный(базисный) вектор, у которого i - я координата равна 1, а остальные равны 0.
Положим
; ,
- целая часть числа .
Будем иметь
Опишем подробно одну итерацию.
Пусть получено . Будем искать .
Вычислим значение функции в точке и проверим неравенство
.
Если это неравенство выполняется, то полагаем
.
В случае, если неравенство не выполняется, то вычисляем и проверим неравенство
.
В случае выполнения последнего неравенства полагаем
.
В случае невыполнения обоих неравенств полагаем
,
- параметр метода; .
Последние условия означают, что если за один цикл из n итераций при переборе направлений всех координатных осей с шагом реализовалась хотя бы одна удачная итерация, то длина шага не дробится и сохраняется по крайне мере на протяжении следующего цикла из n итераций.
Если же среди последних n итераций не оказалось ни одной удачной, то шаг дробится.
Сходимость метода обеспечена для гладких функций, несмотря на то, что это метод 0-го порядка. Оказывается, что если не является гладкой, то метод покоординатного спуска может не сходится к решению.
Другой вариант метода покоординатного спуска может состоять в получении как решения задачи одномерной минимизации:
.
Этот вариант имеет смысл применять в том случае, когда можно найти явно.
Хотя скорость сходимости метода покоординатного спуска невысокая, благодаря его простоте и скромным требованиям к гладкости этот метод довольно широко применяется на практике.
На рисунке приведена блок-схема метода покоординатного спуска для функции дух переменных с оптимизацией длины шага.
Блок-схема метода покоординатного спуска
Пример.
Найти минимум
Напомним, что эту задачу мы решали рассмотренными выше методами и встретились с трудностями в силу ее овражности.
Положим, как и раньше,
;
Находим как решение задачи одномерной минимизации, а именно, ищем , обеспечивающее минимум , это будет .
Отсюда
Далее
;
В результате выполнения 2-й итерации получили точное решение.
Метод Хука-Дживса
Суть этого метода состоит в следующем. Задаются некоторой начальной точкой . Изменяя компоненты вектора , обследуют окрестность данной точки, в результате чего находят направление, в котором происходит уменьшение минимизируемой функции . В выбранном направлении осуществляют спуск до тех пор, пока значение функции уменьшается. После того как в данном направлении не удается найти точку с меньшим значением функции, уменьшают величину шага спуска. Если последовательные дробления шага не приводят к уменьшению функции, от выбранного направления спуска отказываются и осуществляют новое обследование окрестности и т. д.
Метод Хука-Дживса
1-поиск по образцу; 2- исследующий поиск вдоль координатных осей.
Метод Хука и Дживса осуществляет два типа поиска - исследующий поиск и поиск по образцу. Первые две итерации процедуры показаны на рисунке 7.3.
При заданном начальном векторе x1 исследующий поиск по координатным направлениям приводит в точку x2 . Последующий поиск по образцу в направлении x1- x2 приводит в точку y. Затем исследующий поиск, начинающийся из точки y, дает точку x3. Следующий этап поиска по образцу вдоль направления x3- x2 дает y*. Затем процесс повторяется.
Алгоритм Хука-Дживса
Шаг А. Выбрать начальную базисную точку B1 и шаг длиной hj для каждой переменной xj, j = 1, . . . , n.
Шаг Б. Вычислить в базисной точке B1 с целью получения сведений о локальном поведении функции. Эти сведения будут использованы для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значений функции. Информация о локальном поведении находится следующим образом:
1. Вычисляется значение функции в базисной точке B1.
2. Каждая переменная по очереди изменяется прибавлением длины шага.
Вычисляются значения функции , где - единичный вектор в направлении оси xj. Если это приводит к уменьшению значения функции, то B1 заменяется на . В противном случае вычисляется значение , если значение функции уменьшилось, то B1 заменяется на . Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка B1 остается без изменения и рассматриваются изменения в направлении следующей оси и т.д. После рассмотрения всех n переменных получают новую базисную точку B2.
3. Если B2=B1, то есть уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки B1, но с уменьшенной длиной шага (обычно шаг уменьшается в десять раз).
4. Если B2B1, то производится поиск по образцу.
Шаг В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции совершается поиском в направлении, заданном образцом:
1. Разумно двигаться из базисной точки B2 в направлении B2-B1, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке P = B1 + 2(B2-B1).
2. Провести исследующий поиск вокруг точки P.
3. Если наименьшее значение на шаге B-2 меньше значения в базисной точке B2, то получают новую базисную точку B3 и переходят к шагу B-1. В противном случае не проводят поиск по образцу из точки B2, а проводят исследующий поиск в точке B2.
...Подобные документы
Методы условной и безусловной нелинейной оптимизации. Исследование функции на безусловный экстремум. Численные методы минимизации функции. Минимизация со смешанными ограничениями. Седловые точки функции Лагранжа. Использование пакетов MS Excel и Matlab.
лабораторная работа [600,0 K], добавлен 06.07.2009Формирование функции Лагранжа, условия Куна и Таккера. Численные методы оптимизации и блок-схемы. Применение методов штрафных функций, внешней точки, покоординатного спуска, сопряженных градиентов для сведения задач условной оптимизации к безусловной.
курсовая работа [1,8 M], добавлен 27.11.2012Математическое программирование - область математики, в которой изучаются методы решения задач условной оптимизации. Основные понятия и определения в задачах оптимизации. Динамическое программирование – математический метод поиска оптимального управления.
презентация [112,6 K], добавлен 23.06.2013Поиск оптимальных значений некоторых параметров в процессе решения задачи оптимизации. Сравнение двух альтернативных решений с помощью целевой функции. Теорема Вейерштрасса. Численные методы поиска экстремальных значений функций. Погрешность решения.
презентация [80,6 K], добавлен 18.04.2013Рассмотрение эффективности применения методов штрафов, безусловной оптимизации, сопряженных направлений и наискорейшего градиентного спуска для решения задачи поиска экстремума (максимума) функции нескольких переменных при наличии ограничения равенства.
контрольная работа [1,4 M], добавлен 16.08.2010Математическая задача оптимизации. Минимум функции одной и многих переменных. Унимодальные и выпуклые функции. Прямые методы безусловной оптимизации и минимизации, их практическое применение. Методы деления отрезка пополам (дихотомия) и золотого сечения.
курсовая работа [2,0 M], добавлен 26.08.2009Проектирование методов математического моделирования и оптимизации проектных решений. Использование кусочной интерполяции при решении задач строительства автомобильных дорог. Методы линейного программирования. Решение специальных транспортных задач.
методичка [690,6 K], добавлен 26.01.2015Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа [517,9 K], добавлен 30.04.2011Оптимизация как раздел математики, ее определение, сущность, цели, формулировка и особенности постановки задач. Общая характеристика различных методов математической оптимизации функции. Листинг программ основных методов решения задач оптимизации функции.
курсовая работа [414,1 K], добавлен 20.01.2010Изучение методов одномерной оптимизации и сравнение эффективности их применения для конкретных целевых функций. Нахождение минимума функции 1/|x-3|3 методами перебора, поразрядного поиска, дихотомии, золотого сечения, средней точки, хорд и Ньютона.
курсовая работа [761,8 K], добавлен 25.12.2015Сущность и характеристика метода покоординатного спуска (метод Гаусса-Зейделя). Геометрическая интерпретация метода покоординатного спуска для целевой функции z=(x,y). Блок-схема и алгоритм для написания программы для оптимизации методом Хука-Дживса.
контрольная работа [878,3 K], добавлен 26.12.2012Численные методы представляют собой набор алгоритмов, позволяющих получать приближенное (численное) решение математических задач. Два вида погрешностей, возникающих при решении задач. Нахождение нулей функции. Метод половинного деления. Метод хорд.
курс лекций [81,2 K], добавлен 06.03.2009Численные методы решения систем линейных алгебраических уравнений, алгоритмы, их реализующие. Нормы матриц и векторов, погрешность приближенного решения системы и обусловленность матриц. Интеграционные методы решения: методы простой итерации, релаксации.
учебное пособие [340,6 K], добавлен 02.03.2010Математическая формулировка задачи, существующие численные методы и схемы алгоритмов. Интерполирование функции, заданной в узлах, методом Вандермонда. Среднеквадратичное приближение функции. Вычисление интеграла функций по составной формуле трапеций.
курсовая работа [3,4 M], добавлен 14.04.2009Общие свойства функций. Правила дифференциального исчисления. Неопределенный и определенный интегралы, методы их вычисления. Функции нескольких переменных, производные и дифференциалы. Классические методы оптимизации. Модель потребительского выбора.
методичка [2,0 M], добавлен 07.01.2011Численные методы решения систем линейных уравнений: Гаусса, простой итерации, Зейделя. Методы аппроксимации и интерполяции функций: неопределенных коэффициентов, наименьших квадратов. Решения нелинейных уравнений и вычисление определенных интегралов.
курсовая работа [322,7 K], добавлен 27.04.2011Понятие и отличительные особенности численных методов решения, условия и возможности их применения. Оптимизация функции одной переменной, используемые методы и закономерности их комбинации, сравнение эффективности. Сущность и разновидности интерполяции.
реферат [273,3 K], добавлен 29.06.2015Понятие о многокритериальной оптимизации. Линейное и математическое программирование, дающие численные решения многомерных задач с ограничениями. Решение задачи на ранжирование для определения оптимального объекта, исходя из определяющих его параметров.
реферат [254,5 K], добавлен 31.05.2014Выполнение алгебраических преобразований, логическая культура и техника исследования. Основные типы задач с параметрами, нахождение количества решений в зависимости от значения параметра. Основные методы решения задач, методы построения графиков функций.
методичка [88,2 K], добавлен 19.04.2010Составление уравнения Эйлера, нахождение его общего решения. Нахождение с использованием уравнения Эйлера-Лагранжа оптимального управления, минимизирующего функционал для системы. Использование метода динамического программирования для решения уравнений.
контрольная работа [170,3 K], добавлен 01.04.2010
