Лабораторная работа - Методы нулевого и первого порядка - файл 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.pdf1702kb.02.10.2011 14:40скачать
n19.pdf2936kb.23.09.2011 23:15скачать
n20.docx326kb.23.10.2011 18:16скачать
n21.pdf2156kb.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.txt1kb.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) на множестве

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

.

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


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

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


Матрицей Гессе 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:



Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации