Лабораторная работа - Методы нулевого и первого порядка - файл n20.docx

Лабораторная работа - Методы нулевого и первого порядка
скачать (6823 kb.)
Доступные файлы (39):

n1.bpr
n2.cpp
n3.dsk
n4.exe
n5.obj
n6.res
n7.tds
n8.cpp
n9.ddp
n10.dfm
n11.h
n12.obj
n13.cpp
n14.ddp
n15.dfm
n16.h
n17.obj
n18.pdf	1702kb.	02.10.2011 14:40	скачать
n19.pdf	2936kb.	23.09.2011 23:15	скачать
n20.docx	326kb.	23.10.2011 18:16	скачать
n21.pdf	2156kb.	23.10.2011 18:17	скачать
n22.bpr
n23.cpp
n24.dsk
n25.exe
n26.obj
n27.res
n28.tds
n29.cpp
n30.ddp
n31.dfm
n32.h
n33.obj
n34.cpp
n35.ddp
n36.dfm
n37.h
n38.obj
n39.txt	1kb.	28.10.2011 19:21	скачать

n20.docx

Федеральное государственное автономное

образовательное учреждение

высшего профессионального образования

«СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
Институт Космических и Информационных Технологий
Кафедра «Информатика»

УТВЕРЖДАЮ

Заведующий кафедрой

_____ _____________

подпись инициалы, фамилия

« _____» _______ 20 ___ г.

ЛАБОРАТОРНАЯ РАБОТА №1
по дисциплине «Методы оптимизации»
Студент, КИ 08-05 __________ О.В. Дрозд

номер группы подпись, дата инициалы, фамилия

Преподаватель __________ Н.А. Сергеева

подпись, дата инициалы, фамилия

Красноярск 2011
Цель работы:
Найти минимум двух функций, используя следующие методы:

Метод наилучшей пробы
Метод Ньютона – Рафсона

Функции:

Необходимые условия экстремума первого порядка.
Пусть есть точка локального минимума (максимума) функции f(x) на множестве и f(x) дифференцируема в точке . Тогда градиент функции f(x) в точке равен 0, т. е .
Необходимые условия экстремума второго порядка.
Пусть точка есть точка локального минимума (максимума) функции f(x) на множестве и функция f(x) дважды дифференцируемая в этой точке. Тогда матрица Гессе функции f(x), вычисленная в точке , является положительно полуопределенной (отрицательно полуопределенной), т.е .
Достаточные условия экстремума.
Пусть функция f(x) в точке дважды дифференцируема, ее градиент равен нулю, а матрицы Гессе является положительно определенной (отрицательно определенной), т.е

и Тогда точка есть точка локального минимума(максимума) функции f(x) на множестве

Рассмотрим определитель матрицы Гессе , вычисленный в стационарной точке

.

Определители называются угловыми минорами.
Критерий проверки достаточных условий экстремума

Для того чтобы матрица Гессе была положительно определенной () и точка являлась точкой локального минимума, необходимо и достаточно, чтобы знаки угловых миноров были строго положительны:
Для того чтобы матрица Гессе была отрицательно определенной () и точка являлась точкой локального максимума, необходимо и достаточно, чтобы знаки угловых миноров чередовались, начиная с отрицательного:

Матрицей Гессе H(x) дважды дифференцируемой в точки х функции f(x) называется матрица частных производных второго порядка, вычисленных в данной точке:

Квадратичная форма (а также соответствующая матрица Гессе ) называется:

Положительно определенной ), если для любого ненулевого выполняется неравенство ;
Отрицательно определенной ), если для любого ненулевого выполняется неравенство ;
Положительно полуопределенной ), если для любого ненулевого выполняется неравенство и имеется отличный от нуля вектор , для которого ;
Отрицательно полуопределенной ), если для любого ненулевого выполняется неравенство и имеется отличный от нуля вектор , для которого ;
Неопределенной (), если существуют такие векторы , , что выполняются неравенства , ;
Тождественно равной нулю (), если для любого выполняется

Аналитическое решение:

Функция 1:
Найдем первую производную:

Корни уравнения:

Матрица Гессе:

Матрица Гессе не зависит от переменных функций, так как точка (0,0) – точка глобального минимума.
Функция 2:
Найдем первую производную:

Корни уравнения:

Матрица Гессе:

Проверяем корни уравнения:

точка (-1;1) – возможный локальный минимум, проведем дополнительный исследования:

Градиенты равны 0, следовательно по необходимому условию экстремума первого порядка, точка (-1;1) являются точкой локального минимума.
Метод Ньютона-Рафсона:

В результате работы метода строится последовательность точек

таких, что

. Точки последовательности

вычисляются по правилу:

,

где точка

задаётся пользователем, а величина шага

определяется по правилу:

Задача нахождения оптимального шага решена либо с использованием условий

, либо численно с использованием методов одномерной минимизации, как задача

.

При численном решении задачи определения величины шага степень близости найденного значения

к оптимальному значению

, удовлетворяющему условиям

, зависит от задания интервала

и точности метода одномерной оптимизации.

Построение последовательности

заканчивается в точке

, для которой выполняется

, где

– заданное малое положительное число, или

, где

– предельное число итераций, или при двукратном одновременном выполнении двух неравенств

, где

– малое положительное число. Дополнительно исследуется вопрос о том, может ли полученная точка быть принята как точка минимума целевой функции.

Алгоритм:
Шаг 1: Выбираем начальную точку

– предельное число итераций. Найти градиент функции в произвольной точке

и матрицу Гессе

.

Шаг 2: Положить

.

Шаг 3: Вычислить

.

Шаг 4: Проверить выполнение критерия окончания

:

а) если критерий выполнен, расчет закончен,

;

б) если критерий не выполнен, то перейти к шагу 5.

Шаг 5: Проверить выполнение неравенства

:

а) если неравенство выполнено, то расчет окончен

;

б) если нет, то перейти к шагу 6.

Шаг 6: Вычислить матрицу

.

Шаг 7: Вычислить

.

Шаг8: Проверить выполнение условия

:

а) если неравенство верно, то найти

;

б) если нет, то положить

.

Шаг 9: Определить

.

Шаг 10: Шаг найти из условия:

Шаг 11: Проверить выполнение условий:

:

а) если оба условия выполнены при текущем значении

, то расчет окончен,

.

б) если хотя бы одно из условий не выполнено, положить

и перейти к шагу 3.
Сходимость метода обладает теми же особенностями, что и метод Ньютона, однако для неквадратических функций может сходиться за меньшее число шагов. Тем не менее, метод чувствителен к точности настройки одномерного поиска оптимального шага.
Реализация метода Ньютона-Рафсона:
Функция №1:

Функция №2:

Метод наилучшей пробы:

Задается начальная точка

. Каждая последующая точка находится по формуле:

_,

где

величина шага;

случайный вектор единичной длинны, определяющий направление поиска; k - номер итерации. На текущие итерации при помощи генерирования случайных векторов

получается M точек

, лежащих на гипосфере радиуса

с центром в точке

(рис. 3). Среди полученных точек выбирается точка

, в которой значение функции наименьшее. Если в выбранной точке значение функции меньше, чем в центре, то дальнейший поиск продолжается из этой точки. Иначе поиск продолжается из старого центра, но с меньшим шагом до тех пор, пока он не станет меньше заранее заданной величины R.

Реализация метода наилучшей пробы:
Функция №1:

Функция №2: