Оптимизация портфеля с кардинальными ограничениями: смешанное целочисленное программирование

Математическая формулировка кардинального ограничения (Cardinality Constraint) требует введения булевых индикаторных переменных $z_i in {0, 1}$, где $z_i = 1$, если актив $i$ включен в портфель, и $z_i = 0$ в противном случае. Ограничение на максимальное число активов в портфеле записывается как $sum_{i=1}^n z_i le K$, где $K$ — желаемый размер портфеля. Чтобы связать непрерывный вес актива $w_i$ с булевой переменной $z_i$, вводятся полунепрерывные ограничения (Semi-continuous constraints): $L_i z_i le w_i le U_i z_i$. Здесь $L_i$ и $U_i$ — минимально и максимально допустимые веса актива в портфеле (например, нельзя купить акцию на долю меньше 1% от капитала).

Наличие дискретных переменных $z_i$ разрушает выпуклость пространства допустимых решений. Задача становится задачей смешанного целочисленного квадратичного программирования (Mixed-Integer Quadratic Programming, MIQP). Стандартные методы множителей Лагранжа и условия Каруша-Куна-Таккера здесь неприменимы. Для точного поиска глобального оптимума алгоритмы (такие как CPLEX или Gurobi) используют метод Ветвей и Границ (Branch and Bound), комбинированный с методами секущих плоскостей (Cutting Planes). Однако при большом количестве активов (например, индекс S&P 500) вычислительная сложность экспоненциально возрастает, делая точное решение за разумное время невозможным.

Для обхода проклятия размерности количественные аналитики активно применяют метаэвристические алгоритмы. Генетические алгоритмы (Genetic Algorithms), имитация отжига (Simulated Annealing) и алгоритмы роя частиц (Particle Swarm Optimization) позволяют эффективно исследовать негладкое пространство решений. Хромосома в генетическом алгоритме кодируется вектором булевых переменных, а фитнес-функцией (Fitness Function) выступает коэффициент Шарпа, скорректированный на штрафы за нарушение ограничений. Эти методы не гарантируют математически точного глобального оптимума, но быстро находят субоптимальные портфели, которые на практике не отличимы от идеальных.

Дополнительной сложностью является учет транзакционных издержек, которые обычно имеют фиксированную часть (брокерская комиссия за саму сделку) и пропорциональную часть (спред). Фиксированные издержки также требуют введения бинарных переменных, превращая задачу ребалансировки в перебор комбинаторики. Решение таких задач является критическим навыком для построения Smart Beta фондов и индексных трекеров, где алгоритм должен повторить динамику широкого бенчмарка (из 3000 акций), используя репрезентативную выборку всего из 50-100 наиболее ликвидных бумаг с минимальным Tracking Error.

Список литературы:
1. Chang T.J., Meade N., Beasley J.E., Sharaiha Y.M. Heuristics for cardinality constrained portfolio optimisation. — Computers & Operations Research, 2000.
2. Mansini R., Speranza M.G. Heuristic algorithms for the portfolio selection problem with minimum transaction lots. — European Journal of Operational Research, 1999.
3. Фабоцци Ф. Управление инвестициями. — М.: Инфра-М, 2000.
Эксперты: Джон Бизли, Рената Мансини, Фрэнк Фабоцци.