Abstract
Kernel functions play an important role in defining new search directions for interior-point algorithms for solving monotone linear complementarity problems. In this paper we present a new kernel function which yields the complexity bounds \({\mathcal O}(\sqrt{r}\log r\log\frac{r}{\epsilon})\) and \({\mathcal O}(\sqrt{r}\log\frac{r}{\epsilon})\) for large-and small-update methods, respectively, which are currently the best known bounds for such methods.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bai, Y.Q., El Ghami, M., Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15, 101–128 (2004)
Cho, G.M., Cho, Y.Y., Lee, Y.H.: A primal-dual interior-point algorithm based on a new kernel function. ANZIAM J. 51, 476–491 (2010)
Darvay, Z.: New interior point algorithms in linear programming. Adv. Model. Optim. 5(1), 51–92 (2003)
Faraut, J., Kornyi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, Oxford Science Publications, New York (1994)
Faybusovich, L.: Euclidean Jordan algebras and interior-point algorithms. Positivity 1(4), 331–357 (1997)
Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86, 149–175 (1997)
Faybusovich, L.: A Jordan-algebraic approach to potential-reduction algorithms. Math. Z. 239(1), 117–129 (2002)
Kheirfam, B.: Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term. Numer. Algorithms 61(4), 659–680 (2012)
Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7, 86–125 (1997)
Korányi A.: Monotone functions on formally real Jordan algebras. Math. Ann. 269(1), 73–76 (1984)
Lee, Y.H., Cho, Y.Y., Cho, G.M.: Interior-point algorithms for P *(κ)-LCP based on a new class of kernel functions. J. Glob. Optim. (2013). doi:10.1007/s10898-013-0072-z
Lesaja, G., Roos, C.: Unified analysis of kernel-based interior-point methods for P *(κ)-linear complementarity problems. SIAM J. Optim. 20(6), 3014–3039 (2010)
Lesaja, G., Roos, C.: Kernel-based interior-point methods for monotone linear complementarity problems over symmetric cones. J. Optim Theory Appl. (2013). doi:10.1007/s10957-011-9848-9
Lesaja, G., Wang, G.Q., Zhu, D.T.: Interior-point methods for Cartesian P *(κ)-linear complementarity problems over symmetric cones based on the eligible kernel functions. Optim. Methods Softw. 27(4–5), 827–843 (2012)
Nesterov, Y.E., Todd, M.J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8(2), 324–364 (1998)
Peng, J., Roos, C., Terlaky, T.: Self-regularity: a New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, Princeton, NJ (2002)
Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93(1), 129–171 (2002)
Rangarajan, B.K.: Polynomial convergence of infeasible interior-point methods over symmetric cones. SIAM J. Optim. 16(4), 1211–1229 (2006)
Renegar, J: A Mathematical View of Interior-Point Methods in Convex Optimization. MPS/SIAM Ser. Optim. SIAM, Philadelphia (2001)
Roos, C., Terlaky, T., Vial, J-Ph.: Theory and Algorithms for Linear Optimization. An Interior-Point Approach, Wiley, Chichester (1997)
Schmieta, S.H., Alizadeh, F.: Associative and Jordan algebras and polynomial time interior-point algorithms for symmetric cones. Math. Oper. Res. 26, 543–564 (2001)
Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior-point algorithms to symmetric cones. Math. Program. 96(3), 409–438 (2003)
Vieira, M.V.C.: Jordan algebraic approach to symmetric optimization. PhD thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, The Netherlands (2007)
Wang, G.Q.: A new polynomial interior-point algorithm for the monotone linear complementarity problem over symmetric cones with full NT-steps. Asia-Pac. J. Oper. Res. 29(2), 1250015 (2012)
Wang, G.Q., Bai, Y.Q.: A class of polynomial interior-point algorithms for the Cartesian P-matrix linear complementarity problem over symmetric cones. J. Optim. Theory Appl. 152(3), 739–772 (2012)
Wang, G.Q., Lesaja, G.: Full Nesterov-Todd step feasible interior-point method for the Cartesian P *(κ)-SCLCP. Optim. Methods Softw. 28(3), 600–618 (2013)
Yoshise, A.: Homogeneous algorithms for monotone complementarity problems over symmetric cones. Pac. J. Optim. 5, 313–337 (2009)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kheirfam, B. A Generic Interior-point Algorithm for Monotone Symmetric Cone Linear Complementarity Problems Based on a New Kernel Function. J Math Model Algor 13, 471–491 (2014). https://doi.org/10.1007/s10852-013-9240-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10852-013-9240-x
Keywords
- Monotone linear complementarity problem
- Interior-point algorithms
- Kernel functions
- Euclidean Jordan algebra