Finite termination of a Newton-type algorithm for a class of affine variational inequality problems

Many optimization problems can be reformulated as a system of equations. One may use the generalized Newton method or the smoothing Newton method to solve the reformulated equations so that a solution of the original problem can be found. Such methods have been powerful tools to solve many optimization problems in the literature. In this paper, we propose a Newton-type algorithm for solving a class of monotone affine variational inequality problems (AVIPs for short). In the proposed algorithm, the techniques based on both the generalized Newton method and the smoothing Newton method are used. In particular, we show that the algorithm can find an exact solution of the AVIP in a finite number of iterations under an assumption that the solution set of the AVIP is nonempty. Preliminary numerical results are reported.     

Strong convergence theorem by a new hybrid method for equilibrium problems and variational inequality problems

In this paper, we prove a strong convergence theorem for finding a common element of the set of solutions of an equilibrium problem and the set of the solutions of the variational inequality problem by using a new hybrid method. We obtain a new result for finding a solution of an equilibrium problem and the solutions of the variational inequality problem.     

Newton's method for a class of nonsmooth functions

This paper presents and justifies a Newton iterative process for finding zeros of functions admitting a certain type of approximation. This class includes smooth functions as well as nonsmooth reformulations of variational inequalities. We prove for this method an analogue of the fundamental local convergence theorem of Kantorovich including optimal error bounds.The research reported here was sponsored by the National Science Foundation under Grants CCR-8801489 and CCR-9109345, by the Air Force Systems Command, USAF, under Grants AFOSR-88-0090 and F49620-93-1-0068, by the U. S. Army Research Office under Grant No. DAAL03-92-G-0408, and by the U. S. Army Space and Strategic Defense Command under Contract No. DASG60-91-C-0144. The U. S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

Mathematical foundations of nonsmooth embedding methods

This paper establishes a mathematical foundation for application of the well known classical embedding approach to a class of nonsmooth functions, using a recently developed analogue of the derivative in cases where the functions involved fail to be differentiable in the usual sense. As part of this development we show how to obtain an extension to this case of the classical Hadamard theorem giving conditions for a map of ⁿ to itself to be a homeomorphism.The research reported here was sponsored by the National Science Foundation under Grant CCR-8801489, and by the Air Force Systems Command, USAF, under Grants AFOSR-88-0090 and AFOSR-89-0058. The US Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

Regularized gap functions for nonsmooth variational inequality problems

Under the condition that the involved function F is locally Lipschitz, but not necessarily differentiable, we investigate the regularized gap function defined by a generalized distance function for the variational inequality problem (VIP). First, we compute exactly the Clarke-Rockafellar directional derivatives of the regularized gap functions (and of some modified ones). Second, using these results, we show that, under the strongly monotonicity assumption, the regularized gap functions have fractional exponent error bounds, and thereby we provide an algorithm of Armijo type to solve the VIP.     

Existence of solutions for generalized variational inequality problems in Banach spaces

In this paper, we prove the existence of solutions of generalized variational inequality for upper semicontinuous multivalued mappings with compact contractible values over compact convex subsets in a reflexive Banach space with a Fréchet differentiable norm. Moreover, we give some conditions that guarantee the existence of solutions of generalized variational inequality for upper semicontinuous multivalued mappings with compact contractible values over unbounded closed convex subsets. The result obtained in this paper improves and extends the recent ones announced by Yu and Yang [J. Yu, H. Yang, Existence of solutions for generalized variational inequality problems, Nonlinear Anal., 71 (2009) e2327-e2330] and many others.     

Notes on the Dai-Yuan-Yuan modified spectral gradient method

In this paper, we give some notes on the two modified spectral gradient methods which were developed in [10]. These notes present the relationship between their stepsize formulae and some new secant equations in the quasi-Newton method. In particular, we also introduce another two new choices of stepsize. By using an efficient nonmonotone line search technique, we propose some new spectral gradient methods. Under some mild conditions, we show that these proposed methods are globally convergent. Numerical experiments on a large number of test problems from the CUTEr library are also reported, which show that the efficiency of these proposed methods.     

Inexact multisplitting methods for linear complementarity problems

We present an inexact multisplitting method for solving the linear complementarity problems, which is based on the inexact splitting method and the multisplitting method. This new method provides a specific realization for the multisplitting method and generalizes many existing matrix splitting methods for linear complementarity problems. Convergence for this new method is proved when the coefficient matrix is an _H+$H_{+}$-matrix. Then, two specific iteration forms for this inexact multisplitting method are presented, where the inner iterations are implemented either through a matrix splitting method or through a damped Newton method. Convergence properties for both these specific forms are analyzed, where the system matrix is either an _H+$H_{+}$-matrix or a symmetric matrix.     

A new smoothing quasi-Newton method for nonlinear complementarity problems

A new smoothing quasi-Newton method for nonlinear complementarity problems is presented. The method is a generalization of Thomas’ method for smooth nonlinear systems and has similar properties as Broyden's method. Local convergence is analyzed for a strictly complementary solution as well as for a degenerate solution. Presented numerical results demonstrate quite similar behavior of Thomas’ and Broyden's methods.     

BFGS trust-region method for symmetric nonlinear equations

In this paper, we propose a BFGS trust-region method for solving symmetric nonlinear equations. The global convergence and the superlinear convergence of the presented method will be established under favorable conditions. Numerical results show that the new algorithm is effective.     

Necessary optimality conditions for nonsmooth generalized semi-infinite programming problems

This paper is devoted to the study of nonsmooth generalized semi-infinite programming problems in which the index set of the inequality constraints depends on the decision vector and all emerging functions are assumed to be locally Lipschitz. We introduce a constraint qualification which is based on the Mordukhovich subdifferential. Then, we derive a Fritz–John type necessary optimality condition. Finally, interrelations between the new and the existing constraint qualifications such as the Mangasarian–Fromovitz, linear independent, and the Slater are investigated.     

Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints

In this paper, the nonlinear minimax problems with inequality constraints are discussed, and a sequential quadratic programming (SQP) algorithm with a generalized monotone line search is presented. At each iteration, a feasible direction of descent is obtained by solving a quadratic programming (QP). To avoid the Maratos effect, a high order correction direction is achieved by solving another QP. As a result, the proposed algorithm has global and superlinear convergence. Especially, the global convergence is obtained under a weak Mangasarian–Fromovitz constraint qualification (MFCQ) instead of the linearly independent constraint qualification (LICQ). At last, its numerical effectiveness is demonstrated with test examples.     

Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems

In this paper, we propose a new family of NCP-functions and the corresponding merit functions, which are the generalization of some popular NCP-functions and the related merit functions. We show that the new NCP-functions and the corresponding merit functions possess a system of favorite properties. Specially, we show that the new NCP-functions are strongly semismooth, Lipschitz continuous, and continuously differentiable; and that the corresponding merit functions have SC¹$S{C}^1$ property (i.e., they are continuously differentiable and their gradients are semismooth) and LC¹$L{C}^1$ property (i.e., they are continuously differentiable and their gradients are Lipschitz continuous) under suitable assumptions. Based on the new NCP-functions and the corresponding merit functions, we investigate a derivative free algorithm for the nonlinear complementarity problem and discuss its global convergence. Some preliminary numerical results are reported.     

A monotone semismooth Newton type method for a class of complementarity problems

In this paper, we propose a modified semismooth Newton method for a class of complementarity problems arising from the discretization of free boundary problems and establish its monotone convergence. We show that under appropriate conditions, the method reduces to semismooth Newton method. We also do some preliminary numerical experiments to show the efficiency of the proposed method.     

Some quadrature-based versions of the generalized Newton method for solving nonsmooth equations

In this paper, modifications of a generalized Newton method based on some rules of quadrature are studied. The methods considered are Newton-like iterative schemes for numerical solving systems of nonsmooth equations. Some mild conditions are given that ensure superlinear convergence to a solution. Moreover, a parameterized version of the midpoint version is presented. Finally, results of numerical tests are established.     

A generalized distance and enhanced Ekeland’s variational principle for vector functions

We propose a definition of lower closed transitive relations and prove the existence of minimal elements for such a relation. This result is shown to contain probably a large part of existing versions of Ekeland’s variational principle (EVP). We introduce the notion of a weak τ-function p as a generalized distance and use it together with the above result on minimal elements to establish enhanced EVP for various settings, under relaxed lower semicontinuity assumptions. These principles conclude the existence not only of p-strict minimizers of p-perturbations of the considered vector function, but also p-sharp and p-strong minimizers. Our results are proved to be stronger than the classical EVP and many generalizations in the literature, even in the usual one-dimensional case, by numerous corollaries and examples. We include equivalent formulations of our enhanced EVP as well.     

Self-adaptive projection method for co-coercive variational inequalities

In some real-world problems, the mapping of the variational inequalities does not have any explicit forms and only the function value can be evaluated or observed for given variables. In this case, if the mapping is co-coercive, the basic projection method is applicable. However, in order to determine the step size, the existing basic projection method needs to know the co-coercive modulus in advance. In practice, usually even if the mapping can be characterized co-coercive, it is difficult to evaluate the modulus, and a conservative estimation will lead an extremely slow convergence. In view of this point, this paper presents a self-adaptive projection method without knowing the co-coercive modulus. We also give a real-life example to demonstrate the practicability of the proposed method.     

Solving nonconvex nonlinear programming problems via a new aggregate constraint homotopy method

In this paper, by introducing C² mappings ξ_i(x,z_i),i=1,…,m and using the idea of the aggregate function method, a new aggregate constraint homotopy method is proposed to solve the Karush-Kuhn-Tucker (KKT) point of nonconvex nonlinear programming problems. Compared with the previous results, the choice scope of initial points is greatly enlarged, so use of the new aggregate constraint homotopy method may improve the computational efficiency of reduced predictor-corrector algorithms.     

Global optimization for sum of generalized fractional functions

This paper considers the solution of generalized fractional programming (GFP) problem which contains various variants such as a sum or product of a finite number of ratios of linear functions, polynomial fractional programming, generalized geometric programming, etc. over a polytope. For such problems, we present an efficient unified method. In this method, by utilizing a transformation and a two-part linearization method, a sequence of linear programming relaxations of the initial nonconvex programming problem are derived which are embedded in a branch-and-bound algorithm. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm.     

A modified inexact implicit method for mixed variational inequalities

In this paper, we suggest and analyze an inexact implicit method with a variable parameter for mixed variational inequalities by using a new inexactness restriction. Under certain conditions, the global convergence of the proposed method is proved. Some preliminary computational results are given to illustrate the efficiency of the new inexactness restriction. The results proved in this paper may be viewed as improvement and refinement of the previously known results.