GUS-property for Lorentz cone linear complementarity problems on Hilbert spaces

Given a real(finite-dimensional or infinite-dimensional) Hilbert space H with a Jordan product,we consider the Lorentz cone linear complementarity problem,denoted by LCP(T,Ω,q),where T is a continuous linear operator on H,ΩH is a Lorentz cone,and q ∈ H.We investigate some conditions for which the problem concerned has a unique solution for all q ∈ H(i.e.,T has the GUS-property).Several sufficient conditions and several necessary conditions are given.In particular,we provide two suficient and necessary cond...     

The solution set structure of monotone linear complementarity problems over second-order cone

The second-order cone linear complementarity problem (SOCLCP) is a generalization of the linear complementarity problem (LCP). In this paper we characterize the solution set of a monotone SOCLCP with the help of the Jordan-algebraic technique.     

The modulus-based matrix splitting iteration methods for second-order cone linear complementarity problems

This paper presents a new computational technique for solving fractional pantograph differential equations. The fractional derivative is described in the Caputo sense. The main idea is to use Müntz-Legendre wavelet and its operational matrix of fractional-order integration. First, the Müntz-Legendre wavelet is presented. Then a family of piecewise functions is proposed, based on which the fractional order integration of the Müntz-Legendre wavelets are easy to calculate. The proposed approach is used this operational matrix with the collocation points to reduce the under study problem to a system of algebraic equations. An estimation of the error is given in the sense of Sobolev norms. The efficiency and accuracy of the proposed method are illustrated by several numerical examples.     

Solution analysis for the pseudomonotone second-order cone linear complementarity problem

In this paper, we are concerned with the set of the solutions and the geometric property of the pseudomonotone second-order cone linear complementarity problems (SOCLCP). Based on Tao’s recent work [Tao, J. Optim. Theory Appl., 159, 41–56 (2013)] on pseudomonotone LCP on Euclidean Jordan algebras, we characterize the set of solutions and also derive intrinsic properties that reveal the underlying geometry of the pseudomonotone SOCLCP.     

A matrix-splitting method for symmetric affine second-order cone complementarity problems

The affine second-order cone complementarity problem (SOCCP) is a wide class of problems that contains the linear complementarity problem (LCP) as a special case. The purpose of this paper is to propose an iterative method for the symmetric affine SOCCP that is based on the idea of matrix splitting. Matrix-splitting methods have originally been developed for the solution of the system of linear equations and have subsequently been extended to the LCP and the affine variational inequality problem. In this paper, we first give conditions under which the matrix-splitting method converges to a solution of the affine SOCCP. We then present, as a particular realization of the matrix-splitting method, the block successive overrelaxation (SOR) method for the affine SOCCP involving a positive definite matrix, and propose an efficient method for solving subproblems. Finally, we report some numerical results with the proposed algorithm, where promising results are obtained especially for problems with sparse matrices.     

Tensor complementarity problems: the GUS-property and an algorithm

In this paper, we study the global uniqueness and solvability (GUS-property) of tensor complementarity problems (TCPs) for some special structured tensors. The modulus equation for TCPs is also proposed, and based on this equation, we develop the corresponding nonsmooth Newton’s method, which extends the existing method given in the work of Zheng H and Li W. The modulus-based nonsmooth Newton’s method for solving linear complementarity problems. J Comput Appl Math. 2015;288: 116-126. Numerical examples are given to demonstrate the efficiency of the proposed algorithm.     

A smoothing Newton algorithm for solving the monotone second-order cone complementarity problems

In this paper, a new smoothing function is given by smoothing the symmetric perturbed Fischer-Burmeister function. Based on this function, a smoothing Newton algorithm is proposed for solving the monotone second-order cone complementarity problems. The global and local quadratic convergence results of the algorithm are established under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool which is extensively used in our analysis. Numerical results indicate that the proposed algorithm is effective.     

A proximal gradient descent method for the extended second-order cone linear complementarity problem

We consider an extended second-order cone linear complementarity problem (SOCLCP), including the generalized SOCLCP, the horizontal SOCLCP, the vertical SOCLCP, and the mixed SOCLCP as special cases. In this paper, we present some simple second-order cone constrained and unconstrained reformulation problems, and under mild conditions prove the equivalence between the stationary points of these optimization problems and the solutions of the extended SOCLCP. Particularly, we develop a proximal gradient descent method for solving the second-order cone constrained problems. This method is very simple and at each iteration makes only one Euclidean projection onto second-order cones. We establish global convergence and, under a local Lipschitzian error bound assumption, linear rate of convergence. Numerical comparisons are made with the limited-memory BFGS method for the unconstrained reformulations, which verify the effectiveness of the proposed method.     

Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems

Mathematical Programming - The error bound property for a solution set defined by a set-valued mapping refers to an inequality that bounds the distance between vectors closed to a solution of the...     

Generalized linear complementarity problems

It has been shown by Lemke that if a matrix is copositive plus on ⁿ , then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350.     

A regularization smoothing method for second-order cone complementarity problem

In this paper, the second-order cone complementarity problem is studied. Based on the Fischer–Burmeister function with a perturbed parameter, which is also called smoothing parameter, a regularization smoothing Newton method is presented for solving the sequence of regularized problems of the second-order cone complementarity problem. Under proper conditions, the global convergence and local superlinear convergence of the proposed algorithm are obtained. Moreover, the local superlinear convergence is established without strict complementarity conditions. Preliminary numerical results suggest the effectiveness of the algorithm.     

Smoothing Newton method for nonsmooth second-order cone complementarity problems with application to electric power markets

This paper is dedicated to solving a nonsmooth second-order cone complementarity problem, in which the mapping is assumed to be locally Lipschitz continuous, but not necessarily to be continuously differentiable everywhere. With the help of the vector-valued Fischer-Burmeister function associated with second-order cones, the nonsmooth second-order cone complementarity problem can be equivalently transformed into a system of nonsmooth equations. To deal with this reformulated nonsmooth system, we present an approximation function by smoothing the inner mapping and the outer Fischer-Burmeister function simultaneously. Different from traditional smoothing methods, the smoothing parameter introduced is treated as an independent variable. We give some conditions under which the Jacobian of the smoothing approximation function is guaranteed to be nonsingular. Based on these results, we propose a smoothing Newton method for solving the nonsmooth second-order cone complementarity problem and show that the proposed method achieves globally superlinear or quadratic convergence under suitable assumptions. Finally, we apply the smoothing Newton method to a network Nash-Cournot game in oligopolistic electric power markets and report some numerical results to demonstrate its effectiveness.

     

A new class of complementarity functions for symmetric cone complementarity problems

A popular approach to solving the complementarity problem is to reformulate it as an equivalent equation system via a complementarity function. In this paper, we propose a new class of functions, which contains the penalized natural residual function and the penalized Fischer–Burmeister function for symmetric cone complementarity problems. We show that this class of functions is indeed a class of complementarity functions. We finally prove that the merit function of this new class of complementarity functions is coercive.     

A smoothing Newton method for the second-order cone complementarity problem

In this paper we introduce a new smoothing function and show that it is coercive under suitable assumptions. Based on this new function, we propose a smoothing Newton method for solving the second-order cone complementarity problem (SOCCP). The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that any accumulation point of the iteration sequence generated by the proposed algorithm is a solution to the SOCCP. Furthermore, we prove that the generated sequence is bounded if the solution set of the SOCCP is nonempty and bounded. Under the assumption of nonsingularity, we establish the local quadratic convergence of the algorithm without the strict complementarity condition. Numerical results indicate that the proposed algorithm is promising.     

Cycling in linear complementarity problems

A bound for the minimum length of a cycle in Lemke's Algorithm is derived. An example illustrates that this bound is sharp, and that the fewest number of variables is seven.     

On semidefinite linear complementarity problems

Given a linear transformation L:? ⁿ →? ⁿ and a matrix Q∈? ⁿ , where ? ⁿ is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,? ⁿ ₊,Q) over the cone ? ⁿ ₊ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R ^n×n , we consider the linear transformation L _A :? ⁿ →? ⁿ defined by L _A (X):=AX+XA ^T and show that the P- and Q-properties for L _A are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov. Received: March 1999 / Accepted: November 1999?Published online April 20, 2000     

On cone orderings and the linear complementarity problem

This paper first generalizes a characterization of polyhedral sets having least elements, which is obtained by Cottle and Veinott [6], to the situation in which Euclidean space is partially ordered by some general cone ordering (rather than the usual ordering). We then use this generalization to establish the following characterization of the class $\text{C}$ of matrices ($\text{C}$ arises as a generalization of the class of Z-matrices; see [4], [13], [14]): M∈$\text{C}$ if and only if for every vector q for which the linear complementarity problem (q,M) is feasible, the problem (q,M) has a solution which is the least element of the feasible set of (q,M) with respect to a cone ordering induced by some simplicial cone. This latter result generalizes the characterizations of K-and Z-matrices obtained by Cottle and Veinott [6] and Tamir [21], respectively.     

An unconstrained smooth minimization reformulation of the second-order cone complementarity problem

A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over ℝⁿ. A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over ℝⁿ and, for monotone NCP, each stationary point is a solution of the NCP. This merit function and its analysis were subsequently extended to the semidefinite complementarity problem (SDCP), although only differentiability, not continuous differentiability, was established. In this paper, we extend this merit function and its analysis, including continuous differentiability, to the second-order cone complementarity problem (SOCCP). Although SOCCP is reducible to a SDCP, the reduction does not allow for easy translation of the analysis from SDCP to SOCCP. Instead, our analysis exploits properties of the Jordan product and spectral factorization associated with the second-order cone. We also report preliminary numerical experience with solving DIMACS second-order cone programs using a limited-memory BFGS method to minimize the merit function. In honor of Terry Rockafellar on his 70th birthday     

Two classes of merit functions for the second-order cone complementarity problem

Recently Tseng (Math Program 83:159–185, 1998) extended a class of merit functions, proposed by Luo and Tseng (A new class of merit functions for the nonlinear complementarity problem, in Complementarity and Variational Problems: State of the Art, pp. 204–225, 1997), for the nonlinear complementarity problem (NCP) to the semidefinite complementarity problem (SDCP) and showed several related properties. In this paper, we extend this class of merit functions to the second-order cone complementarity problem (SOCCP) and show analogous properties as in NCP and SDCP cases. In addition, we study another class of merit functions which are based on a slight modification of the aforementioned class of merit functions. Both classes of merit functions provide an error bound for the SOCCP and have bounded level sets.Member of Mathematics Division, National Center for Theoretical Sciences, Taipei Office. The author’s work is partially supported by National Science Council of Taiwan.