A new polynomial-time algorithm for linear programming

We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n ^3.5 L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n ^2.5). We prove that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property. The ratio of the radius of the smallest sphere with center a′, containingP′ to the radius of the largest sphere with center a′ contained inP′ isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time. This is a substantially revised version of the paper presented at the Symposium on Theory of Computing, Washington D. C., April 1984.  

Nonlinear programming without a penalty function

In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead, a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm compares favourably with LANCELOT and an implementation of Sl₁QP. Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001  

Bayesian image restoration,with two applications in spatial statistics

There has been much recent interest in Bayesian image analysis, including such topics as removal of blur and noise, detection of object boundaries, classification of textures, and reconstruction of two- or three-dimensional scenes from noisy lower-dimensional views. Perhaps the most straightforward task is that of image restoration, though it is often suggested that this is an area of relatively minor practical importance. The present paper argues the contrary, since many problems in the analysis of spatial data can be interpreted as problems of image restoration. Furthermore, the amounts of data involved allow routine use of computer intensive methods, such as the Gibbs sampler, that are not yet practicable for conventional images. Two examples are given, one in archeology, the other in epidemiology. These are preceded by a partial review of pixel-based Bayesian image analysis.An earlier version of this article was presented at the symposium on the Analysis of Statistical Information held in the Institute of Statistical Mathematics, Tokyo during December 5–8, 1989.This research was carried out partly at the University of Durham, U.K., with the support of an award by the Complex Stochastic Systems Initiative of the Science and Engineering Research Council.  

DISRUPTION MANAGEMENT FOR SUPPLY CHAIN COORDINATION WITH EXPONENTIAL DEMAND FUNCTION

The coordination problem of a supply chain comprising one supplier and one retailer under market demand disruption is studied in this article. A novel exponential demand function is adopted, and the penalty cost is introduced explicitly to capture the deviation production cost caused by the market demand disruption. The optimal strategies are obtained for different disruption scale under the centralized mode. For the decentralized mode, it is proved that the supply chain can be fully coordinated by adjusting the price discount policy appropriately when disruption occurs. Furthermore, the authors point out that similar results can be established for more general demand functions that represent different market circumstances if certain assumptions are satisfied.  

The interpolation theorem for narrow quadrilateral isoparametric finite elements

Summary. The interpolation theorem for convex quadrilateral isoparametric finite elements is proved in the case when the condition is not satisfied, where is the diameter of the element and is the radius of an inscribed circle in . The interpolation error is in the -norm and in the -norm provided that the interpolated function belongs to . In the case when the long sides of the quadrilateral are parallel the constants appearing in the estimates are evaluated. Received September 1993 / Revised version received March 6, 1995  

A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints

This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported.  

A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints

This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported.  

Fixed point theorems for non-Lipschitzian mappings of asymptotically nonexpansive type

LetX be a Banach space,K a nonempty, bounded, closed and convex subset ofX, and supposeT:K→K satisfies: for eachx∈K, lim sup _i→∞{sup _y∈K ‖t ⁱx−Tⁱy∼−‖x−y‖}≦0. IfT ^N is continuous for some positive integerN, and if either (a)X is uniformly convex, or (b)K is compact, thenT has a fixed point inK. The former generalizes a theorem of Goebel and Kirk for asymptotically nonexpansive mappings. These are mappingsT:K→K satisfying, fori sufficiently large, ‖Tⁱx−Tⁱy‖≦k _i‖x−y∼,x,y∈K, wherek _i→1 asi→∞. The precise assumption in (a) is somewhat weaker than uniform convexity, requiring only that Goebel’s characteristic of convexity, ɛ₀ (X), be less than one. Research supported by National Science Foundation Grant GP 18045.  

Convolutions, Transforms, and Convex Bodies

The paper studies convex bodies and star bodies in Rⁿ by usingRadon transforms on Grassmann manifolds, p-cosine transformson the unit sphere, and convolutions on the rotation group ofRⁿ. It presents dual mixed volume characterizations of i-intersectionbodies and L_p-balls which are related to certain volume inequalitiesfor cross sections of convex bodies. It considers approximationsof special convex bodies by analytic bodies and various finitesums of ellipsoids which preserve special geometric properties.Convolution techniques are used to derive formulas for mixedvolumes, mixed surface measures, and p-cosine transforms. Theyare also used to prove characterizations of geometric functionals,such as surface area and dual quermassintegrals. 1991 MathematicsSubject Classification: 52A20, 52A40.