- •Методы оптимизации. Тест
- •2.1). Что означает слово «оптимизация»? Какая функция называется целевой? Дать определение локального и глобального минимумов функции.
- •2.2). Сравнить необходимые количества вычисленных значений Nd и Nn функции f(X) при поиске ее точки минимума на отрезке длины 1 с точностью 10-5 методом деления отрезка пополам и методом перебора.
- •2.3). Сформулировать достаточные условия сходимости метода Ньютона.
- •2.4). Сформулировать необходимые и достаточные условия безусловного экстремума функции f(X) одной переменной.
- •2.5). Функции какого вида называются квадратичными функциями n переменных?
- •2.8). Дать определение общей задачи линейного программирования.
- •2.5). Чему равны градиент и гессиан квадратичной функции?
- •2.8). Дать определение канонической задачи линейного программирования.
- •2.1). Что такое точная нижняя грань функции на множестве? Как соотносятся точная нижняя грань и минимум функции на множестве? Привести примеры.
- •2.3). Сформулировать достаточное условие монотонной сходимости метода Ньютона. Скорость сходимости метода.
- •2.1). Сформулировать условие Липшица для функции f(X) на отрезке [a,b]. Всякая ли унимодальная на отрезке [a,b] функция f(X) удовлетворяет на нем условию Липшица?
- •2.2). Доказать, что в методе дихотомии число итераций, необходимое для определения точки минимума с точностью ε, определяется формулой .
- •2.3). Является ли условие достаточным для того, чтобы число было точкой минимума унимодальной, но не выпуклой функции f(X)? Ответ сопроводить примером.
- •2.5). Каким свойством обладает квадратичная функция с положительно определенной матрицей a?
- •2.8). Описать алгоритм сведения общей задачи к задаче в канонической форме линейного программирования. Привести пример.
- •2.1). Сформулировать условие Липшица для функции f(X) на отрезке [a;b]. Всякая ли функция f(X), удовлетворяющая условию Липшица на отрезке [a;b], унимодальна на нем?
- •2.2). Доказать, что погрешность определения точки минимума X* функции f(X) методом перебора не превосходит величины .
- •2.3). Сформулировать оценку погрешности определения минимума f* многомодальной функции методом перебора.
- •2.4). Классифицировать квадратичную форму и матрицу Гессе .
- •2.8). Какие задачи линейного программирования можно решить графически?
- •2.1). Сформулировать свойства функций, удовлетворяющих на отрезке [a;b] условию Липшица.
- •2.3). Сформулировать достаточные условия сходимости метода Ньютона.
- •2.4). Классифицировать квадратичную форму и матрицу Гессе .
- •2.5). Что такое скорость сходимости минимизирующей последовательности? Какие скорости сходимости вы знаете?
- •2.8). Дать определение общей задачи линейного программирования.
- •2.1). Какая функция называется унимодальной на отрезке [a,b]? Сформулировать свойства унимодальных функций.
- •2.2). Зависит ли точность определения X*, которую гарантируют методы дихотомии и золотого сечения в результате n вычислений функции f(X), от конкретной функции f(X)?
- •2.3). Сформулировать достаточное условие монотонной сходимости метода Ньютона. Скорость сходимости метода.
- •2.4). Вычислить и нарисовать градиенты, а также вычислить матрицу Гессе функции в точках .
- •2.5). Когда говорят, что в итерационном процессе производится исчерпывающий спуск?
- •2.8). Дать определение канонической задачи линейного программирования.
- •2.1). Какая функция называется выпуклой на отрезке [a,b]? Каков геометрический смысл выпуклости функции? Сформулировать два необходимых и достаточных дифференциальных условий выпуклости функций.
- •2.2). Повысится ли эффективность метода поразрядного поиска, если шаг поиска ∆ последовательно уменьшать не в 4, а в какое-либо другое число раз? Ответ обосновать.
- •2.3). Модификации метода Ньютона (метод Ньютона-Рафсона, метод Марквардта). Достоинства и недостатки методов. Скорость сходимости.
- •2.4). Записать приращение функции f(X)∈c2(En) в точке X через градиент и матрицу Гессе.
- •2.5). Какие направления дифференцируемой в точке xk функции f(X) называются направлениями убывания? Каков геометрический смысл направления убывания?
- •2.8). Описать алгоритм графического решения задачи линейного программирования.
- •2.1). В чем заключается классический метод минимизации функций? Для каких целей разработан классический метод минимизации функций? Какова практическая ограниченность применимости этого метода?
- •2.2). Зависит ли точность определения X*, которую получают методом парабол в результате n вычислений функции f(X), от конкретной функции f(X)?
- •2.3). Увеличение используемого значения константы Липшица l при реализации метода ломаных приводит к замедлению сходимости метода. Объяснить этот факт с помощью геометрической иллюстрации.
- •2.4). Что такое градиент и антиградиент функции многих переменных и каков их геометрический смысл? Что такое матрица Гессе функции многих переменных?
- •2.5). Когда говорят, что сильно выпуклая функция f(X) имеет “овражный характер”? Какие задачи минимизации называются хорошо обусловленными, а какие − плохо обусловленными?
- •2.8). Какая задача оптимизации называется задачей линейного программирования?
- •1.1). Унимодальна ли функция на отрезке [1,2]
- •1.2). Решить классическим методом минимизации на отрезке [-4,4]
- •1.3). Найти безусловные экстремумы функции на e2.
- •2.1). Унимодальна ли функция на отрезке [0,π/4]
- •2.2). Решить классическим методом минимизации на отрезке [1/2,3/2]
- •3.1). Унимодальна ли функция на отрезке [0,1]
- •3.2). Решить классическим методом минимизации на отрезке [π/3, 2π/3]
- •4.1). Привести примеры функций f(X), унимодальных на отрезке [a;b], но не выпуклых на нем
- •5.2). Найти минимальную константу Липшица . A). X∈[0;2] б). X∈[2;3].
- •5.4). Показать, что квадратичная функция сильно выпукла.
- •6.1). Найти максимальное b, при котором f(X) унимодальна.
- •6.2). Найти минимальную константу Липшица . A). X∈[0;1] б). X∈[0;10].
- •6.4). Показать, что квадратичная функция сильно выпукла.
- •8.4). При каких a,b,c квадратичная функция будет сильно выпукла?
1.1). Унимодальна ли функция на отрезке [1,2]
Всякая
выпуклая на [a;b]
функция является унимодальной на этом
отрезке. Исследуем данную функцию на
выпуклость
По
второму дифференциальному условию
выпуклости функции неотрицательность
f’’(x)
на[a;b] <=> выпуклости f(x)
на [a;b]. Значит исходная функция выпукла
на [1;2] => унимодальна
на [1;2]
1.2). Решить классическим методом минимизации на отрезке [-4,4]
1)Найдем
стационарные точки (необходиомое условие
минимума)
2)Вычислим функцию в стационарный точках и на концах отрзезка: f(-4)=-64+(80+28)+5=49; f(-3)=-27+81+5=59; f(3)2-81+5=-54+5=49; f(4)=64-108+5=-39;
Ответ: х*=3; f*=-49.
1.3). Найти безусловные экстремумы функции на e2.
1.
Проверим необходимое условие экстремума
:
2.
Проверим достаточное условие экстремума
-
и H(x*)>0
(H(x*)<0)
– минимум (максимум):
-
точка минимума,
достаточное
условие не выполняется.
3.
Для точки
проверим необходимое условие экстремума
2го порядка:
,
главные миноры 1го порядка -6 и 6; главный
минор 2го порядка -36 – необходимое
условие 2го порядка не выполняется – в
точке
экстремума нет.
1.4).=5). Показать, что квадратичная функция
сильно выпукла.
Все
угловые миноры >0
по критерию Сильвестра матрица А
положительно определена
по свойству квадратичной функции с
положительно определенной матрицей A,
данная функция сильно выпукла
1.6)Функция f(x1,x2)=x1-2x2. Ответ: x*=(1;1)T, f*=-1.
Задачи вариант 2
2.1). Унимодальна ли функция на отрезке [0,π/4]
Всякая
выпуклая на [a;b]
функция является унимодальной на этом
отрезке. Исследуем данную функцию на
выпуклость
По
второму дифференциальному условию
выпуклости функции неотрицательность
f’’(x)
на[a;b] <=> выпуклости f(x)
на [a;b]. Значит исходная функция выпукла
на [0,π/4] => унимодальна
на [0,π/4]
2.2). Решить классическим методом минимизации на отрезке [1/2,3/2]
1)Найдем
стационарные точки(необходиомое условие
минимума)
На (1;3/2) корня быть не может, т.к. exp(x-1)>1,
a
cos2πx<1.
Отезок [1/2,1]
-загадка
2)Вычислим функцию в стационарной точке и на концах отрзезка: f(1/2)= -2πexp(-1/2); f(1)=-2π; f(3/2)= -2πexp(1/2); Ответ: х*=3/2; f*=-2πexp(1/2).
2.4).=6).
Показать, что квадратичная функция
сильно выпукла.
Все угловые миноры >0 по критерию Сильвестра матрица А положительно определена по свойству квадратичной функции с положительно определенной матрицей A, данная функция сильно выпукла.
2.6)Функция f(x1,x2)=-x1-3x2. Ответ: x*=(2/3;2/3)T, f*=-8/3.
Задачи вариант 3
3.1). Унимодальна ли функция на отрезке [0,1]
Всякая
выпуклая на [a;b]
функция является унимодальной на этом
отрезке. Исследуем данную функцию на
выпуклость
По
второму дифференциальному условию
выпуклости функции неотрицательность
f’’(x)
на[a;b] <=> выпуклости f(x)
на [a;b]. Значит исходная функция выпукла
на [0,1] => унимодальна
на [0,1]
3.2). Решить классическим методом минимизации на отрезке [π/3, 2π/3]
1)Найдем
стационарные точки (необходиомое условие
минимума)
2)Вычислим
функцию в стационарной точке и на концах
отрзезка:
Ответ: х*= π⁄2; f*=-√2
3.3).
Найти безусловный экстремум функции
на E2.
1. Проверим
необходимое условие экстремума
:
2.
Проверим достаточное условие экстремума
-
и H(x*)>0
(H(x*)<0)
– минимум (максимум):
достаточное условие не выполняется.
- точка минимума,
3.
Для точки
проверим необходимое условие экстремума
2го порядка:
,
главные миноры 1го порядка 0 и 0; главный
минор 2го порядка -9 – необходимое условие
2го порядка не выполняется – в точке
экстремума нет.
3.4).=7).
Показать, что квадратичная функция
сильно выпукла.
Все угловые миноры
>0
по критерию Сильвестра матрица А
положительно определена
по свойству квадратичной функции с
положительно определенной матрицей A,
данная функция сильно выпукла.
3.6)Функция f(x1,x2)=-2x1-x2. Ответ: нет решений
Задачи вариант 4
