Minimum-support solutions of polyhedral concave programs *

Motivated by the successful application of mathematical programming techniques to difficult machine learning problems, we seek solutions of concave minimization problems over polyhedral sets with minimum number of nonzero components. We that if

such problems have a solution, they have a vertex solution with a minimal number of zeros. This includes linear programs and general linear complementarity problems. A smooth concave exponential approximation to a step function solves the minimumsupport problem exactly for a finite value of the smoothing parameter. A fast finite linear-programming-based iterative method terminates at a stationary point, which for many important real world problems provides very useful answers. Utilizing the

complementarity property of linear programs and linear complementarity problems, an upper bound on the number of nonzeros can be obtained by solving a single convex minimization problem on a polyhedral set     

A smoothing method for mathematical programs with equilibrium constraints

Received May 3, 1996 / Revised version received November 19, 1997 Published online January 20, 1999     

The new identity for the scattering matrix of exactly solvable models

We discovered a simple quadratic equation, which relates scattering phases of particles on Fermi surface. We consider one-dimensional Bose gas and XXZ Heisenberg quantum spin chain. Received: 4 December 1997 / Accepted: 17 March 1998     

标准算子代数上完全保对合性的可加映射

刻画了无限维实或复Banach空间上的标准算子代数间完全保对合性的可加映射,证明了这样的映射是同构的常数倍或(复情形下)共轭同构的常数倍.     

A comparison of some domain decomposition and ILU preconditioned iterative methods for nonsymmetric elliptic problems

In recent years, competitive domain-decomposed preconditioned iterative techniques of Krylov-Schwarz type have been developed for nonsymmetric linear elliptic systems. Such systems arise when convection-diffusion-reaction problems from computational fluid dynamics or heat and mass transfer are linearized for iterative solution. Through domain decomposition, a large problem is divided into many smaller problems whose requirements for coordination can be controlled to allow effective solution on parallel machines. A central question is how to choose these small problems and how to arrange the order of their solution. Different specifications of decomposition and solution order lead to a plethora of algorithms possessing complementary advantages and disadvantages. In this report we compare several methods, including the additive Schwarz algorithm, the classical multiplicative Schwarz algorithm, an accelerated multiplicative Schwarz algorithm, the tile algorithm, the CGK algorithm, the CSPD algorithm, and also the popular global ILU-family of preconditioners, on some nonsymmetric or indefinite elliptic model problems discretized by finite difference methods. The preconditioned problems are solved by the unrestarted GMRES method. A version of the accelerated multiplicative Schwarz method is a consistently good performer.     

Parallel computation of two-point boundary-value problems via particular solutions

Nonlinear two-point boundary-value problems (TPBVP) can be reduced to the iterative solution of a sequence of linear problems by means of quasilinearization techniques. Therefore, the efficient solution of linear problems is the key to the efficient solution of nonlinear problems.Among the techniques available for solving linear two-point boundary-value problems, the method of particular solutions (MPS) is particularly attractive in that it employs only one differential system, the original nonhomogeneous system, albeit with different initial conditions. This feature of MPS makes it ideally suitable for implementation on parallel computers in that the following requirements are met: the computational effort is subdivided into separate tasks (particular solutions) assigned to the different processors; the tasks have nearly the same size; there is little intercommunication between the tasks.For the TPBVP, the speedup achievable is ofO(n), wheren is the dimension of the state vector, hence relatively modest for the differential systems of interest in trajectory optimization and guidance. This being the case, we transform the TPBVP into a multi-point boundary-value problem (MPBVP) involvingm time subintervals, withm–1 continuity conditions imposed at the interface of contiguous subintervals. For the MPBVP, the speedup achievable is ofO(mn), hence substantially higher than that achievable for the TPBVP. It reduces toO(m) if the parallelism is implemented only in the time domain and not in the state domain.A drawback of the multi-point approach is that it requires the solution of a large linear algebraic system for the constants of the particular solutions. This drawback can be offset by exploiting the particular nature of the interface conditions: if the vector of constants for the first subinterval is known, the vector of constants for the subsequent subintervals can be obtained with linear transformations. Using decomposition techniques together with the discrete version of MPS, the size of the linear algebraic system for the multi-point case becomes the same as that for the two-point case.Numerical tests on the Intel iPSC/860 computer show that substantial speedup can be achieved via parallel algorithms vis-a-vis sequential algorithms. Therefore, the present technique has considerable interest for real-time trajectory optimization and guidance.Dedicated to the Memory of Professor Jan M. SkowronskiThis paper, based on Refs. 1–3, is a much condensed version of the material contained in these references.The technical assistance of the Research Center on Parallel Computation of Rice University, Houston, Texas is gratefully acknowledged.     

A tabu search procedure for multicommodity location/allocation with balancing requirements

We propose a tabu search heuristic for the location/allocation problem with balancing requirements. This problem typically arises in the context of the medium term management of a fleet of containers of multiple types, where container depots have to be selected, the assignment of customers to depots has to be established for each type of container, and the interdepot container traffic has to be planned to account for differences in supplies and demands in various zones of the geographical territory served by a container shipping company. It is modeled as a mixed integer program, which combines zero-one location variables and a multicommodity network flow structure. Extensive computational results on a set of benchmark problems and comparisons with an efficient dual ascent procedure are reported. These show that tabu search is a competitive approach for this class of problems.     

Skorokhod decomposition of reflected diffusions on bounded Lipschitz domains with singular non-reflection part

Let be a compact set with interior G. Let L ¹ (G,dx), >0 dx-a.e. on G, and m:=dx. Let A=(a _ij ) be symmetric, and globally uniformly strictly elliptic on G. Let be such that ; f, , is closable in L ² (G,m) with closure ( ^r ,D( ^r )). The latter is fulfilled if satisfies the Hamza type condition, or _i L ¹ _loc (G,dx), 1id. Conservative, non-symmetric diffusion processes X _t related to the extension of a generalized Dirichlet form where satisfies are constructed and analyzed. If G is a bounded Lipschitz domain, H ^1,1 (G), and a _ij D( ^r ), a Skorokhod decomposition for X _t is given. This happens through a local time that is uniquely associated to the smooth measure 1_{{ Tr ()>0}} d, where Tr denotes the trace and the surface measure on G.This research has been financially supported by TMR grant HPMF-CT-2000-00942 of the European Union. Mathematics Subject Classification (2000): 60J60, 60J55, 31C15, 31C25, 35J25     

FINITE ELEMENT APPROXIMATION OF A NONLINEAR STEADY-STATE HEAT CONDUCTION PROBLEM

1. Introduction Anciellt Chinese mathematicians have done many fund~al discoveries, even thoughmad of them are now usually called by western names, e.g., the Pascal triangle, the HornerIcheme, the Gaussian elimination, see [231. In the modern era3 Chinese mathematiciare have.jalso got many priorities. For instance, the fast Proof Of convergence of the finite element methodfor a linear elliptic boundary vajue problem was done in the pioneering work [61 by K. Feng in1965 (for the English tra…     

COMPOSITE LEGENDRE-LAGUERRE APPROXIMATION IN UNBOUNDED DOMAINS

1. IntroductionMany problems in science aam engineering are set in unbounded domains. There are severalways for their numerical simulatiolls. We may restrict calculations to some bounded domainswith certain artificial boundary conditions. But they induce errors. In particular, they ductshe wave Propagations in revolutionary problems. In opposite, if we use'spectral methods assorted with orthogonal systems of polynomials in Unbounded domains, then we could avoid tabstrouble, e.g., see Mad'ay,…