Solution Sets of Quadratic Complementarity Problems

In this paper, we study quadratic complementarity problems, which form a subclass of nonlinear complementarity problems with the nonlinear functions being quadratic polynomial mappings. Quadratic complementarity problems serve as an important bridge linking linear complementarity problems and nonlinear complementarity problems. Various properties on the solution set for a quadratic complementarity problem, including existence, compactness and uniqueness, are studied. Several results are established from assumptions given in terms of the comprising matrices of the underlying tensor, henceforth easily checkable. Examples are given to demonstrate that the results improve or generalize the corresponding quadratic complementarity problem counterparts of the well-known nonlinear complementarity problem theory and broaden the boundary knowledge of nonlinear complementarity problems as well.     

A PENALTY TECHNIQUE FOR NONLINEAR COMPLEMENTARITY PROBLEMS

1.IntroductionConsiderthefollowingnonlinearcomplementarityproblemsNCP(F)offindinganxER",suchthatwhereFisamappingfromR"intoitself.ItisanimportantformofthefollowingvariationalinequalityVI(F,X)offindinganxEX,suchthatwhereXCReisaclosedconvexset.WhenX=R7,(1.1)…     

二次有限体积法定价美式期权

本文考虑二次有限体积法定价美式期权.构造了隐式欧拉和Crank-Nicolson两种全离散二次有限体积格式,并得到相应的线性互补问题.采用基于超松弛迭代的模方法求解线性互补问题,并与投影超松弛迭代法作数值比较.数值实验结果表明Crank-Nicolson二次有限体积格式的求解效率高于隐式欧拉格式,模方法的求解速度较快,二次有限体积法的求解精度较高.     

A path-following interior-point algorithm for linear and quadratic problems

We describe an algorithm for the monotone linear complementarity problem (LCP) that converges from any positive, not necessarily feasible, starting point and exhibits polynomial complexity if some additional assumptions are made on the starting point. If the problem has a strictly complementarity solution, the method converges subquadratically. We show that the algorithm and its convergence properties extend readily to the mixed monotone linear complementarity problem and, hence, to all the usual formulations of the linear programming and convex quadratic programming problems.This research was supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Some non-interior path-following methods based on a scaled central path for linear complementarity problems

In this paper we present some non-interior path-following methods for linear complementarity problems. Instead of using the standard central path we use a scaled central path. Based on this new central path, we first give a feasible non-interior path-following method for linear complementarity problems. And then we extend it to an infeasible method. After proving the boundedness of the neighborhood, we prove the convergence of our method. Another point we should present is that we prove the local quadratic convergence of feasible method without the assumption of strict complementarity at the solution.     

求解互补问题的一种序列二次规划方法

通过将互补问题转化为一种带非负约束的极小化问题 ,给出了求解互补问题的一种序列二次规划方法 .该方法中每一个子问题都是可解的 ,迭代产生的序列是非负的 ,在适当的条件下 ,分别证明了算法的全局收敛性、局部超线收敛性以及局部二次收敛性 .     

On active-set methods for the quadratic programming problem

The active-set Newton method developed earlier by the authors for mixed complementarity problems is applied to solving the quadratic programming problem with a positive definite matrix of the objective function. A theoretical justification is given to the fact that the method is guaranteed to find the exact solution in a finite number of steps. Numerical results indicate that this approach is competitive with other available methods for quadratic programming problems.     

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.     

New Sequential Quadratically-Constrained Quadratic Programming Method of Feasible Directions and Its Convergence Rate

This paper discusses optimization problems with nonlinear inequality constraints and presents a new sequential quadratically-constrained quadratic programming (NSQCQP) method of feasible directions for solving such problems. At each iteration. the NSQCQP method solves only one subproblem which consists of a convex quadratic objective function, convex quadratic equality constraints, as well as a perturbation variable and yields a feasible direction of descent (improved direction). The following results on the NSQCQP are obtained: the subproblem solved at each iteration is feasible and solvable: the NSQCQP is globally convergent under the Mangasarian-Fromovitz constraint qualification (MFCQ); the improved direction can avoid the Maratos effect without the assumption of strict complementarity; the NSQCQP is superlinearly and quasiquadratically convergent under some weak assumptions without thestrict complementarity assumption and the linear independence constraint qualification (LICQ). Research supported by the National Natural Science Foundation of China Project 10261001 and Guangxi Science Foundation Projects 0236001 and 0249003. The author thanks two anonymous referees for valuable comments and suggestions on the original version of this paper.     

A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints

This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported.     

Globally and Quadratically Convergent Algorithm for Minimizing the Sum of Euclidean Norms

For the problem of minimizing the sum of Euclidean norms (MSN), most existing quadratically convergent algorithms require a strict complementarity assumption. However, this assumption is not satisfied for a number of MSN problems. In this paper, we present a globally and quadratically convergent algorithm for the MSN problem. In particular, the quadratic convergence result is obtained without assuming strict complementarity. Examples without strictly complementary solutions are given to show that our algorithm can indeed achieve quadratic convergence. Preliminary numerical results are reported.     

Error Bounds for the Solution Sets of Quadratic Complementarity Problems

In this article, two types of fractional local error bounds for quadratic complementarity problems are established, one is based on the natural residual function and the other on the standard violation measure of the polynomial equalities and inequalities. These fractional local error bounds are given with explicit exponents. A fractional local error bound with an explicit exponent via the natural residual function is new in the tensor/polynomial complementarity problems literature. The other fractional local error bounds take into account the sparsity structures, from both the algebraic and the geometric perspectives, of the third-order tensor in a quadratic complementarity problem. They also have explicit exponents, which improve the literature significantly.     

A predictor-corrector smoothing Newton method for symmetric cone complementarity problems

In this paper, we present a predictor-corrector smoothing Newton method for solving nonlinear symmetric cone complementarity problems (SCCP) based on the symmetrically perturbed smoothing function. Under a mild assumption, the solution set of the problem concerned is just nonempty, we show that the proposed algorithm is globally and locally quadratic convergent. Also, the algorithm finds a maximally complementary solution to the SCCP. Numerical results for second order cone complementarity problems (SOCCP), a special case of SCCP, show that the proposed algorithm is effective.     

Stabilized Sequential Quadratic Programming

Recently, Wright proposed a stabilized sequential quadratic programming algorithm for inequality constrained optimization. Assuming the Mangasarian-Fromovitz constraint qualification and the existence of a strictly positive multiplier (but possibly dependent constraint gradients), he proved a local quadratic convergence result. In this paper, we establish quadratic convergence in cases where both strict complementarity and the Mangasarian-Fromovitz constraint qualification do not hold. The constraints on the stabilization parameter are relaxed, and linear convergence is demonstrated when the parameter is kept fixed. We show that the analysis of this method can be carried out using recent results for the stability of variational problems.     

非线性互补问题近似Newton法的二阶收敛性

本文给出了求解非线性互补问题近似Newton法二阶收敛性的一个条件，并且证明了在一定的条件下，有限差分Newton法具有二阶收敛性．     

Nonsingularity of FB system and constraint nondegeneracy in semidefinite programming

For a KKT point of the linear semidefinite programming (SDP), we show that the nonsingularity of the B-subdifferential of Fischer-Burmeister (FB) nonsmooth system, the nonsingularity of Clarke’s Jacobian of this system, and the primal and dual constraint nondegeneracies, are all equivalent. Also, each of these conditions is equivalent to the nonsingularity of Clarke’s Jacobian of the smoothed counterpart of FB nonsmooth system, which particularly implies that the FB smoothing Newton method may attain the local quadratic convergence without strict complementarity assumption. We also report numerical results of the FB smoothing method for some benchmark problems.     

Nonlinear complementarity as unconstrained optimization

Several methods for solving the nonlinear complementarity problem (NCP) are developed. These methods are generalizations of the recently proposed algorithms of Mangasarian and Solodov (Ref. 1) and are based on an unconstrianed minimization formulation of the nonlinear complementarity problem. It is shown that, under certain assumptions, any stationary point of the unconstrained objective function is already a solution of NCP. In particulr, these assumptions are satisfied by the mangasarian and Soolodov implicit Lagranian functioin. Furthermore, a special Newton-type method is suggested, and conditions for its local quadratic convergence are given. Finally, some preliminary numerical results are presented.The author would like to thank Dr. Oswald Knoth (Leipzig) for pointing out that the equivalence of Lemma 2.2. is not true for complementarity problems which have no solutions. He is also grateful to the anonymous referencees for their helpful comments.     

A semismooth equation approach to the solution of nonlinear complementarity problems

In this paper we present a new algorithm for the solution of nonlinear complementarity problems. The algorithm is based on a semismooth equation reformulation of the complementarity problem. We exploit the recent extension of Newton's method to semismooth systems of equations and the fact that the natural merit function associated to the equation reformulation is continuously differentiable to develop an algorithm whose global and quadratic convergence properties can be established under very mild assumptions. Other interesting features of the new algorithm are an extreme simplicity along with a low computational burden per iteration. We include numerical tests which show the viability of the approach.     

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.