A complementarity approach to a quasistatic multi-rigid-body contact problem

In this paper, we study the problem of predicting the quasistatic planar motion of a passive rigid body in frictional contact with a set of active rigid bodies. The active bodies can be thought of as the links of a mechanism or robot manipulator whose positions can be actively controlled by actuators. The passive body can be viewed as a grasped object, which moves only in response to contact forces and other external forces such as those due to gravity. We formulate this problem as a certain uncoupled complementarity problem, and show that it belongs to the class of NP-complete problems. Finally, numerical results of our proposed linear programming-based solution algorithm for this class of problems are presented and compared to the only other currently available solution algorithm.The research of this author was based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739.The research of this author was partially supported by the National Science Foundation under grant IRI-9304734, the Texas Advanced Technology Program under grant 999903-095, and the Texas Advanced Research Program under grant 999903-078.     

Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory,algorithms and applications

Over the past decade, the field of finite-dimensional variational inequality and complementarity problems has seen a rapid development in its theory of existence, uniqueness and sensitivity of solution(s), in the theory of algorithms, and in the application of these techniques to transportation planning, regional science, socio-economic analysis, energy modeling, and game theory. This paper provides a state-of-the-art review of these developments as well as a summary of some open research topics in this growing field.The research of this author was supported by the National Science Foundation Presidential Young Investigator Award ECE-8552773 and by the AT&T Program in Telecommunications Technology at the University of Pennsylvania.The research of this author was supported by the National Science Foundation under grant ECS-8644098.     

Parallel Newton methods for the nonlinear complementarity problem

In this paper, we discuss how the basic Newton method for solving the nonlinear complementarity problem can be implemented in a parallel computation environment. We propose some synchronized and asynchronous Newton methods and establish their convergence.This work was based on research supported by the National Science Foundation under grant ECS-8407240 and by a University Research and Development grant from Cray Research Inc. The research was initiated when the authors were with the University of Texas at Dallas.     

Local convergence of interior-point algorithms for degenerate monotone LCP

Most asymptotic convergence analysis of interior-point algorithms for monotone linear complementarity problems assumes that the problem is nondegenerate, that is, the solution set contains a strictly complementary solution. We investigate the behavior of these algorithms when this assumption is removed.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234.The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

An interior point potential reduction method for constrained equations

We study the problem of solving a constrained system of nonlinear equations by a combination of the classical damped Newton method for (unconstrained) smooth equations and the recent interior point potential reduction methods for linear programs, linear and nonlinear complementarity problems. In general, constrained equations provide a unified formulation for many mathematical programming problems, including complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities and nonlinear programs. Combining ideas from the damped Newton and interior point methods, we present an iterative algorithm for solving a constrained system of equations and investigate its convergence properties. Specialization of the algorithm and its convergence analysis to complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities are discussed in detail. We also report the computational results of the implementation of the algorithm for solving several classes of convex programs. The work of this author was based on research supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and the Office of Naval Research under grant N00014-93-1-0228. The work of this author was based on research supported by the National Science Foundation under grant DMI-9496178 and the Office of Naval Research under grants N00014-93-1-0234 and N00014-94-1-0340.     

The basic theorem of complementarity revisited

The basic theorm of (linear) complementarity was stated in a 1971 paper [6] by B.C. Eaves who credited C.E. Lemke for giving a constructive proof based on his almost complementary pivot algorithm. This theorem asserts that associated with an arbitrary linear complementarity problem, a certain augmented problem always possesses a solution. Many well-known existence results pertaining to the linear complementarity problem are consequences of this fundamental theorem.In this paper, we explore some further implications of the basic theorem of complementarity and derive new existence results for the linear complementarity problem. Based on these results, conditions for the existence of a solution to a linear complementarity problem with a fully-semimonotone matrix are examined. The class of the linear complementarity problems with aG-matrix is also investigated.The work of this author was based on research supported by the National Science Foundation under grant ECS-8717968.     

A likelihood-MPEC approach to target classification

In this paper we develop a method for classifying an unknown data vector as belonging to one of several classes. This method is based on the statistical methods of maximum likehood and borrowed strength estimation. We develop an MPEC procedure (for Mathematical Program with Equilibrium Constraints) for the classification of a multi-dimensional observation, using a finite set of observed training data as the inputs to a bilevel optimization problem. We present a penalty interior point method for solving the resulting MPEC and report numerical results for a multispectral minefield classification application. Related approaches based on conventional maximum likehood estimation and a bivariate normal mixture model, as well as alternative surrogate classification objective functions, are described. Received: October 26, 1998 / Accepted: June 11, 2001?Published online March 24, 2003 RID="***" ID="***"The authors of this work were all partially supported by the Wright Patterson Air Force Base via Veda Contract F33615-94-D-1400. The first and third author were also supported by the National Science Foundation under grant DMS-9705220. RID="*" ID="*"The work of this author was based on research supported by the U.S. National Science Foundation under grant CCR-9624018. RID="**" ID="**"The work of this author was supported by the Office of Naval Research under grant N00014-95-1-0777.     

Inexact primal-dual interior point iteration for linear programs in function spaces

Motivated by a simple optimal control problem with state constraints, we consider an inexact implementation of the primal-dual interior point algorithm of Zhang, Tapia, and Dennis. We show how the control problem can be formulated as a linear program in an infinite dimensional space in two different ways and prove convergence results.The research of this author was supported by an Overseas Research Scholarship of the Ministry of Education, Science and Culture of Japan.The research of this author was supported by National Science Foundation grants #DMS-9024622 and #DMS-9321938, North Atlantic Treaty Organization grant #CRG 920067, and an allocation of computing resources from the North Carolina Supercomputing Program.The research of this author was supported by North Atlantic Treaty Organization grant #CRG 920067.     

Multilevel augmentation methods for differential equations

We develop multilevel augmentation methods for solving differential equations. We first establish a theoretical framework for convergence analysis of the boundary value problems of differential equations, and then construct multiscale orthonormal bases in H₀^m(0,1) spaces. Finally, the multilevel augmentation methods in conjunction with the multiscale orthonormal bases are applied to two-point boundary value problems of both second-order and fourth-order differential equations. Theoretical analysis and numerical tests show that these methods are computationally stable, efficient and accurate. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday with friendship and esteem. Mathematics subject classifications (2000) 65J15, 65R20. Zhongying Chen: Supported in part by the Natural Science Foundation of China under grants 10371137 and 10201034, the Foundation of Doctoral Program of National Higher Education of China under grant 20030558008, Guangdong Provincial Natural Science Foundation of China under grant 1011170 and the Foundation of Zhongshan University Advanced Research Center. Yuesheng Xu: Corresponding author. Supported in part by the US National Science Foundation under grants 9973427 and 0312113, by NASA under grant NCC5-399, by the Natural Science Foundation of China under grant 10371122 and by the Chinese Academy of Sciences under the program of “One Hundred Distinguished Young Scientists”.     

Local and parallel finite element algorithms for the stokes problem

Based on two-grid discretizations, some local and parallel finite element algorithms for the Stokes problem are proposed and analyzed in this paper. These algorithms are motivated by the observation that for a solution to the Stokes problem, low frequency components can be approximated well by a relatively coarse grid and high frequency components can be computed on a fine grid by some local and parallel procedure. One technical tool for the analysis is some local a priori estimates that are also obtained in this paper for the finite element solutions on general shape-regular grids. Y. He was partially subsidized by the NSF of China 10671154 and the National Basic Research Program under the grant 2005CB321703; A. Zhou was partially supported by the National Science Foundation of China under the grant 10425105 and the National Basic Research Program under the grant 2005CB321704; J. Li was partially supported by the NSF of China under the grant 10701001. J. Xu was partially supported by Alexander von Humboldt Research Award for Senior US Scientists, NSF DMS-0609727 and NSFC-10528102.     

On the convergence of Newton iterations to non-stationary points

We study conditions under which line search Newton methods for nonlinear systems of equations and optimization fail due to the presence of singular non-stationary points. These points are not solutions of the problem and are characterized by the fact that Jacobian or Hessian matrices are singular. It is shown that, for systems of nonlinear equations, the interaction between the Newton direction and the merit function can prevent the iterates from escaping such non-stationary points. The unconstrained minimization problem is also studied, and conditions under which false convergence cannot occur are presented. Several examples illustrating failure of Newton iterations for constrained optimization are also presented. The paper also shows that a class of line search feasible interior methods cannot exhibit convergence to non-stationary points. This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported by Department of Energy grant DE-FG02-87ER25047-A004.This author was supported by National Science Foundation grant CCR-9987818 and Department of Energy grant DE-FG02-87ER25047-A004.     

Superlinear primal-dual affine scaling algorithms for LCP

We describe an interior-point algorithm for monotone linear complementarity problems in which primal-dual affine scaling is used to generate the search directions. The algorithm is shown to have global and superlinear convergence with Q-order up to (but not including) two. The technique is shown to be consistent with a potential-reduction algorithm, yielding the first potential-reduction algorithm that is both globally and superlinearly convergent.Corresponding author. The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234. This work was done while the author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.     

Remarks on the reflection principle for harmonic functions

The author was partially supported by the National Science Foundation under grant DMS-8618755.     

Inexact Newton methods for the nonlinear complementarity problem

An exact Newton method for solving a nonlinear complementarity problem consists of solving a sequence of linear complementarity subproblems. For problems of large size, solving the subproblems exactly can be very expensive. In this paper we study inexact Newton methods for solving the nonlinear, complementarity problem. In such an inexact method, the subproblems are solved only up to a certain degree of accuracy. The necessary accuracies that are needed to preserve the nice features of the exact Newton method are established and analyzed. We also discuss some extensions as well as an application. This research was based on work supported by the National Science Foundation under grant ECS-8407240.     

Non-Zenoness of a class of differential quasi-variational inequalities

The Zeno phenomenon of a switched dynamical system refers to the infinite number of mode switches in finite time. The absence of this phenomenon is crucial to the numerical simulation of such a system by time-stepping methods and to the understanding of the behavior of the system trajectory. Extending a previous result for a strongly regular differential variational inequality, this paper establishes that a certain class of non-strongly regular differential variational inequalities is devoid of the Zeno phenomenon. The proof involves many supplemental results that are of independent interest. Specialized to a frictional contact problem with local compliance and polygonal friction laws, this non-Zenoness result is of fundamental significance and the first of its kind. This work was based on research partially supported by the National Science Foundation under grants DMS-0508986 and IIS-0413227 awarded to Rensselaer Polytechnic Institute, where the original version of the paper was first written. The revision was based on research partially supported by the National Science Foundation under grant DMS awarded to the University of Illinois at Urbana-Champaign.     

Denumerable controlled Markov chains with average reward criterion: Sample path optimality

We consider discrete-time nonlinear controlled stochastic systems, modeled by controlled Makov chains with denumerable state space and compact action space. The corresponding stochastic control problem of maximizing average rewards in the long-run is studied. Departing from the most common position which usesexpected values of rewards, we focus on a sample path analysis of the stream of states/rewards. Under a Lyapunov function condition, we show that stationary policies obtained from the average reward optimality equation are not only average reward optimal, but indeed sample path average reward optimal, for almost all sample paths.Research supported by a U.S.-México Collaborative Research Program funded by the National Science Foundation under grant NSF-INT 9201430, and by CONACyT-MEXICO.Partially supported by the MAXTOR Foundation for applied Probability and Statistics, under grant No. 01-01-56/04-93.Research partially supported by the Engineering Foundation under grant RI-A-93-10, and by a grant from the AT&T Foundation.     

Solutions for the prescribing mean curvature equation

By variational methods, for a kind of Yamabe problem whose scalar curvature vanishes in the unit ball BN and on the boundary S^N-1 the mean curvature is prescribed, we construct multi-peak solutions whose maxima are located on the boundary as the parameter tends to 0^＋ under certain assumptions. We also obtain the asymptotic behaviors of the solutions.     

Error bounds for analytic systems and their applications

Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush—Kuhn—Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0–1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.The research of this author is based on work supported by the Natural Sciences and Engineering Research Council of Canada under grant OPG0090391.The research of this author is based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and by the Office of Naval Research under grant 4116687-01.     

Analyticity on circles for rational and real-analytic functions of two real variables

Conditions for rational and real-analytic functions of two real variables to be holomorphic are given in terms of holomorphic extendibility from families of circles. The first author was supported by the Israel Science Foundation, grant No. 279/02-1. The second author was partially supported by a grant from the Slovenian Ministry of Science and Technology. Both authors were supported by the Ministry of Science of Israel and the Ministry of Science and Technology of Slovenia, in the framework of the Program of Exchange by scientists.     

Collusive game solutions via optimization

A Nash-based collusive game among a finite set of players is one in which the players coordinate in order for each to gain higher payoffs than those prescribed by the Nash equilibrium solution. In this paper, we study the optimization problem of such a collusive game in which the players collectively maximize the Nash bargaining objective subject to a set of incentive compatibility constraints. We present a smooth reformulation of this optimization problem in terms of a nonlinear complementarity problem. We establish the convexity of the optimization problem in the case where each player's strategy set is unidimensional. In the multivariate case, we propose upper and lower bounding procedures for the collusive optimization problem and establish convergence properties of these procedures. Computational results with these procedures for solving some test problems are reported. It is with great honor that we dedicate this paper to Professor Terry Rockafellar on the occasion of his 70th birthday. Our work provides another example showing how Terry's fundamental contributions to convex and variational analysis have impacted the computational solution of applied game problems. This author's research was partially supported by the National Science Foundation under grant ECS-0080577. This author's research was partially supported by the National Science Foundation under grant CCR-0098013.