Primal-dual entropy-based interior-point algorithms for linear optimization

Karimi, Mehdi; Luo, Shen; Tunçel, Levent

RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 2, pp. 299-328.

We propose a family of search directions based on primal-dual entropy in the context of interior-point methods for linear optimization. We show that by using entropy-based search directions in the predictor step of a predictor-corrector algorithm together with a homogeneous self-dual embedding, we can achieve the current best iteration complexity bound for linear optimization. Then, we focus on some wide neighborhood algorithms and show that in our family of entropy-based search directions, we can find the best search direction and step size combination by performing a plane search at each iteration. For this purpose, we propose a heuristic plane search algorithm as well as an exact one. Finally, we perform computational experiments to study the performance of entropy-based search directions in wide neighborhoods of the central path, with and without utilizing the plane search algorithms.

Classification : 90C05, 90C51, 41A46, 94A17
Mots clés : Interior-point methods, primal-dual entropy, central path, homogeneous and self-dual embedding, search direction

W. Ai and S. Zhang, An $O\left(\sqrt{n}L\right)$ iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone lcp. SIAM J. Optim. 16 (2005) 400–417. | DOI | MR | Zbl

Y.Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15 (2004) 101–128. | DOI | MR | Zbl

X.Z. Cai, G.Q. Wang, M. El Ghami and Y.J. Yue, Complexity analysis of primal-dual interior-point methods for linear optimization based on a new parametric kernel function with a trigonometric barrier term. Abstr. Appl. Anal. 2014 (2014) 710158. | MR | Zbl

C.I. Chang, Y. Du, J. Wang, S.M. Guo and P.D. Thouin, Survey and comparative analysis of entropy and relative entropy thresholding techniques. In Vol. 153 of IEE Proceedings Vision, Image and Signal Processing. IET (2006) 837–850.

T.M. Cover and J.A. Thomas, Elements of information theory. John Wiley & Sons (2012). | MR | Zbl

Zs. Darvay, A new algorithm for solving self-dual linear optimization problems. Stud. Univ. Babȩs-Bolyai 47 (2003) 15–26. | MR | Zbl

A. Decarreau, D. Hilhorst, C. Lemaréchal and J. Navaza, Dual methods in entropy maximization. application to some problems in crystallography. SIAM J. Optim. 2 (1992) 173–197. | DOI | MR | Zbl

T. Downarowicz, Entropy in dynamical systems. Cambridge University Press (2011) | MR | Zbl

N.J. Dusaussoy and I.E. Abdou, The extended ment algorithm: a maximum entropy type algorithm using prior knowledge for computerized tomography. IEEE Trans. Signal Proces. 39 (1991) 1164–1180. | DOI

M. Dyer, A class of convex programs with applications to computational geometry. In Proc. of the Eighth Annual Symposium on Computational Geometry. ACM (1992) 9–15.

H. Edelsbrunner, Algorithms in Computational Geometry. Springer New York (1987). | MR

S. Erlander, Accessibility, entropy and the distribution and assignment of traffic. Transport. Res. 11 (1977) 149–153. | DOI

S. Erlander, Entropy in linear programs. Math. Program. 21 (1981) 137–151. | DOI | MR | Zbl

S. Fang, J.R. Rajasekera and H.J. Tsao, Vol. 8 of Entropy Optimization and Mathematical Programming. Springer (1997). | MR | Zbl

R.M. Freund, On the behavior of the homogeneous self-dual model for conic convex optimization. Math. Program. 106 (2006) 527–545. | DOI | MR | Zbl

N. Karmarkar, A new polynomial time algorithm for linear programming. Combinatorica 4 (1984) 373–395. | DOI | MR | Zbl

Y.H. Lee, J.H. Jin and G.M. Cho, Kernel function based interior-point algorithms for semidefinite optimization. Math. Inequal. Appl. 16 (2013) 1279–1294. | MR | Zbl

X.S. Li, Entropy and optimization. Ph.D. thesis, University of Liverpool, UK (1987).

S. Luo, Interior-Point Algorithms Based on Primal-Dual Entropy. Master’s thesis, University of Waterloo, Canada (2006).

N. Megiddo, Linear-time algorithms for linear programming in $R^3$ and related problems. In Foundations of Computer Science. SFCS’08. 23rd Annual Symposium on. IEEE (1982) 329–338. | MR

S. Mizuno, M.J. Todd and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming. Math. Oper. Res. 18 (1993) 964–981. | DOI | MR | Zbl

R.D.C. Monteiro, I. Adler and M.G.C. Resende, A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Math. Operat. Res. 15 (1990) 191–214. | DOI | MR | Zbl

C. Nadeu and M. Bertran, A flatness-based generalized optimization approach to spectral estimation. Signal Process. 19 (1990) 311–320. | DOI

J.L. Nazareth, A reformulation of the central path equations and its algorithmic implications. Department of Pure and Applied Math., Washington State Univ. (1994).

J.L. Nazareth, Deriving potential functions via a symmetry principle for nonlinear equations. Oper. Res. Lett. 21 (1997) 147–152. | DOI | MR | Zbl

Y. Nesterov, Parabolic target space and primal–dual interior-point methods. Discrete Appl. Math. 156 (2008) 2079–2100. | DOI | MR | Zbl

NETLIB. Available at http://www.netlib.org/lp/data/.

S. Pan, X. Li and S. He, An infeasible primal–dual interior point algorithm for linear programs based on logarithmic equivalent transformation. J. Math. Anal. Appl. 314 (2006) 644–660. | DOI | MR | Zbl

M.Ç. Pınar and S.A. Zenios, An entropic approximation of $\ell {}_1$ penalty function. Trans. Oper. Res. (1995) 101–120.

F.A. Potra, Primal-dual affine scaling interior point methods for linear complementarity problems. SIAM J. Optim. 19 (2008) 114–143. | DOI | MR | Zbl

T. Pynchon, A survey of entropy methods for partial differential equations. Amer. Math. Soc. 41 (2004) 409–438. | DOI | MR | Zbl

C. E. Shannon, A mathematical theory of communication. ACM SIGMOBILE Mobile Comput. Commun. Rev. 5 (2001) 3–55. | DOI

J.F. Sturm, Implementation of interior point methods for mixed semidefinite and second order cone optimization problems. Optim. Meth. Softw. 17 (2002) 1105–1154. | DOI | MR | Zbl

L. Tunçel, On the convergence of primal-dual interior-point methods with wide neighborhoods. Comput. Optim. Appl. 4 (1995) 139–158. | DOI | MR | Zbl

L. Tunçel and M.J. Todd, On the interplay among entropy, variable metrics and potential functions in interior-point algorithms. Comput. Optim. Appl. 8 (1997) 5–19. | DOI | MR | Zbl

Y. Ye, An $O\left(n^{3}L\right)$ potential reduction algorithm for linear programming. Math. Program. 50 (1991) 239–258. | DOI | MR | Zbl

Y. Ye, M.J. Todd and S. Mizuno, An $O\left(\sqrt{n}L\right)$-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19 (1994) 53–67. | DOI | MR | Zbl

P. Zhang and X. Li, An infeasible-start path-following method for monotone LCPs. Math. Comput. Model. 38 (2003) 23–31. | DOI | MR | Zbl