A smoothing least square method for nonlinear complementarity problem

By using the smoothing functions and the least square reformulation, in this paper, we present a smoothing least square method for the nonlinear complementarity problem. The method can overcome the difficulty of the non‐smooth method and a major drawback of some existed equation‐based methods. Under the standard assumptions, we obtain the global convergence of the proposed method. Copyright © 2013 John Wiley & Sons, Ltd.     

Predictor-corrector method for nonlinear complementarity problem

Recently, Ye et al. proved that the predictor-corrector method proposed by Mizuno et al. maintains -iteration complexity while exhibiting the quadratic convergence of the dual gap to zero under very mild conditions. This impressive result becomes the best-known in the interior point methods. In this paper, we modify the predictor-corrector method and then extend it to solving the nonlinear complementarity problem. We prove that the new method has a -iteration complexity while maintaining the quadratic asymptotic convergence.     

On the Karush-Kuhn-Tucker reformulation of the bilevel optimization problem

This paper is mainly concerned with the classical KKT reformulation and the primal KKT reformulation (also known as an optimization problem with generalized equation constraint (OPEC)) of the optimistic bilevel optimization problem. A generalization of the MFCQ to an optimization problem with operator constraint is applied to each of these reformulations, hence leading to new constraint qualifications (CQs) for the bilevel optimization problem. M- and S-type stationarity conditions tailored for the problem are derived as well. Considering the close link between the aforementioned reformulations, similarities and relationships between the corresponding CQs and optimality conditions are highlighted. In this paper, a concept of partial calmness known for the optimal value reformulation is also introduced for the primal KKT reformulation and used to recover the M-stationarity conditions.     

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 modified SQP-filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. Moreover, filter method, for its good numerical results, are extensively studied to handle nonlinear programming problems recently. In this paper, a modified quadratic subproblem is proposed. Based on it, we employ filter technique to tackle nonlinear complementarity problem. This method has no demand on initial point. The restoration phase, which is always used in traditional filter method, is not needed. Global convergence results of the proposed algorithm are established under suitable conditions. Some numerical results are reported in this paper.     

A new exact discrete linear reformulation of the quadratic assignment problem

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.     

Superlinear/quadratic smoothing Broyden-like method for the generalized nonlinear complementarity problem

In this article, we first reformulate the generalized nonlinear complementarity problem (GNCP) over a polyhedral cone as a smoothing system of equations and then suggest a smoothing Broyden-like method for solving it. The proposed algorithm has to solve only one system of nonhomogeneous linear equations, perform only one line search and update only one matrix per iteration. We show that the iteration sequence generated by the proposed algorithm converges globally and superlinearly under suitable conditions. Furthermore, the algorithm has local quadratic convergence under mild assumptions. Some numerical examples are given to illustrate the performance and efficiency of the presented algorithm.     

非线性互补问题的SQP方法

In this paper, the nonlinear complementarity problem is transformed into the least squares problem with nonnegative constraints ,and a SQP algorithm for this reformulation based on a damped Gauss-Newton type method is presented. It is shown that the algorithm is globally and locally superlinearly (quadratically) convergent without the assumption of monotonicity.     

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.     

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.     

一种求解非线性互补问题的filter内点算法

利用Armijio条件和信赖域方法,构造新的价值函数.首次将内点算法与filter技术结合起来,提出一种求解非线性互补问题的新算法,即filter内点算法.在主算法中使用Armijio型线搜索求取步长,在修复算法中使用信赖域方法进行适当控制以保证算法的收敛性.文章还讨论了算法的全局收敛性.最后用数值实验表明了该方法是有效的.     

求解张量随机互补问题的光滑牛顿算法

近年来, 越来越多的人意识到随机互补问题在经济管理中具有十分重要的作用。有学者已将随机互补问题由矩阵推广到张量, 并提出了张量随机互补问题。本文通过引入一类光滑函数, 提出了求解张量随机互补问题的一种光滑牛顿算法, 并证明了算法的全局和局部收敛性, 最后通过数值实验验证了算法的有效性。     

求解张量随机互补问题的光滑牛顿算法

近年来, 越来越多的人意识到随机互补问题在经济管理中具有十分重要的作用。有学者已将随机互补问题由矩阵推广到张量, 并提出了张量随机互补问题。本文通过引入一类光滑函数, 提出了求解张量随机互补问题的一种光滑牛顿算法, 并证明了算法的全局和局部收敛性, 最后通过数值实验验证了算法的有效性。     

INEXACT DAMPED NEWTON METHOD FOR NONLINEAR COMPLEMENTARITY PROBLEMS

In this paper, we propose an inexact clamped Newton method for solving nonlinear complementarity problems based on the equivalent B-differentiable equations.Global convergence and locally quadratic convergence are obtained,and numerical results are given.     

Additive Schwarz algorithm for the nonlinear complementarity problem with M-function

In this paper, an additive Schwarz algorithm is considered for solving the finite-dimensional nonlinear complementarity problem with M-function. The monotone convergence of the algorithm is obtained with special choices of initial values. Moreover, the weighted max-norm bound is obtained for the iterative errors.     

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     

A penalty method for a mixed nonlinear complementarity problem

We propose a power penalty method for a mixed nonlinear complementarity problem (MNCP) and show that the solution to the penalty equation converges to that of the MNCP exponentially as the penalty parameter approaches infinity, provided that the mapping involved in the MNCP is both continuous and ξ-monotone. Furthermore, a convergence theorem is established when the monotonicity assumption on the mapping is removed. To demonstrate the usefulness and the convergence rates of this method, we design a non-trivial test MNCP problem arising in shape-preserving bi-harmonic interpolation and apply our method to this test problem. The numerical results confirm our theoretical findings.