A mortar mimetic finite difference method on non-matching grids

We consider mimetic finite difference approximations to second order elliptic problems on non-matching multiblock grids. Mortar finite elements are employed on the non-matching interfaces to impose weak flux continuity. Optimal convergence and, in certain cases, superconvergence is established for both the scalar variable and its flux. The theory is confirmed by computational results. Supported by the US Department of Energy, under contractW-7405-ENG-36. LA-UR-04-4740. Partially supported by NSF grants EIA 0121523 and DMS 0411413, by NPACI grant UCSD 10181410, and by DOE grant DE-FGO2-04ER25617. Partially supported by NSF grants DMS 0107389, DMS 0112239 and DMS 0411694 and by DOE grant DE-FG02-04ER25618.     

An asymptotic analysis of two-phase fluid mixing

We study the motion of the slightly compressible multi-phase flow model proposed by Chen, Glimm, Sharp and Zhang. The interface velocity and constitutive law are analyzed by derivation of the exact quantity. Using singular perturbation theory, a formal asymptotic expansion is derived for the solution of the compressible equations. An asymptotic analysis in the incompressible limit, for slightly compressible flows supplies important new information to resolve nonuniqueness of the pressure difference between the two fluid species of the incompressible flow equations.Supported in part by the U.S. Department of Energy DE-FG02-90ER25084, DE-FG02-989ER2536, DE-FG03-98DP00206, the National Science Foundation DMS-0102480, the Army Research Office grant DAAD19-01-0642 and Los Alamos National Laboratory.Supported in part by the Clay Mathematics Institute.     

Minimal surfaces bounded by convex curves in parallel planes

The research described in this paper was supported by research grant DE-FG02-86ER250125 of the Applied Mathematical Science subprogram of Office of Energy Research, U.S. Department of Energy, and National Science Foundation grant DMS-8900285.     

The maximum principle at infinity for minimal surfaces in flat three manifolds

The research described in this paper was supported by research grant DE-FG02-86ER250125 of the Applied Mathematical Science subprogram of Office of Energy Research, U.S. Department of Energy, and National Science Foundation grant DMS-8611574.     

Equivariant entire cyclic cohomology: I. Finite groups

We extend the framework of entire cyclic cohomology to the equivariant context.Supported in part by the Department of Energy under Grant DE-FG02-88ER25065.     

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.     

The structure of singly-periodic minimal surfaces

The research described in this paper was supported by research grant DE-FG02-86ER250125 of the Applied Mathematical Science subprogram of Office of Energy Research, U.S. Department of Energy, and National Science Foundation grants DMS-8611574 and DMS-8802858     

Embedded minimal surfaces with an infinite number of ends

The research described in this paper was supported by research grant DE-FG02-86ER250125 of the Applied Mathematical Science subprogram of the Office of Energy Research, U.S. Department of Energy, and National Science Foundation grants DMS-8503350 and DMS-8611574     

Chern character in equivariant entire cyclic cohomology

We construct the Chern character in the equivariant entire cyclic cohomology. We prove a general index theorem for theG-invariant Dirac operator.Supported in part by the Department of Energy under Grant DE-FG02-88ER25065.     

Quadratic programming with one negative eigenvalue is NP-hard

We show that the problem of minimizing a concave quadratic function with one concave direction is NP-hard. This result can be interpreted as an attempt to understand exactly what makes nonconvex quadratic programming problems hard. Sahni in 1974 [8] showed that quadratic programming with a negative definite quadratic term (n negative eigenvalues) is NP-hard, whereas Kozlov, Tarasov and Haijan [2] showed in 1979 that the ellipsoid algorithm solves the convex quadratic problem (no negative eigenvalues) in polynomial time. This report shows that even one negative eigenvalue makes the problem NP-hard.This author's work supported by the Applied Mathematical Sciences Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013. A000 and in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS 8920550.     

The principal pivoting method revisited

The principal pivoting method (PPM) for the linear complementarity problem (LCP) is shown to be applicable to the class of LCPs involving the newly identified class of sufficient matrices.Research partially supported by the National Science Foundation grant DMS-8800589, U.S. Department of Energy grant DE-FG03-87ER25028 and Office of Naval Research grant N00014-89-J-1659.Dedicated to George B. Dantzig on the occasion of his 75th birthday.     

Local minima for indefinite quadratic knapsack problems

We consider the complexity of finding a local minimum for the nonconvex Quadratic Knapsack Problem. Global minimization for this example of quadratic programming is NP-hard. Moré and Vavasis have investigated the complexity of local minimization for the strictly concave case of QKP; here we extend their algorithm to the general indefinite case. Our main result is an algorithm that computes a local minimum in O(n(logn)²) steps. Our approach involves eliminating all but one of the convex variables through parametrization, yielding a nondifferentiable problem. We use a technique from computational geometry to address the nondifferentiable problem.Supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, Department of Energy, under contract W-31-109-Eng-38, in part by a Fannie and John Hertz Foundation graduate fellowship, and in part by Department of Energy grant DE-FG02-86ER25013.A000.     

Asymptotic expansions of some matrix argument hypergeometric functions, with applications to macromolecules

We have studied the asymptotics of two special two-matrix hypergeometric functions. The validity of the asymptotic expressions for these functions is seen in several selected numerical comparisons between the exact and asymptotic results. These hypergeometric functions find applications in configuration statistics of macromolecules as well as multivariate statistics.This work was supported by grant DE-FG06-84ER45123 from the Department of Energy, U.S.A.     

Duality,crossing and MacLane’s coherence

It is shown that MacLane’ rectangle, pentagon and hexagon identities in category theory, when applied in particle physics to duality diagrams or to rational conformal field theories in two dimensions, yield the necessary physical algebraic constraints. Supported in part by DOE grant no. DE-FG05-85ER40200 Supported by US-Israel BSF grant 87-00009/1.     

An algorithm for the fast solution of symmetric linear complementarity problems

This paper studies algorithms for the solution of mixed symmetric linear complementarity problems. The goal is to compute fast and approximate solutions of medium to large sized problems, such as those arising in computer game simulations and American options pricing. The paper proposes an improvement of a method described by Kocvara and Zowe (Numer Math 68:95–106, 1994) that combines projected Gauss–Seidel iterations with subspace minimization steps. The proposed algorithm employs a recursive subspace minimization designed to handle severely ill-conditioned problems. Numerical tests indicate that the approach is more efficient than interior-point and gradient projection methods on some physical simulation problems that arise in computer game scenarios. The research of J. L. Morales was supported by Asociación Mexicana de Cultura AC and CONACyT-NSF grant J110.388/2006. The research of J. Nocedal was supported by National Science Foundation grant CCF-0514772, Department of Energy grant DE-FG02-87ER25047-A004 and a grant from the Intel Corporation.     

On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds

We consider a new algorithm, an interior-reflective Newton approach, for the problem of minimizing a smooth nonlinear function of many variables, subject to upper and/or lower bounds on some of the variables. This approach generatesstrictly feasible iterates by using a new affine scaling transformation and following piecewise linear paths (reflection paths). The interior-reflective approach does not require identification of an activity set. In this paper we establish that the interior-reflective Newton approach is globally and quadratically convergent. Moreover, we develop a specific example of interior-reflective Newton methods which can be used for large-scale and sparse problems.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000, and in part by NSF, AFOSR, and ONR through grant DMS-8920550, and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.Corresponding author.     

Dines—Fourier—Motzkin quantifier elimination and an application of corresponding transfer principles over ordered fields

A constructive procedure using Dines—Fourier—Motzkin elimination is given for eliminating quantifiers in a linear first order formula over ordered fields. An ensuing transfer principle is illustrated by showing that a locally one-to-one affine map is globally one-to-one and onto all over ordered fields.This research is based on work supported in part by the National Science Foundation under Grant DMS-86-03232, by the Department of Energy grant DE-FG03-87ER25028 and by the United States-Israel Binational Science Foundation Grant 85-00295.     

Approximation algorithms for indefinite quadratic programming

We consider-approximation schemes for indefinite quadratic programming. We argue that such an approximation can be found in polynomial time for fixed andt, wheret denotes the number of negative eigenvalues of the quadratic term. Our algorithm is polynomial in 1/ for fixedt, and exponential int for fixed. We next look at the special case of knapsack problems, showing that a more efficient (polynomial int) approximation algorithm exists.Part of this work was done while the author was visiting Sandia National Laboratories, Albuquerque, New Mexico, supported by the U.S. Department of Energy under contract DE-AC04-76DP00789. Part of this work was also supported by the Applied Mathematical Sciences Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000 and in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS 8920550.     

A superquadratic infeasible-interior-point method for linear complementarity problems

We consider a modification of a path-following infeasible-interior-point algorithm described by Wright. In the new algorithm, we attempt to improve each major iterate by reusing the coefficient matrix factors from the latest step. We show that the modified algorithm has similar theoretical global convergence properties to those of the earlier algorithm while its asymptotic convergence rate can be made superquadratic by an appropriate parameter choice. The work of this author was based on research supported by the Office of Scientific Computing, US Department of Energy, under Contract W-31-109-Eng-38. The work of this author was based on research supported in part by the US Department of Energy under Grant DE-FG02-93ER25171.     

An algorithm for nonlinear optimization using linear programming and equality constrained subproblems

This paper describes an active-set algorithm for large-scale nonlinear programming based on the successive linear programming method proposed by Fletcher and Sainz de la Maza [10]. The step computation is performed in two stages. In the first stage a linear program is solved to estimate the active set at the solution. The linear program is obtained by making a linear approximation to the ₁ penalty function inside a trust region. In the second stage, an equality constrained quadratic program (EQP) is solved involving only those constraints that are active at the solution of the linear program. The EQP incorporates a trust-region constraint and is solved (inexactly) by means of a projected conjugate gradient method. Numerical experiments are presented illustrating the performance of the algorithm on the CUTEr [1, 15] test set.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 in part by the EPSRC grant GR/R46641.These authors were supported by National Science Foundation grants CCR-9987818, ATM-0086579 and CCR-0219438 and Department of Energy grant DE-FG02-87ER25047-A004.Report OTC 2002/4, Optimization Technology CenterTo Roger Fletcher, with respect and admiration