Условия оптимальности

Пусть - множество направлений убывания функции в точке , а - множество возможных направлений относительно множества в точке . Напомним, что вектор задаёт направление убывания функции в точке , если при всех достаточно малых , и возможное направление относительно множества в точке , если точка при всех достаточно малых .

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. Условия регулярности Слейтера выполнено, следовательно, функция Лагранжа регулярная:

3. Выпишем необходимые условия:

Пусть , тогда , но данная точка не удовлетворяет ограничению задачи. Отсюда следует, что . Система перепишется в виде:

Разрешая систему, получим:

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.

94. Доказать, что если , - положительные числа, причём , то .

Пусть

(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. Решить задачу: