Applications of Mathematics, Vol. 68, No. 4, pp. 387-404, 2023
Finite convergence into a convex polytope via facet reflections
Dinesh B. Ekanayake, Douglas J. LaFountain, Boris Petracovici
Received June 11, 2022. Published online November 3, 2022.
Abstract: The problem of utilizing facet reflections to bring a point outside of a convex polytope to inside has not been studied explicitly in the literature. Here we introduce two algorithms that complete the task in finite iterations. The first algorithm generates multiple solutions on the plane, and can be readily utilized in creating games on a plane or as a level generation method for video games. The second algorithm is a new efficient way to bring infeasible starting points of an optimization problem to inside a feasible region defined by constraints. Using simulations, we demonstrate many desirable properties of the algorithm. Specifically, more edges do not lead to more iterations in $\mathbb{R}^2$, the algorithm is extremely efficient in high dimensions, and it can be employed to discretize the feasibility region using a grid of points outside the region.
Keywords: convex geometry; optimization; infeasible start; strategy games
References: [1] D. H. Ackley: A Connectionist Machine for Genetic Hillclimbing. The Springer International Series in Engineering and Computer Science 28. Springer, New York (2012). DOI 10.1007/978-1-4613-1997-9
[2] M. S. Bazaraa, J. J. Jarvis, H. D. Sherali: Linear Programming and Network Flows. John Wiley & Sons, Hoboken (2005). DOI 10.1002/9780471703778 | MR 2106392 | Zbl 1061.90085
[3] S. Boyd, L. Vandenberghe: Convex Optimization. Cambridge University Press, Cambridge (2004). DOI 10.1017/CBO9780511804441 | MR 2061575 | Zbl 1058.90049
[4] G. B. Dantzig, M. N. Thapa: Linear Programming II: Theory and Extensions. Springer Series in Operations Research. Springer, New York (2003). DOI 10.1007/b97283 | MR 1994342 | Zbl 1029.90037
[5] H. J. Greenberg: Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method. University of Colorado at Denver, Denver (1997).
[6] W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery: Numerical Recipes: The Art of Scientific Computing. Cambridge University Press, Cambridge (2007). MR 2371990 | Zbl 1132.65001
[7] J. Renegar: A polynomial-time algorithm, based on Newton's method, for linear programming. Math. Program., Ser. A 40 (1988), 59-93. DOI 10.1007/BF01580724 | MR 0923697 | Zbl 0654.90050
[8] Y. Ye, M. J. Todd, S. Mizuno: An $O(\sqrt{n}L)$-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19 (1994), 53-67. DOI 10.1287/moor.19.1.53 | MR 1290010 | Zbl 0799.90087
Affiliations: Dinesh B. Ekanayake (corresponding author), Douglas J. LaFountain, Boris Petracovici, Western Illinois University, 1 University Cir, Macomb, IL 61455, Illinois, USA, e-mail: db-ekanayake@wiu.edu, d-lafountain@wiu.edu, b-petracovici@wiu.edu
