A new polynomial time method for a linear complementarity problem

The purpose of this paper is to present a new polynomial time method for a linear complementarity problem with a positive semi-definite matrix. The method follows a sequence of points. If we generate the sequence on a path, we can construct a path following method, and if we generate the sequence based on a potential function, we can construct a potential reduction method. The method has the advantage that it requires at most iterations for any initial feasible point whose components lie between 2^–O(L) and 2^O(L).Research was supported in part by Grant-in-Aids for Encouragement of Young Scientists (63730014) and for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.     

Global convergence in infeasible-interior-point algorithms

This paper presents a wide class of globally convergent interior-point algorithms for the nonlinear complementarity problem with a continuously differentiable monotone mapping in terms of a unified global convergence theory given by Polak in 1971 for general nonlinear programs. The class of algorithms is characterized as: Move in a Newton direction for approximating a point on the path of centers of the complementarity problem at each iteration. Starting from a strictly positive but infeasible initial point, each algorithm in the class either generates an approximate solution with a given accuracy or provides us with information that the complementarity problem has no solution in a given bounded set. We present three typical examples of our interior-point algorithms, a horn neighborhood model, a constrained potential reduction model with the use of the standard potential function, and a pure potential reduction model with the use of a new potential function.Research supported in part by Grant-in-Aids for Co-Operative Research (03832017) of the Japan Ministry of Education, Science and Culture.Corresponding author.     

A primal—dual infeasible-interior-point algorithm for linear programming

As in many primal—dual interior-point algorithms, a primal—dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not confine the iterates within the feasible region. This paper proposes a step length rule with which the algorithm takes large distinct step lengths in the primal and dual spaces and enjoys the global convergence.Part of this research was done when M. Kojima and S. Mizuno visited at the IBM Almaden Research Center. Partial support from the Office of Naval Research under Contract N00014-91-C-0026 is acknowledged.Supported by Grant-in-Aids for Co-operative Research (03832017) of The Japan Ministry of Education, Science and Culture.Supported by Grant-in-Aids for Encouragement of Young Scientist (03740125) and Co-operative Research (03832017) of The Japan Ministry of Education, Science and Culture.     

A Smoothing-Type Algorithm for Solving Linear Complementarity Problems with Strong Convergence Properties

In this paper, we construct an augmented system of the standard monotone linear complementarity problem (LCP), and establish the relations between the augmented system and the LCP. We present a smoothing-type algorithm for solving the augmented system. The algorithm is shown to be globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, if the LCP has a solution, then the algorithm either generates a maximal complementary solution of the LCP or detects correctly solvability of the LCP, and in the latter case, an existing smoothing-type algorithm can be directly applied to solve the LCP without any additional assumption and it generates a maximal complementary solution of the LCP; and that if the LCP is infeasible, then the algorithm detect correctly infeasibility of the LCP. To the best of our knowledge, such properties have not appeared in the existing literature for smoothing-type algorithms. This work was partially supported by the National Natural Science Foundation of China (Grant No. 10571134), the Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200), and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems

This paper provides an analysis of the polynomiality of primal-dual interior point algorithms for nonlinear complementarity problems using a wide neighborhood. A condition for the smoothness of the mapping is used, which is related to Zhu’s scaled Lipschitz condition, but is also applicable to mappings that are not monotone. We show that a family of primal-dual affine scaling algorithms generates an approximate solution (given a precision ε) of the nonlinear complementarity problem in a finite number of iterations whose order is a polynomial ofn, ln(1/ε) and a condition number. If the mapping is linear then the results in this paper coincide with the ones in Jansen et al., SIAM Journal on Optimization 7 (1997) 126–140. Research supported in part by Grant-in-Aids for Encouragement of Young Scientists (06750066) from the Ministry of Education, Science and Culture, Japan. Research supported by Dutch Organization for Scientific Research (NWO), grant 611-304-028     

Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems

In this paper, we propose a Newton-type method for solving a semismooth reformulation of monotone complementarity problems. In this method, a direction-finding subproblem, which is a system of linear equations, is uniquely solvable at each iteration. Moreover, the obtained search direction always affords a direction of sufficient decrease for the merit function defined as the squared residual for the semismooth equation equivalent to the complementarity problem. We show that the algorithm is globally convergent under some mild assumptions. Next, by slightly modifying the direction-finding problem, we propose another Newton-type method, which may be considered a restricted version of the first algorithm. We show that this algorithm has a superlinear, or possibly quadratic, rate of convergence under suitable assumptions. Finally, some numerical results are presented. Supported by Research Fellowships of the Japan Society for the Promotion of Science for Young Scientists. Supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan.     

Global Error Bound for the Generalized Linear Complementarity Problem over a Polyhedral Cone

In this paper, the global error bound estimation for the generalized linear complementarity problem over a polyhedral cone (GLCP) is considered. To obtain a global error bound for the GLCP, we first develop some equivalent reformulations of the problem under milder conditions and then characterize the solution set of the GLCP. Based on this, an easily computable global error bound for the GLCP is established. The results obtained in this paper can be taken as an extension of the existing global error bound for the classical linear complementarity problems. This work was supported by the Research Grant Council of Hong Kong, a Chair Professor Fund of The Hong Kong Polytechnic University, the Natural Science Foundation of China (Grant No. 10771120) and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

On the existence of Feller semigroups with discontinuous coefficients II

This paper is devoted to the functional analytic approach to the problem of existence of Markov processes with Dirichlet boundary condition, oblique derivative boundary condition and first-order Wentzell boundary condition for second-order, uniformly elliptic differential operators with discontinuous coefficients. More precisely, we construct Feller semigroups associated with absorption, reflection, drift and sticking phenomena at the boundary. The approach here is distinguished by the extensive use of the ideas and techniques characteristic of the recent developments in the Calderon- Zygmund theory of singular integral operators with non-smooth kernels.     

The extended linear complementarity problem

In this paper we define the Extended Linear Complementarity Problem (ELCP), an extension of the well-known Linear Complementarity Problem (LCP). We show that the ELCP can be viewed as a kind of unifying framework for the LCP and its various generalizations. We study the general solution set of an ELCP and we develop an algorithm to find all its solutions. We also show that the general ELCP is an NP-hard problem.This paper presents research results of the Belgian programme on interuniversity attraction poles (IUAP-50) initiated by the Belgian State, Prime Minister's Office for Science, Technology and Culture. The scientific responsibility is assumed by its authors.Supported by the N.F.W.O. (Belgian National Fund for Scientific Research).     

Bifurcation phenomena associated to a class of p-Laplacian like operators

 Global bifurcation of positive solutions for some degenerate quasilinear elliptic problems is considered. The uniform estimate of the gradient of weak solutions is given. This estimate is crucial in our arguments. Received: 10 August 2001 Supported in part by Grant-in-Aid for Scientific Research (No. 11640207), Ministry of Education, Science, Sports and Culture, Japan. Mathematics Subject Classification (2000): 35B32, 35J25, 35J70     

Theoretical and numerical investigation of the D-gap function for box constrained variational inequalities

The D-gap function, recently introduced by Peng and further studied by Yamashita et al., allows a smooth unconstrained minimization reformulation of the general variational inequality problem. This paper is concerned with the D-gap function for variational inequality problems over a box or, equivalently, mixed complementarity problems. The purpose of this paper is twofold. First we investigate theoretical properties in depth of the D-gap function, such as the optimality of stationary points, bounded level sets, global error bounds and generalized Hessians. Next we present a nonsmooth Gauss-Newton type algorithm for minimizing the D-gap function, and report extensive numerical results for the whole set of problems in the MCPLIB test problem collection. The work of this author was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports and Culture, Japan.     

Ideal polytopes and face structures of some combinatorial optimization problems

Given a finite setX and a family of feasible subsetsF ofX, the 0–1 polytope P (F is defined as the convex hull of all the characteristic vectors of members ofF We show that under a certain assumption a special type of face ofP(F) is equivalent to the ideal polytope of some pseudo-ordered set. Examples of families satisfying the assumption are those related to the maximum stable set problem, set packing and set partitioning problems, and vertex coloring problem. Using this fact, we propose a new heuristic for such problems and give results of our preliminary computational experiments for the maximum stable set problem.Supported by a JSPS Fellowship for Young Scientists.Supported by Grant-in-Aids for Co-operative Research (06740147) of the Ministry of Education, Science and Culture.     

Hybrid Approach with Active Set Identification for Mathematical Programs with Complementarity Constraints

We consider a mathematical program with complementarity constraints (MPCC). Our purpose is to develop methods that enable us to compute a solution or a point with some kind of stationarity to MPCC by solving a finite number of nonlinear programs. We apply an active set identification technique to a smoothing continuation method (Ref. 1) and propose a hybrid algorithm for solving MPCC. We develop also two modifications: one makes use of an index addition strategy; the other adopts an index subtraction strategy. We show that, under reasonable assumptions, all the proposed algorithms possess a finite termination property. Further discussions and numerical experience are given as well This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and Culture of Japan. The authors are grateful to Professor Paul Tseng for helpful suggestions on an earlier version of the paper.     

Infinitary Jónsson functions and elementary embeddings

Summary We give an extender characterization of a very strong elementary embedding between transitive models of set theory, whose existence is known as the axiom I2. As an application, we show that the positive solution of a partition problem raised by Magidor would refute it.Mathematics subject classifications (1991): 03E55, 03E05This work is part of the author's thesis written under the direction of Professor K. Eda, to whom he is very grateful. He also wishes to thank the referee and Professor A. Blass for their careful reading and helpful suggestions. This research was partially supported by Grant-in-Aid for Scientific Research (No. 04302009), Ministry of Education, Science and Culture     

Superlinear Noninterior One-Step Continuation Method for Monotone LCP in the Absence of Strict Complementarity

We propose a noninterior continuation method for the monotone linear complementarity problem (LCP) by modifying the Burke–Xu framework of the noninterior predictor-corrector path-following method (Refs. 1–2). The new method solves one system of linear equations and carries out only one line search at each iteration. It is shown to converge to the LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution. Our analysis of the continuation method is based on a broader class of the smooth functions introduced by Chen and Mangasarian (Ref. 3).     

On the convergence of partial differential equations of parabolic type with rapidly oscillating coefficients to stochastic partial differential equations

In this paper we consider the convergence of the solutions to a sequence of partial differential equations of parabolic type with rapidly oscillating coefficients to the solutions of a stochastic partial differential equation. We use the martingale method and the characteristic functional to prove that the martingale problem has a unique solution. Our emphasis is in treating strongly mixing noises.This research was partially supported by Stifting Volkswagenwerk through Forschungszentrum BiBoS Universität Bielefeld and Grant-in-Aid for General Scientific Research (C) 61540162, the Ministry of Education, Science and Culture (Japan). Presented at the International Workshop on Diffusion Approximations and Related Topics, IISA, Laxenburg, Austria, 29 June to 3 July 1987.     

Characterization of totally umbilic hypersurfaces in a space form by circles

In this paper we characterize totally umbilic hypersurfaces in a space form by a property of the extrinsic shape of circles on hypersurfaces. This characterization corresponds to characterizations of isoparametric hypersurfaces in a space form by properties of the extrinsic shape of geodesics due to Kimura-Maeda.The first author was partially supported by Grant-in-Aid for Scientific Research (C) No. 14540075, Ministry of Education, Science, Sports and Culture. The second author was partially supported by Grant-in-Aid for Scientific Research (C) No. 14540080, Ministry of Education, Science, Sports and Culture.     

Equivalence of the generalized complementarity problem to differentiable unconstrained minimization

We consider an unconstrained minimization reformulation of the generalized complementarity problem (GCP). The merit function introduced here is differentiable and has the property that its global minimizers coincide with the solutions of GCP. Conditions for its stationary points to be global minimizers are given. Moreover, it is shown that the level sets of the merit function are bounded under suitable assumptions. We also show that the merit function provides global error bounds for GCP. These results are based on a condition which reduces to the condition of the uniform P-function when GCP is specialized to the nonlinear complementarity problem. This condition also turns out to be useful in proving the existence and uniqueness of a solution for GCP itself. Finally, we obtain as a byproduct an error bound result with the natural residual for GCP.We thank Jong-Shi Pang for his valuable comments on error bound results with the natural residual for the nonlinear complementarity problem. We are also grateful to the anonymous referees for some helpful comments. The research of the second author was supported in part by the Science Research Grant-in-Aid from the Ministry of Education, Science, and Culture, Japan.     

Robust solution of monotone stochastic linear complementarity problems

We consider the stochastic linear complementarity problem (SLCP) involving a random matrix whose expectation matrix is positive semi-definite. We show that the expected residual minimization (ERM) formulation of this problem has a nonempty and bounded solution set if the expected value (EV) formulation, which reduces to the LCP with the positive semi-definite expectation matrix, has a nonempty and bounded solution set. We give a new error bound for the monotone LCP and use it to show that solutions of the ERM formulation are robust in the sense that they may have a minimum sensitivity with respect to random parameter variations in SLCP. Numerical examples including a stochastic traffic equilibrium problem are given to illustrate the characteristics of the solutions.     

A tagged particle process in the Boltzmann-Grad limit for the Broadwell modell

Summary We study a tagged particle process for a model dynamical system in which identical particles move deterministically with discrete velocities, initially starting from a random configuration. We pass to the Boltzmann-Grad limit so that the tagged particle process converges to a nontrivial process (for short times). We can show that recollisions are vanishing in this limit, and this fact may have one expect that the limiting process would be Markovian. Nevertheless it is not Markovian, for which claim we give intuitive reasoning as well as a mathematical proof.Supported in part by Grant-in-Aid for Scientific Research (No. 62302006), Ministry of Education, Science and Culture