Положение о порядке организации и проведения экзаменов;pdf

Курс "МЕТОДЫ ОПТИМИЗАЦИИ". Вопросы к экзамену.
3 курс ВМК МГУ, I поток, 2013-2014 учебный год, лектор Будак Б.А.
1. Методы минимизации функции одной переменной. (лекции; [1]: 9-20, 29-30, 33-34, 45-46)
2. Теорема Вейерштрасса (метрический вариант). ([1]: 74-75, [2]: 46-47)
3. Теорема Вейерштрасса (слабый вариант). Применение к задаче минимизации квадратичного функционала вида ||Au − f ||2 . (лекции; [2]: 49-50)
4. Существование решения задач минимизации терминального и интегрального квадратичных функционалов на решениях линейной системы обыкновенных дифференциальных уравнений. (лекции; [2]: 57-59)
5. Существование решения задачи об оптимальном нагреве стержня. (лекции)
6. Дифференцирование по Фреше (первая и вторая производные). Применение к квадратичному функционалу вида ||Au − f ||2 . (лекции; [1]: 79-80, [2]: 18-20)
7. Необходимое условие локального минимума. Примеры. (лекции; [1]: 165)
8. Градиент терминального квадратичного функционала. (лекции; [2]: 29-33)
9. Градиент интегрального квадратичного функционала. (лекции)
10. Градиент функционала в задаче о нагреве стержня. (лекции; [2]: 116-122)
11. Выпуклые функции и функционалы. Теоремы о локальном минимуме, о множестве Лебега, о касательной плоскости. Критерий оптимальности. Примеры. ([1]: 161-169, [2]: 24, 28-29)
12. Критерии выпуклости функций и функционалов. Выпуклость квадратичного функционала. (лекции;
[1]: 165-169, [2]: 24-25)
13. Сильно выпуклые функции и функционалы, их свойства. Критерии сильной выпуклости функций и
функционалов. (лекции; [1]: 181, 184-186, [2]: 25)
14. Теорема Вейерштрасса для сильно выпуклых функционалов. (лекции; [1]: 182-183, [2]: 155)
15. Метрическая проекция точки на выпуклое замкнутое множество в гильбертовом пространстве, её свойства. Примеры. ([1]: 188-193, [2]: 72)
16. Градиентный метод. Метод проекции градиента. Их сходимость. (лекции; [1]: 277, 281-282, [2]: 73, 76)
17. Непрерывный аналог градиентного метода. (лекции)
18. Метод Ньютона; его сходимость. (лекции; [1]: 329-333)
19. Метод покоординатного спуска; его сходимость. (лекции; [1]: 342-345)
20. Метод штрафных функций; его сходимость. (лекции; [1]: 363-369)
21. Правило множителей Лагранжа. (лекции; [1]: 379-381)
22. Теорема Куна-Таккера. (лекции; [1]: 234-240)
23. Двойственная задача, её свойства. (лекции; [1]: 248-249)
24. Каноническая и общая задачи линейного программирования. Их эквивалентность. (лекции; [1]: 101-102,
105-106)
25. Критерий угловой точки в канонической задаче линейного программирования. (лекции; [1]: 109-113; [3])
26. Симплекс-метод для канонической задачи линейного программирования. Его сходимость за конечное
число шагов для невырожденной задачи. (лекции; [1]: 113-119, 123; [3])
27. Метод искусственного базиса для поиска угловой точки в канонической задаче линейного программирования. (лекции; [1]: 136-137, 145-146; [3])
28. Неустойчивые задачи минимизации. Метод стабилизации А.Н. Тихонова. (лекции)
Литература:
[1]
[2]
[3]
[4]
Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988.
Васильев Ф.П. Методы решения экстремальных задач. М.: Наука, 1981.
Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998.
(Основная книга) Васильев Ф.П. Методы оптимизации (в 2-х томах). М.:МЦМНО, 2011.
Курс "МЕТОДЫ ОПТИМИЗАЦИИ". Задачи к экзамену.
1. Рассматривается функция J(u) = x2 + 2axy + 2by 2 + cz 2 , u = (x, y, z).
а) При каких a, b, c эта функция выпукла на E3 ? Сильно выпукла?
б) Выбирая в качестве начального приближения точку u0 = (1, 1, 1), сделать один шаг градиентного метода
(метода Ньютона).
в) В предположении, что J(u) минимизируется на множестве U1 = {u = (x, y, z) | 0 6 x 6 1, 0 6 y 6 1},
сделать один шаг метода проекции градиента (условного градиента). В качестве начального приближения
выбрать точку u0 = (1, 0, 1). Будут ли сходиться эти методы?
г) Те же вопросы для множеств U2 = {u = (x, y, z) | x + y = 1} и U3 = {u = (x, y, z) | x > 0, 1 6 y 6 2}.
д) Корректно ли поставлена задача на E3 ? U1 ? U2 ? U3 ?
е) Для решения задачи минимизации функции J(u) при ограничениях U1 , U2 , U3 применить правило множителей Лагранжа или теорему Куна-Таккера.
ж) Применить для решения задачи минимизации функции J(u) при ограничениях U1 , U2 , U3 метод штрафных функций.
2. Исследовать на выпуклость, непрерывность, полунепрерывность снизу и слабую полунепрерывность
снизу функционалы:
∫1
J1 (u) =

u2 (t) sin t dt и J2 (u) = 
−1
J3 (x) =
+∞
∑
∫1
4
u(t) dt в пространстве L2 (−1, 1);
−1
x22n−1 ,
J4 (x) =
( +∞
∑
n=1
)2
x2n−1
n=1
( +∞
)2
∑ x2n−1
в пространстве l2 .
и J5 (x) =
2n
−
1
n=1
3. Найти первую и вторую производную по Фреше функционалов
∫1
∫1
u(t)u(1 − t) dt, J2 (u) =
J1 (u) =
0


0
J4 (x) =
+∞
∑
x22n−1 ,
n=1
∫t
2
u(s) ds dt, J3 (u) =
0
∫1
2
√
∫t


2
 u(s) ds dt в пространстве L (0, 1);
0
0
+∞
∑
+∞
∑
1
J5 (x) =
xn xn+1 , J6 (x) =
4
n
n=1
n=1
(
n
∑
)2
xk
в пространстве ℓ2 .
k=1
4. Рассматриваются задачи оптимального управления


x(t)
˙
= x(t) + 3y(t) + u(t),
x(t)
˙
= x(t) − 2y(t) + u(t),






y(t)
˙ = −x(t) − y(t) − u(t),
y(t)
˙ = 2x(t) + y(t) + v(t),
x(0) = y(0) = 0,
x(0) = y(0) = 0,






|u(t)| 6 1,
|u(t)| 6 1, 0 6 v(t) 6 1,

x(t)
˙
= x(t) − y(t) + u(t),



y(t)
˙ = 2x(t) + y(t) + v(t),
x(0) = y(0) = 0,



|u(t)|2 + |v(t)|2 6 1,
с функционалами
∫1
2
2
2
∫1
2
J(u) = x (1), J(u) = x (1) + y (1), J(u) = y(1), J(u) =
x (t)dt, J(u) =
0
(
)
x2 (t) + y 2 (t) dt.
0
а) Дифференцируемы ли эти функционалы? В каком пространстве? Как найти их градиенты?
б) Выпуклы ли эти функционалы? Как выглядит критерий оптимальности?
в) Сделать один шаг метода проекции градиента (условного градиента), выбирая в качестве начального
приближения какое-либо ненулевое допустимое управление.
г) Как ввести штраф при наличии фазового ограничения y(t) 6 1 или |x(t)| 6 1?
д) Корректно ли поставлена задача в L2 (0, 1)? Как её регуляризовать?
е) Как ввести штраф при наличии краевых условий x(1) = y(1) = 1 или x2 (1) + y 2 (1) = 1?