Search

International audience; Simulating frictional contacts remains a challenging research topic in robotics. Recently, differentiable physics emerged and has proven to be a key element in modelbased Reinforcement Learning (RL) and optimal control fields. However, most of the current formulations deploy coarse approximations of the underlying physical principles. Indeed, the classic simulators lose precision by casting the Nonlinear Complementarity Problem (NCP) of frictional contact into a Linear Complementarity Problem (LCP) to simplify computations. Moreover, such methods deploy non-smooth operations and cannot be automatically differentiated. In this paper, we propose (i) an extension of the staggered projections algorithm for more accurate solutions of the problem of contacts with friction. Based on this formulation, we introduce (ii) a differentiable simulator and an efficient way to compute the analytical derivatives of the involved optimization problems. Finally, (iii) we validate the proposed framework with a set of experiments to present a possible application of our differentiable simulator. In particular, using our approach we demonstrate accurate estimation of friction coefficients and object masses both in synthetic and real experiments.

Based on a smoothing symmetric disturbance FB-function, a smoothing inexact Newton method for solving the nonlinear complementarity problem with P0-function was proposed. It was proved that under mild conditions, the given algorithm performed global and superlinear convergence without strict complementarity. For the same linear complementarity problem(LCP), the algorithm needs similar iteration times to the literature. However, its accuracy is improved by at least 4 orders with calculation time reduced by almost 50%, and the iterative number is insensitive to the size of the LCP. Moreover, fewer iterations and shorter time are required for solving the problem by using inexact Newton methods for different initial points.

The symmetric cone complementarity problem (denoted by SCCP) is a class of equilibrium optimization problems, and it contains the standard linear/nonlinear complementarity problem (LCP/NCP), the second-order cone complementarity problem (SOCCP) and the semidefinite complementarity problem (SDCP) as special cases. In this paper, we present a regularized smoothing Newton algorithm for SCCP by making use of Euclidean Jordan algebraic technique. Under suitable conditions, we obtain global convergence and local quadratic convergence of the proposed algorithm. Some numerical results are reported in this paper, which confirm the good theoretical properties of the proposed algorithm.

In this work the solution of the generalized nonlinear complementarity problem (GNCP) in polyhedral cones is addressed by two interior-point strategies: a perturbed Newton method and a predictor–corrector method. The latter may be considered as a member of the so-called Chebyshev–Halley family of methods for nonlinear systems, adapted to conform with the interior-point approach. Applied to a linear complementarity problem, the proposed method becomes the well-known Mehrotra's predictor–corrector method. Quadratic local convergence results are proved under the assumptions usually made for the GNCP. Numerical experiments validate the usage of both ideas for solving the GNCP in polyhedral cones. The proposed predictor–corrector method is implementable and competitive with Newton's method for some problems.

The generalized complementarity problem includes the well-known nonlinear complementarity problem and linear complementarity problem as special cases. In this paper, based on a class of smoothing functions, a smoothing Newton-type algorithm is proposed for solving the generalized complementarity problem. Under suitable assumptions, the proposed algorithm is well-defined and global convergent.

This paper formulates the dynamic equilibrium conditions for a single bottleneck model with heterogeneous commuters as a linear complementarity problem. This novel formulation offers a formal framework for the rigorous study and solution of a single bottleneck model with general heterogeneity parameter assumptions, enabling the adoption of well established complementarity theory and methods to analyze the model, and providing a significant contribution to the existing literature that either lacks a rigorous formulation or solves the problem under a limited set of heterogeneity parameter assumptions. The paper presents theoretical proofs for solution existence and uniqueness, and numerical results and insights for different heterogeneity assumptions. � 2009 Elsevier Ltd. All rights reserved.

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. Moreover, filter method, for its good numerical results, are extensively studied to handle nonlinear programming problems recently. In this paper, a modified quadratic subproblem is proposed. Based on it, we employ filter technique to tackle nonlinear complementarity problem. This method has no demand on initial point. The restoration phase, which is always used in traditional filter method, is not needed. Global convergence results of the proposed algorithm are established under suitable conditions. Some numerical results are reported in this paper.

In this paper a filled function method is suggested for solving the nonlinear complementarity problem. Firstly, the original problem is converted into a corresponding unconstrained optimization problem by using the Fischer-Burmeister function. Subsequently, a new filled function with one parameter is proposed for solving unconstrained optimization problems. Some properties of the filled function are studied and discussed without Lipschitz continuity condition. Finally, an algorithm based on the proposed filled function for solving the nonlinear complementarity problem is presented. The implementation of the algorithm on several test problems is reported with numerical results.

A mechanism for proving global convergence in filter-SQP (sequence of quadratic programming) method with the nonlinear complementarity problem (NCP) function is described for constrained nonlinear optimization problem. We introduce an NCP function into the filter and construct a new SQP-filter algorithm. Such methods are characterized by their use of the dominance concept of multi-objective optimization, instead of a penalty parameter whose adjustment can be problematic. We prove that the algorithm has global convergence and superlinear convergence rates under some mild conditions.

This paper formulates the continuous network design problem as a mathematical program with complementarity constraints (MPCC), with the upper level a nonlinear programming problem and the lower level a nonlinear complementarity problem. Unlike in most previous studies, the proposed framework is more general, in which both symmetric and asymmetric user equilibria can be captured. By applying the complementarity slackness condition of the lower-level problem, the original bilevel formulation can be converted into a single-level and smooth nonlinear programming problem. In order to solve the problem, a relaxation scheme is applied by progressively restricting the complementarity condition, which has been proven to be a rigorous approach under certain conditions. The model and solution algorithm are tested for well-known network design problems and promising results are shown.

In this article a detailed analytical formulation of the unilateral contact boundary conditions with Coulomb's law of dry friction is first attempted and the quasi-static contact problem between 3-D elastic bodies is studied thereafter. Discretizing the bodies by the Finite Element Method, introducing fictitious contact bonds and using the concept of the equivalent structural system, an incremental Nonlinear Complementarity Problem is finally formulated. Then, using additional simplifying assumptions, this problem can be transformed into an incremental Linear Complementarity Problem.

In this article, the non-smooth contact dynamics of multi-body systems is formulated as a complementarity problem. Minimal coordinates operational space formulation is used to derive the dynamics equations of motion. Depending on the approach used for modeling Coulomb’s friction, the complementarity problem can be posed either as a linear or a nonlinear problem. Both formulations are studied in this paper. An exact modeling of the friction cone leads to a nonlinear complementarity problem (NCP) formulation whereas a polyhedral approximation of the friction cone results in a linear complementarity problem (LCP) formulation. These complementarity problems are further recast as non-smooth unconstrained optimization problems, which are solved by employing a class of Levenberg-Marquardt algorithms. The necessary theory detailing these techniques is discussed and five schemes are implemented to solve contact dynamics problems. A simple test case of a sphere moving on a plane surface is used to validate these schemes, while a twelve-link pendulum example is chosen to compare the speed and accuracy of the schemes presented in this paper.Copyright © 2014 by ASME

In this paper, we present a neural network approach for solving nonlinear complementarity problems. The neural network model is derived from an unconstrained minimization reformulation of the complementarity problem. The existence and the convergence of the trajectory of the neural network are addressed in detail. In addition, we also explore the stability properties, such as the stability in the sense of Lyapunov, the asymptotic stability and the exponential stability, for the neural network model. The theory developed here is also valid for neural network models derived from a number of reformulation methods for nonlinear complementarity problems. Simulation results are also reported.

We investigate the properties of a new merit function which allows us to reduce a nonlinear complementarity problem to an unconstrained global minimization one. Assuming that the complementarity problem is defined by a $P_0$-function, we prove that every stationary point of the unconstrained problem is a global solution; furthermore, if the complementarity problem is defined by a uniform $P$-function, the level sets of the merit function are bounded. The properties of the new merit function are compared with those of Mangasarian--Solodov's implicit Lagrangian and Fukushima's regularized gap function. We also introduce a new simple active-set local method for the solution of complementarity problems and show how this local algorithm can be made globally convergent by using the new merit function.

When the nonlinear complementarity problem is reformulated as that of finding the zero of a self-mapping, the norm of the selfmapping serves naturally as a merit function for the problem. We study the growth behavior of such a merit function. In particular, we show that, for the linear complementarity problem, whether the merit function is coercive is intimately related to whether the underlying matrix is aP-matrix or a nondegenerate matrix or anRo-matrix. We also show that, for the more popular choices of the merit function, the merit function is bounded below by the norm of the natural residual raised to a positive integral power. Thus, if the norm of the natural residual has positive order of growth, then so does the merit function.

We show that the Cottle—Dantzig generalized linear complementarity problem (GLCP) is equivalent to a nonlinear complementarity problem (NLCP), a piecewise linear system of equations (PLS), a multiple objective programming problem (MOP), and a variational inequalities problem (VIP). On the basis of these equivalences, we provide an algorithm for solving problem GLCP.

This paper is concerned with the mixed linear complementarity problem and the role it and its variants play in the stability analysis of the nonlinear complementarity problem and the Karush-Kuhn-Tucker system of a variational inequality problem. Under a nonsingular assumption, the mixed linear complementarity problem can be converted to the standard problem; in this case, the rich theory of the latter can be directly applied to the former. In this work, we employ degree theory to derive some sufficient conditions for the existence of a solution to the mixed linear complementarity problem in the absence of the nonsingularity property. Next, we extend this existence theory to the mixed nonlinear complementarity problem and establish a main stability result under a certain degree-theoretic assumption concerning the linearized problem. We then specialize this stability result and its consequences to the parametric variational inequality problem under the assumption of a unique set of multipliers. Finally, we consider the latter problem with the uniqueness assumption of the multipliers replaced by a convexity assumption and obtain stability results under some weak second-order conditions. In addition to the new existence results for the mixed linear complementarity problem, the main contributions of this paper in the stability category are the following: a resolution to a conjecture concerning the local solvability of a parametric variational inequality, the use of the generalized linear complementarity problem as a tool to broaden the second-order conditions, the characterization of the solution stability of the linear complementarity problem and the affine variational inequality problem in terms of the solution isolatedness under some weak hypotheses, and various stability theorems under some weak second-order conditions.

The mapping in a nonlinear complementarity problem may be discontinuous. The integral global optimization algorithm is proposed to solve a nonlinear complementarity problem with a robust piecewise continuous mapping. Numerical examples are given to illustrate the effectiveness of the algorithm.

We study mathematical programming problems with complementarity constraints (MPCC) from the topological point of view. The (topological) stability of the MPCC feasible set is addressed. Therefore, we introduce Mangasarian-Fromovitz condition (MFC) and its stronger version (SMFC). Under SMFC, the MPCC feasible set is shown to be a Lipschitz manifold. The links to other well-known constraint qualifications for MPCCs are elaborated. The critical point theory for MPCCs is presented. We also characterize the strong stability of C-stationary points for MPCC, dealing with parametric aspects for MPCCs.

This paper presents a new method for solving three-dimensional frictional contact problems. A semismooth Newton method for solving nonlinear complementarity problems is proposed based on generalized Fischer-Burmeister functions. The parametric variational principle and parametric quadratic programming method are applied to the analysis of the three-dimensional frictional contact problem. The solution of the contact problem is finally reduced to a linear complementarity problem. Then the semismooth Newton method presented is employed to solve the problem. Results of numerical experiments demonstrate the efficiency and reliability of the method proposed.

Dynamical systems include measuring sensor inputs of phenomena to yield accurate predictions of the evolving sensor outputs or to determine optimal control management policies based on sensor data. The input and output sets of the system may be generalized and transformed with respect to the sets of sensors available and formal deductive methods and chaos theory may be formulated to obtain Dynamical Inquiring Systems over a horizon to yield solutions which will be precise and be certainty equivalent to the future results of the phenomenon.The aim of this chapter is to present a formalization of Mathematical Systems Theory to demonstrate the theoretical basis of nonlinear dynamical chaotic systems solved by simultaneous estimation and optimal control processes and to present accurate predictions based on generalized sensor data of many forms both in input and output such as dynamic malfunctioning of systems including engineering, medical, economic, and environmental inquiring systems.

This paper is concerned with two well-known families of iterative methods for solving the linear and nonlinear complementarity problems. For the linear complementarity problem, we consider the class of matrix splitting methods and establish, under a finiteness assumption on the number of solutions, a necessary and sufficient condition for the convergence of the sequence of iterates produced. A rate of convergence result for this class of methods is also derived under a stability assumption on the limit solution. For the nonlinear complementarity problem, we establish the convergence of the Newton method under the assumption of a “pseudo-regular” solution which generalizes Robinson's concept of a “strongly regular” solution. In both instances, the convergence proofs rely on a common sensitivity result of the linear complementarity problem under perturbation.

Nonlinear complementarity problem with P0-function is studied Based on a new class of one-parametric nonlinear complementarity functions, the problem is approximated by a family of parameterized smooth equations and a one-step smoothing Newton method is presented The proposed algorithm only need to solve one system of linear equations and perform one line search per iteration It is proved to be convergent globally and superlinearly without strict complementarity Moreover, the algorithm has locally quadratic convergence under mild conditions.

In this paper, we present an extension to the NE/SQP method; the latter is a robust algorithm that we proposed for solving the nonlinear complementarity problem in an earlier article. In this extended version of NE/SQP, instead of exactly solving the quadratic program subproblems, approximate solutions are generated via an inexact rule.Under a proper choice for this rule, this inexact method is shown to inherit the same convergence properties of the original NE/SQP method. In addition to developing the convergence theory for the inexact method, we also present numerical results of the algorithm tested on two problems of varying size.

In this paper an eigenvalue complementarity problem (EiCP) is studied, which finds its origins in the solution of a contact problem in mechanics. The EiCP is shown to be equivalent to a Nonlinear Complementarity Problem, a Mathematical Programming Problem with Complementarity Constraints and a Global Optimization Problem. A finite Reformulation–Linearization Technique (Rlt)-based tree search algorithm is introduced for processing the EiCP via the lattermost of these formulations. Computational experience is included to highlight the efficacy of the above formulations and corresponding techniques for the solution of the EiCP. http://dx.doi.org/10.1007/s10589-007-9017-0

The versatility of a robot to perform a task is limited principally by the flexibilityof its end-effector. In the last years, research has been focused on the development of a hand with several fingers since these devices are capable of manipulating and grasping objects of different forms. A dexterous manipulation system, composed of a robot hand with several fingers and an object that will be held or manipulated, could be modeled as a set of rigid bodies in contact. The dynamics of several rigid bodies in contact tries to predict the accelerations and forces at the contact points of the set of rigid bodies with Coulomb friction. The calculation of such forces allows us to determine if the contact is maintained or disappears and to plan a determined action. The equations that describe the problem form a system of differential algebraic equations. In this contribution the problem is reformulated as a mixed nonlinear complementarity problem (MNCP). Then, an optimization problem with box constraints associated to the MNCP is presented using an adequate merit function. Conditions about the equivalence between the problems are established. Finally, the optimization problem is solved using a robust and efficient algorithm. Encouraging numerical results are reported.

In the paper, we examine conditions that guarantee the existence of a solution to the parametric nonlinear complementarity problem with a monotone with respect to x mapping f: R

Replicator systems are a class of first order, nonlinear differential equations, arising in an extraordinary variety of modeling situations. It is shown that finding the stationary points of replicator systems is equivalent to solving a nonlinear complementarity problem. One consequence is that it becomes possible to use replicator systems to solve very large instances of the NP-complete graph bisection problem. The methodological and philosophical import of their equivalence with complementarity problems (upto stationarity) is discussed.

Recently, much effort has been made in solving and analyzing the nonlinear complementarity problem (NCP) by means of a reformulation of the problem as an equivalent unconstrained optimization problem involving a merit function. In this paper, we propose a new merit function for the NCP and show several favorable properties of the proposed function. In particular, we give conditions under which the function provides a global error bound for the NCP and conditions under which its level sets are bounded. Moreover, we propose a new derivative-free descent algorithm for solving the NCP based on this function. We show that any accumulation point generated by the algorithm is a solution of the NCP under the monotonicity assumption on the problem. Also, we prove that the sequence generated by the algorithm converges linearly to the solution under the strong monotonicity assumption.

The solution of an optimal power flow (OPF) problem by interior-point (IP) and non-interior-point (NIP) methods for nonlinear programming (NLP) is described. The IP and NIP algorithms are derived in details from a general NLP problem model that is suitable to express most OPF problems. The NIP algorithm, in contrast to IP algorithms, can start from arbitrary points. Numerical results illustrate the viability of the proposed algorithms as applied to several power networks that range in size from 30 to 2098 nodes.

We describe some first- and second-order optimality conditions for mathematical programs with equilibrium constraints (MPEC). Mathematical programs with parametric nonlinear complementarity constraints are the focus. Of interest is the result that under a linear independence assumption that is standard in nonlinear programming, the otherwise combinatorial problem of checking whether a point is stationary for an MPEC is reduced to checking stationarity of single nonlinear program. We also present a piecewise sequential quadratic programming (PSQP) algorithm for solving MPEC. Local quadratic convergence is shown under the linear independence assumption and a second-order sufficient condition. Some computational results are given.

QPCOMP is an extremely robust algorithm for solving mixed nonlinear complementarity problems that has fast local convergence behavior. Based in part on the NE/SQP method of Pang and Gabriel [14], this algorithm represents a significant advance in robustness at no cost in efficiency. In particular, the algorithm is shown to solve any solvable Lipschitz continuous, continuously differentiable, pseudo-monotone mixed nonlinear complementarity problem. QPCOMP also extends the NE/SQP method for the nonlinear complementarity problem to the more general mixed nonlinear complementarity problem. Computational results are provided, which demonstrate the effectiveness of the algorithm.

In this paper we develop an algorithm for solving a version of the (static) traffic equilibrium problem in which the cost incurred on each path is not simply the sum of the costs on the arcs that constitute that path. The method we describe is based on the recent NE/SQP algorithm, a fast and robust technique for solving nonlinear complementarity problems. Finally, we present an example that illustrates both the importance of using nonadditive costs and the effectiveness of the NE/SQP method.

We study some iterative methods for the General Order Complementarity Problem associating some heterotonic operators.

In this paper we prove the following existence and uniqueness theorem for the nonlinear complementarity problem by using the Banach contraction principle. If T: K → H is strongly monotone and lipschitzian with k2 < 2c < k2+1, then there is a unique y ∈ K, such that Ty ∈ K* and (Ty, y) = 0 where H is a Hilbert space, K is a closed convex cone in H, and K* the polar cone.

It is shown that McCormick's second order sufficient optimality conditions are also necessary for a solution to a quadratic program to be locally unique and hence these conditions completely characterize a locally unique solution of any quadratic program. This result is then used to give characterizations of a locally unique solution to the linear complementarity problem. Sufficient conditions are also given for local uniqueness of solutions of the nonlinear complementarity problem.

In the paper “A nonlinear complementarity problem for monotone functions”, Bull. Austral. Math. Soc. 20 (1979), 227–231, Nanda and Patel proved that for a monotone function that fixes the origin, the complementarity problem admits a solution. In this note we give a short proof of the same result under weaker assumptions.