лаба4вариант1

Филиал ФБГОУ ВПО «УГАТУ»

в г.Кумертау

Кафедра ИИТ

Лабораторная работа №4

Метод Ньютона поиска экстремума

по дисциплине

«Теория оптимизации и комплексирования»

Выполнили: ст. гр. АП-509д

Насретдинов Р.М.

Проверил: ассистент

Мизин С.В.

г. Кумертау

2012 г.

Метод Ньютона поиска экстремума

Цель работы

Изучение численного метода Ньютона поиска экстремума и программ поиска экстремума функций системы MATLAB.

Задание

1. Изучить метод Ньютона для численного решения системы нели­нейных уравнений.

2. Изучить метод Ньютона для поиска экстремумов функции многих переменных.

3. Вычислить экстремум функции многих переменных методом Ньютона.

4. Изучить способы программирования для определения экстрему­мов функции многих переменных в системе MATLAB.

5. Решить задачи нелинейного программирования без ограничений и с ограничениями, используя программы системы MATLAB.

Теоретическая часть

Среди методов поиска экстремума второго порядка наиболее известен метод Ньютона, получивший свое название в связи с тем, что в нем необходимое условие безусловного экстремума f(x)=0 рассматривается как система алгебраических уравнений, решаемая методом Ньютона.

Рассмотрим метод Ньютона для решения системы n – уравнений  (x) = ( ₁(x),  ₂(x),,  _n(x))^T = 0 от n - неизвестных x₁, x₂, …, x_n . Разложим функции  _i(x) в ряд Тейлора в окрестности точки x^(k) и оставим только линейные члены

(3.1)

Умножив справа на обратную матрицу первых производных (x^(k))^-1 , определяем

(3.2)

Из формулы следуют, что для применения метода Ньютона, который называют также методом касательных, надо вычислять обратную матрицу первых производных (x^(k))^-1.

Перейдем к задаче поиска экстремума функции многих переменных. В точке экстремума градиент функции равен нулю: f(x)=0. Применяя формулу (3.2) с учетом того, что  (x) = f(x), (x) =d²f(x)/dx², где d²f(x)/dx² – матрица вторых производных, которую называют также Гессианом, получим формулу Ньютона для поиска экстремума функции многих переменных

(3.3)

Геометрический смысл метода Ньютона заключатся в том, что на каждой итерации очередная точка x^(k+1) выбирается так, чтобы она доставляла глобальный минимум квадратичной аппроксимации функции f(x). Это следует из того, что формулу (3.3) можно получить, раскладывая функцию в ряд Тейлора до степеней второго порядка и вычисляя градиент этой функции.

Поиск экстремума методом Ньютона является более эффективным, чем градиентные методы, так как квадратичная функция локально точнее аппроксимирует целевую функцию, чем линейная, лежащая в основе градиентных методов. Если отыскивается экстремум квадратичной функции f(x) = x^TAx+bx+c, то по методу Ньютона экстремум определяется за один шаг. Недостатком метода является необходимость вычисления обратной матрицы вторых производных – Гессиана. Отметим, что многие программные системы используют для поиска экстремума модификации метода Ньютона.

Рассмотрим способы решения задач оптимизации с применением пакета MATLAB. В этой системе для решения оптимизационных задач имеется пакет оптимизации Optimization Toolbox. Для ознакомления с программированием задач оптимизации надо открыть в меню «Help» раздел Optimization Toolbox, в котором описаны команды оптимизации. Там же приведены названия файлов демонстрационных меню. Чтобы их вызвать в окно редактора надо открыть файл MATLAB/toolbox. В нем расположены демонстрационные файлы «optdemo», «tutdemo», «bandemo», «goaldemo», «dfildemo», «datdemo», и другие. Рассмотрим две из них.

В файле «optdemo» рассмотрены применение различных численных методов оптимизации. В диалоговом режиме можно выбрать метод номер метода оптимизации и метод аппроксимации функции. Решение сопровождается графиком, в котором указывается последовательность точек решения задачи.

Более полезным является файл «tutdemo». При его запуске в командном окне можно посмотреть 6 примеров с программами и комментариями. Программа периодически останавливается и можно понять – как надо составлять различные программы оптимизации. В примерах сначала приводится математическая постановка задачи, потом программа и результаты. Рассматриваются программы решения задач математического программирования без ограничений и с ограничениями.

Приведем программу поиска безусловного минимума функции.

fun=’ exp(x(1)*(4*x(1)^2+2*x(2)^+4*x(1)*x(2)+2*x(2)+1)’;

x0=[-1,1];

options=[];

[x,options]=fminu(fun,x0,options);

x

option(8)

option(10)

В программе задается функция fun в виде символьного выражения, задаются начальные условия x0, опции в виде options[]. Выводится результат x, точность расчета - командой options(8) и число шагов – командой options(10).

Рассмотрим, как программируется задача поиска точки минимума функции f(x) при ограничениях в виде неравенств:

(3.4)

Программа имеет следующий вид.

funf = ’f = exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+1);’;

fung = ‘g=[1.5+x(1)*x(2)-x(1)-x(2); -x(1)-x(2)-10];’;

fun = [funf,fung];

x0=[-1,1];

options[];

[x,options]=const(fun,x0,options);

x

options(8)

options(10)

Из программы можно понять, как вводятся ограничения в программу оптимизации. В файле ‘tutdemo’ приведены примеры программирования задач оптимизации при различных ограничениях на переменные, а также способы применения опции ‘options’.

Ход работы

Изучим способы составления программ поиска экстремума без ограничений и с ограничениями в системе MATLAB. В демонстрационной программе tutdemo, которая расположена в каталоге Matlab/toolbox/optim, приводится шесть примеров программирования задач поиска экстремума. Вызовим программу tutdemo в окно редактора. Изучим программу. Программа имеет много пауз, во время которой можно посмотреть операции, которые выполнялись в программе. Чтобы продолжить выполнение программы, надо нажать любую клавишу.

По аналогии с программой tutdemo составим программу для поиска безусловного экстремума функции:

fun='(x(1)-3)^2+(x(2)-2)^2+(x(1)-x(2)-4)^2';

x0=[-1,1];

options=[];

[x,options]=fminu(fun,x0,options);

x

options(8)

options(10)

x = 4.0000 1.0000

ans = 3.0000

ans = 15 >>

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