Conditions for Error Bounds of Linear Complementarity Problems over Second-Order Cones with Pseudomonotonicity

We first discuss some properties of the solution set of a pseudomonotone second-order cone linear complementarity problem (SOCLCP), and then analyse the limiting behavior of a sequence of strictly feasible solutions within a new wide neighborhood of the central trajectory for the pseudomonotone SOCLCP under assumptions of strict complementarity. Based on this, we derive four different characterizations of an error bound for the pseudomonotone SOCLCP.     

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.     

二阶锥线性互补问题的低阶罚函数算法

本文研究了二阶锥线性互补问题的低阶罚函数算法.利用低阶罚函数算法将二阶锥线性互补问题转化为低阶罚函数方程组,获得了低阶罚函数方程组的解序列在特定条件下以指数速度收敛于二阶锥线性互补问题解的结果,推广了二阶锥线性互补问题的幂罚函数算法.数值实验结果验证了算法的有效性.     

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.     

Analysis of a smoothing Newton method for second-order cone complementarity problem

In this paper, we consider the second-order cone complementarity problem with P ₀-property. By introducing a smoothing parameter into the Fischer-Burmeister function, we present a smoothing Newton method for the second-order cone complementarity problem. The proposed algorithm solves only a linear system of equations and performs only one line search at each iteration. At the same time, the algorithm does not have restrictions on its starting point and has global convergence. Under the assumption of nonsingularity, we establish the locally quadratic convergence of the algorithm without strict complementarity condition. Preliminary numerical results show that the algorithm is promising.     

Exceptional family and solvability of copositive complementarity problems

In this paper, by extending the concept of exceptional family to complementarity problems over the cone of symmetric copositive real matrices, we propose an existence theorem of a solution to the copositive complementarity problem. Extensions of Isac–Carbone?s condition, Karamardian?s condition, weakly properness and coercivity are also introduced. Several applications of these results are presented, and we prove that without exceptional family is a sufficient and necessary condition for the solvability of pseudomonotone copositive complementarity problems.     

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.     

Complementarity problems over cones with monotone and pseudomonotone maps

The notion of a monotone map is generalized to that of a pseudomonotone map. It is shown that a differentiable, pseudoconvex function is characterized by the pseudomonotonicity of its gradient. Several existence theorems are established for a given complementarity problem over a certain cone where the underlying map is either monotone or pseudomonotone under the assumption that the complementarity problem has a feasible or strictly feasible point.This work was supported in part by the National Science Foundation, Grant No. GP-34619.     

The convergence of a modified smoothing-type algorithm for the symmetric cone complementarity problem

The symmetric cone complementarity problem (denoted by SCCP) is a broad class of optimization problems, which contains the semidefinite complementarity problem, the second-order cone complementarity problem, and the nonlinear complementarity problem. In this paper we first extend the smoothing function proposed by Huang et al. (Sci. China 44:1107–1114, 2001) for the nonlinear complementarity problem to the context of symmetric cones and show that it is coercive under suitable assumptions. Based on this smoothing function, a smoothing-type algorithm, which is a modified version of the Qi-Sun-Zhou method (Qi et al. in Math. Program. 87:1–35, 2000), is proposed for solving the SCCP. By using the theory of Euclidean Jordan algebras, we prove that the proposed algorithm is globally and locally quadratically convergent under suitable assumptions. Preliminary numerical results for some second-order cone complementarity problems are reported which indicate that the proposed algorithm is effective.     

A descent method for a reformulation of the second-order cone complementarity problem

Analogous to the nonlinear complementarity problem and the semi-definite complementarity problem, a popular approach to solving the second-order cone complementarity problem (SOCCP) is to reformulate it as an unconstrained minimization of a certain merit function over Rⁿ${\mathbb{R}}^n$. In this paper, we present a descent method for solving the unconstrained minimization reformulation of the SOCCP which is based on the Fischer–Burmeister merit function (FBMF) associated with second-order cone [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Programming 104 (2005) 293–327], and prove its global convergence. Particularly, we compare the numerical performance of the method for the symmetric affine SOCCP generated randomly with the FBMF approach [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Programming 104 (2005) 293–327]. The comparison results indicate that, if a scaling strategy is imposed on the test problem, the descent method proposed is comparable with the merit function approach in the CPU time for solving test problems although the former may require more function evaluations.     

求解一类逆鲁棒优化问题的牛顿型扰动方法

逆优化问题是指通过调整目标函数和约束中的某些参数使得已知的一个解成为参数调整后的优化问题的最优解.本文考虑求解一类逆鲁棒优化问题.首先,我们将该问题转化为带有一个线性等式约束,一个二阶锥互补约束和一个线性互补约束的极小化问题;其次,通过一类扰动方法来对转化后的极小化问题进行求解,然后利用带Armijo线搜索的非精确牛顿法求解每一个扰动问题.最后,通过数值实验验证该方法行之有效.     

二阶锥线性互补问题的广义模系矩阵分裂迭代算法

通过将二阶锥线性互补问题转化为等价的不动点方程,介绍了一种广义模系矩阵分裂迭代算法,并研究了该算法的收敛性.进一步,数值结果表明广义模系矩阵分裂迭代算法能够有效地求解二阶锥线性互补问题.     

Expected Value and Sample Average Approximation Method for Solving Stochastic Second-Order Cone Complementarity Problems

In this paper, we consider the stochastic second-order cone complementarity problems (SSOCCP). We first formulate the SSOCCP contained expectation as an optimization problem using the so-called second-order cone complementarity function. We then use sample average approximation method and smoothing technique to obtain the approximation problems for solving this reformulation. In theory, we show that any accumulation point of the global optimal solutions or stationary points of the approximation problems are global optimal solution or stationary point of the original problem under suitable conditions. Finally, some numerical examples are given to explain that the proposed methods are feasible.     

On the Coderivative of the Projection Operator onto the Second-order Cone

The limiting (Mordukhovich) coderivative of the metric projection onto the second-order cone $\mathbb{R}^{n}$ is computed. This result is used to obtain a sufficient condition for the Aubin property of the solution map of a parameterized second-order cone complementarity problem and to derive necessary optimality conditions for a mathematical program with a second-order cone complementarity problem among the constraints.     

Linear Complementarity Problems over Symmetric Cones: Characterization of Q b -transformations and Existence Results

This paper is devoted to the study of the symmetric cone linear complementarity problem (SCLCP). Specifically, our aim is to characterize the class of linear transformations for which the SCLCP has always a nonempty and bounded solution set in terms of larger classes. For this, we introduce a couple of new classes of linear transformations in this SCLCP context. Then, we study them for concrete particular instances (such as second-order and semidefinite linear complementarity problems) and for specific examples (Lyapunov, Stein functions, among others). This naturally permits to establish coercive and noncoercive existence results for SCLCPs.     

A nonmonotone smoothing Newton method for circular cone programming

The circular cone programming (CCP) problem is to minimize or maximize a linear function over the intersection of an affine space with the Cartesian product of circular cones. In this paper, we study nondegeneracy and strict complementarity for the CCP, and present a nonmonotone smoothing Newton method for solving the CCP. We reformulate the CCP as a second-order cone programming (SOCP) problem using the algebraic relation between the circular cone and the second-order cone. Then based on a one parametric class of smoothing functions for the SOCP, a smoothing Newton method is developed for the CCP by adopting a new nonmonotone line search scheme. Without restrictions regarding its starting point, our algorithm solves one linear system of equations approximately and performs one line search at each iteration. Under mild assumptions, our algorithm is shown to possess global and local quadratic convergence properties. Some preliminary numerical results illustrate that our nonmonotone smoothing Newton method is promising for solving the CCP.     

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 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.     

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     

一类广义隐互补问题的外梯度法

隐互补问题在自然科学中的诸多领域有着广泛的应用.本文研究了一类广义隐互补问题.本文将外梯度法应用到这类广义隐互补问题中,研究了在伪单调的条件下算法的收敛性,并证明了算法具有R-线性收敛性.