Методы нелинейной оптимизации

Методы нелинейной оптимизации

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

«Нижегородский государственный архитектурно-строительный университет»

Международный факультет экономики, права и менеджмента

Расчетно-графическая работа

по дисциплине «Исследование операций и методы оптимизации»

по теме «Методы нелинейной оптимизации»

Выполнил студент

Курс III

Группа ПИэ 13.13

Преподаватель

Нижний Новгород

год

Содержание

Постановка задачи

Определение унимодальности функции

Точный метод поиска экстремума

Приближенные методы поиска экстремума

.1 Метод перебора

.2 Метод поразрядного поиска

.3 Метод дихотомии

.4 Метод золотого сечения

.5 Метод средней точки

.6 Метод хорд

.7 Метод Ньютона

Сравнение методов

1 Постановка задачи

Знакомство с оптимизационными задачами, изучение различных методов одномерной оптимизации и сравнение эффективности их применения для конкретных целевых функций.

Нахождение минимума функции 1/|x-3|3 методами перебора, поразрядного поиска, дихотомии, золотого сечения, средней точки, хорд и Ньютона на интервале [2;4] cточностью до e=0,05, а также сравнение методов по скорости вычисления и точности.

2 Определение унимодальности функции

нелинейный оптимизация минимум функция

Функция F(x) является унимодальной на отрезке [A, B] в том и только в том случае, если она монотонна по обе стороны от единственной на рассматриваемом интервале оптимальной точки х* и принимаем значения f``(x)≥0.

Определим унимодальность заданной функции 1/|x-3|3 двумя способами.

Аналитический способ. Найдем последовательно первую и вторую производные функции:

3/|x-3|4

-12/|x-3|5

Для аналитического определения унимодальности необходимо решить уравнение .

Графический способ

3 Точный метод поиска экстремума

1) Найти производную функции .

) Найти стационарные точки (точки, подозрительные на экстремум), решив уравнение .Обратить внимание на точки, в которых не существует двусторонней конечной производной.

) Выяснить, меняет ли производная свой знак в точках, подозрительных на экстремум. Если она меняет знак с минуса на плюс, то в этой точке функция имеет свой минимум. Если с плюса на минус, то максимум, а если знак производной не меняется, то экстремума в этой точке нет.

) Найти значение функции в точках минимума (максимума).

3/|x-3|4;

/|x-3|4 ≠ 0;

 - глобальный минимум .

4 Приближенные методы поиска экстремума

.1 Метод перебора

Описание:

Метод перебора - простейший из методов поиска значений действительно-значных функций <#"878190.files/image010.gif">=a+i*(b-a)/10, i=2,...2,9

)Вычислив значения F(x) в точках . путем сравнения найдем точку

. где m - это число от 2 до 2,9. такую, что F() = minF() для всех i от 2 до 2,9.

)Погрешность определения точки минимума  функции F(x) методом перебора не превосходит E=(b-a)/n.

Для заданной функции

4.2 Метод поразрядного поиска

Описание:

Метод поразрядного поиска. Этот метод представляет собой усовершенствование метода перебора. Поиск точки минимума функции осуществляется с переменным шагом.

Алгоритм:

) Выбрать начальный шаг h=(b-a)/4. Положить х0=а. Вычислить F(x0).

2) Положить =+h. Вычислить F().

) Сравнить F() и F(). Если F()>F(), то перейти к шагу 4, иначе - к шагу 5.

) Положить =и F()=F(). Проверить условие принадлежности хо интервалу [а, b]. Если а <<b, то перейти к шагу 2, иначе - к шагу 5.

) Проверка на окончание поиска: если |h| <= e, то вычисления завершить, полагая х*=, Fmin=F(), иначе - перейти к шагу 6.

) Изменить направление поиска: положить =, F()=F(), h=-h/4.Перейти к шагу 2.

Для заданной функции:

Блок-схема:

4.3    Метод дихотомии

Описание:

Этот метод является методом прямого поиска. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.

Алгоритм:

Дана функция F(x). Необходимо найти , доставляющий минимум (или максимум) функции F(x) на интервале [a,b] с заданной точностью .

) На каждом шаге процесса поиска делим отрезок [a,b] пополам, x=(a+b)/2 - координата середины отрезка [a,b].

2) Вычисляем значение функции F(x ±вычисленной точки x.

) Сравниваем F1 и F2 и отбрасываем одну из половинок отрезка [a,b].

Если F1<F2, то отрезок [x,b], тогда b=x. Иначе отрезок [a,x], тогда a=x.

) Деление отрезка [a,b] продолжается, пока его длина не станет меньше заданной точности , т.е.

Блок схема:

Для заданной функции

4.4 Метод золотого сечения

Описание:

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

Алгоритм:

) Задаются начальные границы отрезка [a ; b] и точность .

) Рассчитывают начальные точки:

и значения в них целевой функции <https://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BB%D0%B5%D0%B2%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F>:

Если  (для поиска max изменить неравенство на ), то

Иначе .

)Если , то  и останов. Иначе возврат к шагу 2.

Блок схема:

Для заданной функции

.5 Метод средней точки

Описание: основан на алгоритме исключения интервалов, на каждой итерации которого рассматривается одна пробная точка R. Если в точке R выполняется неравенство f'(R) < 0, то в следствии унимодальности функции точка оптимума не может лежать левее точки R. Аналогично, если f'(R) > 0, то интервал x>R можно исключить.

Алгоритм:

1) Определить = , на заданном отрезке [a;b].

) Вычислить f '().

) Проверить критерий окончания вычислений. Если êf '() ê£e, ,перейти к шагу 5, иначе - к шагу 4.

) Перейти к новому отрезку локализации [a, b]. Если f '() > 0, то положить b = . Иначе положить a = . Перейти к шагу 2.

) Положить x* ». Вычислить f(x*).

Блок-схема:

Для заданной функции

4.6 Метод хорд

Описание: Ориентирован на нахождение корня уравнения f'(x) в интервале [a;b], в котором имеются две точки N и P, в которых знаки производных различны. Алгоритм метода хорд позволяет аппроксимировать функцию f'(x) "хордой" и найти точку, в которой секущая графика f'(x) пересекает ось абсцисс.

Алгоритм:

В этом методе кривая f(x) заменяется прямой линией - хордой. В зависимости от знака выражения f(a)*f //(a) метод хорд имеет два варианта.

Если f(a) f //(a)>0, то x0=b и

.

Если же f(a) f //(a)<0, то x0=a и

.

Окончание итерационного цикла в этом методе происходит по условию: |f(x1)| < ε или .

Блок-схема:

Для заданной функции:

Так как x*=1,749944 не попадает на отрезок [2;2,9], то приравняем x к самому наиближайшему числу на отрезке.

x=2 , следовательно Fmin = 1.

4.7 Метод Ньютона

Описание: Ориентирован на нахождение корня уравнения f'(x) в интервале [a,b], в котором имеются две точки N и P, в которых знаки производных различны. Работа алгоритма начинается из точки xo, которая представляет начальное приближение корня уравнения f'(x)=0. Далее строится линейная аппроксимация функции f'(x) в точке x1, и точка, в которой аппроксимирующая линейная функция обращается в нуль, принимается в качестве следующего приближения. Если точка xk принята в качестве текущего приближения к оптимальной точке, то линейная функция, аппроксимирующая функцию f'(x) в точке xk, записывается в виде

f'(x,xk) = f'(xk) + f''(xk)(x-xk)

Алгоритм:

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

) В точке F(x0) строится касательная к кривой у = F(x) и ищется ее пересечение с осью х. Точка пересечения принимается за новую итерацию. Метод Ньютона самый быстрый способ нахождения корней уравнений.

) Высчитываем по формуле:

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

Блок схема:

Для заданной функции:

Сравнение методов

Для данной функции самыми точными оказались: Точный метод , метод перебора, метод средней точки и метод поразрядного поиска

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