Abstract Recently, J.-S. Chen and P. Tseng extended two merit functions for the nonlinear complementarity problem (NCP) and the semidefinite complementarity problem (SDCP) to the second-order cone commplementarity problem (SOCCP) and showed several favorable properties. In this paper, we extend a merit function for the NCP studied by Yamada, Yamashita, and Fukushima to the SOCCP and show that the SOCCP is equivalent to an unconstrained smooth minimization via this new merit function. Furthermore, we study conditions under which the new merit function provides a global error bound which plays an important role in analyzing the convergence rate of iterative methods for solving the SOCCP; and conditions under which the new merit function has bounded level sets which ensures that the sequence generated by a descent method has at least one accumulation point.

No abstract uploaded!

No abstract uploaded!

The trust-region problem,which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite linear programming problem and so, their solutions can be validated in polynomial time.

In this paper, we consider a family of neural networks for solving nonlinear complementarity problems (NCP). The neural networks are constructed from the merit functions based on three classes of NCP-functions: the generalized natural residual function and its two symmetrizations. In this paper, we first characterize the stationary points of the induced merit functions. Growth behavior of the complementarity functions is also described, as this will play an important role in describing the level sets of the merit functions. In addition, the stability of the steepest descent-based neural network model for NCP is analyzed. We provide numerical simulations to illustrate the theoretical results, and also compare the proposed neural networks with existing neural networks based on other well-known NCP-functions. Numerical results indicate that the performance of the neural network is better when the parameter <i>p</i> associated