We consider a class of derivative-free descent methods for solving the second-order cone complementarity problem (SOCCP). The algorithm is based on the FischerBurmeister (FB) unconstrained minimization reformulation of the SOCCP, and utilizes a convex combination of the negative partial gradients of the FB merit function <sub>FB</sub> as the search direction. We establish the global convergence results of the algorithm under monotonicity and the uniform Jordan <i>P</i>-property, and show that under strong monotonicity the merit function value sequence generated converges at a linear rate to zero. Particularly, the rate of convergence is dependent on the structure of second-order cones. Numerical comparisons are also made with the limited BFGS method used by Chen and Tseng (<i>An unconstrained smooth minimization reformulation of the second-order cone complementarity problem</i>, Math. Program. 104(2005), pp
In this paper, we consider a bilevel polynomial optimization problem where the objective and the constraint functions of both the upper-and the lower-level problems are polynomials. We present methods for finding its global minimizers and global minimum using a sequence of semidefinite programming (SDP) relaxations and provide convergence results for the methods. Our scheme for problems with a convex lower-level problem involves solving a transformed equivalent single-level problem by a sequence of SDP relaxations, whereas our approach for general problems involving a nonconvex polynomial lower-level problem solves a sequence of approximation problems via another sequence of SDP relaxations.
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) 227251] 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 FischerBurmeister 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
Yuhao ZhouDepartment of Computer Science and Technology, Tsinghua University, ChinaChenglong BaoYau Mathematical Sciences Center, Tsinghua University, China and Yanqi Lake Beijing Institute of Mathematical Sciences and Applications, ChinaChao DingInstitute of Applied Mathematics, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, ChinaJun ZhuDepartment of Computer Science and Technology, Tsinghua University, China
This paper is devoted to studying an augmented Lagrangian method for solving a class of manifold optimization problems, which have nonsmooth objective functions and non-negative constraints. Under the constant positive linear dependence condition on manifolds, we show that the proposed method converges to a stationary point of the nonsmooth manifold optimization problem. Moreover, we propose a globalized semismooth Newton method to solve the augmented Lagrangian subproblem on manifolds efficiently. The local superlinear convergence of the manifold semismooth Newton method is also established under some suitable conditions. We also prove that the semismoothness on submanifolds can be inherited from that in the ambient manifold. Finally, numerical experiments on compressed modes and (constrained) sparse principal component analysis illustrate the advantages of the proposed method.
We consider the Tikhonov regularization method for the second-order cone complementarity problem (SOCCP) with the Cartesian P 0-property. We show that many results of the regularization method for the P 0-nonlinear complementarity problem still hold for this important class of nonmonotone SOCCP. For example, under the more general setting, every regularized problem has the unique solution, and the solution trajectory generated is bounded if the original SOCCP has a nonempty and bounded solution set. We also propose an inexact regularization algorithm by solving the sequence of regularized problems approximately with the merit function approach based on FischerBurmeister merit function, and establish the convergence result of the algorithm. Preliminary numerical results are also reported, which verify the favorable theoretical properties of the proposed method.