A bisection/successive approximation method for computing Gittins indices

An iterative method, combining bisections and successive approximations, is proposed for computing intervals containing the Gittins indices. The intervals could be of a specified maximum length, or be merely disjoint. The first option gives approximations of the Gittins indices. The second option gives a ranking of indices, which in many applications is sufficient.Supported by the Royal Norwegian Council for Industrial and Scientific Research and by the National Science Foundation.     

A successive projection method

It is of both theoretical and practical interest to find the projection of a point to the intersection of a finite number of closed convex sets by a sequence of projections to the individual sets successively. In this paper we study such a method and analyze its convergence properties. A main feature of the method is its capability to decompose the projection problem into several small ones. For some structured sparse problems these small subproblems can be solved independently and the presented method has a potential use in parallel computation.This material is based on work supported in part by the National Science Foundation under Grant DMS-8602419 and by the Center for Supercomputing Research and Development, University of Illinois.     

A successive convex approximation method for multistage workforce capacity planning problem with turnover

Workforce capacity planning in human resource management is a critical and essential component of the services supply chain management. In this paper, we consider the planning problem of transferring, hiring, or firing employees among different departments or branches of an organization under an environment of uncertain workforce demands and turnover, with the objective of minimizing the expected cost over a finite planning horizon. We model the problem as a multistage stochastic program and propose a successive convex approximation method which solves the problem in stages and iteratively. An advantage of the method is that it can handle problems of large size where normally solving the problems by equivalent deterministic linear programs is considered to be computationally infeasible. Numerical experiments indicate that solutions obtained by the proposed method have expected costs near optimal.     

A SUCCESSIVE APPROXIMATION METHOD FOR SOLVING PROBABILISTIC CONSTRAINED PROGRAMS

ＡＳＵＣＣＥＳＳＩＶＥＡＰＰＲＯＸＩＭＡＴＩＯＮＭＥＴＨＯＤＦＯＲＳＯＬＶＩＮＧＰＲＯＢＡＢＩＬＩＳＴＩＣＣＯＮＳＴＲＡＩＮＥＤＰＲＯＧＲＡＭＳＷＡＮＧＪＩＮＤＥ（王金德）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＮａｎｊｉｎｇＵｎｉｖｅｒｓ...     

Maximal vectors in Hilbert space and quantum entanglement

Let V be a norm-closed subset of the unit sphere of a Hilbert space H that is stable under multiplication by scalars of absolute value 1. A maximal vector (for V) is a unit vector ξ∈H whose distance to V is maximum

     

非线性半定规划的逐次线性化柔性惩罚法

针对非线性不等式约束半定规划问题提出一种新的逐次线性化方法, 新算法既不要求罚函数单调下降, 也不使用过滤技巧, 尝试步的接受准则仅仅依赖于目标函数和约束违反度, 罚函数中对应于成功迭代点的罚因子不需要单调增加. 新算法或者要求违反约束度量有足够改善, 或者在约束违反度的一个合理范围内要求目标函数值充分下降, 在通常假设条件下, 分析了新算法的适定性及全局收敛性. 最后, 给出了非线性半定规划问题的数值试验结果, 结果表明了新算法的有效性.     

A parametric successive underestimation method for convex multiplicative programming problems

This paper addresses itself to the algorithm for minimizing the product of two nonnegative convex functions over a convex set. It is shown that the global minimum of this nonconvex problem can be obtained by solving a sequence of convex programming problems. The basic idea of this algorithm is to embed the original problem into a problem in a higher dimensional space and to apply a branch-and-bound algorithm using an underestimating function. Computational results indicate that our algorithm is efficient when the objective function is the product of a linear and a quadratic functions and the constraints are linear. An extension of our algorithm for minimizing the sum of a convex function and a product of two convex functions is also discussed.     

A commentary on the method of successive starts

A number of comments are made on the method of successive starts. These include a derivation of the method, a discussion of it in its most general setting, remarks on its use, suggestions to improve its accuracy, and some open questions about the method. Several numerical examples are discussed illustrating both success and failure with the method.     

An LP-based successive overrelaxation method for linear complementarity problems

A sparsity preserving LP-based SOR method for solving classes of linear complementarity problems including the case where the given matrix is positive-semidefinite is proposed. The LP subproblems need be solved only approximately by a SOR method. Heuristic enhancement is discussed. Numerical results for a special class of problems are presented, which show that the heuristic enhancement is very effective and the resulting program can solve problems of more than 100 variables in a few seconds even on a personal computer.This research was sponsored by the Air Force Office of Scientific Research, Grant No. AFOSR-86-0124. Part of this material is based on work supported by the National Science Foundation under Grant No. MCS-82-00632.The author is grateful to Dr. R. De Leone for his helpful and constructive comments on this paper.     

The small quantum group as a quantum double

We prove that the quantum double of the quasi-Hopf algebra of dimension attached in [P. Etingof, S. Gelaki, On radically graded finite-dimensional quasi-Hopf algebras, Mosc. Math. J. 5 (2) (2005) 371–378] to a simple complex Lie algebra and a primitive root of unity q of order n² is equivalent to Lusztig's small quantum group (under some conditions on n). We also give a conceptual construction of using the notion of de-equivariantization of tensor categories.     

Conditions for strong ellipticity and M-eigenvalues

The strong ellipticity condition plays an important role in nonlinear elasticity and in materials. In this paper, we define M-eigenvalues for an elasticity tensor. The strong ellipticity condition holds if and only if the smallest M-eigenvalue of the elasticity tensor is positive. If the strong ellipticity condition holds, then the elasticity tensor is rank-one positive definite. The elasticity tensor is rank-one positive definite if and only if the smallest Z-eigenvalue of the elasticity tensor is positive. A Z-eigenvalue of the elasticity tensor is an M-eigenvalue but not vice versa. If the elasticity tensor is second-order positive definite, then the strong ellipticity condition holds. The converse conclusion is not right. Computational methods for finding M-eigenvalues are presented.      

Optimal output tracking control for nonlinear systems via successive approximation approach

This paper deals with the optimal output tracking control (OOTC) problem of a class of nonlinear systems whose reference input to be tracked is produced by a generalized linear exosystem. To solve the nonlinear OOTC problem, the nonlinear two-point boundary value (TPBV) problem derived from the necessary conditions of the OOTC problem is transformed into two decoupled iterative sequences of linear differential equations. The OOTC law obtained consists of accurate feedforward and feedback terms and a nonlinear compensation term. The former can be found by solving a Sylvester equation and a Riccati equation, and the latter can be approximated using a successive approximation approach (SAA). A reduced-order reference input observer is constructed to make the feedforward control law physically realizable. A simulation example is employed to illustrate the validity of the results.     

求解线性矩问题的一个逼近方法

给出一种求解线性矩问题的逼近方法，并给出以B样条函数为基的数值例子，证明了该方法的有效性．     

Block-successive approximation for a discounted Markov decision model

In this paper we suggest a new successive approximation method to compute the optimal discounted reward for finite state and action, discrete time, discounted Markov decision chains. The method is based on a block partitioning of the (stochastic) matrices corresponding to the stationary policies. The method is particularly attractive when the transition matrices are jointly nearly decomposable or nearly completely decomposable.     

The method of successive affine reduction for nonlinear minimization

The traditional development of conjugate gradient (CG) methods emphasizes notions of conjugacy and the minimization of quadratic functions. The associated theory of conjugate direction methods, strictly a branch of numerical linear algebra, is both elegant and useful for obtaining insight into algorithms for nonlinear minimization. Nevertheless, it is preferable that favorable behavior on a quadratic be a consquence of a more general approach, one which fits in more naturally with Newton and variable metric methods. We give new CG algorithms along these lines and discuss some of their properties, along with some numerical supporting evidence.I acknowledge partial support by ONR Contract #N00014-76-C-0013 at the Center for Pure & Applied Mathematics, University of California, Berkeley in the dissemination of this article.     

基于块循环矩阵的对称张量的最佳秩-1逼近

对称张量的最佳秩-1问题是张量研究中非常重要的部分.首先,基于三阶张量的块循环矩阵,提出了求解对称张量最佳秩-1逼近问题的一个新方法.其次,针对求解对称张量的最佳秩-1逼近方法,给出了对称张量的最佳秩-1逼近不变性的一个充要条件,以及逼近误差上界的估计.最后,数值算例表明了上述方法的可行性和误差上界的正确性.