Weak Sharp Solutions for Nonsmooth Variational Inequalities

In this paper, we study the weak sharp solutions for nonsmooth variational inequalities and give a characterization in terms of error bound. Some characterizations of solution set of nonsmooth variational inequalities are presented. Under certain conditions, we prove that the sequence generated by an algorithm for finding a solution of nonsmooth variational inequalities terminates after a finite number of iterates provided that the solutions set of a nonsmooth variational inequality is weakly sharp. We also study the finite termination property of the gradient projection method for solving nonsmooth variational inequalities under weak sharpness of the solution set.     

A globally convergent BFGS method for nonlinear monotone equations without any merit functions

Since 1965, there has been significant progress in the theoretical study on quasi-Newton methods for solving nonlinear equations, especially in the local convergence analysis. However, the study on global convergence of quasi-Newton methods is relatively fewer, especially for the BFGS method. To ensure global convergence, some merit function such as the squared norm merit function is typically used. In this paper, we propose an algorithm for solving nonlinear monotone equations, which combines the BFGS method and the hyperplane projection method. We also prove that the proposed BFGS method converges globally if the equation is monotone and Lipschitz continuous without differentiability requirement on the equation, which makes it possible to solve some nonsmooth equations. An attractive property of the proposed method is that its global convergence is independent of any merit function.We also report some numerical results to show efficiency of the proposed method.

     

Finite convergence analysis and weak sharp solutions for variational inequalities

In this paper, we study the weak sharpness of the solution set of variational inequality problem (in short, VIP) and the finite convergence property of the sequence generated by some algorithm for finding the solutions of VIP. In particular, we give some characterizations of weak sharpness of the solution set of VIP without considering the primal or dual gap function. We establish an abstract result on the finite convergence property for a sequence generated by some iterative methods. We then apply such abstract result to discuss the finite termination property of the sequence generated by proximal point method, exact proximal point method and gradient projection method. We also give an estimate on the number of iterates by which the sequence converges to a solution of the VIP.     

On Stochastic Mirror-prox Algorithms for Stochastic Cartesian Variational Inequalities: Randomized Block Coordinate and Optimal Averaging Schemes

Motivated by multi-user optimization problems and non-cooperative Nash games in uncertain regimes, we consider stochastic Cartesian variational inequality problems where the set is given as the Cartesian product of a collection of component sets. First, we consider the case where the number of the component sets is large and develop a randomized block stochastic mirror-prox algorithm, where at each iteration only a randomly selected block coordinate of the solution vector is updated through implementing two consecutive projection steps. We show that when the mapping is strictly pseudo-monotone, the algorithm generates a sequence of iterates that converges to the solution of the problem almost surely. When the maps are strongly pseudo-monotone, we prove that the mean-squared error diminishes at the optimal rate. Second, we consider large-scale stochastic optimization problems with convex objectives and develop a new averaging scheme for the randomized block stochastic mirror-prox algorithm. We show that by using a different set of weights than those employed in the classical stochastic mirror-prox methods, the objective values of the averaged sequence converges to the optimal value in the mean sense at an optimal rate. Third, we consider stochastic Cartesian variational inequality problems and develop a stochastic mirror-prox algorithm that employs the new weighted averaging scheme. We show that the expected value of a suitably defined gap function converges to zero at an optimal rate.     

Strong convergence of a double projection-type method for monotone variational inequalities in Hilbert spaces

We introduce a projection-type algorithm for solving monotone variational inequality problems in real Hilbert spaces without assuming Lipschitz continuity of the corresponding operator. We prove that the whole sequence of iterates converges strongly to a solution of the variational inequality. The method uses only two projections onto the feasible set in each iteration in contrast to other strongly convergent algorithms which either require plenty of projections within a step size rule or have to compute projections on possibly more complicated sets. Some numerical results illustrate the behavior of our method.     

A NONMONOTONIC TRUST REGION TECHNIQUE FOR NONLINEAR CONSTRAINED OPTIMIZATION

1.IntroductionConsiderthenonlinearequalityc0nstrainedoptimizati0npr0blemminf(x),s.t.c(x)=0(l-1)wheref:R"-R1andc:R"-R",m5n.RecentlyreducedHessianmethodsarepr0p0sedt0s0lvethispr0blem.C0lemanandConn[1l,andNocedalandOvertonl6lproposedseparatelysimilarquasi-Newt0nmethodsusingapproximatereducedHessian,However,suchmethodscann0tensuregl0balconvergenceandthereforeareavailableonlywhentheinitialstartsaregooden0ugh.TwobaJsicappr0aches,namelythelinesearchandthetrustregion,havebeende-velopedinordertoen…     

A Hybrid Smoothing Method for Mixed Nonlinear Complementarity Problems

In this paper, we describe a new, integral-based smoothing method for solving the mixed nonlinear complementarity problem (MNCP). This approach is based on recasting MNCP as finding the zero of a nonsmooth system and then generating iterates via two types of smooth approximations to this system. Under weak regularity conditions, we establish that the sequence of iterates converges to a solution if the limit point of this sequence is regular. In addition, we show that the rate is Q-linear, Q-superlinear, or Q-quadratic depending on the level of inexactness in the subproblem calculations and we make use of the inexact Newton theory of Dembo, Eisenstat, and Steihaug. Lastly, we demonstrate the viability of the proposed method by presenting the results of numerical tests on a variety of complementarity problems.     

Proximal algorithm for solving monotone variational inclusion

In this paper, we introduce a contraction algorithm for solving monotone variational inclusion problem. To reach this goal, our main iterative algorithm combine Dong’s projection and contraction algorithm with resolvent operator. Under suitable assumptions, we prove that the sequence generated by our main iterative algorithm converges weakly to the solution of the considered problem. Finally, we give two numerical examples to verify the feasibility of our main algorithm.     

Polyak’s gradient method for split feasibility problem constrained by level sets

In this paper, we are concerned with the split feasibility problem (SFP) whenever the convex sets involved are composed of level sets. By applying Polyak’s gradient method, we get a new and simple algorithm for such a problem. Under standard assumptions, we prove that the whole sequence generated by the algorithm weakly converges to a solution. We also modify the proposed algorithm and state the strong convergence without regularity conditions on the sets involved. Numerical experiments are included to illustrate its applications in signal processing.     

Subgradient Projection Algorithms and Approximate Solutions of Convex Feasibility Problems

In the present paper, we use subgradient projection algorithms for solving convex feasibility problems. We show that almost all iterates, generated by a subgradient projection algorithm in a Hilbert space, are approximate solutions. Moreover, we obtain an estimate of the number of iterates which are not approximate solutions. In a finite-dimensional case, we study the behavior of the subgradient projection algorithm in the presence of computational errors. Provided computational errors are bounded, we prove that our subgradient projection algorithm generates a good approximate solution after a certain number of iterates.     

A strongly convergent hybrid proximal method in Banach spaces

This paper is devoted to the study of strong convergence in inexact proximal like methods for finding zeroes of maximal monotone operators in Banach spaces. Convergence properties of proximal point methods in Banach spaces can be summarized as follows: if the operator have zeroes then the sequence of iterates is bounded and all its weak accumulation points are solutions. Whether or not the whole sequence converges weakly to a solution and which is the relation of the weak limit with the initial iterate are key questions. We present a hybrid proximal Bregman projection method, allowing for inexact solutions of the proximal subproblems, that guarantees strong convergence of the sequence to the closest solution, in the sense of the Bregman distance, to the initial iterate.     

Generalized viscosity approximation methods in multiobjective optimization problems

In this paper, we consider an extend-valued nonsmooth multiobjective optimization problem of finding weak Pareto optimal solutions. We propose a class of vector-valued generalized viscosity approximation method for solving the problem. Under some conditions, we prove that any sequence generated by this method converges to a weak Pareto optimal solution of the multiobjective optimization problem.     

A block coordinate variable metric linesearch based proximal gradient method

In this paper we propose an alternating block version of a variable metric linesearch proximal gradient method. This algorithm addresses problems where the objective function is the sum of a smooth term, whose variables may be coupled, plus a separable part given by the sum of two or more convex, possibly nonsmooth functions, each depending on a single block of variables. Our approach is characterized by the possibility of performing several proximal gradient steps for updating every block of variables and by the Armijo backtracking linesearch for adaptively computing the steplength parameter. Under the assumption that the objective function satisfies the Kurdyka-?ojasiewicz property at each point of its domain and the gradient of the smooth part is locally Lipschitz continuous, we prove the convergence of the iterates sequence generated by the method. Numerical experience on an image blind deconvolution problem show the improvements obtained by adopting a variable number of inner block iterations combined with a variable metric in the computation of the proximal operator.     

An approximate decomposition algorithm for convex minimization

For nonsmooth convex optimization, Robert Mifflin and Claudia Sagastizábal introduce a VU-space decomposition algorithm in Mifflin and Sagastizábal (2005) [11]. An attractive property of this algorithm is that if a primal-dual track exists, this algorithm uses a bundle subroutine. With the inclusion of a simple line search, it is proved to be globally and superlinearly convergent. However, a drawback is that it needs the exact subgradients of the objective function, which is expensive to compute. In this paper an approximate decomposition algorithm based on proximal bundle-type method is introduced that is capable to deal with approximate subgradients. It is shown that the sequence of iterates generated by the resulting algorithm converges to the optimal solutions of the problem. Numerical tests emphasize the theoretical findings.     

Convergence to a second-order point of a trust-region algorithm with a nonmonotonic penalty parameter for constrained optimization

In a recent paper (Ref. 1), the author proposed a trust-region algorithm for solving the problem of minimizing a nonlinear function subject to a set of equality constraints. The main feature of the algorithm is that the penalty parameter in the merit function can be decreased whenever it is warranted. He studied the behavior of the penalty parameter and proved several global and local convergence results. One of these results is that there exists a subsequence of the iterates generated by the algorithm that converges to a point that satisfies the first-order necessary conditions.In the current paper, we show that, for this algorithm, there exists a subsequence of iterates that converges to a point that satisfies both the first-order and the second-order necessary conditions.This research was supported by the Rice University Center for Research on Parallel Computation, Grant R31853, and the REDI Foundation.     

A feasible SQP-GS algorithm for nonconvex, nonsmooth constrained optimization

The gradient sampling (GS) algorithm for minimizing a nonconvex, nonsmooth function was proposed by Burke et al. (SIAM J Optim 15:751–779, 2005), whose most interesting feature is the use of randomly sampled gradients instead of subgradients. In this paper, combining the GS technique with the sequential quadratic programming (SQP) method, we present a feasible SQP-GS algorithm that extends the GS algorithm to nonconvex, nonsmooth constrained optimization. The proposed algorithm generates a sequence of feasible iterates, and guarantees that the objective function is monotonically decreasing. Global convergence is proved in the sense that, with probability one, every cluster point of the iterative sequence is stationary for the improvement function. Finally, some preliminary numerical results show that the proposed algorithm is effective.     

Regularized and inertial algorithms for common fixed points of nonlinear operators

This paper deals with a general fixed point iteration for computing a point in some nonempty closed and convex solution set included in the common fixed point set of a sequence of mappings on a real Hilbert space. The proposed method combines two strategies: viscosity approximations (regularization) and inertial type extrapolation. The first strategy is known to ensure the strong convergence of some successive approximation methods, while the second one is intended to speed up the convergence process. Under classical conditions on the operators and the parameters, we prove that the sequence of iterates generated by our scheme converges strongly to the element of minimal norm in the solution set. This algorithm works, for instance, for approximating common fixed points of infinite families of demicontractive mappings, including the classes of quasi-nonexpansive operators and strictly pseudocontractive ones.     

A TRULY GLOBALLY CONVERGENT FEASIBLE NEWTON-TYPE METHOD FOR MIXED COMPLEMENTARITY PROBLEMS

Typical solution methods for solving mixed complementarity problems either generatefeasible iterates but have to solve relatively complicated subproblems such as quadraticprograms or linear complementarity problems,or(those methods)have relatively simplesubproblems such as system of linear equations but possibly generate infeasible iterates.In this paper,we propose a new Newton-type method for solving monotone mixed com-plementarity problems,which ensures to generate feasible iterates,and only has to solve asystem of well-conditioned linear equations with reduced dimension per iteration.Withoutany regularity assumption,we prove that the whole sequence of iterates converges to a so-lution of the problem(truly globally convergent).Furthermore,under suitable conditions,the local superlinear rate of convergence is also established.     

A Second-Order Bundle Method Based on -Decomposition Strategy for a Special Class of Eigenvalue Optimizations

In the past decade, eigenvalue optimization has gained remarkable attention in various engineering applications. One of the main difficulties with numerical analysis of such problems is that the eigenvalues, considered as functions of a symmetric matrix, are not smooth at those points where they are multiple. We propose a new explicit nonsmooth second-order bundle algorithm based on the idea of the proximal bundle method on minimizing the arbitrary eigenvalue over an affine family of symmetric matrices, which is a special class of eigenvalue function–D.C. function. To the best of our knowledge, few methods currently exist for minimizing arbitrary eigenvalue function. In this work, we apply the -Lagrangian theory to this class of D.C. functions: the arbitrary eigenvalue function λ_i with affine matrix-valued mappings, where λ_i is usually not convex. We prove the global convergence of our method in the sense that every accumulation point of the sequence of iterates is stationary. Moreover, under mild conditions we show that, if started close enough to the minimizer x*, the proposed algorithm converges to x* quadratically. The method is tested on some constrained optimization problems, and some encouraging preliminary numerical results show the efficiency of our method.     

On the minimal displacement vector of the Douglas–Rachford operator

The Douglas–Rachford algorithm can be represented as the fixed point iteration of a firmly nonexpansive operator. When the operator has no fixed points, the algorithm’s iterates diverge, but the difference between consecutive iterates converges to the so-called minimal displacement vector, which can be used to certify infeasibility of an optimization problem. In this paper, we establish new properties of the minimal displacement vector, which allow us to generalize some existing results.