Computation of differential Chow forms for ordinary prime differential ideals

In this paper, we propose algorithms for computing differential Chow forms for ordinary prime differential ideals which are given by characteristic sets. The algorithms are based on an optimal bound for the order of a prime differential ideal in terms of a characteristic set under an arbitrary ranking, which shows the Jacobi bound conjecture holds in this case. Apart from the order bound, we also give a degree bound for the differential Chow form. In addition, for a prime differential ideal given by a characteristic set under an orderly ranking, a much simpler algorithm is given to compute its differential Chow form. The computational complexity of the algorithms is single exponential in terms of the Jacobi number, the maximal degree of the differential polynomials in a characteristic set, and the number of variables.     

Optimal portfolio execution under time-varying liquidity constraints

In this article, we take an algorithmic approach to solve the problem of optimal execution under time-varying constraints on the depth of a limit order book (LOB). Our algorithms are within the resilience model proposed by Obizhaeva and Wang (2013) with a more realistic assumption on the order book depth; the amount of liquidity provided by an LOB market is finite at all times. For the simplest case where the order book depth stays at a fixed level for the entire trading horizon, we reduce the optimal execution problem into a one-dimensional root-finding problem which can be readily solved by standard numerical algorithms. When the depth of the order book is monotone in time, we apply the Karush-Kuhn-Tucker conditions to narrow down the set of candidate strategies. Then, we use a dichotomy-based search algorithm to pin down the optimal one. For the general case, we start from the optimal strategy subject to no liquidity constraints and iterate over execution strategy by sequentially adding more constraints to the problem in a specific fashion until primal feasibility is achieved. Numerical experiments indicate that our algorithms give comparable results to those of current existing convex optimization toolbox CVXOPT with significantly lower time complexity.     

Frequency evaluation in exponential fitting multistep algorithms for ODEs

We consider the linear multistep algorithms for first order ODEs and examine the problem of how the λ-frequencies should be tuned in order to obtain the maximal benefit from the exponential fitting versions of such algorithms. We find out that the key of the answer consists in analysing the behaviour of the error. On further investigating the simple case of two-step bdf algorithms we produce formulae for the optimal λ's and show that, if the optimal λ's are used, the order of the method is increased by one unit. The reported numerical illustrations suggest that further investigations along these lines deserve a real attention.     

Optimal dynamic multi-attribute hashing for range queries

This paper examines a partial match retrieval scheme which supports range queries for highly dynamic databases. The scheme relies on order preserving multi-attribute hashing. In general, designing optimal indexes is NP-hard. Greedy algorithms used to determine the optimal indexes for simple partial match queries are not directly applicable because there are a larger number of queries to consider in determining the optimal indexes. In this paper we present heuristic algorithms which provide near-optimal solutions. The optimisation scheme we propose can be used to design other dynamic file structures such as the grid file, BANG file and multilevel grid file to further enhance their retrieval performance taking into consideration the query distribution.     

Outer approximation algorithms for canonical DC problems

The paper discusses a general framework for outer approximation type algorithms for the canonical DC optimization problem. The algorithms rely on a polar reformulation of the problem and exploit an approximated oracle in order to check global optimality. Consequently, approximate optimality conditions are introduced and bounds on the quality of the approximate global optimal solution are obtained. A thorough analysis of properties which guarantee convergence is carried out; two families of conditions are introduced which lead to design six implementable algorithms, whose convergence can be proved within a unified framework.     

Sourcing decision under disruption risk with supply and demand uncertainty: A newsvendor approach

Multi-sourcing is considered as a common practice to hedge against supply disruption risk. In this context, this paper proposes two models for optimal order allocation in newsvendor setting, where both supply and demand are uncertain. The first model considers a risk neutral decision maker who maximizes the total expected profit under disruption risk. The second one is for a risk averse decision maker who does so under service level constraints. Analytical closed form solutions for both the models are derived. To overcome the computational complexity of the exact optimal solution, two algorithms are developed to generate optimal order quantity and the corresponding set of suppliers. The solutions with exact optimization algorithms and the proposed ones are illustrated and compared with numerical examples. The results show that the proposed algorithms give the exact optimal solution while being tractable. Finally, a case study is used to illustrate the applicability of the proposed model.     

最优传输理论在图像处理中的应用

最优传输问题是寻找概率测度间的最优传输变换的一类特殊的优化问题,近年来在众多领域得到了广泛的关注.针对传统最优传输问题存在的计算量过大、正则性缺失等问题,学者们提出了多种改进的最优传输模型和算法,用于处理实际中的各种问题.简述最优传输问题的基本理论和方法,介绍Wasserstein距离的概念及其衍生出的Wasserstein重心,探讨离散化最优传输模型及其在正则化等方面的改进,讨论求解最优传输问题的算法进展,综述Wasserstein距离在图像处理领域的简单应用,并展望有待进一步研究的工作.     

Algorithms for Unconstrained Optimization Problems via Control Theory

Existing algorithms for solving unconstrained optimization problems are generally only optimal in the short term. It is desirable to have algorithms which are long-term optimal. To achieve this, the problem of computing the minimum point of an unconstrained function is formulated as a sequence of optimal control problems. Some qualitative results are obtained from the optimal control analysis. These qualitative results are then used to construct a theoretical iterative method and a new continuous-time method for computing the minimum point of a nonlinear unconstrained function. New iterative algorithms which approximate the theoretical iterative method and the proposed continuous-time method are then established. For convergence analysis, it is useful to note that the numerical solution of an unconstrained optimization problem is none other than an inverse Lyapunov function problem. Convergence conditions for the proposed continuous-time method and iterative algorithms are established by using the Lyapunov function theorem.     

Structural optimization by wavelet transforms and neural networks

An efficient methodology is presented to achieve optimal design of structures for earthquake loading. In this methodology a combination of wavelet transforms, neural networks and evolutionary algorithms are employed. The stochastic nature of the evolutionary algorithms makes the slow convergence. Specially, when earthquake induced loads are taken into account. To reduce the computational burden, a discrete wavelet transform is used by means of which the number of points in the earthquake record is decreased. Then, by using a surrogate model, the dynamic responses of the structures are predicted. In order to investigate the efficiency of the proposed methodology, two structures are designed for optimal weight. The numerical results demonstrate the computational advantages of the proposed hybrid methodology to optimal dynamic design of structures.     

A self-organising model for the travelling salesman problem

This work describes a new algorithm, based on a self-organising neural network approach, to solve the Travelling Salesman Problem (TSP). Firstly, various features of the available adaptive neural network algorithms for TSP are reviewed and a new algorithm is proposed. In order to investigate the performance of the algorithms, a comprehensive empirical study has been provided. The simulations, which are conducted on a series of standard data, evaluate the overall performance of this approach by comparing the results with the best known or the optimal solutions of the problems. The proposed algorithm shows significant advances in both the quality of the solution and computational effort for most of the experimental data. The deviation from the optimal solution of this algorithm was, in the worst case, around 2%. This fact indicates that the self-organising neural network may be regarded as a promising heuristic approach for optimisation problems.     

Optimal scaling of random-walk metropolis algorithms on general target distributions

One main limitation of the existing optimal scaling results for Metropolis–Hastings algorithms is that the assumptions on the target distribution are unrealistic. In this paper, we consider optimal scaling of random-walk Metropolis algorithms on general target distributions in high dimensions arising from practical MCMC models from Bayesian statistics. For optimal scaling by maximizing expected squared jumping distance (ESJD), we show the asymptotically optimal acceptance rate 0.234 can be obtained under general realistic sufficient conditions on the target distribution. The new sufficient conditions are easy to be verified and may hold for some general classes of MCMC models arising from Bayesian statistics applications, which substantially generalize the product i.i.d. condition required in most existing literature of optimal scaling. Furthermore, we show one-dimensional diffusion limits can be obtained under slightly stronger conditions, which still allow dependent coordinates of the target distribution. We also connect the new diffusion limit results to complexity bounds of Metropolis algorithms in high dimensions.     

Single vehicle routing with predefined client sequence and multiple warehouse returns: the case of two warehouses

We examine three interesting cases of the single vehicle routing problem with a predefined client sequence and two load replenishment warehouses. Given the location and demand of the clients, we seek the minimal cost route, which includes optimal load replenishment visits to the warehouses in order to fully satisfy the client demand. The cases studied vary with respect to inventory availability at each warehouse and are of increasing complexity. We have developed solution algorithms that address this complexity, ranging from a standard dynamic programming algorithm for the simplest case, to labeling algorithms and a new partitioning heuristic. The efficiency of these algorithms has been studied by solving a wide range of problem instances, and by comparing the results with those obtained from a state-of-the-art MILP solver.     

Cascadic Multigrid for Finite Volume Methods for Elliptic Problems

In this paper, some effective cascadic multigrid methods are proposed for solving the large scale symmetric or nonsymmetric algebraic systems arising from the finite volume methods for second order elliptic problems. It is shown that these algorithms are optimal in both accuracy and computational complexity. Numerical experiments are reported to support our theory.     

Improvements to Variable Elimination and Symbolic Probabilistic Inference for evaluating Influence Diagrams

An Influence Diagram is a probabilistic graphical model used to represent and solve decision problems under uncertainty. Its evaluation requires performing several combinations and marginalizations on the potentials attached to the Influence Diagram. Finding an optimal order for these operations, which is NP-hard, is an element of crucial importance for the efficiency of the evaluation. In this paper, two methods for optimizing this order are proposed. The first one is an improvement of the Variable Elimination algorithm while the second is the adaptation of the Symbolic Probabilistic Inference for evaluating Influence Diagrams. Both algorithms can be used for the direct evaluation of IDs but also for the computation of clique-to-clique messages in Lazy Evaluation of Influence Diagrams. In the experimental work, the efficiency of these algorithms is tested with several Influence Diagrams from the literature.     

A new optimal algorithm for weighted approximation and integration over ℝ

The complexities of weighted approximation and weighted integration problems for univariate functions defined over ℝ have recently been found in [7]. Complexity (almost) optimal algorithms have also been provided therein. In this paper, we propose another class of (almost) optimal algorithms that, for a number of instances, are easier to implement. More importantly, these new algorithms have a cost smaller than the original algorithms from [7]. Since both classes of algorithms are (almost) optimal, their costs differ by a multiplicative constant that depends on the specific weight functions and the error demand. In one of our tests we observed this constant to be as large as four, which means a cost reduction by a factor of four. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Adult Training Centre Problem: A Case Study

An optimal solution is found to a real-world problem which has the characteristics of a multiple travelling-salesman problem. It deals specifically with methods of obtaining the 'best' routeing for four vehicles which provide a daily service from a depot to 38 locations. The solution technique uses both heuristic and exact algorithms to derive the order for visits to the 38 locations.     

Strongly optimal algorithms and optimal information in estimation problems

This paper studies some aspects of information-based complexity theory applied to estimation, identification, and prediction problems. Particular emphasis is given to constructive aspects of optimal algorithms and optimal information, taking into account the characteristics of certain types of problems. Special attention is devoted to the investigation of strongly optimal algorithms and optimal information in the linear case. Two main results are obtained for the class of problems considered. First, central algorithms are proved to be strongly optimal. Second, a simple solution is given to a particular case of optimal information, called optimal sampling design, which is of great interest in system and identification theory.     

Multi-level substructuring combined with model order reduction methods

In many fields of engineering problems linear time-invariant dynamical systems (LTI systems) play an outstanding role. They result for instance from discretizations of the unsteady heat equation and they are also used in optimal control problems. Often the order of LTI systems is a limiting factor, since it becomes easily very large. As a consequence these systems cannot be treated efficiently without model reduction algorithms. In this paper a new approach for the combination of model order reduction methods and recent multi-level substructuring (MLS) techniques is presented. Similar multi-level substructuring methods have already been applied successfully to huge eigenvalue problems up to several millions of degrees of freedom. However, the presented approach does not make use of a modal analysis like former algorithms. Instead the original system is decomposed in smaller LTI systems which are treated with recent model reduction methods. Furthermore, the error which is induced by this substructuring approach is analysed and numerical examples based on the Oberwolfach benchmark collection are given in this paper.     

时变需求等量进货情形下集成供应链生产订货策略研究

构建了一个包含原料采购、生产和销售过程的集成供应链模型,研究了由原料、生产商和销售商产品构成的三层库存系统的生产订货问题。在有限的规划期内,销售商每次进货量相同,生产商按照EOQ模型采购原材料。以最小化供应链系统的总运营成本为目标,构建一个混合整数非线性规划模型,寻找销售商最优订货方案和生产商最佳生产策略。首先利用网络优化方法求解生产商的最优生产计划,其次利用定界穷举法寻求销售商最优的订货周期,给出了具体的计算方法和Matlab程序。通过算例分析验证了算法的有效性,并研究了各参数对最小费用及最优解的影响。     

带有资源转移时间的RCPSP资源流模型及算法

本文在传统资源受限项目调度问题(resource-constrained project scheduling problem, RCPSP)中引入资源转移时间,为有效获得问题的最优解,采用资源流编码方式表示可行解,建立了带有资源转移时间的RCPSP资源流优化模型,目标为最小化项目工期。根据问题特征设计了改进的资源流重构邻域算子,分别设计了改进的禁忌搜索算法和贪心随机自适应禁忌搜索算法求解模型。数据实验结果表明,相较于现有文献中的方法,所提两种算法均可针对更多的项目实例求得最优解,并且得到最优解的时间更短,求解效率更高。此外,分析了算法在求解具有不同特征的项目实例时的性能,所得结果为项目经理结合项目特征评价算法适用性提供了指导。