Finite convergence into a convex polytope via facet reflections

Dinesh B. Ekanayake; Douglas J. LaFountain; Boris Petracovici

Applications of Mathematics (2023)

  • Volume: 68, Issue: 4, page 387-404
  • ISSN: 0862-7940

Abstract

top
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 ℝ 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.

How to cite

top

Ekanayake, Dinesh B., LaFountain, Douglas J., and Petracovici, Boris. "Finite convergence into a convex polytope via facet reflections." Applications of Mathematics 68.4 (2023): 387-404. <http://eudml.org/doc/299337>.

@article{Ekanayake2023,
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.},
author = {Ekanayake, Dinesh B., LaFountain, Douglas J., Petracovici, Boris},
journal = {Applications of Mathematics},
keywords = {convex geometry; optimization; infeasible start; strategy games},
language = {eng},
number = {4},
pages = {387-404},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Finite convergence into a convex polytope via facet reflections},
url = {http://eudml.org/doc/299337},
volume = {68},
year = {2023},
}

TY - JOUR
AU - Ekanayake, Dinesh B.
AU - LaFountain, Douglas J.
AU - Petracovici, Boris
TI - Finite convergence into a convex polytope via facet reflections
JO - Applications of Mathematics
PY - 2023
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 68
IS - 4
SP - 387
EP - 404
AB - 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.
LA - eng
KW - convex geometry; optimization; infeasible start; strategy games
UR - http://eudml.org/doc/299337
ER -

References

top
  1. Ackley, D. H., 10.1007/978-1-4613-1997-9, The Springer International Series in Engineering and Computer Science 28. Springer, New York (2012). (2012) DOI10.1007/978-1-4613-1997-9
  2. Bazaraa, M. S., Jarvis, J. J., Sherali, H. D., 10.1002/9780471703778, John Wiley & Sons, Hoboken (2005). (2005) Zbl1061.90085MR2106392DOI10.1002/9780471703778
  3. Boyd, S., Vandenberghe, L., 10.1017/CBO9780511804441, Cambridge University Press, Cambridge (2004). (2004) Zbl1058.90049MR2061575DOI10.1017/CBO9780511804441
  4. Dantzig, G. B., Thapa, M. N., 10.1007/b97283, Springer Series in Operations Research. Springer, New York (2003). (2003) Zbl1029.90037MR1994342DOI10.1007/b97283
  5. Greenberg, H. J., Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method, University of Colorado at Denver, Denver (1997). (1997) 
  6. Press, W. H., Teukolsky, S. A., Vetterling, W. T., Flannery, B. P., Numerical Recipes: The Art of Scientific Computing, Cambridge University Press, Cambridge (2007). (2007) Zbl1132.65001MR2371990
  7. Renegar, J., 10.1007/BF01580724, Math. Program., Ser. A 40 (1988), 59-93. (1988) Zbl0654.90050MR0923697DOI10.1007/BF01580724
  8. Ye, Y., Todd, M. J., Mizuno, S., 10.1287/moor.19.1.53, Math. Oper. Res. 19 (1994), 53-67. (1994) Zbl0799.90087MR1290010DOI10.1287/moor.19.1.53

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.