E.A. Nurminski. A bicomposition of conical projections ... P. 73-87

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

REFERENCES

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, pp. 95–110. doi: 10.1007/s10898-015-0337-9 

8.   Nurminski E.A. Projection onto polyhedra in outer representation. Comp. Math. and Math. Phys., 2008, vol. 48, no. 3, pp. 367–375.

9.   Shikin E.V. Linejnye prostranstva i otobrazhenija [Linear spaces and mappings]. Moscow: URSS, 2022, 312 p. 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, pp. 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, pp. 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, pp. 7–35.

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

Cite this article as: E.A. Nurminski. A bicomposition of conical projections. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 73–87; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2023, Vol. 323, Suppl. 1, pp. S179–S193.