Методы отсекающих плоскостей

1979: Хачиян ломает 30-летнюю догму, что LP экспоненциально сложен в худшем случае. Метод эллипсоидов даёт полиномиальную сложность - но через геометрию выпуклых тел, а не через симплекс-таблицу. Это открыло двери для оптимизации задач с экспоненциально большими LP, у которых separation oracle поллога: максимальное паросочетание, robust optimization, structured SVM.

• **Robust LP (Ben-Tal-Nemirovski):** оптимизация с эллипсоидальной неопределённостью параметров - решается cutting-plane по реализациям сценариев
• **Benders decomposition:** в энергетике и логистике задачи планирования декомпозируются на master-LP и subproblems через cutting planes по двойственным переменным
• **Structured SVM:** обучение с потерей по выходным структурам (parsing trees, sequences) - cutting-plane на most-violated-constraint (Tsochantaridis et al. 2005)
• **Column generation:** crew scheduling в авиакомпаниях - LP с миллиардами столбцов решается через separation oracle на dual

Предварительные знания

• Выпуклые функции и субградиенты
• Линейное программирование, двойственность LP

• Выпуклые задачи: базовые понятия

Метод Келли и идея отсекающих плоскостей

До сих пор мы предполагали явную формулу для f(x) и её производных. В реальности часто доступен только **subgradient oracle**: подал x - получил значение f(x) и какой-нибудь субградиент g ∈ ∂f(x). Так устроены задачи MaxFlow с барьером, large-scale робастная оптимизация, инженерные black-box модели. Idea Келли (1960): использовать каждый запрос к оракулу для построения линейной нижней оценки и постепенно сужать допустимую область.

**Метод Келли (Kelley 1960)** для min f(x), x ∈ X (X - компактный многогранник): На итерации k имеем точки x⁰, ..., x^{k-1} и субградиенты g⁰, ..., g^{k-1}. Строим **кусочно-линейную нижнюю оценку**: f̂ₖ(x) = max_{i < k} [f(xⁱ) + ⟨gⁱ, x − xⁱ⟩] Каждое слагаемое - касательная гиперплоскость к выпуклой f. Следующая точка: x^k = arg min_{x ∈ X} f̂ₖ(x) (LP-задача!) Новый запрос оракулом даёт новую касательную - модель становится точнее. Сходимость: f̂ₖ(x^k) ↑ min f, но скорость зависит от размерности: O((1/ε)^d) запросов в худшем случае.

Сильная сторона Келли - простота и геометрическая ясность: каждый шаг видим как отсечение. Слабая сторона - **проклятие размерности**: число LP-фасеток растёт экспоненциально с d, а LP-подзадача с m накопленными ограничениями становится дорогой. В практике используют bundle methods (модификация Келли с регуляризацией) или вообще другие схемы.

Метод эллипсоидов: полиномиальная сложность для LP

1979 год: Леонид Хачиян публикует статью, показывающую, что LP решается за полиномиальное время методом эллипсоидов. Это была первая полиномиальная гарантия для LP - до Кармаркара (1984) и его interior point. Метод не лучше Симплекса на практике, но **теоретически революционен**: открыл полиномиальность LP и применим к огромному классу задач, заданных только сепарирующим оракулом.

**Метод эллипсоидов** для min cᵀx, x ∈ K (K выпуклое, заданное **separation oracle**): 1. Начать с эллипсоида E₀ ⊃ K, содержащего оптимум. 2. На шаге k: центр эллипсоида - текущая точка x^k. Запросить separation oracle: - Если x^k ∈ K: получить отсекающую плоскость cᵀ(x − x^k) ≤ 0 (от целевой функции). - Если x^k ∉ K: получить плоскость aᵀ(x − x^k) ≤ 0, отделяющую x^k от K. 3. Построить **минимальный по объёму эллипсоид Eₖ₊₁, содержащий половину Eₖ** (отсечённую плоскостью). 4. Повторять, пока объём не упадёт ниже порога точности. **Сходимость:** vol(Eₖ) ≤ vol(E₀) · exp(−k / (2(n+1))). Для точности ε нужно O(n² · log(1/ε)) итераций; каждая - O(n²) обновление эллипсоида. Итого O(n⁴ log(1/ε)). **Ключевая теорема (Хачиян 1979):** LP размера ⟨L⟩ бит решается за poly(n, L) времени.

Практическое значение: метод эллипсоидов до сих пор - **единственный известный полиномиальный алгоритм** для огромного класса комбинаторных задач, у которых separation oracle поллога (subgradient полиномиален), но число явных ограничений экспоненциально. Например, задача максимального паросочетания, polymatroid optimization, robust LP с эллипсоидальной неопределённостью - всё это решается через ellipsoid + сепарацию.

ACCPM и современные cutting-plane методы

Чистый метод Келли сильно осциллирует: точка x^k часто оказывается на границе многогранника, далеко от внутренности. **ACCPM** (Analytic Center Cutting-Plane Method, Goffin-Vial 1990-е) исправляет это - на каждой итерации выбирается **аналитический центр** локализующего многогранника (минимум барьерной функции на нём). Это даёт численно более стабильный метод и лучшие практические гарантии.

**ACCPM-итерация** для min f(x), f выпуклая: 1. Локализующий многогранник Pₖ = {x : aᵢᵀx ≤ bᵢ, i ≤ k} (накопленные отсечения). 2. **Аналитический центр** xₐ = arg min_{x ∈ Pₖ} −Σ log(bᵢ − aᵢᵀx). - Решается методом Ньютона за O(log(1/δ)) итераций (барьер само-согласован!). 3. Запросить оракул в xₐ - получить новое отсечение, добавить в Pₖ₊₁. **Скорость:** O(n² log(1/ε)) запросов оракула в гладком случае - **на порядок лучше** метода эллипсоидов. Каждая итерация дороже (внутренний Ньютон), но запросов меньше - выгодно когда оракул дорог. **Bundle methods** (Lemarechal, Kiwiel 1970-80-е) - другая модификация Келли: регуляризация ‖x − x_ref‖² подавляет осцилляции.

Современные применения cutting-plane: **robust LP** (Ben-Tal, Nemirovski) - оптимизация с эллипсоидальной неопределённостью, где явная формулировка имеет SDP-размер; **stochastic programming** через L-shaped method (Benders decomposition - это cutting-plane по двойственным переменным); **column generation** для задач планирования транспорта и crew scheduling в авиакомпаниях. В машинном обучении - **structured SVM** обучается cutting-plane методом (Tsochantaridis et al. 2005).

Итог

• **Метод Келли:** piecewise-linear модель из касательных, на каждом шаге - LP-подзадача; работает с subgradient oracle, но страдает от проклятия размерности
• **Метод эллипсоидов (Хачиян 1979):** первое полиномиальное LP, O(n⁴ log(1/ε)); важен теоретически - даёт polynomial-time для задач с separation oracle
• **ACCPM (Goffin-Vial):** аналитический центр локализующего многогранника как точка запроса; O(n² log(1/ε)) запросов оракула; основа robust LP, Benders, structured SVM

Связанные темы

Cutting-plane методы - параллельная ветка к interior point: разные предположения об оракуле, разные классы задач.

• Метод внутренней точки — IPM работает с явной формулой f и её производных; cutting-plane - только с oracle. ACCPM использует log-барьер от IPM для аналитического центра
• Двойственность и декомпозиция — Benders decomposition - cutting-plane по двойственным переменным; column generation - dual версия cutting-plane
• Robust optimization — Robust LP с неопределённостью в полиэдральном или эллипсоидальном множестве решается cutting-plane по сценариям

Вопросы для размышления

• Почему метод эллипсоидов даёт полиномиальную сложность, но проигрывает Симплексу на практике? Какие задачи раскрывают его теоретическое преимущество?
• ACCPM требует решать барьерную задачу на каждой итерации - это дороже одного LP в Келли. При каких условиях ACCPM всё равно выгоднее?
• Bundle methods регуляризуют шаг как ‖x − x_ref‖². Как это связано с проксимальным оператором и почему помогает против осцилляций Келли?

Связанные уроки

• stat-09-regression