Непустое множество 
называется выпуклым, если 
при всех 
, 
.
Функция 
, определенная на выпуклом множестве , называется выпуклой, если
(11)
при всех , . Если при всех , 
, 
неравенство (11) выполняется как строгое, то называется строго выпуклой.
Функция , определенная на выпуклом множестве , называется сильно выпуклой с константой 
, если
при всех , .
Ниже приведены необходимые и достаточные условия выпуклости и сильной выпуклости дифференцируемых функций. Для краткости формулировок выпуклые функции рассматриваются как сильно выпуклые с параметром 
.
Теорема 9 (Первый дифференциальный критерий сильной выпуклости)
Пусть функция дифференцируема на выпуклом множестве . Тогда для того, чтобы была сильно выпуклой с параметром 
на 
, необходимо и достаточно выполнения условия:
, при всех 
.
Теорема 10 (Второй дифференциальный критерий сильной выпуклости)
Пусть функция непрерывно дифференцируема на выпуклом множестве . Тогда для того, чтобы была сильно выпуклой с параметром на , необходимо и достаточно выполнения условия:
, при всех .
Теорема 11 (Третий дифференциальный критерий сильной выпуклости)
Пусть дважды непрерывно дифференцируема на выпуклом множестве , причем внутренность множества не пуста (
). Тогда для того, чтобы была сильно выпуклой с параметром на , необходимо и достаточно выполнения условия:
для всех 
.
37. Показать, что множество выпукло тогда и только тогда, когда 
при всех 
. Здесь 
- алгебраическая сумма множеств 
(
).
38. Являются ли выпуклыми множествами следующие множества на плоскости:
а) круг 
с центром в начале координат;
в) часть круга 
, получающаяся из него путём вырезания сектора, лежащего в правом квадранте.
|
|
39. Верно ли, что объединение и пересечение двух выпуклых множеств выпукло?
40. Пусть 
- выпуклые множества, 
- произвольные числа. Доказать, что множество 
выпукло.
41. Перечислить все выпуклые множества, принадлежащие числовой прямой 
.
42. Показать, что следующие множества являются выпуклыми:
а) 
- прямая, проходящая через точку 
в направлении 
;
в) 
- луч, выходящий из точки в направлении ;
с) 
- гиперплоскость с нормалью 
(
) 
;
d) 
,
- порождаемые гиперплоскостью с нормалью () полупространства. Здесь 
.
43. Показать, что множество 
, где 
- некоторая матрица размера (
) со строками 
, 
, является выпуклым.
44. Показать, что множество 
является выпуклым. Здесь 
, - заданные числа.
Точка 
выпуклого множества называется крайней, если её нельзя представить в виде 
45. Определить все крайние точки множества , заданного в задаче 44.
46. Определить все крайние точки множества 
, где 
.
47. Указать все крайние точки множества 
, определённого в задаче 42.
В задачах 48-53 множество предполагается выпуклым.
48. Доказать, что функция 
- выпукла, если 
выпукла и 
.
49. Доказать, что функция 
- выпукла, если выпукла, 
.
50. Проверить, что функция 
- выпукла на 
.
51. Пусть 
- выпуклые функции на множестве . Доказать, что функция 
- выпукла на .
52. Пусть - выпуклые функции на множестве , 
, и хотя бы при одном 
функция 
строго (сильно) выпукла, 
. Доказать, что 
- строго (сильно) выпукла на .
53. Доказать, что функция 
- выпукла на , если функции , 
, выпуклы на .
54. Пусть - выпуклая функция на выпуклом множестве . Показать, что 
при всех 
, для которых .
55. Доказать, что функция 
сильно выпукла на 
, 
.
|
|
56. Доказать, что строго вогнутая функция может достигать своего минимального значения только в крайних точках выпуклого множества , на котором она определена.
57. Найти максимальное значение функции 
при выполнении ограничений:
58. Пусть функция 
- непрерывная, монотонно неубывающая функция на отрезке 
. Показать, что функция 
является выпуклой на отрезке .
- Проверить, что функция
выпукла на .
Задача
(12)
называется выпуклой, если - выпуклое множество, а выпуклая функция на .
60. Доказать, что в выпуклой задаче любое её локальное решение является также и глобальным.
61. Пусть функция выпукла на и дифференцируема в точке 
. Доказать, что если 
, то 
- точка минимума функции на .
62. Известно, что выпуклая задача (12) имеет решение. Доказать, что тогда множество её решений выпукло, если при этом строго выпукла на , то решение задачи (12) единственно.
Условия оптимальности
Пусть 
- множество направлений убывания функции в точке , а 
- множество возможных направлений относительно множества в точке 
. Напомним, что вектор 
задаёт направление убывания функции в точке , если 
при всех достаточно малых 
, и возможное направление относительно множества в точке , если точка 
при всех достаточно малых .
63. Доказать, что если - локальное решение задачи (3) без каких-либо предположений на множество и функцию , то 
.
64. Пусть в задаче (12) множество выпукло, а функция - дифференцируема в точке . Доказать, что тогда, если - локальное решение задачи (12), то
, (13)
если же выпукла на и выполняется (13), то - глобальное решение задачи (12).
|
|
65. Доказать, что если 
( - внутренняя точка множества ), то (13) эквивалентно условию 
.
66. Пусть множество имеет вид 
, где 
, 
(если 
или 
, то соответствующий знак неравенства в задании множества следует понимать как строгий). Доказать, что тогда условие (13) эквивалентно условию: для любого
67. Пусть множество имеет вид 
, 
(
соответствует случаю 
). Доказать, что тогда (13) эквивалентно условиям:
68. Решить задачу:
69. Решить задачу:
70. Пусть - дифференцируемая сильно выпуклая функция на . Показать, что при любом 
решение уравнения 
на существует и единственно.
71. Пусть - дифференцируемая выпуклая функция на . Показать, что при любом 
решение уравнения 
на существует и единственно.
Напомним необходимое условие оптимальности (Принцип Лагранжа) в задаче математического программирования (1).
Теорема 12 (Принцип Лагранжа)
Пусть в задаче (1) множество 
- выпукло, функции 
дифференцируемы в точке 
, функции 
непрерывно дифференцируемы в некоторой окрестности точки . Если - локальное решение задачи (1), то существует число 
и вектор 
не равные нулю одновременно и такие, что
(14)
. (15)
Используемые здесь обозначения пояснены после формулировки задачи (1) на странице 3, а числа 
, также как в классической задаче на условный экстремум, называются множителями Лагранжа.
Теорема 13 (Достаточное условие оптимальности)
Пусть в задаче (1) множество выпукло, функции выпуклы на и дифференцируемы в точке , функции линейны. Если при 
и некотором 
выполняются условия (14), (15), то - глобальное решение задачи (1).
Теорема 14 (Условия регулярности)
Пусть в задаче (1) множество выпукло, функции дифференцируемы в точке , функции 
выпуклы на , функции линейны. Предположим, что дополнительно выполняется хотя бы одно из следующих условий:
1) ограничения-равенства отсутствуют (
) и существует точка 
такая, что 
при всех ;
2) 
, функции линейны.
Тогда, если - локальное решение задачи (1), то существует такой, что при будут выполнены условия (14), (15).
Условие 1) теоремы называется условием регулярности Слейтера.
Теорема 15 (Теорема Куна-Таккера в дифференциальной форме)
Пусть в дополнение к условиям теоремы 14 функция выпукла на . Тогда точка является решением задачи (1) в том и только том случае, если существует вектор такой, что при выполняются условия (14), (15).
Пример 3.
Рассмотрим задачу:
Решение:
1. Очевидно, что данная задача - задача выпуклого программирования.
2. Условия регулярности Слейтера выполнено, следовательно, функция Лагранжа регулярная:
.
- Выпишем необходимые условия:
Пусть 
, тогда 
, но данная точка не удовлетворяет ограничению задачи. Отсюда следует, что 
. Система перепишется в виде:
Разрешая систему, получим:
.
4. Для задачи выпуклого программирования необходимые условия оптимальности являются и достаточными (теорема 13), то есть - глобальное решение задачи.
72. Опираясь на решение задач 65-67, конкретизировать условие (14) в случае, когда 
и когда имеет вид, указанный в задачах 66, 67.
Проекцией точки 
на множество D называется точка 
, ближайшая к среди всех точек из D. Иными словами, является решением задачи проектирования
.
Заметим, что понятие проекции точки на множество используется в численных методах условной оптимизации, основанных на идее проектирования очередной точки, вырабатываемой методом решения безусловной задачи, на допустимое множество задачи с ограничениями.
Доказать следующие утверждения для произвольной точки 
.
73. Если 
- сфера, то 
.
74. Если 
- координатный параллелепипед, то
75. Если 
- неотрицательный октант, то 
.
76. Если 
- гиперплоскость (), то 
.
77. Если 
- полупространство (), то 
.
78. Если 
- аффинное множество, причём строки матрицы 
линейно независимы, то 
, где 
- транспонированная матрица, 
.
79. Решить задачу:
80. Доказать, что решением задачи выпуклого программирования
является точка 
.
81. Показать, что других решений, кроме , в задаче 80 нет.
82. Доказать, что решением задачи выпуклого программирования
является точка 
.
83. Показать, что других решений, кроме , в задаче 82 нет.
В задачах 84-88 
.
84. Используя необходимые условия оптимальности (14), (15), разработать численный метод отыскания решения задачи
Решить задачи:
85. 
- положительные числа, 
.
86. 
- произвольные числа, .
87. 
88. 
89. 
90. 
91. 
92. 
93. 
- Доказать, что если
, 
- положительные числа, причём 
, то 
.
Пусть
,
(17)
95. Показать, что если 
дифференцируемы в точке и - локальное решение задачи (17), то существуют числа 
, такие, что
.
Предполагая, что в задаче (1) 
, обозначим через 
точную нижнюю грань целевой функции задачи (1) на её допустимом множестве: 
. Вектор называется вектором Куна-Таккера задачи (1), если 
при всех 
.
Двойственной к задаче (1) называется задача
(18)
, 
.
При этом задача (1) называется прямой. Предполагая, что 
, обозначим через 
.
96. Показать, что в задаче (18) множество 
выпукло, а функция 
вогнута на .
97. Показать, что для любых 
и 
справедливо неравенство 
. Если , , то 
.
Теорема 16 (Теорема существования вектора Куна-Таккера)
Пусть в задаче (1) множество выпукло, функции выпуклы на , функции линейны. Предположим, что дополнительно выполняется хотя бы одно из следующих условий:
1) ограничения равенства отсутствуют () и существует точка такая, что 
;
2) , функции линейны, множество .
Тогда вектор Куна-Таккера задачи (1) существует.
Теорема 17 (Теорема двойственности)
Пусть вектор Куна-Таккера задачи (1) существует. Если значение прямой задачи (1) конечно (
) в частности, если она имеет решение, то множество решений двойственной задачи (18) непусто и совпадает с множеством векторов Куна-Таккера задачи (1). При этом справедливо соотношение двойственности
. (19)
98. Показать, что если вектор Куна – Таккера задачи (1) существует, а допустимое множество двойственной задачи непусто, то она имеет решение. Если же 
, то 
.
99. Для задачи
построить двойственную и найти её решение. Убедится в справедливости соотношения (19).
Теорема 18 (Теорема Куна-Таккера в форме двойственности).
Пусть вектор Куна-Таккера задачи (1) существует. Тогда точка является решением задачи (1) в том и только том случае, если существует вектор такой, что справедливо соотношение двойственности
, (20)
равносильное условиям
,
.
Множество векторов , удовлетворяющее (20), совпадает с множеством решений двойственной задачи (18) или же с множеством векторов Куна-Таккера прямой задачи (1).
100. Решить задачу:
- заданные числа.
Литература
1. Давыдов Н.А., Коровкин П.П., Никольский В.Н. Сборник задач по математическому анализу. –М.: Просвещение, 1964.
2. Лидский В.Б., Овсянников Л.В., Тулайков А.Н., Шабунин М.И. Задачи по элементарной математике. –М.: Наука, 1965.
3. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. –М.: Наука, 1984.
4. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации.
–М.: Наука, 1986.
5. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. –М.: Высшая школа, 1986.
