Kernel-based interior-point methods for monotone linear complementarity problems over symmetric cones
type: Item
instance of: scholarly article
title: Kernel-based interior-point methods for monotone linear complementarity problems over symmetric cones
zbMATH Open document ID: 1250.90097
published in: Journal of Optimization Theory and Applications
publication date: 2011-11-25T00:00:00Z
review text: An Euclidean Jordan algebra (EJA) is a triple \((V,\circ ,\left\langle \cdot ,\cdot \right\rangle ),\) where \(V\) is a finite-dimensional real vector space, \(\circ :V\times V\rightarrow V\) is a symmetric bilinear form (product) satisfying the Jordan Axiom \[ x\circ (x^{2}\circ y)=x^{2}\circ (x\circ y)\quad \forall x,y\in V, \] and \(\left\langle \cdot ,\cdot \right\rangle :V\times V\rightarrow V\) is a positive definite symmetric bilinear form (inner product)\ satisfying the associative axiom \[ \left\langle x\circ z,y\right\rangle =\left\langle x,z\circ y\right\rangle \quad \forall x,y,z\in V. \] It is known that a cone \(K\) is symmetric if and only if there exists some EJA \((V,\circ ,\left\langle \cdot ,\cdot \right\rangle )\) such that \( K=\left\{ x^{2},x\in V\right\} \) (the cone of squares of \(V\)). The monotone linear complementarity problems over a symmetric cone problem (SCLCP) considered by the authors consists of, given a symmetric cone \(K\) with associated EJA \((V,\circ ,\left\langle \cdot ,\cdot \right\rangle )\) and an affine subspace \(L\) of \(V\times V\) satisfying the\ monotone property, i.e., \[ \left\langle x_{1}-x_{2},y_{1}-y_{2}\right\rangle \geq 0\quad \forall \left( x_{1},y_{1}\right) ,\left( x_{2},y_{2}\right) \in L, \] find a pair \((x,s)\in K\times K\) such that \[ (x,s)\in L\text{ and }\left\langle x,s\right\rangle =0. \] The optimality conditions of several important optimization problems can be written in the form of SCLCP. For example, the solution of any Linear Optimization problem over symmetric cones can be formulated as SCLCP. The paper proposes an interior-point method for monotone linear complementarity problems over symmetric cones (SCLCP) that is based on barrier functions which are defined by a large class of univariate functions, called eligible kernel functions. Computational experience is provided.
reviewed by: Miguel Angel Goberna
Mathematics Subject Classification ID: 90C33
Mathematics Subject Classification ID: 90C51
zbMATH DE Number: 5980386
zbMATH Keywords: linear complementarity problem
zbMATH Keywords: Euclidean Jordan algebras and symmetric cones
zbMATH Keywords: Interior-point method
zbMATH Keywords: Kernel functions
zbMATH Keywords: polynomial complexity
author: Goran Lesaja
author: C. Roos
MaRDI profile type: Publication
OpenAlex ID: W2122341846
cites work: Unified Analysis of Kernel-Based Interior-Point Methods for $P_*(\kappa)$-Linear Complementarity Problems
cites work: Q4321748
cites work: Q4324980
cites work: Self-Scaled Barriers and Interior-Point Methods for Convex Programming
cites work: Primal-Dual Interior-Point Methods for Self-Scaled Cones
cites work: Barrier Functions in Interior Point Methods
cites work: Linear systems in Jordan algebras and primal-dual interior-point algorithms
cites work: Euclidean Jordan algebras and interior-point algorithms
cites work: Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones.
cites work: Extension of primal-dual interior point algorithms to symmetric cones
cites work: An infeasible-interior-point predictor-corrector algorithm for the \(P_ *\)-geometric LCP
cites work: Equivaence between different formulations of the linear complementarity promblem
cites work: Q5453751
cites work: Corrector‐Predictor Methods for Sufficient Linear Complementarity Problems in a Wide Neighborhood of the Central Path
cites work: A unified approach to interior point algorithms for linear complementarity problems: A summary
cites work: A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem
cites work: A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with \(O(\sqrt nL)\)-iteration complexity
cites work: A superquadratic infeasible-interior-point method for linear complementarity problems
cites work: On homogeneous and self-dual algorithms for LCP
cites work: Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices
cites work: Polynomiality of primal-dual algorithms for semidefinite linear complementarity problems based on the Kojima-Shindoh-Hara family of directions
cites work: Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcp∗
cites work: Polynomial Convergence of Infeasible-Interior-Point Methods over Symmetric Cones
cites work: Interior Point Trajectories and a Homogeneous Model for Nonlinear Complementarity Problems over Symmetric Cones
cites work: Q3632453
cites work: A Comparative Study of Kernel Functions for Primal-Dual Interior-Point Algorithms in Linear Optimization
cites work: Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
cites work: An Interior-Point Method for Semidefinite Programming
cites work: A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming
cites work: On a commutative class of search directions for linear programming over symmetric cones
cites work: Geometric means on symmetric cones
cites work: Q4791754
cites work: A polynomial-time algorithm for linear optimization based on a new simple kernel function
cites work: A class of large-update and small-update primal-dual interior-point algorithms for linear optimization
cites work: Conic convex programming and self-dual embedding
DOI: 10.1007/S10957-011-9848-9
description: scientific article; zbMATH DE number 5980386