On Finding a Relative Interior Point of a Polyhedral Set

Document Type : Original Scientific Paper


Department of Mathematics and Applications, University of Mohaghegh Ardabili, Ardabil, Iran



This paper proposes a new linear program for finding a relative interior point of a polyhedral set. Based on characterizing the relative interior of a polyhedral set through its polyhedral representing sets, two main contributions are made. First, we complete the existing results in the literature that require the non-negativity of the given polyhedral set. Then, we deal with the general case where this requirement may not be met.


[1] I. Adler and R. D. C. Monteiro, A geometric view of parametric linear programming, Algorithmica 8 (1992) 161–176.
[2] A. Ben-Tal, L. El Ghaoui and A. Nemirovski, Robust Optimization, Princeton University Press, Princeton, NJ, 2009.
[3] D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, Massachusetts, 1997.
[4] C. Cartis and N. I. M. Gould, Finding a point in the relative interior of a polyhedron, Technical Report NA-07/01, Computing Laboratory Oxford University, 2007.
[5] C. Cartis and N. I. M. Gould, Finding a point in the relative interior of a polyhedron, with applications to compressed sensing, SPARS09 - Signal Processing with Adaptive Sparse Structured Representations, Inria Rennes-Bretagne Atlantique, Apr 2009, Saint Malo, France.
[6] G. Dahl, An Introduction to Convexity, Polyhedral Theory and Combinatorial Optimization, University of Oslo, Department of Informatics, 1997.
[7] S. M. Mirdehghan and M. Mehdiloo, Finding a relative interior point of a polyhedron using linear programming: Application to geometric programming, J. Oper. Res. Appl. 15 (3) (2018) 1–13.
[8] M. Mehdiloozad, K. Tone, R. Askarpour and M. B. Ahmadi, Finding a maximal element of a non-negative convex set through its characteristic cone: An application to finding a strictly complementary solution, Comput. Appl. Math. 37 (1) (2018) 53–80.
[9] S. Mehrotra and Y. Ye, Finding an interior point in the optimal face of linear programs, Math. Programm. 62 (1) (1993) 497–515.
[10] E. D. Nering and A. W. Tucker, Linear Programs and Related Problems, Academic Press, San Diego, 1993.
[11] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970.
[12] G. Sierksma and G. A. Tijssen, Degeneracy degrees of constraint collections, Math. Methods Oper. Res. 57 (2003) 437–448.
[13] P. J. Stuckey, Incremental linear constraint solving and detection of implicit equalities, ORSA J. Comput. 3 (4) (1991) 269–274.
[14] J. Telgen, Identifying redundant constraints and implicit equalities in systems of linear constraints, Manag. Sci. 29 (10) (1982) 1209–1222.