Illés, Tibor and Rigó, Petra Renáta and Török, Roland (2022) New predictor-corrector interior-point algorithm with AET function having inflection point. Working Paper. Corvinus University of Budapest, Budapest.
|
PDF
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
744kB |
Abstract
In this paper we introduce a new predictor-corrector interior-point algorithm for solving P_* (κ)-linear complementarity problems. For the determination of search directions we use the algebraically equivalent transformation (AET) technique. In this method we apply the function φ(t)=t^2-t+√t which has inflection point. It is interesting that the kernel corresponding to this AET function is neither self-regular, nor eligible. We present the complexity analysis of the proposed interior-point algorithm and we show that it's iteration bound matches the best known iteration bound for this type of PC IPAs given in the literature. It should be mentioned that usually the iteration bound is given for a fixed update and proximity parameter. In this paper we provide a set of parameters for which the PC IPA is well defined. Moreover, we also show the efficiency of the algorithm by providing numerical results.
| Item Type: | Monograph (Working Paper) |
|---|---|
| Series Name: | Corvinus Economics Working Papers - CEWP |
| Series Number / Identification Number: | 2022/05 |
| Uncontrolled Keywords: | Predictor-corrector; Linear complementarity problems; Interior-point algorithm; Complexity analysis |
| JEL classification: | C61 - Optimization Techniques; Programming Models; Dynamic Analysis |
| Divisions: | Institute of Data Analytics and Information Systems Institute of Operations and Decision Sciences |
| Subjects: | Mathematics, Econometrics |
| References: | S. Asadi, H. Mansouri, G. Lesaja, and M. Zangiabadi. A long-step interior-point algorithm
S. Asadi, N. Mahdavi-Amiri, Zs. Darvay and P.R. Rigó, Full-NT step feasible interior-point algorithm for symmetric cone horizontal linear complementarity problem
C. Brás, G. Eichfelder, and J. Júdice, Copositivity tests based on the linear complementarity
S. Burer, Copositive programming, In: Handbook on semidefinite, conic and polynomial
S.-J. Chung, NP-completeness of the linear complementarity problem, J. Optim. Theory Appl. 60 (1989) 393-399.
R. W. Cottle, J.-S. Pang, and R. E. Stone, The Linear Complementarity Problem, Computer
R. W. Cottle, J.-S. Pang, and V. Venkateswaran, Sufficient matrices and the linear complementarity problem, Linear Algebra Appl. 114 (1989) 231-249.
Zs. Csizmadia and T. Illés, New criss-cross type algorithms for linear complementarity
Zs. Csizmadia, T. Illés, and A. Nagy, The s-monotone index selection rules for pivot algorithms
Zs. Darvay, New interior point algorithms in linear programming, Adv. Model. Optim. 5
Zs. Darvay, A predictor-corrector algorithm for linearly constrained convex optimization,
Zs. Darvay, T. Illés, B. Kheirfam, and P. R. Rigó, A corrector-predictor interior-point
Zs. Darvay, T. Illés, and Cs. Majoros, Interior-point algorithm for sufficient LCPs based on
Zs. Darvay, T. Illés, J. Povh, and P.R. Rigó, Feasible corrector-predictor interior-point
Zs. Darvay, T. Illés, and P.R. Rigó, Predictor-corrector interior-point algorithm for P*(k)-linear complementarity problems based on a new type of algebraic equivalent transformation technique, Eur. J. Oper. Res. 298 (2022), 25-35.
Zs. Darvay, I.-M. Papp, and P.-R. Takács, Complexity analysis of a full-Newton step interior-point method for linear optimization, Period. Math. Hung. 73 (2016) 27-42.
Zs. Darvay and P.R. Rigó, New predictor-corrector algorithm for symmetric cone horizontal linear complementarity problems, J. Optim. Theory Appl. (2022), DOI: 10.1007/s10957-022-02078-z.
E. De Klerk and M. E.-Nagy, On the complexitiy of computing the handicap of a sufficient matrix, Math. Program. 129 (2011) 383-402.
M. E.-Nagy, T. Illés, J. Povh, A. Varga and J. Žerovnik, Sufficient matrices: properties,
M. Ferris and J. Pang, Engineering and economic applications of complementarity problems, SIAM Review, 39 (1997) 669-713.
K. Fukuda, M. Namiki, and A. Tamura, EP theorems and linear complementarity problems,
K. Fukuda and T. Terlaky, Criss-cross methods: A fresh view on pivot algorithms, Math. Program. 79 (1997) 369-395.
M. El Ghami, I. Ivanov, J.B. Melissen, C. Roos, and T. Steihaug, A polynomial-time algorithm for linear optimization based on a new class of kernel functions, J. Comput. Appl. Math. 224 (2009) 500-513.
F. Gurtuna, C. Petra, F.A. Potra, O. Shevchenko, and A. Vancea, Corrector-predictor methods for sufficient linear complementarity problems, Comput. Optim. Appl. 48 (2011)
T. Illés and S. Morapitiye, Generating sufficient matrices. In F. Friedler, editor, 8th VOCAL Optimization Conference: Advanced Algorithms, Pázmány Péter Catholic University, Budapest, Hungary, (2018), pages 56-61.
T. Illés and M. Nagy, A Mizuno-Todd-Ye type predictor-corrector algorithm for sufficient
T. Illés, M. Nagy, and T. Terlaky, EP theorem for dual linear complementarity problems,
T. Illés, M. Nagy, and T. Terlaky, Polynomial interior point algorithms for general linear
T. Illés, M. Nagy, and T. Terlaky, A polynomial path-following interior point algorithm
T. Illés, J. Peng, C. Roos and T. Terlaky, A Strongly Polynomial Rounding Procedure Yielding a Maximally Complementary Solution for P*(k) Linear Complementarity Problems, SIAM J. Optim. 11 (2000) 320-340.
T. Illés, P.R. Rigó and R. Török, Unified approach of primal-dual interior-point algorithms for a new class of AET functions. Corvinus Econ. Work. Paper. (2) (2022)
B. Kheirfam, A new infeasible interior-point method based on Darvay’s technique for symmetric optimization, Ann. Oper. Res. 211 (2013) 209-224.
B. Kheirfam, A predictor-corrector interior-point algorithm for P*(k)-horizontal linear complementarity
B. Kheirfam and M. Haghighi, A full-Newton step feasible interior-point algorithm for
M. Kojima, N. Megiddo, T. Noma, and A. Yoshise, A Unified Approach to Interior Point
G. Lešaja and F.A. Potra, Adaptive full Newton-step infeasible interior-point method for
G. Lešaja and C. Roos, Unified analysis of kernel-based interior-point methods for P*(k)-linear complementarity problems, SIAM J. Optim. 20 (2010) 3014-3039.
X. Liu and F.A. Potra, Corrector-predictor methods for sufficient linear complementarity
J. Miao, A quadratically convergent O((k+1)p
S. Mizuno, M. Todd, and Y. Ye, On adaptive-step primal-dual interior-point algorithms for
M. Nagy, Interior point algorithms for general linear complementarity problems, PhD thesis,
J. Peng, C. Roos, and T. Terlaky, Self-Regular Functions: a New Paradigm for Primal-Dual
F.A. Potra, Corrector-predictor methods for monotone linear complementarity problems in
F.A. Potra, Interior point methods for sufficient horizontal LCP in a wide neighborhood of
F.A. Potra and X. Liu, Predictor-corrector methods for sufficient linear complementarity
F.A. Potra and R. Sheng, Predictor-corrector algorithm for solving P*(k)-matrix LCP from
F.A. Potra and R. Sheng, A large-step infeasible-interior-point method for the P*-Matrix
P.R. Rigó, New trends in algebraic equivalent transformation of the central path and its
C. Roos, T. Terlaky, and J.-P. Vial, Theory and Algorithms for Linear Optimization,
R. Török, T. Illés, and P.R. Rigó, Implementation of primal-dual interior-point algortihm
P. Tseng, Co-NP-completeness of some matrix classification problems, Math. Program. 88 (2000) 183-192.
G. Wang and Y. Bai, Polynomial interior-point algorithms for P*(k) horizontal linear complementarity problem, J. Comput. Appl. Math. 223 (2009) 248-263.
Q. Wang and H. Sun, Sparse Markowitz portfolio selection by using stochastic linear complementarity approach, J. Ind. Manag. Optim. 14 (2018) 541-559.
Y. Ye, A path to the Arrow-Debreu competitive market equilibrium, Math. Program. 111 (2008) 315-348. |
| ID Code: | 7724 |
| Deposited By: | Ádám Hoffmann |
| Deposited On: | 18 Nov 2022 13:02 |
| Last Modified: | 18 Nov 2022 13:02 |
Repository Staff Only: item control page
Download Statistics
Download Statistics