- •Методы оптимизации. Тест
- •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 квадратичная функция будет сильно выпукла?
5.4). Показать, что квадратичная функция сильно выпукла.
Все
угловые миноры >0
по критерию Сильвестра матрица А
положительно определена
по свойству квадратичной функции с
положительно определенной матрицей A,
данная функция сильно выпукла.
5.6)Функция f(x1,x2)=x1-2x2. Ответ: x*=(1;1)T, f*=-1.
Задачи вариант 6
6.1). Найти максимальное b, при котором f(X) унимодальна.
Всякая
выпуклая на [a;b]
функция является унимодальной на этом
отрезке. Исследуем f(x)
на выпуклость
По
второму дифференциальному условию
выпуклости функции неотрицательность
f’’(x)
на[a;b] <=> выпуклости f(x)
на [a;b]. Значит исходная функция не выпукла
на R,
однако она может быть унимодальной.
Построим график – парабола ветвями
вниз, пересечение с осью OX:
х=2;x=3;Вершина:
х=2,5. По
определению f(x)
унимодальна на отрезке [-5;2,5] (a =α =β)
Опр Функция 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] в точку)
6.2). Найти минимальную константу Липшица . A). X∈[0;1] б). X∈[0;10].
–
парабола
Минимальная L = max|f’(x)|
a). x∈[0;1]: от -2 до 1 f’(x)<0 и возрастает => L = max|f’(x)|=f’(0)=15;
б). x∈[0;10]: L = max|f’(x)|=|f’(10)|=3(100+4*10-5)=3*135=405.
6.3).
Найти безусловный экстремум функции
на E2.
1.
Проверим необходимое условие экстремума
:
- одна стационарная точка
2. Проверим достаточное условие экстремума - и H(x*)>0 (H(x*)<0) – минимум (максимум): достаточное условие не выполняется.
- точка минимума,
6.4). Показать, что квадратичная функция сильно выпукла.
Все угловые миноры >0 по критерию Сильвестра матрица А положительно определена по свойству квадратичной функции с положительно определенной матрицей A, данная функция сильно выпукла.
6.6)Функция f(x1,x2)=-x1-3x2. Ответ: x*=(2/3;2/3)T, f*=-8/3.
Задачи вариант 7
7.1).
Унимодальна ли функция
на отрезке [1,2]
и a>3
Всякая
выпуклая на [a;b]
функция является унимодальной на этом
отрезке. Исследуем f(x)
на выпуклость
По
второму дифференциальному условию
выпуклости функции неотрицательность
f’’(x)
на[a;b] <=> выпуклости f(x)
на [a;b]. Значит исходная функция выпукла
на [1,2] => унимодальна
на [1,2]
7.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.
7.3). Показать, что квадратичная функция сильно выпукла.
Все угловые миноры >0 по критерию Сильвестра матрица А положительно определена по свойству квадратичной функции с положительно определенной матрицей A, данная функция сильно выпукла.
7.4).
Найти безусловные экстремумы функции
на E2.
1.
Проверим необходимое условие экстремума
:
- одна стационарная точка
2.
Проверим достаточное условие экстремума
-
и H(x*)>0
(H(x*)<0)
– минимум (максимум):
согласно критерию Сильвестра H(x*)>0
- достаточное условие выполняется и
- точка минимума, f*=0+0+9-0-18=-9.
7.6)Функция f(x1,x2)=-2x1-x2. Ответ: нет решений
Задачи вариант 8
8.1).Доказать, что из выпуклости f(x) на [a;b] следует ее унимодальность на [a;b], если ограничиться дифференцируемыми на [a;b] ф-ями.
Пусть
f(x)
выпукла на [a;b]
f’(x)
не убывает на [a;b]; Допустим f(x)
неунимодальна на [a;b], тогда есть на [a;b]
такие х1<х2<x3,что
f(x1)<f(x2)
и f(x3)<f(x2).
Тогда
Получили,
что большему значению аргумента
соответствует меньшее значение функции
f’(x3)<0<f’(x1),
т.е. f’(x)
убывает=> f(x)
не выпукла. Пришли к противоречию, значит
наше допущение неверно и f(x)
унимодальна.
8.2).
На каких отрезках вещественной оси
функция
является выпуклой?
По 2му дифференциальному критерию выпуклости функция выпукла, если f”(x)≥0;
при x∈(-∞;-4]U[0;+
∞). Функция выпукла на отрезках [a;-4]
и [0;b],
где a∈(-∞;-4)
и b∈(0;+
∞).
8.3).
Найти безусловный экстремум функции
на E2.
1.
Проверим необходимое условие экстремума
:
- одна стационарная точка
2.
Проверим достаточное условие экстремума
-
и H(x*)>0
(H(x*)<0)
– минимум (максимум):
согласно критерию Сильвестра H(x*)>0
- достаточное условие выполняется и
- точка минимума, f*=0.
