задача выпуклой оптимизации

1,11 Mb.страница14/21Дата конвертации07.08.2012Размер1,11 Mb.Тип Смотрите также:             14           ^ Задачи выпуклой оптимизации Перейдем теперь собственно к задачам оптимизации, обобщающим задачи линейного программирования. Сначала рассмотрим задачу об отыскании минимума выпуклой функции на некотором выпуклом множестве . Естественно предполагать, что множество X содержится в выпуклом множестве , на котором определяется целевая функция, для простоты будем считать, что . Важной характеристикой сформулированной задачи является совпадение локального и глобального минимумов. Напомним, что под точкой глобального минимума понимается собственно решение рассматриваемой задачи, т. е. такая точка x*, для которой выполняется . Если же это неравенство выполняется на пересечении множества ^ X с некоторой окрестностью точки х*, то говорят, что х* точка локального минимума. Вид окрестности не является существенным. Важно, что это открытое множество, содержащее х*. Таким образом, если х* точка локального минимума в рассматриваемой задаче, то это означает, что найдется такое, что , где некоторая -окрестность точки . Очевидно, что если х* точка глобального минимума, то она же является и точкой локального минимума. При этом, благодаря выпуклости функции , верно и обратное (доказательство этого факта остается в качестве упражнения). Это позволяет легко сформулировать признак оптимальности в случае, если функция является дифференцируемой. Если , то является решением задачи тогда и только тогда, когда . Обобщение на случай не дифференцируемой функции является естественным. Пусть выпукла на , но не обязательно дифференцируема. Тогда если , то является решением задачи тогда и только тогда, когда . ^ Задачи выпуклого программирования Среди оптимизационных задач описанного общего класса выделяется подкласс задач выпуклого программирования. Эти задачи характеризуются специальным способом описания допустимого множества X, а именно: в качестве множества X рассматривается множество решений некоторой системы неравенств, задаваемой выпуклыми функциями. Точнее, речь идет о задачах в Rn вида где и выпуклые функции, области определения которых включают множество ^ X. Для простоты в дальнейшем мы предполагаем, что все эти функции заданы на всем Rn. Для выпуклого программирования можно предложить, по аналогии с линейным программированием, два способа построения геометрической интерпретации рассматриваемых задач: в пространстве переменных xи в пространстве значений функций и . При интерпретации задачи в исходном пространстве Rn переменного х мы вводим множества, каждое из которых является выпуклым. Множество ^ X допустимых решений исходной задачи тогда является пересечением множеств X (следовательно, также выпукло). Целевая функция интерпретируется в виде однопараметрического семейства вложенных множеств . Ясно, что если , то . Тогда задача состоит в отыскании минимального из тех значений параметра , при которых еще пересекается с множеством X:. См. рис. 10. Рис. 10. Геометрическая интерпретация задачи выпуклого программирования, Иной способ геометрической интерпретации мы получаем, обобщая для рассматриваемой задачи схему интерпретации двойственных задач. Для этого запишем полученную задачу минимизации параметра в другой форме: и сведем эти неравенства к равенствам, добавляя вспомогательные неотрицательные переменные

Задачи по линейному программированию и оптимизации 1 чел. помогло.

Задачи выпуклой оптимизации - Задачи по линейному программированию и оптимизации