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.     

A continuation method for (strongly) monotone variational inequalities

We consider the variational inequality problem, denoted by VIP(X, F), whereF is a strongly monotone function and the convex setX is described by some inequality (and possibly equality) constraints. This problem is solved by a continuation (or interior-point) method, which solves a sequence of certain perturbed variational inequality problems. These perturbed problems depend on a parameter > 0. It is shown that the perturbed problems have a unique solution for all values of > 0, and that any sequence generated by the continuation method converges to the unique solution of VIP(X,F) under a well-known linear independence constraint qualification (LICQ). We also discuss the extension of the continuation method to monotone variational inequalities and present some numerical results obtained with a suitable implementation of this method. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Convergence and Error Bound of a Method for Solving Variational Inequality Problems via the Generalized D-Gap Function

The variational inequality problem (VIP) can be reformulated as an unconstrained minimization problem through the generalized D-gap function. Recently, a hybrid Newton-type method was proposed by Peng and Fukushima for minimizing a special form of the generalized D-gap function. In this paper, the hybrid Newton-type algorithm is extended to minimize the general form g of the generalized D-gap function. It is shown that the algorithm has nice convergence properties. Under some reasonable conditions, it is proved that the algorithm is locally and globally convergent. Moreover, it is proved that the function g has bounded level sets for strongly monotone VIP. An error bound of the algorithm is obtained.     

Error Bounds for R0-Type and Monotone Nonlinear Complementarity Problems

The paper generalizes the Mangasarian–Ren (Ref. 1) error bounds forlinear complementarity problems (LCPs) to nonlinear complementarity problems(NCPs). This is done by extending the concept of R ₀-matrixto several R ₀-type functions, which include a subset ofmonotone functions as a special case. Both local and global error bounds areobtained for R ₀-type NCPs and some monotone NCPs.     

Robust a Posteriori Error Estimation for a Singularly Perturbed Reaction–Diffusion Equation on Anisotropic Tetrahedral Meshes

We consider a singularly perturbed reaction–diffusion problem and derive and rigorously analyse an a posteriori residual error estimator that can be applied to anisotropic finite element meshes. The quotient of the upper and lower error bounds is the so-called matching function which depends on the anisotropy (of the mesh and the solution) but not on the small perturbation parameter. This matching function measures how well the anisotropic finite element mesh corresponds to the anisotropic problem. Provided this correspondence is sufficiently good, the matching function is O(1). Hence one obtains tight error bounds, i.e. the error estimator is reliable and efficient as well as robust with respect to the small perturbation parameter. A numerical example supports the anisotropic error analysis.     

Finite volume element method for monotone nonlinear elliptic problems

In this article, we consider the finite volume element method for the monotone nonlinear second‐order elliptic boundary value problems. With the assumptions which guarantee that the corresponding operator is strongly monotone and Lipschitz‐continuous, and with the minimal regularity assumption on the exact solution, that is, u∈H¹(Ω), we show that the finite volume element method has a unique solution, and the finite volume element approximation is uniformly convergent with respect to the H¹ ‐norm. If u∈H^1+ε(Ω),0 < ε ≤ 1, we develop the optimal convergence rate \begin{align*}\mathcal{O}(h^{\epsilon})\end{align*} in the H¹ ‐norm. Moreover, we propose a natural and computationally easy residual‐based H¹ ‐norm a posteriori error estimator and establish the global upper bound and local lower bounds on the error. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

On the resolution of monotone complementarity problems

A reformulation of the nonlinear complementarity problem (NCP) as an unconstrained minimization problem is considered. It is shown that any stationary point of the unconstrained objective function is a solution of NCP if the mapping F involved in NCP is continuously differentiable and monotone, and that the level sets are bounded if F is continuous and strongly monotone. A descent algorithm is described which uses only function values of F. Some numerical results are given.     

Two-Grid hp-Version DGFEMs for Strongly Monotone Second-Order Quasilinear Elliptic PDEs

In this article we develop the a priori error analysis of so-called two-grid hp-version discontinuous Galerkin finite element methods for the numerical approximation of strongly monotone second-order quasilinear partial differential equations. In this setting, the fully nonlinear problem is first approximated on a coarse finite element space V(𝒯_H, P ). The resulting ‘coarse’ numerical solution is then exploited to provide the necessary data needed to linearize the underlying discretization on the finer space V(𝒯_h, p ); thereby, only a linear system of equations is solved on the richer space V(𝒯_h, p ). Numerical experiments confirming the theoretical results are presented. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Kernel-Based Interior-Point Methods for Monotone Linear Complementarity Problems over Symmetric Cones

We present an interior-point method for monotone linear complementarity problems over symmetric cones (SCLCP) that is based on barrier functions which are defined by a large class of univariate functions, called eligible kernel functions. This class is fairly general and includes the classical logarithmic function, the self-regular functions, as well as many non-self-regular functions as special cases. We provide a unified analysis of the method and give a general scheme on how to calculate the iteration bounds for the entire class. We also calculate the iteration bounds of both large-step and short-step versions of the method for ten frequently used eligible kernel functions. For some of them we match the best known iteration bound for large-step methods, while for short-step methods the best iteration bound is matched for all cases. The paper generalizes results of Lesaja and Roos (SIAM J. Optim. 20(6):3014–3039, 2010) from P _∗(κ)-LCP over the non-negative orthant to monotone LCPs over symmetric cones.     

Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start

We study Lanczos and polynomial algorithms with random start for estimating an eigenvector corresponding to the largest eigenvalue of an n × n large symmetric positive definite matrix. We analyze the two error criteria: the randomized error and the randomized residual error. For the randomized error, we prove that it is not possible to get distribution-free bounds, i.e., the bounds must depend on the distribution of eigenvalues of the matrix. We supply such bounds and show that they depend on the ratio of the two largest eigenvalues. For the randomized residual error, distribution-free bounds exist and are provided in the paper. We also provide asymptotic bounds, as well as bounds depending on the ratio of the two largest eigenvalues. The bounds for the Lanczos algorithm may be helpful in a practical implementation and termination of this algorithm. © 1998 John Wiley & Sons, Ltd.     

Bounds for the infinity norm of the inverse for certain M- and H-matrices

The paper presents new two-sided bounds for the infinity norm of the inverse for the so-called PM-matrices, which form a subclass of the class of nonsingular M-matrices and contain the class of strictly diagonally dominant matrices. These bounds are shown to be monotone with respect to the underlying partitioning of the index set, and the equality cases are analyzed. Also an upper bound for the infinity norm of the inverse of a PH-matrix (whose comparison matrix is a PM-matrix) is derived. The known Ostrowski, Ahlberg–Nilson–Varah, and Mora?a bounds are shown to be special cases of the upper bound obtained.     

Towards an <Emphasis Type="Italic">L</Emphasis><Superscript>p</Superscript>-potential theory for sub-Markovian semigroups: variational inequalities and balayage theory

We give a new variational approach toL ^p -potential theory for sub-Markovian semigroups. It is based on the observation that the Gâteaux-derivative of the corresponding L ^p-energy functional is a monotone operator. This allows to apply the well established theory of Browder and Minty on monotone operators to the nonlinear problems in L ^p-potential theory. In particular, using this approach it is possible to avoid any symmetry assumptions of the underlying semigroup. We prove existence of corresponding (r, p)-equilibrium potentials and obtain a complete characterization in terms of a variational inequality. Moreover we investigate associated potentials and encounter a natural interpretation of the so-called nonlinear potential operator in the context of monotone operators.     

A class of smoothing functions for nonlinear and mixed complementarity problems

We propose a class of parametric smooth functions that approximate the fundamental plus function, (x)₊=max{0, x}, by twice integrating a probability density function. This leads to classes of smooth parametric nonlinear equation approximations of nonlinear and mixed complementarity problems (NCPs and MCPs). For any solvable NCP or MCP, existence of an arbitrarily accurate solution to the smooth nonlinear equations as well as the NCP or MCP, is established for sufficiently large value of a smoothing parameter . Newton-based algorithms are proposed for the smooth problem. For strongly monotone NCPs, global convergence and local quadratic convergence are established. For solvable monotone NCPs, each accumulation point of the proposed algorithms solves the smooth problem. Exact solutions of our smooth nonlinear equation for various values of the parameter , generate an interior path, which is different from the central path for interior point method. Computational results for 52 test problems compare favorably with these for another Newton-based method. The smooth technique is capable of solving efficiently the test problems solved by Dirkse and Ferris [6], Harker and Xiao [11] and Pang & Gabriel [28].This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grant CCR-9322479.     

Solution continuity in variational conditions

We present some results about Lipschitzian behavior of solutions to variational conditions when the sets over which the conditions are posed, as well as the functions appearing in them, may vary. These results rely on calmness and inner semicontinuity, and we describe some conditions under which those conditions hold, especially when the sets involved in the variational conditions are convex and polyhedral. We then apply the results to find error bounds for solutions of a strongly monotone variational inequality in which both the constraining polyhedral multifunction and the monotone operator are perturbed.      

GUARANTEED BOUNDS FOR THE SOLUTION OF THE WAVE EQUATION

Abstract

Numerical solution of the wave equation in the form of close lower and upper bounds provides a secure a posteriori error estimate that can be used for efficient accuracy control. The method considered in this paper uses some monotone properties of the differential operator in the wave equation to construct bounds for the solution in the form of trigonometric polynomials of x. Aspects of the numerical implementation, the accuracy of the computed bounds and some numerical examples are discussed.     

Infinite-Dimensional Integration in Weighted Hilbert Spaces: Anchored Decompositions,Optimal Deterministic Algorithms,and Higher-Order Convergence

We study the numerical integration of functions depending on an infinite number of variables. We provide lower error bounds for general deterministic algorithms and provide matching upper error bounds with the help of suitable multilevel algorithms and changing-dimension algorithms. More precisely, the spaces of integrands we consider are weighted, reproducing kernel Hilbert spaces with norms induced by an underlying anchored function space decomposition. Here the weights model the relative importance of different groups of variables. The error criterion used is the deterministic worst-case error. We study two cost models for function evaluations that depend on the number of active variables of the chosen sample points, and we study two classes of weights, namely product and order-dependent weights and the newly introduced finite projective dimension weights. We show for these classes of weights that multilevel algorithms achieve the optimal rate of convergence in the first cost model while changing-dimension algorithms achieve the optimal convergence rate in the second model. As an illustrative example, we discuss the anchored Sobolev space with smoothness parameter \(\alpha \) and provide new optimal quasi-Monte Carlo multilevel algorithms and quasi-Monte Carlo changing-dimension algorithms based on higher-order polynomial lattice rules.     

The monotone circuit complexity of boolean functions

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of sizes in a graphm vertices requires monotone circuits of size Ω(m ^s /(logm)^2s ) for fixeds, and sizem ^Ω(logm) form/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/logm)^2/3 requires monotone circuits exp (Ω((m/logm)^1/3)). For fixeds, any monotone circuit that detects cliques of sizes requiresm) ^s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function ofn variables is exp (Ω(n ^1/4 · (logn)^1/2)), improving a recent result of exp (Ω(n ^1/8-ε)) due to Andreev. First author supported in part by Allon Fellowship, by Bat Sheva de-Rotschild Foundation by the Fund for basic research administered by the Israel Academy of Sciences. Second author supported in part by a National Science Foundation Graduate Fellowship.     

Diagonal dominance characterization of <Emphasis Type="Italic">PM</Emphasis>-and <Emphasis Type="Italic">PH</Emphasis>-matrices

The paper presents new bounds for the inverses of the so-called PM- and PH-matrices. Also bounds for the spectral radii of the inverses to PM- and PH-matrices are obtained, and the monotonicity of these bounds with respect to the underlying partition of the index set is established. Finally, the so-called quasi-PM- and quasi-PH-matrices are introduced, and bounds for the inverses of such matrices are suggested. Bibliography: 10 titles.     

Tight global linear convergence rate bounds for Douglas–Rachford splitting

Recently, several authors have shown local and global convergence rate results for Douglas–Rachford splitting under strong monotonicity, Lipschitz continuity, and cocoercivity assumptions. Most of these focus on the convex optimization setting. In the more general monotone inclusion setting, Lions and Mercier showed a linear convergence rate bound under the assumption that one of the two operators is strongly monotone and Lipschitz continuous. We show that this bound is not tight, meaning that no problem from the considered class converges exactly with that rate. In this paper, we present tight global linear convergence rate bounds for that class of problems. We also provide tight linear convergence rate bounds under the assumptions that one of the operators is strongly monotone and cocoercive, and that one of the operators is strongly monotone and the other is cocoercive. All our linear convergence results are obtained by proving the stronger property that the Douglas–Rachford operator is contractive.     

On error bounds for lower semicontinuous functions

We give some sufficient conditions for proper lower semicontinuous functions on metric spaces to have error bounds (with exponents). For a proper convex function f on a normed space X the existence of a local error bound implies that of a global error bound. If in addition X is a Banach space, then error bounds can be characterized by the subdifferential of f. In a reflexive Banach space X, we further obtain several sufficient and necessary conditions for the existence of error bounds in terms of the lower Dini derivative of f. Received: April 27, 2001 / Accepted: November 6, 2001?Published online April 12, 2002