In this paper, we consider complementarity problem associated with circular cone, which is a type of nonsymmetric cone complementarity problem. The main purpose of this paper is to show the readers how to construct complementarity functions for such nonsymmetric cone complementarity problem, and propose a few merit functions for solving such a complementarity problem. In addition, we study the conditions under which the level sets of the corresponding merit functions are bounded, and we also show that these merit functions provide an error bound for the circular cone complementarity problem. These results ensure that the sequence generated by descent methods has at least one accumulation point, and build up a theoretical basis for designing the merit function method for solving circular cone complementarity problem.
In contrast to the generalized FischerBurmeister function that is a natural extension of the popular FischerBurmeister function NCP-function, the generalized natural residual NCP-function based on discrete extension, recently proposed by Chen, Ko, and Wu, does not possess symmetric graph. In this paper we symmetrize the generalized natural residual NCP-function, and construct not only new NCP-functions and merit functions for the nonlinear complementarity problem, but also provide parallel functions to the generalized FischerBurmeister function.
We present an alternating direction dual augmented Lagrangian method for solving semidefinite programming (SDP) problems in standard form. At each iteration, our basic algorithm minimizes the augmented Lagrangian function for the dual SDP problem sequentially, first with respect to the dual variables corresponding to the linear constraints, and then with respect to the dual slack variables, while in each minimization keeping the other variables fixed, and then finally it updates the Lagrange multipliers (i.e., primal variables). Convergence is proved by using a fixed-point argument. For SDPs with inequality constraints and positivity constraints, our algorithm is extended to separately minimize the dual augmented Lagrangian function over four sets of variables. Numerical results for frequency assignment, maximum stable set and binary integer quadratic programming problems demonstrate that our
In the paper [J.-S. Chen, S. Pan, A family of NCP-functions and a descent method for the nonlinear complementarity problem, Computational Optimization and Applications, 40 (2008) 389404], the authors proposed a derivative-free descent algorithm for nonlinear complementarity problems (NCPs) by the generalized FischerBurmeister merit function: p (a, b)= 1 2 [(a, b) p(a+ b)] 2, and observed that the choice of the parameter p has a great influence on the numerical performance of the algorithm. In this paper, we analyze the phenomenon theoretically for a derivative-free descent algorithm which is based on a penalized form of p and uses a different direction from that of Chen and Pan. More specifically, we show that the algorithm proposed is globally convergent and has a locally R-linear convergence rate, and furthermore, its convergence rate will become worse when the parameter p decreases
For the symmetric cone complementarity problem, we show that each stationary point of the unconstrained minimization reformulation based on the FischerBurmeister merit function is a solution to the problem, provided that the gradient operators of the mappings involved in the problem satisfy column monotonicity or have the Cartesian P 0-property. These results answer the open question proposed in the article that appeared in Journal of Mathematical Analysis and Applications 355 (2009) 195215.
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
This paper is devoted to the study of the proximal point algorithm for solving monotone and nonmonotone nonlinear complementarity problems. The proximal point algorithm is to generate a sequence by solving subproblems that are regularizations of the original problem. After given an appropriate criterion for approximate solutions of subproblems by adopting a merit function, the proximal point algorithm is verified to have global and superlinear convergence properties. For the purpose of solving the subproblems efficiently, we introduce a generalized Newton method and show that only one Newton step is eventually needed to obtain a desired approximate solution that approximately satisfies the appropriate criterion under mild conditions. The motivations of this paper are twofold. One is analyzing the proximal point algorithm based on the generalized Fischer-Burmeister function which includes the Fischer-Burmeister function as special case, another one is trying to see if there are relativistic change on numerical performance when we adjust the parameter in the generalized Fischer-Burmeister.