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

ФЕДЕРАЛЬНОЕ
АГЕНСТВО ПО ОБРАЗОВАНИЮ.

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

«Санкт-Петербургский
государственный электротехнический
университет «ЛЭТИ» имени В.И. Ульянова
(Ленина)»

(СПБГЭТУ)

Кафедра
ВТ

Практическая
работа №7

«Исследование
методов безусловной оптимизации первого
порядка»

Выполнил: ст.
группы 9307 Джабаров Р.Р.

Проверил: проф.
Дмитревич Г.Д.

Санкт-Петербург

2014
г.

Оглавление

Задание. 2

Описание
методов оптимизации. 2

Спецификация
программы. 4

Результаты
тестирования программы 6

Ответы
на контрольные вопросы 6

Задание.

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

Описание
методов оптимизации.

Метод
трехточечного поиска на равных интервалах

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

Начальный
этап
(1) Задать [a₁,
b₁]
— начальный интервал поиска, где a₁,
b₁
— границы интервала, удовлетворяющие
условию f (a₁)f
(b₁)<0;

— погрешность вычисления минимума х*.
(2) Положить x_m
= (a₁
+ b₁)/2
и k = 1.

Основной
этап

Шаг
1. Взять две пробные точки x₁
= a_k
+ L_k/4
и x₂
= b_k
— L_k/4,
где L_k
= b_k
— a_k
— длина текущего интервала. Точки х₁,
х₂
и х_m
делят [a_k,
b_k]
на четыре равные части.

Шаг
2. Сократить текущий интервал локализации
минимума:

(1)
если f₁
< f_m,
то положить a_k+1
= a_k,
b_k+1
= x_m,
x_m
= x₁,
перейти на шаг 3;

(2)
если f₁
≥ f_m
≤
f₂,
то положить a_k+1
= x₁,
b_k+1
= x₂;
иначе — a_k+1
= x_m,
b_k+1
= b_k,
x_m
= x₂.

Шаг
3. Проверить критерий окончания поиска:

(1)
заменить k на k +1;

(2)
если L_k
= b_k
— a_k
≤
,
то остановиться. Если данное условие
не выполняется, вернуться на шаг 1.

Метод
Полака-Рибьера

Метод
Полака-Рибьера является разновидностью
метода Флетчера-Ривза. Ниже приводятся
операции этого алгоритма:

Шаг
1. В

вычисляется

.

Шаг
2. На k-м
шаге с помощью одномерного поиска в
направлении
,
находим минимум
.
Это определяет точку
.

Шаг
3. Вычисляются

и
.

Шаг
4. Направление

определяется из соотношения

(4.5)

После
(n+1)
итерации (k=n)
процедура циклически повторяется с
заменой

на
.

Шаг
5. Алгоритм заканчивается, когда
,
где

— произвольная константа.

Спецификация
программы.

В
программе использовался метод сопряженных
градиентов – “метод Полака-Рибъера”,
а также метод одномерного поиска –
“Метод трехточечного поиска”.

Текст
программы

//
bn.cpp: определяет точку входа для консольного
приложения.

//

#include
«stdafx.h»

#include
<stdio.h>

#include
<iostream>

#include
<conio.h>

#include
<math.h>

using
namespace
std;

double
icount =1;

double
icountz=1;

double
x0[2] = {0,3}, p[2];

double
f(double
x1, double
x2) {

return
(x1-2)*(x1-2)*(x1-2)*(x1-2) + (x1-2*x2)*(x1-2*x2);

}

double
y (double
alfa) {

return
f (x0[0]+p[0]*alfa,x0[1]+p[1]*alfa);

}

double
norm (double
x[2]) {

return
sqrt(x[0]*x[0] + x[1]*x[1]);

}

void
swann( double
x, double&
a, double&
b, double
h = 0.0001) {

int
k;

if(
y(x) < y(x+h) )

h
*= -1;

for(
k=0; y(x+h) < y(x); k++ ) {

h
*= 2;

x
+= h;

}

if(h>0)

{

a=x-h;

b=x+h;

}

else

{

a=x+h;

b=x-h;

}

if(
icount )

icount
= k;

}

double
three_point_search( double
a, double
b, double
eps = 0.0001, int*
icount = NULL ) {

double
L, x_m = (a + b)/2, x_1, x_2;

int
k;

for(
k=0; abs(b — a) > eps; k++ ) {

L
= abs(b — a);

x_1
= a + L/4;

x_2
= b — L/4;

if(
y(x_1) < y(x_m) ) {

b
= x_m;

x_m
= x_1;

}

else
if(
y(x_m) <= y(x_1) && y(x_m) <= y(x_2) ) {

a
= x_1;

b
= x_2;

}

else
{

a
= x_m;

x_m
= x_2;

}

}

if(
icountz )

icountz
= k;

return
x_m;

}

void
VecCopy ( double
dst[2], double
src[2]) {

dst[0]
= src [0];

dst[1]
= src [1];

}

double
dif (double
x[2], int
nom, double
h = 0.0001) {

if
(nom == 0) {

return
( f(x[0] + h, x[1]) — f(x[0] — h, x[1]))/(2*h);

}

else

return
( f(x[0], x[1] + h) — f( x[0], x[1] — h))/(2*h);

}

double
polaka_ribera (void)
{

int
k = 1;

double
g [2];

double
glast [2], beta, betaz ;

while
(1) {

g[0]
= dif(x0,0);

g[1]
= dif(x0,1);

if
(k%2) {

VecCopy
( p, g);

}

else
{

beta
= g[1]*(g[1]-g[0])/(glast[0]*glast[0]);

betaz
= g[1]*(g[1]-g[0])/(glast[1]*glast[1]);

p[0]
= — g[0] — beta*p[0];

p[1]
= — g[1] — betaz*p[1];

}

VecCopy
(glast,g);

double
a, b;

swann(
0,a, b ); //работаем
с одномерным пространством

double
alpha = three_point_search( a, b ); //работаем
с одномерным пространством

x0[0]
= x0[0] + p[0]*alpha; //получаем
векторные значения

x0[1]
= x0[1] + p[1]*alpha;

if
(abs(norm(g)) < 0.0001)

return
alpha;

}

}

int
main (void)
{

double
alpha = polaka_ribera();

cout << «Minimum
function»
; cout << endl;

cout << (x0[0] + p[0]*alpha) ; cout << endl;

cout
<< (x0[1] + p[1]*alpha); cout << endl;

cout <<«Kol-vo
Iteracii methoda trehtochechnogo poiska:»
<< icount; cout << endl;

getch();

return
0;

}

Результаты
тестирования
программы

Точность	0.001
Метод Полака-Рибьера	11- метод одномерного поиска	x=[2;1]

Ответы
на контрольные вопросы

1.
Определить характер матрицы Гессе
функции y(x) = (x₂ – x₁)² + 
+ (1 – x₁)²
в точке минимума x^* = (1; 1)^t.
Используя матрицу Гессе найти направление,
сопряженное к p = (1; 0)^t.

G=
=>H=

P1*H*p2=0
=>

Пусть
y=2
=> x=1
=> p2=

1. Являются
   ли направления p¹ = (0; 1)^t
   и p² = (1; 0)^t
   линейно независимыми? Ортогональными?
   Сопряженными?

Данные
вектора являются ортогональными
=>независимы

P1*p2=0*1+1*0=0-Ортогональные

P1*H*p2=
— Сопряженные

е

1. Дана
   функция y(x) = x₁² + x₂² + x₃²
   и точка x^k = (1; 2; 3)^t.
   Определить точку x^k + 1
   методом
   Даниела.

Ш1:
p1=-g1==

Ш2:
x2==>f(a1)=(1+2*a1)^2+(2+4*a1)^2+(3+6*a1)^2

F’(a1)=4(1+2*a1)+
16(1+2*a1)+36*(1+2*a1)=0 => a1=1/2

Ш3:
x2=
Ш4:
||g1||=(4+16+36)^1/2 > E

1. Используя
   метод сопряженных градиентов найти
   точку x^k + 1
   для функции y(x) = x₁² + 2x₁x₂ + x₂²
   и x^k = (1; 1; 1)^t.

Ш1:
p1=-g1==

Ш2:
x2==>f(a1)=(1+4*a1)^2+2*(1+4*a1)*(1+4*a1)+(1+4*a1)^2

F’(a1)=32*(1+4*a1)
=0 => a1=1/4

Ш3:
x2=
Ш4:
||g1||=(4+4+1)^1/2=3
> E

Вывод.

Были
изучены методы сопряженных градиентов
и разработана программа, описывающая
эти методы.

---

С этим файлом связано 19 файл(ов). Среди них: Контрольный вопрос к 1 лабораторной работе.docx, ИДЗ.docx, OtchetKG3.docx, лаб1.pdf, Otchet_Odintsov_D_O_0362_UP.pdf, Лабораторная работа №7.doc, ИДЗ 1.docx, Задания (семинар №2).docx, Лаба 10.docx, otchet_po_laboratornoe_rabote-7.docx, estim_h_537417.pdf, lab_5.docx, Лаба 5н.docx, ООП_9302_Плюснина_Лаб1.docx, Фома.pdf, Декарт.pdf, pravila2018_2 (1).docx, Лабораторная работа №2(1).DOC, Matveev_Andrey_lb1.pdf и ещё 9 файл(а).
Показать все связанные файлы

---

Подборка по базе: Курсовая. Методы модульной технологии на уроках истории.doc, Дипломная Методы и приемы развития речи у детей дошкольного возр, Принципы и методы исследований и принятия решений кр.pdf, Тема 1.1.Предмет, задачи и методы детской физиологии. Гигиена ка, простейшие методы физиотерапии.pptx, Мастер-класс _Интерактивные методы обучения — основа инновационн, Пределы функций.docx, Инновационные методы преподавания русского языка , Эустресс и дистресс. Стадии стресса. Методы выхода из стресса. Р, Курсовая т.5 Методы учета затрат.docx

---

МИНОБРНАУКИ РОССИИ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)

Кафедра МО ЭВМ

ОТЧЕТ

по лабораторной работе №1

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

Тема: Методы безусловной минимизации функций

Студент гр. 9381		Матвеев А. Н.
Преподаватель		Мальцева Н.В.

Санкт-Петербург

2022

Цели работы:

1. Решение задачи безусловной минимизации функций с помощью стандартной программы.
2. Исследование и объяснение полученных результатов.

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

Минимизировать функцию F(x₁,x₂,a) = (x₂ — x₁²)² + a(x₁ — 1)² с точностью до 10^-5 ( abs ( F(x_1k,x_2k,a) — F(x₁^*,x₂^*,a) ) < 10^-5 ) предложенными в задании методами. Оценить скорость и порядок сходимости методов. Провести сравнительный анализ эффективности методов в зависимости от предложенных параметров (начальной точки, величины шага, параметра а>0).
Краткие общие сведения
— порядок сходимости метода, где Δ_k=||x_k-x^*||
ϕ(x_k)-ϕ(x^*)

<const⋅q^k – геометрическая скорость сходимости, где q<1
ϕ(x_k)-ϕ(x^*)<const⋅q^2k – квадратичная скорость сходимости, где q<1
Для проведения лабораторной работы составлена программа, обеспечивающая решение задачи безусловной минимизации при задании с терминала исходных значений.
Постановка задачи. Описание всех заданных в работе методов минимизации и их характеристик.
Задание.

8. Минимизировать функцию F(x₁,x₂,a) = (x₂ — x₁²)² + a(x₁ — 1)² с точностью до 10^-5 ( abs ( F(x_1k,x_2k,a) — F(x₁^*,x₂^*,a) ) < 10^-5 ) градиентными методами — методом с дроблением шага и методом наискорейшего спуска. Оценить скорость и порядок сходимости обоих методов.

Провести сравнительный анализ эффективности методов в зависимости от начальной точки и параметра а>0.
Выполнение работы.
Формальная постановка задачи – описание всех заданных в работе методов минимизации и их характеристик.

Итак, будем рассматривать задачу:

(безусловная минимизация),

предполагая, что функция ϕ(x) непрерывно дифференцируема на Rⁿ, т.е. ϕ(x)∈C¹(Rⁿ).

По определению дифференцируемой функции

, (1)

где .
Метод с дроблением шага.

Ещё один адаптивный способ выбора коэффициентов α_k. Выбираются некоторые const β >0 и 0 < λ < 1 (обычно λ = ½). Для коэффициента α = β проверяется выполнение условия . Если оно выполняется, то полагают α_k= α. Если нет, то производится дробление шага, т.е. принимается α = λβ, и т.д. до тех пор, пока не выполнится требуемое неравенство.

Процесс дробления не может продолжаться бесконечно, поскольку −ϕ′(x) – направление убывания функции. Первое α, при котором условие выполнено и принимается за α_k.

Как показывает следующая лемма, с помощью описанного процесса дробления шага можно добиться выполнения неравенства. (1)
Лемма 3. Пусть функция ϕ дифференцируема на Rⁿ. Тогда для найдется такое α₀ > 0, что при ∀α∈(0, α₀] выполнено условие

.
Если необходимое неравенство оказывается выполненным при начальном значении α = β, то иногда полезно увеличить шаг, взяв α = μβ, где μ > 1. Так можно продолжать до тех пор, пока значения функции не перестанут уменьшаться. Последнее α, при котором произошло уменьшение, и берется в этом случае за α_k.
Метод наискорейшего спуска.

На луче , направленном по антиградиенту, введем функцию одной переменной

и определим α_k из условий

.

Другими словами α_k выбирается так, чтобы ϕ(x_k+1) в заданном направлении была наименьшей для чего на любом шаге необходимо решать задачу одномерной минимизации функции ψ (α), например, с помощью .
Обоснование выбора перечня вариантов запуска программы (количество начальных точек, начальных шагов, значений параметра а).

F(x1,x2,a) = (x2 — x12)2 + a(x1 — 1)2 Минимум функции находится в точке x* = (1,1), f(x*) = 0.

Оценим эффективность методов в зависимости от начальной точки и параметра a. Для этого рассмотрим 6 различных начальных точек, которые отличаются расстоянием от x*. Будем работать с тремя различными параметрами a и одним начальным шагом для двух методов.
Исследуем зависимость скорости сходимости и порядка сходимости от начальной точки и параметра a.

2, 2

3, -2

6, 3

4, -8

6, 10

-7, -12

Выберем следующие параметры a.

a

1

5

15

Начальный шаг возьмём одним для 2-х методов для всех комбинаций h = 0.03.

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

Обозначения:

3.1. Метод с дроблением шага.

	2, 2	Вывод программы
a	1	527 1.003284 1.007937 0.0000126295 1 528 1.003251 1.007855 0.0000123720 1 529 1.003217 1.007775 0.0000121197 1 530 1.003184 1.007695 0.0000118726 1 531 1.003152 1.007616 0.0000116305 1 532 1.003120 1.007538 0.0000113933 1 533 1.003088 1.007461 0.0000111610 1 534 1.003056 1.007384 0.0000109334 1 535 1.003025 1.007308 0.0000107104 1 536 1.002994 1.007233 0.0000104919 1 537 1.002963 1.007159 0.0000102779 1 538 1.002932 1.007086 0.0000100683 1 539 1.002902 1.007013 0.0000098629 1
k*	539

Точка, в которой значение F(x1k,x2k,a) в первый раз стало < 10-5:

x1= 1.002902 x2=1.007013 a=1

	2, 2	Вывод программы
a	5	167 1.001518 1.006428 0.0000230149 1 168 1.001470 1.006225 0.0000215821 1 169 1.001424 1.006028 0.0000202384 1 170 1.001379 1.005837 0.0000189783 1 171 1.001335 1.005653 0.0000177966 1 172 1.001293 1.005474 0.0000166884 1 173 1.001252 1.005301 0.0000156492 1 174 1.001212 1.005133 0.0000146747 1 175 1.001174 1.004970 0.0000137608 1 176 1.001137 1.004813 0.0000129039 1 177 1.001101 1.004661 0.0000121002 1 178 1.001066 1.004513 0.0000113466 1 179 1.001032 1.004370 0.0000106399 1 180 1.000999 1.004232 0.0000099772 1
k*	180

Точка, в которой значение F(x1k,x2k,a) в первый раз стало < 10-5:

x1=1.000999 x2=1.004232 a=5

	2, 2	Вывод программы
a	15	109 1.000684 1.006229 0.0000306409 1 110 1.000652 1.005937 0.0000278392 1 111 1.000621 1.005659 0.0000252937 1 112 1.000592 1.005394 0.0000229809 1 113 1.000565 1.005142 0.0000208795 1 114 1.000538 1.004901 0.0000189703 1 115 1.000513 1.004672 0.0000172356 1 116 1.000489 1.004453 0.0000156596 1 117 1.000466 1.004244 0.0000142276 1 118 1.000444 1.004046 0.0000129266 1 119 1.000423 1.003856 0.0000117445 1 120 1.000404 1.003676 0.0000106705 1 121 1.000385 1.003504 0.0000096947 1
k*	121

Точка, в которой значение F(x1k,x2k,a) в первый раз стало < 10-5:

x1=1.000385 x2=1.003504 a=15

	3, -2	Вывод программы
a	1	461 0.996707 0.992058 0.0000127107 1 462 0.996741 0.992140 0.0000124491 1 463 0.996775 0.992222 0.0000121929 1 464 0.996808 0.992302 0.0000119421 1 465 0.996841 0.992381 0.0000116964 1 466 0.996874 0.992460 0.0000114557 1 467 0.996906 0.992538 0.0000112200 1 468 0.996938 0.992615 0.0000109892 1 469 0.996970 0.992691 0.0000107632 1 470 0.997001 0.992767 0.0000105418 1 471 0.997032 0.992841 0.0000103249 1 472 0.997063 0.992915 0.0000101126 1 473 0.997093 0.992989 0.0000099046 1
k*	473

Точка, в которой значение F(x1k,x2k,a) в первый раз стало < 10-5:

x1=0.997093 x2=0.992989 a=1

	3, -2	Вывод программы
a	5	175 0.998557 0.993886 0.0000208415 1 176 0.998603 0.994080 0.0000195406 1 177 0.998647 0.994268 0.0000183209 1 178 0.998690 0.994450 0.0000171774 1 179 0.998732 0.994626 0.0000161053 1 180 0.998772 0.994796 0.0000151002 1 181 0.998811 0.994961 0.0000141579 1 182 0.998848 0.995121 0.0000132743 1 183 0.998885 0.995275 0.0000124460 1 184 0.998920 0.995425 0.0000116693 1 185 0.998955 0.995570 0.0000109412 1 186 0.998988 0.995710 0.0000102585 1 187 0.999020 0.995846 0.0000096184 1
k*	187

Точка, в которой значение F(x1k,x2k,a) в первый раз стало < 10-5:

x1 =0.999020 x2 =0.995846 a=5