Global s-type error bound for the extended linear complementarity problem and applications

For the extended linear complementarity problem over an affine subspace, we first study some characterizations of (strong) column/row monotonicity and (strong) R ₀-property. We then establish global s-type error bound for this problem with the column monotonicity or R ₀-property, especially for the one with the nondegeneracy and column monotonicity, and give several equivalent formulations of such error bound without the square root term for monotone affine variational inequality. Finally, we use this error bound to derive some properties of the iterative sequence produced by smoothing methods for solving such a problem under suitable assumptions. Received: May 2, 1999 / Accepted: February 21, 2000?Published online July 20, 2000     

Conditions for Error Bounds and Bounded Level Sets of Some Merit Functions for the Second-Order Cone Complementarity Problem

Recently this author studied several merit functions systematically for the second-order cone complementarity problem. These merit functions were shown to enjoy some favorable properties, to provide error bounds under the condition of strong monotonicity, and to have bounded level sets under the conditions of monotonicity as well as strict feasibility. In this paper, we weaken the condition of strong monotonicity to the so-called uniform P ^*-property, which is a new concept recently developed for linear and nonlinear transformations on Euclidean Jordan algebra. Moreover, we replace the monotonicity and strict feasibility by the so-called R ₀₁ or R ₀₂-functions to keep the property of bounded level sets. This work is partially supported by National Science Council of Taiwan.     

Modules Whose t-Closed Submodules Have a Summand as a Complement

We define and investigate T ₁₁-type modules as a generalization of t-extending modules, and modules satisfying C ₁₁ condition. A module M is said to be T ₁₁-type if every t-closed submodule of M has a complement which is a direct summand. Direct sums of T ₁₁-type modules inherit the property. Some equivalent conditions for a module M to be T ₁₁-type are given. We characterize a module M for which every direct summand satisfies T ₁₁ condition. If R _R is T ₁₁-type, then R/Z ₂(R _R ) is a C ₂ ring if and only if it is a von Neumann regular ring. Applying this result, we characterize a right t-extending (resp., finitely Σ-t-extending, or Σ-t-extending) ring R for which R/Z ₂(R _R ) is von Neumann regular.     

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.     

Stochastic Nonlinear Complementarity Problem and?Applications to?Traffic Equilibrium under?Uncertainty

The expected residual minimization (ERM) formulation for the stochastic nonlinear complementarity problem (SNCP) is studied in this paper. We show that the involved function is a stochastic R ₀ function if and only if the objective function in the ERM formulation is coercive under a mild assumption. Moreover, we model the traffic equilibrium problem (TEP) under uncertainty as SNCP and show that the objective function in the ERM formulation is a stochastic R ₀ function. Numerical experiments show that the ERM-SNCP model for TEP under uncertainty has various desirable properties. This work was partially supported by a Grant-in-Aid from the Japan Society for the Promotion of Science. The authors thank Professor Guihua Lin for pointing out an error in Proposition 2.1 on an earlier version of this paper. The authors are also grateful to the referees for their insightful comments.     

Inverse problems and solution methods for a class of nonlinear complementarity problems

In this paper, motivated by the KKT optimality conditions for a sort of quadratic programs, we first introduce a class of nonlinear complementarity problems (NCPs). Then we present and discuss a kind of inverse problems of the NCPs, i.e., for a given feasible decision [`(x)]\bar{x} , we aim to characterize the set of parameter values for which there exists a point [`(y)]\bar{y} such that ([`(x)],[`(y)])(\bar{x},\bar{y}) forms a solution of the NCP and require the parameter values to be adjusted as little as possible. This leads to an inverse optimization problem. In particular, under ℓ _∞, ℓ ₁ and Frobenius norms as well as affine maps, this paper presents three simple and efficient solution methods for the inverse NCPs. Finally, some preliminary numerical results show that the proposed methods are very promising.     

Lifting Central Idempotents Modulo Jacobson Radicals and Ranks of K 0 Groups

Let R be a ring and let J(R) be the Jacobson radical of R. We discuss the problem of determining when the central idempotents in R/J(R) can be lifted to R. If R is a noetherian (artinian) ring, we give some conditions relative to the ranks of K ₀ groups under which the central idempotents in R/J(R) can be lifted. In particular, when R is semilocal, these conditions are necessary and sufficient. Moreover, we consider ranks of K ₀ groups of pullbacks of rings and obtain the upper and lower bounds on them under some suitable conditions.     

On a class of least-element complementarity problems

The present paper studies the linear complementarity problem of finding vectorsx andy inR ₊ ⁿ such thatc + Dx + y 0,b – x 0 andx ^T (c + Dx + y) = y ^T (b – x) = 0 whereD is aZ-matrix andb > 0. Complementarity problems of this nature arise, for example, from the minimization of certain quadratic functions subject to upper and lower bounds on the variables. Two least-element characterizations of solutions to the above linear complementarity problem are established first. Next, a new and direct method to solve this class of problems, which depends on the idea of least-element solution is presented. Finally, applications and computational experience with its implementation are discussed.Research partially supported by the National Science Foundation Grant MCS 71-03341 A04 and the Air Force Office of Scientific Research Contract F 44620 14 C 0079.     

On the Upper Semi-continuity of the Solution Map to the Vertical Implicit Homogeneous Complementarity Problem of Type <Emphasis Type="Italic">R</Emphasis><Subscript>0</Subscript>

In this paper, we introduce a class of vertical implicit complementarity problems and give a necessary and sufficient condition for the upper semi-continuity of the solution map to the vertical implicit homogeneous complementarity problem of type R₀. This work is supported by the Basic and Applied Research Projection of Sichuan Province (05JY029-009-1).     

On error bounds of polynomial complementarity problems with structured tensors

The recently introduced polynomial complementarity problem (PCP) is an interesting generalization of the tensor complementarity problem (TCP) studied extensively in the literature. In this paper, we make a contribution to analysing the error bounds of PCPs with structured tensors. Specifically, we first show that the solution set of PCPs with a leading ER-tensor is nonempty and compact. Then, we analyse lower bounds of solutions of PCPs under the strict semicopositiveness, thereby gainfully establishing error bounds of PCPs, which, to the best of our knowledge, are not studied in the current PCPs and TCPs literature. Moreover, it is noteworthy that, due to the special structure of PCPs, our error bounds are better than the direct results obtained by applying the theory of non-linear complementarity problems to PCPs.     

On the Lorentz Cone Complementarity Problems in Infinite-Dimensional Real Hilbert Space

In this article, we consider the Lorentz cone complementarity problems in infinite-dimensional real Hilbert space. We establish several results that are standard and important when dealing with complementarity problems. These include proving the same growth of the Fishcher–Burmeister merit function and the natural residual merit function, investigating property of bounded level sets under mild conditions via different merit functions, and providing global error bounds through the proposed merit functions. Such results are helpful for further designing solution methods for the Lorentz cone complementarity problems in Hilbert space.     

态R_0代数

本文研究了R_0代数上有关态算子的问题.利用MV-代数上内态的引入方法引入了态算子,定义了态R_0代数,它是R_0代数的一般化.给出了一些非平凡态R_0代数的例子并讨论了态R_0代数的一些基本性质.在此基础上给出了态滤子和态局部R_0代数的概念,并利用态滤子刻画了态局部R_0代数.推广了局部R_0代数的相关理论.     

Error bounds for nondegenerate monotone linear complementarity problems

Error bounds and upper Lipschitz continuity results are given for monotone linear complementarity problems with a nondegenerate solution. The existence of a nondegenerate solution considerably simplifies the error bounds compared with problems for which all solutions are degenerate. Thus when a point satisfies the linear inequalities of a nondegenerate complementarity problem, the residual that bounds the distance from a solution point consists of the complementarity condition alone, whereas for degenerate problems this residual cannot bound the distance to a solution without adding the square root of the complementarity condition to it. This and other simplified results are a consequence of the polyhedral characterization of the solution set as the intersection of the feasible region {zMz + q 0, z 0} with a single linear affine inequality constraint.This material is based on research supported by National Science Foundation Grants CCR-8723091 and DCR-8521228 and Air Force Office of Scientific Research Grant AFOSR-86-0172.     

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.     

A regularization semismooth Newton method based on the generalized Fischer–Burmeister function for -NCPs

We consider a regularization method for nonlinear complementarity problems with F being a P₀-function which replaces the original problem with a sequence of the regularized complementarity problems. In this paper, this sequence of regularized complementarity problems are solved approximately by applying the generalized Newton method for an equivalent augmented system of equations, constructed by the generalized Fischer–Burmeister (FB) NCP-functions φ_p with p>1. We test the performance of the regularization semismooth Newton method based on the family of NCP-functions through solving all test problems from MCPLIB. Numerical experiments indicate that the method associated with a smaller p, for example p[1.1,2], usually has better numerical performance, and the generalized FB functions φ_p with p[1.1,2) can be used as the substitutions for the FB function φ₂.     

An infeasible-interior-point predictor-corrector algorithm for theP *-geometric LCP

AP _*-geometric linear complementarity problem (P _*GP) as a generalization of the monotone geometric linear complementarity problem is introduced. In particular, it contains the monotone standard linear complementarity problem and the horizontal linear complementarity problem. Linear and quadratic programming problems can be expressed in a “natural” way (i.e., without any change of variables) asP _*GP. It is shown that the algorithm of Mizunoet al. [6] can be extended to solve theP _*GP. The extended algorithm is globally convergent and its computational complexity depends on the quality of the starting points. The algorithm is quadratically convergent for problems having a strictly complementary solution. The work of F. A. Potra was supported in part by NSF Grant DMS 9305760     

Computation of generalized differentials in nonlinear complementarity problems

Let f and g be continuously differentiable functions on R ⁿ . The nonlinear complementarity problem NCP(f,g), 0≤f(x)⊥g(x)≥0, arises in many applications including discrete Hamilton-Jacobi-Bellman equations and nonsmooth Dirichlet problems. A popular method to find a solution of the NCP(f,g) is the generalized Newton method which solves an equivalent system of nonsmooth equations F(x)=0 derived by an NCP function. In this paper, we present a sufficient and necessary condition for F to be Fréchet differentiable, when F is defined by the “min” NCP function, the Fischer-Burmeister NCP function or the penalized Fischer-Burmeister NCP function. Moreover, we give an explicit formula of an element in the Clarke generalized Jacobian of F defined by the “min” NCP function, and the B-differential of F defined by other two NCP functions. The explicit formulas for generalized differentials of F lead to sharper global error bounds for the NCP(f,g).     

A regularized projection method for complementarity problems with non-Lipschitzian functions

We consider complementarity problems involving functions which are not Lipschitz continuous at the origin. Such problems arise from the numerical solution for differential equations with non-Lipschitzian continuity, e.g. reaction and diffusion problems. We propose a regularized projection method to find an approximate solution with an estimation of the error for the non-Lipschitzian complementarity problems. We prove that the projection method globally and linearly converges to a solution of a regularized problem with any regularization parameter. Moreover, we give error bounds for a computed solution of the non-Lipschitzian problem. Numerical examples are presented to demonstrate the efficiency of the method and error bounds.

     

Functions Without Exceptional Family of Elements and Complementarity Problems

In Ref. 1, Isac, Bulavski, and Kalashnikov introduced the concept of exceptional family of elements for a continuous function f: R ⁿR ⁿ. It is known that, if there does not exist an exceptional family of elements for f, then the corresponding complementarity problem has a solution. In this paper, we show that several classes of nonlinear functions, known in complementarity theory or other domains, are functions without exceptional family of elements and consequently the corresponding complementarity problem is solvable. It is evident that the notion of exceptional family of elements provides an alternative way of determining whether or not the complementarity problem has a solution.     

Convexity of Torsion Subgroups in K 0 Groups and Dimension Group Properties of K 0 of Pullbacks

Firstly, we characterize the partially ordered K ₀ groups of some rings. Secondly, let R be a ring, we discuss the problem when the pre-order on K ₀(R) is actually a partial order and when Tor(K ₀(R)) is a convex subgroup of K ₀(R). Finally, we examine the transfer of some ordering properties (such as partial order, unperforated, interpolation property) on K ₀ groups of rings to the K ₀ groups of pullbacks. Let R be a pullback of R ₁ and R ₂ over S, under some suitable conditions, we prove that if each K ₀(R _i ) (i = 1, 2) is a dimension group, then so is K ₀(R).