Дискретная оптимизация портфеля Марковица с использованием открытых классических и квантово-вдохновлённых алгоритмов: кросс-рыночное исследование с пошаговой валидацией

Дискретная оптимизация портфеля Марковица с использованием открытых классических и квантово-вдохновлённых алгоритмов: кросс-рыночное исследование с пошаговой валидацией

Авдошин С.М. (НИУ ВШЭ, Москва, Россия)
Патрушев К.А. (НИУ ВШЭ, Москва, Россия)

Аннотация

Задача Марковица с ограничением на кардинальность является NP-трудной и традиционно решается коммерческими MIQP-решателями (Mixed-Integer Quadratic Programming). После введения в 2022 году экспортных ограничений, сделавших недоступными с территории РФ как коммерческое программное обеспечение (ПО) MIQP, так и облачные квантовые платформы (IBM Quantum, D-Wave Leap), практикам необходимы открытые альтернативы. В работе проведено систематическое сравнение трёх семейств решателей: двух открытых классических MIQP (решатели SCIP и ECOS_BB с библиотекой CVXPY) и квантово-вдохновлённого решателя имитационного отжига на бинарной QUBO-формулировке включения активов с двухэтапным гибридным конвейером. Все решатели используют единую инстанцию задачи. В эксперименте по синтетической масштабируемости метод квантово-вдохновлённой имитации отжига становится самым быстрым (в 7 раз быстрее SCIP при некоторых условиях), но с зазором оптимальности 11–13%. В другом эксперименте (пошаговое тестирование на биржевых данных индексов S&P 500 и MOEX с реалистичными транзакционными издержками) дискретная оптимизация показывает рост относительно простой стратегии равной доли активов по индексу S&P 500, однако подход neal SA уступает алгоритму SCIP из-за остаточного зазора и повышенного оборота. На нестационарном российском рынке все стратегии оптимизации по среднему и дисперсии уступают стратегии равной доли активов, воспроизводя парадокс DeMiguel–Garlappi–Uppal. Исследование количественно характеризует компромисс между масштабируемостью и качеством, раскладывает зазор оптимальности на составляющие (формулировка, сэмплер, калибровка штрафа) и определяет условия, при которых текущий конвейер на основе стратегии neal недостаточен для практического применения.

Ключевые слова

портфельная оптимизация; Марковиц; задача оптимизации QUBO; имитационный отжиг; квантово-вдохновлённые алгоритмы; смешанное целочисленное квадратичное программирование; пошаговое тестирование; ограничение на кардинальность; квантовый метод QAOA.

Издание

Труды Института системного программирования РАН, том 38, вып. 4, часть 2, 2026, стр. 245-256.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2026-38(4)-29

Для цитирования

Авдошин С.М., Патрушев К.А. Дискретная оптимизация портфеля Марковица с использованием открытых классических и квантово-вдохновлённых алгоритмов: кросс-рыночное исследование с пошаговой валидацией. Труды Института системного программирования РАН, том 38, вып. 4, часть 2, 2026, стр. 245-256. DOI: 10.15514/ISPRAS-2026-38(4)-29.

Полный текст статьи в формате pdf (на английском) Вернуться к содержанию тома