- •Методы оптимизации. Тест
- •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 квадратичная функция будет сильно выпукла?
4.1). Привести примеры функций f(X), унимодальных на отрезке [a;b], но не выпуклых на нем
Опр. Функция f(x) наз-ся унимодальной на [a;b], если она непрерывна на [a;b] и есть a ≤ α ≤ β ≤ b такие что: 1)если a < α, то на [a;α] ф-я f(x) мотонно убывает; 2)если β < b, то на [β;b] ф-я f(x) мотонно возрастает
3)при х∈[0;π/4] f(x)=f*=minf(x) на [a;b] (Возможны вырождения одного, двух отрезков [a,α], [α,β], [β,b] в точку)
Пример1:
Исследуем
данную функцию на выпуклость
По
второму дифференциальному условию
выпуклости функции неотрицательность
f’’(x)
на[a;b] <=> выпуклости f(x)
на [a;b]. Получается, что ф-я не
выпукла, но унимодальна на [-2,2] (по
определению a =α =β).
Пример2:
Исследуем
данную функцию на выпуклость
Аналогично
примеру1 получается, что ф-я унимодальна
на
по
определению, но не выпукла.
Пример3:
.
Исследуем
ее на выпуклость:
Аналогично
примерам1и2 получается, что ф-я унимодальна
на [-3;3] по определению, но не выпукла.
4.2). Показать, что для дифференцируемых на [a;b] ф-ций f(x) величина L=max|f’(x)| на [a;b] является минимальной константой Липшица для f(x) на [a;b].
Допустим это не так, тогда есть L1<L такая, что |f(x1)-f(x2)| ≤ L1|x1-x2| ∀x∈[a;b], тогда (|f(x1)-f(x2)| /|x1-x2|) ≤ L1. Перейдя к пределу x1->x2 получим |f’(x2)| ≤ L1. Т.к. х1и х2 произвольны, то |f’(x)| ≤ L1=>max|f’(x)| ≤ L1<L= max|f’(x)|. Пришли противоречию,значи допущение не верно и не существует L1<L. Чтд
4.3).
Найти безусловный экстремум функции
на E2.
1. Проверим
необходимое условие экстремума
:
-
одна стационарная точка
2.
Проверим достаточное условие экстремума
-
и H(x*)>0
(H(x*)<0)
– минимум (максимум):
достаточное условие не выполняется.
3. Проверим необходимое условие экстремума 2го порядка:
,
главные миноры 1го порядка 2 и 0 ≥ 0;
главный минор 2го порядка 0 ≥ 0 –
необходимое условие 2го порядка
выполняется – в точке
может быть точка минимума.
4.
Дополнительные исследования: f(x*)=0
Рассмотрим f(x)
на некоторой ε-окрестности точки
:
x*
- точка минимума и f*=0.
4.4).=8).
При каких a,b,c
квадратичная функция
будет сильно выпукла?
функция сильно
выпукла
матрица А положительно определена
все угловые миноры >0 -
.
4.6)Функция f(x1,x2)=-x1-x2. Ответ: Ответ: x*=(α;1- α)T, α∈[0,1], f*=-1.
Задачи вариант 5
5.1). Разбить отрезок [-1;2] на 3 части так, чтобы f(x) =||(x(x-1)|-1| была унимодальна ли функция
Преобразуем функцию и последовательно построим
Ответ[-1;0],[0;1],[1;2]
5.2). Найти минимальную константу Липшица . A). X∈[0;2] б). X∈[2;3].
–
парабола
Минимальная L = max|f’(x)|
a). x∈[0;2]: от -∞ до 2 f’(x)>0 и убывает => L = max|f’(x)|=f’(0)=72;
б). x∈[2;3]: max|f’(x)|=|f’(2,5)|=12(6,25-5*2,5+6)=12*0,25=3.
5.3).
Найти безусловный экстремум функции
на E2.
1.
Проверим необходимое условие экстремума
:
-
одна стационарная точка
2.
Проверим достаточное условие экстремума
-
и H(x*)>0
(H(x*)<0)
– минимум (максимум):
достаточное условие не выполняется.
3. Проверим необходимое условие экстремума 2го порядка:
,
главные миноры 1го порядка 2>0 и -2<0;
главный минор 2го порядка -4 < 0 –
необходимое условие 2го порядка не
выполняется – в точке
экстремума нет.
