Geodesic
An efficient logarithmic barrier method without line search
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 25 (2022) no. 2, pp. 193-207.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this work, we deal with a convex quadratic problem with inequality constraints. We use a logarithmic barrier method based on some new approximate functions. These functions have the advantage that they allow computing the displacement step easily and without consuming much time contrary to a line search method, which is time-consuming and expensive to identify the displacement step. We have developed an implementation with MATLAB and conducted numerical tests on some examples of considerable size. The obtained numerical results show the accuracy and efficiency of our approach. 
@article{SJVM_2022_25_2_a6,
     author = {S. Chaghoub and D. Benterki},
     title = {An efficient logarithmic barrier method without line search},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {193--207},
     publisher = {mathdoc},
     volume = {25},
     number = {2},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2022_25_2_a6/}
}
TY  - JOUR
AU  - S. Chaghoub
AU  - D. Benterki
TI  - An efficient logarithmic barrier method without line search
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2022
SP  - 193
EP  - 207
VL  - 25
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJVM_2022_25_2_a6/
LA  - ru
ID  - SJVM_2022_25_2_a6
ER  - 
%0 Journal Article
%A S. Chaghoub
%A D. Benterki
%T An efficient logarithmic barrier method without line search
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2022
%P 193-207
%V 25
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJVM_2022_25_2_a6/
%G ru
%F SJVM_2022_25_2_a6
S. Chaghoub; D. Benterki. An efficient logarithmic barrier method without line search. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 25 (2022) no. 2, pp. 193-207. http://geodesic.mathdoc.fr/item/SJVM_2022_25_2_a6/

[1] Bai Y., El Ghami M., Roos C., “A comparative study of kernel functions for primal-dual interior point algorithms in linear optimization”, SIAM J. Optim., 15:1 (2005), 101–128 | DOI | MR

[2] Belabbaci A., Djebbar B., Mokhtari A., “Optimization of a strictly concave quadratic form”, Proc. 4th Intern. Conf. on Applied Operational Research (Bangkok, Thailand, 2012), 16–20

[3] Belabbaci A., Djebbar B., “Algorithm and separating method for the optimization of quadratic functions”, Int. J. Computing Science and Mathematics, 8:2 (2017), 183–192 | DOI | MR | Zbl

[4] Ben-Daya M., Al-Sultan K. S., “A new penalty function algorithm for convex quadratic programming”, European J. of Operational Research, 101:1 (1997), 155–163 | DOI | MR | Zbl

[5] Benterki D., Crouzeix J. P., Merikhi B., “A numerical feasible interior point method for linear semidefinite programs”, RAIRO-Operations Research, 41 (2007), 49–59 | DOI | MR | Zbl

[6] Boudjellal N., Roumili H., Benterki D., “A primal-dual interior point algorithm for convex quadratic programming based on a new parametric kernel function”, Optimization, 2020 | DOI | MR

[7] Cherif L. B., Merikhi B., “A penalty method for nonlinear programming”, RAIRO-Operations Research, 53 (2019), 29–38 | DOI | MR | Zbl

[8] Chikhaoui A., Djebbar B., Belabbaci A., Mokhtari A., “Optimization of a quadratic function under its canonical form”, Asian J. of Applied Sciences, 2:6 (2009), 499–510 | DOI

[9] Crouzeix J. P., Merikhi B., “A logarithm barrier method for semi-definite programming”, RAIRO-Operations Research, 42 (2008), 123–139 | DOI | MR | Zbl

[10] Dikin I. I., “Iterative solution of problems of linear and quadratic programming”, Dokl. Akad. Nauk SSSR, 174 (1967), 747–748 | MR | Zbl

[11] Dozzi M., Méthodes non linéaires et stochastiques de la recherche opérationnelle https://iecl.univ-lorraine.fr Marco.Dozzi

[12] Frank M., Wolfe P., “An algorithm for quadratic programming”, Naval Research Logistics Quarterly, 3:1–2 (1956), 95–110 | DOI | MR

[13] Gartner B., Schonherr S., Smallest Enclosing Circles – An Exact and Generic Implementation in C++, 2016 ftp://ftp.inf.fu-berlin.de/pub/reports/tr-b-98-05.ps.gz

[14] Karmarkar N. K., “A new polynomial-time algorithm for linear programming”, Proc. 16th Annual ACM Symposium on Theory of Computing, Combinatorica, v. 4, 1984, 373–395 | MR | Zbl

[15] Leulmi A., Leulmi S., “Logarithmic barrier method via minorant function for linear programming”, J. of Siberian Federal University. Mathematics and Physics, 12:2 (2019), 191–201 | DOI | MR | Zbl

[16] Leulmi A., Merikhi B., Benterki D., “Study of a logarithmic barrier approach for linear semidefinite programming”, J. of Siberian Federal University. Mathematics and Physics, 11:3 (2018), 300–312 | DOI | MR | Zbl

[17] Menniche L., Benterki D., “A logarithmic barrier approach for linear programming”, J. of Computational and Applied Mathematics. Elsevier, 312 (2017), 267–275 | DOI | MR | Zbl

[18] Roos C., Terlaky T., Vial J. P., Theory and Algorithms for Linear Optimization: An Interior Point Approach, Wiley, Chichester, 1997 | MR | Zbl

[19] Vaidya P. M., “An algorithm for linear programming which requires arithmetic operations”, Proc. 19th Annual ACM Symposium Theory of Computing, 1987, 29–38 | MR

[20] Wolfe P., “The simplex method for quadratic programming”, Econometrica: J. of the Econometric Society, 27:3 (1959), 382–398 | DOI | MR | Zbl

[21] Wolkowicz H., Styan G. P. H., “Bounds for eigenvalues using traces”, Linear Algebra and Appl., 29 (1980), 471–506 | DOI | MR | Zbl

[22] Wright S. J., Primal-dual Interior-point Methods, SIAM, 1997 | MR | Zbl

[23] Ye Y., Tse E., “An extension of Karmarkar's projective algorithm for convex quadratic programming”, Mathematical Programming, 44 (1989), 157–179 | DOI | MR | Zbl

[24] Ye Y., Tse E., A Polynomial Algorithm for Convex Quadratic Programming, Stanford University, 1986