Научная визуализация
Двойственная задача для min(x₁²+x₂²+x₃²) при 2x₁+3x₂+5x₃=10
Двойственная задача для min(x₁²+x₂²+x₃²) при 2x₁+3x₂+5x₃=10. Оптимум прямой задачи x*=(10,15,25)/19; значения прямой и двойственной задач равны 50/19.
min ||x||² s.t. 2x₁+3x₂+5x₃=10; x*=(10,15,25)/19
Условие
Выпишите двойственную задачу для
min x₁²+x₂²+x₃²
при ограничении 2x₁+3x₂+5x₃=10.
Лагранжиан источника
L(x,λ)=x₁²+x₂²+x₃²+λ(2x₁+3x₂+5x₃−10).
Условия минимума по x:
x₁=−λ, x₂=−3λ/2, x₃=−5λ/2.
Двойственная функция
Подставляя эти значения, получаем
g(λ)=−(19/2)λ²−10λ.
Двойственная задача: max_{λ∈R} g(λ).
Решение
g′(λ)=−19λ−10, поэтому λ*=−10/19. Тогда
x*=(10/19,15/19,25/19).
Ограничение проверяется: 20/19+45/19+125/19=10.
Сильная двойственность
Primal value равен ||x*||²=(100+225+625)/361=50/19. Двойственное значение g(−10/19) также равно 50/19. Для выпуклой квадратичной задачи с аффинным допустимым ограничением разрыва двойственности здесь нет.
Борис Демешев и участники · mlearn_pro, задача 63 · CC BY 4.0. Лагранжиан и FOC источника сохранены; двойственная квадратичная форма упрощена и решена.