Smoothing methods for convex inequalities and linear complementarity problems

A smooth approximationp (x, ) to the plus function max{x, 0} is obtained by integrating the sigmoid function 1/(1 + e^–x ), commonly used in neural networks. By means of this approximation, linear and convex inequalities are converted into smooth, convex unconstrained minimization problems, the solution of which approximates the solution of the original problem to a high degree of accuracy for sufficiently large. In the special case when a Slater constraint qualification is satisfied, an exact solution can be obtained for finite. Speedup over MINOS 5.4 was as high as 1142 times for linear inequalities of size 2000 × 1000, and 580 times for convex inequalities with 400 variables. Linear complementarity problems are converted into a system of smooth nonlinear equations and are solved by a quadratically convergent Newton method. For monotone LCPs with as many as 10 000 variables, the proposed approach was as much as 63 times faster than Lemke's method.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9101801 and CCR-9322479.  

Re-entrant lines

Traditionally, manufacturing systems have mainly been treated as either job shops or flow shops. In job shops, parts may arrive with random routes, with each route having a low volume. In flow shops, the routes are fixed and acyclic, as in assembly lines. With the advent of semiconductor manufacturing plants, and more recently, thin film lines, this dichotomy needs to be expanded to consider another class of systems, which we call re-entrant lines. The distinguishing feature of these manufacturing systems is that parts visit some machines more than once at different stages of processing.Scheduling problems arise because several parts at different stages of processing may be in contention with each other for service at the same machine. There may be uncertainties in the form of random service or set-up times, as well as random machine failures and repairs. The goal of scheduling is to improve performance measures such as mean sojourn time in the system, which is also known as the mean cycle-time, or the variance of the cycle-time.In this paper we provide a tutorial account of some recent results in this field. We describe several scheduling policies of interest, and provide some results concerning their stability and performance. Several open problems are suggested.The research reported here has been partially supported by the National Science Foundation under Grant No. ECS-90-25007, and the Joint Services Electronics Program under Contract No. N00014-84-C-0149.  

A class of smoothing functions for nonlinear and mixed complementarity problems

We propose a class of parametric smooth functions that approximate the fundamental plus function, (x)₊=max{0, x}, by twice integrating a probability density function. This leads to classes of smooth parametric nonlinear equation approximations of nonlinear and mixed complementarity problems (NCPs and MCPs). For any solvable NCP or MCP, existence of an arbitrarily accurate solution to the smooth nonlinear equations as well as the NCP or MCP, is established for sufficiently large value of a smoothing parameter . Newton-based algorithms are proposed for the smooth problem. For strongly monotone NCPs, global convergence and local quadratic convergence are established. For solvable monotone NCPs, each accumulation point of the proposed algorithms solves the smooth problem. Exact solutions of our smooth nonlinear equation for various values of the parameter , generate an interior path, which is different from the central path for interior point method. Computational results for 52 test problems compare favorably with these for another Newton-based method. The smooth technique is capable of solving efficiently the test problems solved by Dirkse and Ferris [6], Harker and Xiao [11] and Pang & Gabriel [28].This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grant CCR-9322479.  

Direct and converse results for operators of Baskakov-Durrmeyer type

We consder the n-th so-called operators of Baskakov-Durrmeyer type, which result from the classical Baskakov-type operators with weights p_nk, if the discrete values f(k/n) are replaced by the integral terms (n-c∫ ₀ ^∞ p _n k(t)f(t)dt. The main differences between these operators and their classical and Kantorovicvariants respectively is that they commute. We prove direct and converse theorems also for linear combinations of the operators and results of Zamansky-Sunouchi type. As an important tool for measuring the smootheness of a function we use the Ditzian-Totik modulus of smoothness and its equivalence to appropriate K-functionals. This paper is part of the author's dissertation.  

Convergence of a multiscale finite element method for elliptic problems with rapidly oscillating coefficients

We propose a multiscale finite element method for solving second order elliptic equations with rapidly oscillating coefficients. The main purpose is to design a numerical method which is capable of correctly capturing the large scale components of the solution on a coarse grid without accurately resolving all the small scale features in the solution. This is accomplished by incorporating the local microstructures of the differential operator into the finite element base functions. As a consequence, the base functions are adapted to the local properties of the differential operator. In this paper, we provide a detailed convergence analysis of our method under the assumption that the oscillating coefficient is of two scales and is periodic in the fast scale. While such a simplifying assumption is not required by our method, it allows us to use homogenization theory to obtain a useful asymptotic solution structure. The issue of boundary conditions for the base functions will be discussed. Our numerical experiments demonstrate convincingly that our multiscale method indeed converges to the correct solution, independently of the small scale in the homogenization limit. Application of our method to problems with continuous scales is also considered.

  

A B-spline approach for empirical mode decompositions

We propose an alternative B-spline approach for empirical mode decompositions for nonlinear and nonstationary signals. Motivated by this new approach, we derive recursive formulas of the Hilbert transform of B-splines and discuss Euler splines as spline intrinsic mode functions in the decomposition. We also develop the Bedrosian identity for signals having vanishing moments. We present numerical implementations of the B-spline algorithm for an earthquake signal and compare the numerical performance of this approach with that given by the standard empirical mode decomposition. Finally, we discuss several open mathematical problems related to the empirical mode decomposition. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday with friendship and esteem Mathematics subject classification (2000) 94A12. Supported in part by National Aeronautics and Space Administration under grant NAG5-5364, and National Science Foundation under grants NSF0314742 and NSF0312113. Yuesheng Xu: Corresponding author. Supported in part by Natural Science Foundation of China under grant 10371122.  

Financing newsvendor inventory

If the cost of borrowing is not too high, the capital-constrained newsvendor borrows funds to procure an amount that is less than would be ideal. The lender charges an interest rate that decreases in the newsvendor’s equity. Furthermore, we derived a non-linear loan schedule that coordinates the channel.  

Nonlinear complementarity as unconstrained and constrained minimization

The nonlinear complementarity problem is cast as an unconstrained minimization problem that is obtained from an augmented Lagrangian formulation. The dimensionality of the unconstrained problem is the same as that of the original problem, and the penalty parameter need only be greater than one. Another feature of the unconstrained problem is that it has global minima of zero at precisely all the solution points of the complementarity problem without any monotonicity assumption. If the mapping of the complementarity problem is differentiable, then so is the objective of the unconstrained problem, and its gradient vanishes at all solution points of the complementarity problem. Under assumptions of nondegeneracy and linear independence of gradients of active constraints at a complementarity problem solution, the corresponding global unconstrained minimum point is locally unique. A Wolfe dual to a standard constrained optimization problem associated with the nonlinear complementarity problem is also formulated under a monotonicity and differentiability assumption. Most of the standard duality results are established even though the underlying constrained optimization problem may be nonconvex. Preliminary numerical tests on two small nonmonotone problems from the published literature converged to degenerate or nondegenerate solutions from all attempted starting points in 7 to 28 steps of a BFGS quasi-Newton method for unconstrained optimization.Dedicated to Phil Wolfe on his 65th birthday, in appreciation of his major contributions to mathematical programming.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grant CCR-9101801.  

Convergence of algebraic multigrid based on smoothed aggregation

Summary. We prove an abstract convergence estimate for the Algebraic Multigrid Method with prolongator defined by a disaggregation followed by a smoothing. The method input is the problem matrix and a matrix of the zero energy modes of the same problem but with natural boundary conditions. The construction is described in the case of a general elliptic system. The condition number bound increases only as a polynomial of the number of levels, and requires only a uniform weak approximation property for the aggregation operators. This property can be a-priori verified computationally once the aggregates are known. For illustration, it is also verified here for a uniformly elliptic diffusion equations discretized by linear conforming quasiuniform finite elements. Only very weak and natural assumptions on the hierarchy of aggregates are needed. Received March 1, 1998 / Revised version received January 28, 2000 / Published online: December 19, 2000  

The modified method of characteristics with adjusted advection

Summary. The MMOC procedure for approximating the solutions of transport-dominated diffusion problems does not automatically preserve integral conservation laws, leading to (mass) balance errors in many kinds of flow problems. The variant, called the MMOCAA, discussed herein preserves the conservation law at a minor additional computational cost. It is shown that its solution, in either Galerkin or finite difference form, converges at the same rates as were proved earlier by Dougl as and Russell for the standard MMOC procedure. Received June 25, 1997 / Revised version received October 6, 1998 / Published online: July 7, 1999