A polynomial time interior–point path–following algorithm for LCP based on Chen–Harker–Kanzow smoothing techniques

$$Osqrt{n}L$$ ); otherwise, the complexity bound is O(nL). The relations between our search direction and the one used in the standard interior-point algorithm are also discussed. Received September 9, 1996 / Revised version received December 22, 1997? Published online March 16, 1999     

Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem

This paper deals with the LCP (linear complementarity problem) with a positive semi-definite matrix. Assuming that a strictly positive feasible solution of the LCP is available, we propose ellipsoids each of which contains all the solutions of the LCP. We use such an ellipsoid for computing a lower bound and an upper bound for each coordinate of the solutions of the LCP. We can apply the lower bound to test whether a given variable is positive over the solution set of the LCP. That is, if the lower bound is positive, we know that the variable is positive over the solution set of the LCP; hence, by the complementarity condition, its complement is zero. In this case we can eliminate the variable and its complement from the LCP. We also show how we efficiently combine the ellipsoid method for computing bounds for the solution set with the path-following algorithm proposed by the authors for the LCP. If the LCP has a unique non-degenerate solution, the lower bound and the upper bound for the solution, computed at each iteration of the path-following algorithm, both converge to the solution of the LCP.Supported by Grant-in-Aids for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.Supported by Grant-in-Aids for Young Scientists (63730014) and for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.     

The Stein--Tikhomirov Method and a Nonclassical Central Limit Theorem

We present a simplified version of the Stein--Tikhomirov method realized by defining a certain operator in the class of twice differentiable characteristic functions. Using this method, we establish a criterion for the validity of a nonclassical central limit theorem in terms of characteristic functions.     

Bifurcation of reaction pathways: the set of valley ridge inflection points of a simple three-dimensional potential energy surface

This paper serves for the better understanding of the branching phenomenon of reaction paths of potential energy hypersurfaces in more than two dimensions. We apply the recently proposed reduced gradient following (RGF) method for the analysis of potential energy hypersurfaces having valley-ridge inflection (VRI) points. VRI points indicate the region of possible reaction path bifurcation. The relation between RGF and the so-called global Newton search for stationary points (Branin method) is shown. Using a 3D polynomial test surface, a whole 1D manifold of VRI points is obtained. Its relation to RGF curves, steepest descent and gradient extremals is discussed as well as the relation of the VRI manifold to bifurcation points of these curves. Received: 8 July 1998 / Accepted: 24 August 1998 / Published online: 23 November 1998     

Parametric Ghost Image Processes for Fixed-Charge Problems: A Study of Transportation Networks

We present a parametric approach for solving fixed-charge problems first sketched in Glover (1994). Our implementation is specialized to handle the most prominently occurring types of fixed-charge problems, which arise in the area of network applications. The network models treated by our method include the most general members of the network flow class, consisting of generalized networks that accommodate flows with gains and losses. Our new parametric method is evaluated by reference to transportation networks, which are the network structures most extensively examined, and for which the most thorough comparative testing has been performed. The test set of fixed-charge transportation problems used in our study constitutes the most comprehensive randomly generated collection available in the literature. Computational comparisons reveal that our approach performs exceedingly well. On a set of a dozen small problems we obtain ten solutions that match or beat solutions found by CPLEX 9.0 and that beat the solutions found by the previously best heuristic on 11 out of 12 problems. On a more challenging set of 120 larger problems we uniformly obtain solutions superior to those found by CPLEX 9.0 and, in 114 out of 120 instances, superior to those found by the previously best approach. At the same time, our method finds these solutions while on average consuming 100 to 250 times less CPU time than CPLEX 9.0 and a roughly equivalent amount of CPU time as taken by the previously best method.     

Interior path following primal-dual algorithms. part I: Linear programming

We describe a primal-dual interior point algorithm for linear programming problems which requires a total of number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea.     

A stabilized Nitsche‐type extended embedding mesh approach for 3D low‐ and high‐Reynolds‐number flows

This paper presents a stabilized extended finite element method (XFEM) based fluid formulation to embed arbitrary fluid patches into a fixed background fluid mesh. The new approach is highly beneficial when it comes to computational grid generation for complex domains, as it allows locally increased resolutions independent from size and structure of the background mesh. Motivating applications for such a domain decomposition technique are complex fluid‐structure interaction problems, where an additional boundary layer mesh is used to accurately capture the flow around the structure. The objective of this work is to provide an accurate and robust XFEM‐based coupling for low‐ as well as high‐Reynolds‐number flows. Our formulation is built from the following essential ingredients: Coupling conditions on the embedded interface are imposed weakly using Nitsche's method supported by extra terms to guarantee mass conservation and to control the convective mass transport across the interface for transient viscous‐dominated and convection‐dominated flows. Residual‐based fluid stabilizations in the interior of the fluid subdomains and accompanying face‐oriented fluid and ghost‐penalty stabilizations in the interface zone stabilize the formulation in the entire fluid domain. A detailed numerical study of our stabilized embedded fluid formulation, including an investigation of variants of Nitsche's method for viscous flows, shows optimal error convergence for viscous‐dominated and convection‐dominated flow problems independent of the interface position. Challenging two‐dimensional and three‐dimensional numerical examples highlight the robustness of our approach in all flow regimes: benchmark computations for laminar flow around a cylinder, a turbulent driven cavity flow at Re = 10000 and the flow interacting with a three‐dimensional flexible wall. Copyright © 2016 John Wiley & Sons, Ltd.     

Charge transfer excitations in TDDFT: A ghost‐hunter index

This work presents a new index, M _AC, enabling the on‐the‐fly detection of ghost charge transfer (CT) states, a major problem in time‐dependent density‐functional theory calculations. This computationally inexpensive index, derived as a modification of the Mulliken estimation of transition energy for CT excitations, relies on two basic ingredients: an effective CT distance, computed using our density‐based index (D _CT), and an orbital weighted estimation of the Ionization Potential and Electron Affinity. Some model systems, representative of both intermolecular and intramolecular CT excitations, were chosen as test cases. The robustness of our approach was verified by analyzing the behavior of functionals belonging to different classes (GGA, global hybrids and range separated hybrids). The results obtained show that ghost states are correctly spotted, also in the delicate case of intramolecular excitations displaying substantial donor‐bridge‐acceptor delocalization, in a regime for which the standard Mulliken formulation attends its limits. © 2017 Wiley Periodicals, Inc.     

A geometry‐based level set method for curvilinear overset grids with application to ship hydrodynamics

In a previous work (Int. J. Numer. Meth. Fluids 2007; 55 :867–897), we presented a two‐phase level set method to simulate air/water turbulent flows using curvilinear body‐fitted grids for ship hydrodynamics problems. This two‐phase level set method explicitly enforces jump conditions across the interface, thus resulting in a fully coupled representation of the air/water flow. Though the method works well with multiblock curvilinear grids, severe robustness problems were found when attempting to use it with overset grids. The problem was tracked to small unphysical level set discontinuities across the overset grids with large differences in curvature. Though negligible for single‐phase approaches, the problem magnifies with large density differences between the phases, causing computation failures. In this paper, we present a geometry‐based level set method for curvilinear overset grids that overcomes these difficulties. The level set transport and reinitialization equations are not discretized along grid coordinates, but along the upwind streamline and level set gradient directions, respectively. The method is essentially an unstructured approach that is transparent to the differences between overset grids, but still the discretization is under the framework of a finite differences approach. As a result, significant improvements in robustness and to a less extent in accuracy are achieved for the level set function interpolation between overset grids, especially with big differences in grid curvature. Example tests are shown for the case of bow breaking waves around the surface combatant model David Taylor Model Basin (DTMB) 5415 and for the steady‐state ONR Tumblehome DTMB 5613 with superstructure. In the first case, the results are compared against experimental data available and in the second against results of a semi‐coupled method. Copyright © 2011 John Wiley & Sons, Ltd.