Е.А. Нурминский. Бикомпозиция конусных проекций ... С. 73-87

УДК 519.85

MSC: 47H09, 90C25, 90C06

DOI: 10.21538/0134-4889-2023-29-3-73-87

Работа выполнена в Дальневосточном центре математических исследований при финансовой поддержке Минобрнауки России (соглашение № 075-02-2023-946 от 16 февраля 2023 г. по реализации программ развития региональных научно-образовательных математических центров).

Рассматривается декомпозиционный подход для решения задачи ортогонального проектирования заданной точки на выпуклый полиэдральный конус, заданный конечным множеством своих образующих. Сводимость проблемы линейной оптимизации к подобной проекционной задаче потенциально делает этот подход одним из возможных новых способов решения задач линейного программирования большой размерности. В качестве основы подобного подхода может быть предложена идея рекуррентной бинарной декомпозиции, представляющей исходную задачу большой размерности в виде бинарного дерева конусных проекций последовательного разложения первоначального конуса на сумму конусов меньших размерностей. Базовой операцией такого подхода является решение задачи проекции некоторой точки на конус, представленный как сумма двух подконусов при минимальной, по возможности, их модификации и достаточно произвольном их выборе. В работе предложены три итеративных алгоритма, реализующие эту базовую операцию, доказана их сходимость, проведены вычислительные эксперименты, демонстрирующие как вычислительную эффективность предлагаемого подхода, так и некоторые проблемы, возникающие при его применении.

Ключевые слова: ортогональная проекция, полиэдральные конусы, декомпозиция, линейная оптимизация

СПИСОК ЛИТЕРАТУРЫ

1.   NEOS Server: State-of-the-Art Solvers for Numerical Optimization. URL: https://neos-server.org/neos/ 

2.   IBM ILOG CPLEX Optimizer. URL: https://www.ibm.com/products/ilog-cplex-optimization-studio/cplex-optimi...

3.   The Leader in Decision Intelligence Technology – Gurobi Optimization. URL: https://www.gurobi.com 

4.   Cardinal Optimizer (COPT): [website]. URL: https://www.shanshu.ai/copt 

5.   GNU Linear Programming Kit (GLPK): [website]. URL: https://www.gnu.org/software/glpk/ 

6.   Open Source Linear and Mixed-Integer Programming Software and Solvers [e-resource]. URL: https://www.gurobi.com/resources/open-source-linear-and-mixed-integer-pr...

7.   Nurminski E.A. Single-projection procedure for linear optimization // J. Global Optim. 2016. Vol. 66, no. 1. P. 95–110. doi: 10.1007/s10898-015-0337-9

8.   Нурминский Е.А. Проекция на внешне заданные полиэдры//  Журн. вычисл. математики и мат. физики. 2008. Т. 48, №  3. С. 387–396.

9.   Шикин Е.В. Линейные пространства и отображения. М.: URSS, 2022. 312 с. ISBN: 978-5-9519-2967-9.

10.   Nurminski E.A. Follow-up on conversion of outer projection to inner [e-resource]. doi: 10.13140/RG.2.2.28487.88489

11.   Nesterov Yu.E. Efficiency of coordinate descent methods on huge-scale optimization problems // SIAM J. Optim. 2022. Vol. 22, no. 2. P. 341–362. doi: 10.1137/100802001

12.   Bauschke H.H., Borwein J.M. On the convergence of von Neumann’s alternating projection algorithm for two sets // Set-Valued Anal. 1993. Vol. 1. 1993. P. 185–212.

13.   Luo Z.Q., Tseng P. On the convergence of the coordinate descent method for convex differentiable minimization // J Optim Theory Appl. 1992. Vol. 72. P. 7–35.

14.   Wright S.J. Coordinate descent algorithms //  Mathematical Programming. 2015. Vol.  151, no.  1. P.  3–34. doi: 10.1007/s10107-015-0892-3

Поступила 25.05.2023

После доработки 8.07.2023

Принята к публикации 17.07.2023

Нурминский Евгений Алексеевич
д-р физ.-мат. наук, профессор
директор программы развития Дальневосточного центра математических исследований
Дальневосточный федеральный университет
г. Владивосток
e-mail: nurminskiy.ea@dvfu.ru

Ссылка на статью: Е.А. Нурминский. Бикомпозиция конусных проекций // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. С. 73-87

English

E.A. Nurminskii. A bicomposition of conical projections

We consider a decompositional approach to the problem of finding the orthogonal projection of a given point onto a convex polyhedral cone represented by a finite set of its generators. The reducibility of an arbitrary linear optimization problem to such projection problem potentially makes this approach one of the possible new ways to solve large-scale linear programming problems. Such an approach can be based on the idea of a recurrent binary decomposition that splits the original large-scale problem into a binary tree of conical projections corresponding to a sequential decomposition of the initial cone into the sum of lesser subcones. The key operation of this approach is solving the problem of projecting of a certain point onto a cone represented as the sum of two subcones with the smallest possible modification of these subcones and their arbitrary choice. Three iterative algorithms implementing this basic operation are proposed, their convergence is proved, and numerical experiments demonstrating both the computational efficiency of the algorithms and certain problems of their application are performed.

Keywords: orthogonal projection, polyhedral cones, decomposition, linear optimization

Received May 25, 2023

Revised July 8, 2023

Accepted July 17, 2023

Funding Agency: This work was carried out at the Far-East Mathematical Research Center and was supported by the Ministry of Science and Higher Education of the Russian Federation (agreement no. 075-02-2023-946 of February 16, 2023, for the realization of programs for the development of regional centers for mathematical research and education).

Evgeni Alekseevich Nurminski, Dr. Phys.-Math. Sci., Prof., Far Eastern Federal University, Vladivostok, 690922 Russia, email: nurminskiy.ea@dvfu.ru

Cite this article as: E.A. Nurminskii. A bicomposition of conical projections. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 73–87.

[References -> on the "English" button bottom right]