Комментарии 6
Немогли бы вы уточнить что означают в ||x||1 и ||x||2 индексы 1 и 2, и далее ||μ||inf
Это индексы нормы. Эта запись используется для сокращения размеров формул.
Первая норма вектора = сумма модулей компонент вектора
Вторая норма вектора = обычная евклидова норма = корень из суммы квадратов компонент вектора
Бесконечная норма вектора = максимум из модулей компонент вектора
Чуть более подробно можно посмотреть вот тут в разделе «примеры»
Первая норма вектора = сумма модулей компонент вектора
Вторая норма вектора = обычная евклидова норма = корень из суммы квадратов компонент вектора
Бесконечная норма вектора = максимум из модулей компонент вектора
Чуть более подробно можно посмотреть вот тут в разделе «примеры»
Пример бы посодержательней… и собственно про содержательную интерпретацию двойственной задачи.
Изначально я начал писать пост про робастную оптимизацию, но там получилась большая простыня текста.
Поэтому я решил вынести технику построения двойственной задачи через конусы в отдельный небольшой пост, на который можно будет сослаться.
После публикации поста про робастную оптимизацию добавлю соответствующую ссылку в этот текст. Там будут более содержательные примеры.
С другой стороны содержательная интерпретация двойственной задачи естественным образом зависит от содержательной интерпретации прямой задачи (для которой мы строили двойственную). То есть интерпретация двойственной задачи зависит от контекста.
Конечно, есть несколько важных свойств двойственной задачи, которые остаются верными всегда:
— Слабая двойственность (при выполнении некоторых условий, сильная двойственность), связывающая значения целевых функций в прямой и двойственной задачах.
— Выпуклость двойственной задачи и, следовательно, возможность ее эффективно численно решить.
В детали тут входить тяжело (объемная тема). Самое лучшее изложение, пожалуй, можно найти в первой главе вот этой замечательной книги.
Поэтому я решил вынести технику построения двойственной задачи через конусы в отдельный небольшой пост, на который можно будет сослаться.
После публикации поста про робастную оптимизацию добавлю соответствующую ссылку в этот текст. Там будут более содержательные примеры.
С другой стороны содержательная интерпретация двойственной задачи естественным образом зависит от содержательной интерпретации прямой задачи (для которой мы строили двойственную). То есть интерпретация двойственной задачи зависит от контекста.
Конечно, есть несколько важных свойств двойственной задачи, которые остаются верными всегда:
— Слабая двойственность (при выполнении некоторых условий, сильная двойственность), связывающая значения целевых функций в прямой и двойственной задачах.
— Выпуклость двойственной задачи и, следовательно, возможность ее эффективно численно решить.
В детали тут входить тяжело (объемная тема). Самое лучшее изложение, пожалуй, можно найти в первой главе вот этой замечательной книги.
Я бы скорее рекомендовал книгу Бойда&Ванденберге (ссылка на нее есть в этой статье), вот например на страницах 230 и 239 есть интерпретация на примере матричных игр: играют двое друг против друга, прямая задача — это задача первого игрока побольше заработать, двойственная — это задача второго игрока поменьше проиграть.
Или вот есть совсем классический, но частный случай: максимальный поток — минимальный разрез. С одной стороны «какой максимальный объем воды можно пропустить по трубам из S в T», с другой «Какой минимальный набор труб (по суммарной пропускной способности) нужно убрать, чтобы разделить S и T»
Или вот есть совсем классический, но частный случай: максимальный поток — минимальный разрез. С одной стороны «какой максимальный объем воды можно пропустить по трубам из S в T», с другой «Какой минимальный набор труб (по суммарной пропускной способности) нужно убрать, чтобы разделить S и T»
Именно в качестве источника примеров книга Бойд и Вандерберге действительно очень хороша. Но опять же это примеры и смысл двойственной задачи будет определен контекстом.
Про какие-то более универсальные вещи лучше смотреть книгу Бен Таля, Гуоуи и Немировского.
В целом самое общее, что приходит в голову:
Обычно задача оптимизации выгляди так: мы пытаемся максимизировать некоторый функционал при наличии ограничений. Ограничены обычно ресурсы. То есть какой уровень некоторого функционала качества мы можем достичь, если у нас есть некоторое заданное количество ресурсов. Двойственная задача ставит вопрос по другому: сколько минимально нам нужно ресурсов, чтобы уровень функционала качества из прямой задачи был не меньше, чем некоторая заданная величина.
Про какие-то более универсальные вещи лучше смотреть книгу Бен Таля, Гуоуи и Немировского.
В целом самое общее, что приходит в голову:
Обычно задача оптимизации выгляди так: мы пытаемся максимизировать некоторый функционал при наличии ограничений. Ограничены обычно ресурсы. То есть какой уровень некоторого функционала качества мы можем достичь, если у нас есть некоторое заданное количество ресурсов. Двойственная задача ставит вопрос по другому: сколько минимально нам нужно ресурсов, чтобы уровень функционала качества из прямой задачи был не меньше, чем некоторая заданная величина.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Немного про коническую двойственность