Extrapolated Smoothing Descent Algorithm for Constrained Nonconvex and Nonsmooth Composite Problems*

In this paper, the authors propose a novel smoothing descent type algorithm with extrapolation for solving a class of constrained nonsmooth and nonconvex problems,where the nonconvex term is possibly nonsmooth. Their algorithm adopts the proximal gradient algorithm with extrapolation and a safe-guarding policy to minimize the smoothed objective function for better practical and theoretical performance. Moreover, the algorithm uses a easily checking rule to update the smoothing parameter to ensure that any accumulation point of the generated sequence is an (affine-scaled) Clarke stationary point of the original nonsmooth and nonconvex problem. Their experimental results indicate the effectiveness of the proposed algorithm.     

线型/圈型网络上单台车辆分群调度问题

本文研究线型/圈型网络上单台车辆分群调度问题。给定一个线型/圈型网络,若干客户分布其中。所有客户被划分成若干个子集,每个子集称为一个群。每个客户有一个释放时间和一个服务时间。给定一台车辆,其需要服务所有客户,且每个群内的客户连续服务。问题的要求是计算一个时间表,使得车辆能够按要求服务完所有客户并返回初始出发位置所花费的时间最少。针对该问题,就线型网络和圈型网络,分别给出一个7/4和一个13/7近似算法。     

ALTERNATION THEORY IN APPROXIMATION BY POLYNOMIALS HAVING BOUNDED COEFFICIENTS

ＡＬＴＥＲＮＡＴＩＯＮＴＨＥＯＲＹＩＮＡＰＰＲＯＸＩＭＡＴＩＯＮＢＹＰＯＬＹＮＯＭＩＡＬＳＨＡＶＩＮＧＢＯＵＮＤＥＤＣＯＥＦＦＩＣＩＥＮＴＳＸＵＳＨＵＳＨＥＮＧ（许树声）（ＪｉａｎｇｎａｎＵｎｉｖｅｒｓｉｔｙ,Ｗｕｘｉ２１４０６３,Ｃｈｉｎａ）Ａｂｓ...     

Massively time-parallel,approximate simulation of loss queueing systems

A time-parallel simulation obtains parallelism by partitioning the time domain of the simulation. An approximate time-parallel simulation algorithm named GG1K is developed for acyclic networks of loss FCFSG/G/1/K queues. The GG1K algorithm requires two phases. In the first phase, a similar system (i.e. aG/G/1/ queue) is simulated using the GLM algorithm. Then the resultant trajectory is transformed into an approximateG/G/1/K trajectory in the second phase. The closeness of the approximation is investigated theoretically and experimentally. Our results show that the approximation is highly accurate except whenK is very small (e.g. 5) in certain models. The algorithm exploits unbounded parallelism and can achieve near-linear speedup when the number of arrivals simulated is sufficiently large.     

An energy-transport model for semiconductors derived from the Boltzmann equation

An energy-transport model is rigorously derived from the Boltzmann transport equation of semiconductors under the hypothesis that the energy gain or loss of the electrons by the phonon collisions is weak. Retaining at leading order electron-electron collisions and elastic collisions (i.e., impurity scattering and the elastic part of phonon collisions), a rigorous diffusion limit of the Boltzmann equation can be carried over, which leads to a set of diffusion equations for the electron density and temperature. The derivation is given in both the degenerate and nondegenerate cases.     

On the convergence of multipoint Padé-type approximants and quadrature formulas associated with the unit circle

We study the convergence of rational interpolants with prescribed poles on the unit circle to the Herglotz-Riesz transform of a complex measure supported on [–, ]. As a consequence, quadrature formulas arise which integrate exactly certain rational functions. Estimates of the rate of convergence of these quadrature formulas are also included.This research was performed as part of the European project ROLLS under contract CHRX-CT93-0416.     

An analysis of cubic approximation schemes for conic sections

In this paper a piece of a conic section is approximated by a cubic or piecewise cubic polynomial. The main tool is to define the two inner control points of the cubic as an affine combination, defined by [0, 1], of two control points of the conic. If is taken to depend on the weightw of the latter, a function (w) results which is used to distinguish between different algorithms and to analyze their properties. One of the approximations is a piecewise cubic havingG ⁴ continuity at the break points.     

The asymptotic behavior of queueing systems: Large deviations theory and dominant pole approximation

This paper presents the exact asymptotics of the steady state behavior of a broad class of single-node queueing systems. First we show that the asymptotic probability functions derived using large deviations theory are consistent (in a certain sense) with the result using dominant pole approximations. Then we present an exact asymptotic formula for the cumulative probability function of the queue occupancy and relate it to the cell loss ratio, an important performance measure for service systems such as ATM networks. The analysis relies on a new generalization of the Taylor coefficients of a complex function which we call characteristic coefficients. Finally we apply our framework to obtain new results for the M/D/1 system and for a more intricate multiclass M/D/n system.     

WKB-type approximations for second-order differential equations in -algebras

Rigorous asymptotic approximations of the WKB (or Liouville-Green) type are obtained for a basis of solutions to in the framework of -algebras. Both cases and are included, thus generalizing the classical theory for scalar equations developed by F.W.J. Olver to matrix as well as to infinite-dimensional equations.

     

A -functional and the rate of convergence of some linear polynomial operators

We show that the -functional

where , is equivalent to the rate of convergence of a certain linear polynomial operator. This operator stems from a Riesz-type summability process of expansion by Legendre polynomials. We use the operator above to obtain a linear polynomial approximation operator with a rate comparable to that of the best polynomial approximation.