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.     

Improved smoothing Newton methods for symmetric cone complementarity problems

There recently has been much interest in smoothing Newton method for solving nonlinear complementarity problems. We extend such method to symmetric cone complementarity problems (SCCP). In this paper, we first investigate a one-parametric class of smoothing functions in the context of symmetric cones, which contains the Fischer–Burmeister smoothing function and the CHKS smoothing function as special cases. Then we propose a smoothing Newton method for the SCCP based on the one-parametric class of smoothing functions. For the proposed method, besides the classical step length, we provide a new step length and the global convergence is obtained. Finally, preliminary numerical results are reported, which show the effectiveness of the two step lengthes in the algorithm and provide efficient domains of the parameter for the complementarity problems.     

Convergence of a non-interior continuation algorithm for the monotone SCCP

It is well known that the symmetric cone complementarity problem（SCCP） is a broad class of optimization problems which contains many optimization problems as special cases.Based on a general smoothing function,we propose in this paper a non-interior continuation algorithm for solving the monotone SCCP.The proposed algorithm solves at most one system of linear equations at each iteration.By using the theory of Euclidean Jordan algebras,we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions.     

Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search

In this paper, we propose a smoothing algorithm for solving the monotone symmetric cone complementarity problems (SCCP for short) with a nonmonotone line search. We show that the nonmonotone algorithm is globally convergent under an assumption that the solution set of the problem concerned is nonempty. Such an assumption is weaker than those given in most existing algorithms for solving optimization problems over symmetric cones. We also prove that the solution obtained by the algorithm is a maximally complementary solution to the monotone SCCP under some assumptions. This work was supported by National Natural Science Foundation of China (Grant Nos. 10571134, 10671010) and Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200)     

Strong convergence properties of a modified nonmonotone smoothing algorithm for the SCCP

The smoothing algorithms have been successfully applied to solve the symmetric cone complementarity problem (denoted by SCCP), which in general have the global and local superlinear/quadratic convergence if the solution set of the SCCP is nonempty and bounded. Huang, Hu and Han [Science in China Series A: Mathematics, 52: 833–848, 2009] presented a nonmonotone smoothing algorithm for solving the SCCP, whose global convergence is established by just requiring that the solution set of the SCCP is nonempty. In this paper, we propose a new nonmonotone smoothing algorithm for solving the SCCP by modifying the version of Huang-Hu-Han’s algorithm. We prove that the modified nonmonotone smoothing algorithm not only is globally convergent but also has local superlinear/quadratical convergence if the solution set of the SCCP is nonempty. This convergence result is stronger than those obtained by most smoothing-type algorithms. Finally, some numerical results are reported.     

A non-interior continuation algorithm for the CP based on a generalized smoothing function

Based on the generalized CP-function proposed by Hu et al. [S.L. Hu, Z.H. Huang, J.S. Chen, Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math. 230 (2009) 69-82], we introduce a smoothing function which is a generalization of several popular smoothing functions. By which we propose a non-interior continuation algorithm for solving the complementarity problem. The proposed algorithm only needs to solve at most one system of linear equations at each iteration. In particular, we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions. The preliminary numerical results demonstrate that the algorithm is effective.     

A smoothing Newton-type method for generalized nonlinear complementarity problem

By using a new type of smoothing function, we first reformulate the generalized nonlinear complementarity problem over a polyhedral cone as a smoothing system of equations, and then develop a smoothing Newton-type method for solving it. For the proposed method, we obtain its global convergence under milder conditions, and we further establish its local superlinear (quadratic) convergence rate under the BD-regular assumption. Preliminary numerical experiments are also reported in this paper.     

A Smoothing Newton Algorithm for a Class of Non-monotonic Symmetric Cone Linear Complementarity Problems

Recently, the study of symmetric cone complementarity problems has been a hot topic in the literature. Many numerical methods have been proposed for solving such a class of problems. Among them, the problems concerned are generally monotonic. In this paper, we consider symmetric cone linear complementarity problems with a class of non-monotonic transformations. A smoothing Newton algorithm is extended to solve this class of non-monotonic symmetric cone linear complementarity problems; and the algorithm is proved to be well-defined. In particular, we show that the algorithm is globally and locally quadratically convergent under mild assumptions. The preliminary numerical results are also reported.     

Log-Sigmoid nonlinear Lagrange method for nonlinear optimization problems over second-order cones

This paper analyzes the rate of local convergence of the Log-Sigmoid nonlinear Lagrange method for nonconvex nonlinear second-order cone programming. Under the componentwise strict complementarity condition, the constraint nondegeneracy condition and the second-order sufficient condition, we show that the sequence of iteration points generated by the proposed method locally converges to a local solution when the penalty parameter is less than a threshold and the error bound of solution is proportional to the penalty parameter. Finally, we report numerical results to show the efficiency of the method.     

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.     

A one-parametric class of merit functions for the symmetric cone complementarity problem

In this paper, we extend the one-parametric class of merit functions proposed by Kanzow and Kleinmichel [C. Kanzow, H. Kleinmichel, A new class of semismooth Newton-type methods for nonlinear complementarity problems, Comput. Optim. Appl. 11 (1998) 227-251] for the nonnegative orthant complementarity problem to the general symmetric cone complementarity problem (SCCP). We show that the class of merit functions is continuously differentiable everywhere and has a globally Lipschitz continuous gradient mapping. From this, we particularly obtain the smoothness of the Fischer-Burmeister merit function associated with symmetric cones and the Lipschitz continuity of its gradient. In addition, we also consider a regularized formulation for the class of merit functions which is actually an extension of one of the NCP function classes studied by [C. Kanzow, Y. Yamashita, M. Fukushima, New NCP functions and their properties, J. Optim. Theory Appl. 97 (1997) 115-135] to the SCCP. By exploiting the Cartesian P-properties for a nonlinear transformation, we show that the class of regularized merit functions provides a global error bound for the solution of the SCCP, and moreover, has bounded level sets under a rather weak condition which can be satisfied by the monotone SCCP with a strictly feasible point or the SCCP with the joint Cartesian R₀₂-property. All of these results generalize some recent important works in [J.-S. Chen, P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104 (2005) 293-327; C.-K. Sim, J. Sun, D. Ralph, A note on the Lipschitz continuity of the gradient of the squared norm of the matrix-valued Fischer-Burmeister function, Math. Program. 107 (2006) 547-553; P. Tseng, Merit function for semidefinite complementarity problems, Math. Program. 83 (1998) 159-185] under a unified framework.     

Finite termination of a Newton-type algorithm for a class of affine variational inequality problems

Many optimization problems can be reformulated as a system of equations. One may use the generalized Newton method or the smoothing Newton method to solve the reformulated equations so that a solution of the original problem can be found. Such methods have been powerful tools to solve many optimization problems in the literature. In this paper, we propose a Newton-type algorithm for solving a class of monotone affine variational inequality problems (AVIPs for short). In the proposed algorithm, the techniques based on both the generalized Newton method and the smoothing Newton method are used. In particular, we show that the algorithm can find an exact solution of the AVIP in a finite number of iterations under an assumption that the solution set of the AVIP is nonempty. Preliminary numerical results are reported.     

A generalized Newton method for absolute value equations associated with second order cones

In this paper, we introduce the absolute value equations associated with second order cones (SOCAVE in short), which is a generalization of the absolute value equations discussed recently in the literature. It is proved that the SOCAVE is equivalent to a class of second order cone linear complementarity problems (SOCLCP in short). In particular, we propose a generalized Newton method for solving the SOCAVE and show that the proposed method is globally linearly and locally quadratically convergent under suitable assumptions. We also report some preliminary numerical results of the proposed method for solving the SOCAVE and the SOCLCP, which show the efficiency of the proposed method.     

线性二阶锥互补问题的一种非精确光滑算法

在光滑算法的框架下,就线性二阶锥互补问题,给出了一种非精确光滑算法. 在适当的条件下,证明了该算法具有全局收敛性. 数值试验表明该算法对高维线性二阶锥互补问题是有效的.     

Smoothing algorithms for complementarity problems over symmetric cones

There recently has been much interest in studying optimization problems over symmetric cones. In this paper, we first investigate a smoothing function in the context of symmetric cones and show that it is coercive under suitable assumptions. We then extend two generic frameworks of smoothing algorithms to solve the complementarity problems over symmetric cones, and prove the proposed algorithms are globally convergent under suitable assumptions. We also give a specific smoothing Newton algorithm which is globally and locally quadratically convergent under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool which is extensively used in our analysis. Preliminary numerical results for second-order cone complementarity problems are reported.     

A non-interior continuation method for second-order cone programming

We extend the smoothing function proposed by Huang, Han and Chen [Journal of Optimization Theory and Applications, 117 (2003), pp. 39–68] for the non-linear complementarity problems to the second-order cone programming (SOCP). Based on this smoothing function, a non-interior continuation method is presented for solving the SOCP. The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that our algorithm is globally and locally superlinearly convergent in absence of strict complementarity at the optimal solution. Numerical results indicate the effectiveness of the algorithm.     

对称锥互补问题

对称锥互补问题是一类均衡优化,包括标准互补问题、二阶锥互补问题和半定互补问题等,近几年,人们借助欧几里德若当代数技术,在对称锥互补问题的研究方面获得了突破性进展并使之逐渐受到重视,本文主要从理论和算法两方面总结和评述这些新成果,同时,列出了相应的重要文献。     

Smoothing Newton algorithm for symmetric cone complementarity problems based on a one-parametric class of smoothing functions

In this paper, we introduce a one-parametric class of smoothing functions in the context of symmetric cones which contains two symmetric perturbed smoothing functions as special cases, and show that it is coercive under suitable assumptions. Based on this class of smoothing functions, a smoothing Newton algorithm is extended to solve the complementarity problems over symmetric cones, and it is proved that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool which is extensively used in our analysis. Preliminary numerical results for randomly generated second-order cone programs and several practical second-order cone programs from the DIMACS library are reported.     

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.     

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.