Invariant imbedding and inverse problems with applications to radiative transfer

In this paper, we developed two methods to solve the inverse problem of a nonlinear integro-differential equation. Both methods are based on the principle of invariant imbedding. The first method involves two auxiliary integro-differential equations. The inverse problem is solved by a sequence of approximation solutions of linear equations. The second method involves algebraic equations of scattering matrices under the so-called star-product. An application to a radiative transfer problem such as correction of atmospheric effects on remote sensing is discussed.     

Invariant imbedding and the method of lines for parallel computers

Recursion relations have been used to allow the solution of the invariant imbedding equations with singularities. We demonstrate that these same relations can be used in an efficient implementation of invariant imbedding for massively parallel computers. The parallel implementation of invariant imbedding can be used in conjuction with the method of lines to solve partial differential equations. We consider the problem of assigning lines to processors to minimize communication delays and the effect of asynchronous relaxation. Each algorithm is implemented and run on the NCUBE/ten hypercube, and timing data, speedup and normalized speedup are given. Operation counts are also given for each algorithm.     

Solution of the general moment problem via a one-parameter imbedding

This paper presents a computational theory for the general scalar moment problem. The formalism is sufficiently general to encompass problems in sensor arrays with arbitrary geometry and dynamics, and in nonuniform multidimensional sampling. Given a finite set of moments, the theory provides a test for the existence of a positive measure which is consistent with such data. At the same time, the theory also provides a characterization of all such consistent positive measures. It should be noted that classical results (e.g., in the theory of the trigonometric moment problem, Hamburger, Stieljes, Nevanlinna-Pick interpolation, etc.) are not applicable to the general setting sought herein where there is no natural shift operator in the space spanned by the integration kernels. The centerpiece of the theory is a differential equation which depends on the given finite set of moments and on an arbitrary positive function /spl Psi/-which plays the role of a "free parameter." The differential equation has an exponentially attractive point of equilibrium if and only if there exists a consistent positive measure. For each /spl Psi/, the fixed point determines a corresponding measure. Suitable choice of /spl Psi/ allows recovering any measure which is consistent with the data. The fixed point of the differential equation corresponds to an extremum of an entropy-like functional, and the differential equation is constructed via an appropriate homotopy that follows changes in the Lagrange multipliers from a convenient starting value to a value for the multipliers that corresponds to the given moments.     

An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs

In this paper, a graph problem on connected, weighted, undirected graphs, called the searchlight guarding problem, is considered. Assume that there is a fugitive who moves along the edges of the graph at a random speed. The task involves placing a set of searchlights at vertices to search the edges of the graph and to spot the fugitive. Suppose that placing a searchlight at some vertex incurs some building cost. The searchlight guarding problem is to allocate a set S of searchlights at the vertices such that the total cost of the vertices in S is minimized. If there is more than one set of searchlights, each with a minimum building cost, then identify the set with the minimum search time, that is, where the time slots needed to spot the fugitive is the minimum. As is well established, the problem is NP-hard on weighted bipartite graphs but is linear-time solvable on weighted trees. In this paper, the design of a linear-time optimal algorithm for the searchlight guarding problem on weighted interval graphs is presented. It entails two phases. In the first phase, a set of searchlights with minimum guarding cost is identified and the search directions of all edges are assigned. To achieve this task, a new problem, called the edge-direction assignment problem, is first defined and the problem on weighted complete-split graphs is solved by the greedy strategy. Based on this computational result, the problem of finding the set of searchlights with minimum guarding cost and assigning the search directions of all edges is solved by the dynamic programming strategy. Then, in the second phase, the search time slots of each edge are determined on the basis of the results of the first phase and on some properties of interval graphs.     

An optimal algorithm for solving the searchlight guarding problem on weighted two-terminal series-parallel graphs

In this paper, we consider a graph problem on a connected weighted undirected graph, called the searchlight guarding problem. Our problem is an extension of so-called graph searching/guarding problem by considering the time slot parameter in addition to the traditional building cost. Suppose that there is a fugitive who moves along the edges of the graph at any speed. We want to place a set of searchlights at the vertices to search the edges of the graph and capture the fugitive. It costs some building cost to place a searchlight at some vertex. The searchlight guarding problem is to allocate a set S of searchlights at the vertices such that the total costs of the vertices in S is minimized. If there is more than one set of searchlights with the minimum building cost, then find the one with the minimum searching time, that is, the time slots needed to capture the fugitive is the minimum. The problem is known to be NP-hard on weighted bipartite graphs, split graphs, and chordal graphs; and it is linear time solvable on weighted trees and interval graphs. In this paper, an algorithm is designed to solve the problem on weighted two-terminal series-parallel graphs. It works on the parsing tree structure of the given two-terminal series-parallel graph. The algorithm is divided into two phases. In the phase one, we first extract some useful properties of optimal solutions. Employing these properties, an algorithm is designed to find the set of searchlights with the minimum guarding cost and to assign the searching directions of all edges by the dynamic programming strategy. In the phase two, the searched time slots of all edges are determined by the breadth-first-search from the root of the parsing tree. The time complexities of both phases are linear. Thus, our algorithm is time optimal. Received: 12 March 1996 / 27 May 1997     

Discrete invariant imbedding and front-tracking

Discrete invariant imbedding is combined with frontracking to give a method for the numerical solution of free boundary problems in one dimension which requires only marginally more effort than that required to solve analogous problems with fixed boundaries.     

The slab dividing approach to solve the EuclideanP-Center problem

Givenn demand points on the plane, the EuclideanP-Center problem is to findP supply points, such that the longest distance between each demand point and its closest supply point is minimized. The time complexity of the most efficient algorithm, up to now, isO(n ² p–1· logn). In this paper, we present an algorithm with time complexityO(n ⁰(P)).     

基于列生成算法求解动态库存板坯分配问题

针对钢铁企业中遇到的动态库存板坯分配问题进行了研究。建立了一个0-1整数规划数学模型,该模型的目标是最小化板坯与合同规格差异费用以及板坯在库停留所产生的库存成本费用之和。根据问题特点,使用Danzig-Wolfe策略将这个模型分解为一个带有集划分约束的主问题和一个具有背包特征约束的价格子问题,开发了分支价格算法进行求解。计算结果表明所开发的分支价格算法能够最优求解生产实际问题。     

钢铁企业板坯动态分配问题的建模与分散搜索算法求解

板坯动态分配问题是在一定周期内, 将炼钢-连铸工序动态产出的余材板坯合理分配给期货合同、潜在合同或自拟合同, 使加权费用和最小. 对该问题建立0-1 整数规划模型, 针对问题的NP- 难求解性, 设计基于多邻域的分散搜索算法对问题近似求解, 并加入随机策略防止算法陷入局部最优. 分别采用模拟数据和实际数据进行测试, 所提出的算法与商业软件CPLEX 相比, 可在较短时间内获得近优解, 在解的质量和计算时间方面均优于人工方法.     

基于粒子群算法求解区间值板坯设计优化问题

为了适应大规模定制对连铸计划的新要求,提出了在板坯设计阶段固定板坯重量的策略,以减少过度追求生产柔性造成的高成本。建立了考虑工艺限制的区间值板坯设计模型,该模型是以最小化板坯数量和总盈余量为优化目标的多目标整数规划模型。结合问题的特点,采用模糊决策方法对多目标函数进行集成,提出了符合板坯设计的粒子群编码规则,并利用粒子群算法对模型进行了求解,最后通过实例验证了算法的可行性,并与该问题的下界进行比较,表明了算法的有效性和稳定性。     

约束满足技术在板坯排序中的应用

热轧调度中的板坯排序问题是一类特殊的排序问题,具有约束条件复杂、NP难特点。为了简化问题,将板坯排序问题转化为一个约束满足问题处理。给出板坯排序问题的约束满足模型,设计了基于约束满足和启发式混合求解算法。用3组实际生产数据对算法性能进行验证,说明了算法的有效性。     

Modelling and a segmented dynamic programming-based heuristic approach for the slab stack shuffling problem

This paper studies the slab stack shuffling (SSS) problem in the slab yard, which is a key logistics problem between the continuous casting stage and the hot rolling mill in the steel industry. The problem is to choose appropriate slabs for a sequence of rolling items, from their respective candidate slab sets (families) with a view to reducing the resulting shuffling workload. Although the SSS problem has been investigated by a few researchers, the problem under consideration has several new features. One of them is that the shuffled slab will not return the original stack but remain at the new position. Another requires that every selected slab be taken out in time, which will result in balancing the crane workloads among the storage areas of the slab yard to a degree. In addition, the local similarity of slab families is also considered, the closer the items in the rolling sequence, the more the common slabs between the corresponding families. For the problem, an integer programming model is proposed by considering the above features and requirements. For small-scaled problem, a dynamic programming approach is first constructed to obtain its optimal solution. For the practical scale, due to its intractability, we propose a segmented dynamic programming (SDP)-based heuristic, which partitions the sequence of items into a series of segments, each of which corresponds to a subproblem. The subproblems are solved sequentially using the dynamic programming. And the reassignment strategy of common slabs and the exchange strategy of candidate slabs are designed to improve the heuristic. Two interesting properties of the problem are also derived to speed up the SDP-based heuristic approach. The experiment results show that the heuristic is very close to the optimum in average solution quality for the small-scaled problem, obviously better than the CP Optimizer for the medium scale, and can reduce the crane workload by 10.76% on average for the practical scale.     

A comparative study of invariant imbedding and superposition

A comparison is made between a certain version of invariant imbedding and the method of superposition, as represented by the Goodman-Lance method of complementary functions, with regard to their computational efficiency and effectiveness for linear two-point boundary-value problems. The comparison is most complete for the class of problems termed normal. For such problems superposition appears to be preferable for problems with a sufficiently short underlying interval, on grounds of lesser effort, but the accuracy of super position degenerates more rapidly than that of invariant imbedding as the interval length increases, and consequently the latter method seems preferable for long problems. General areas of possible future investigation are identified.     

非线性奇异系统的受控不变分布及其不变性

该文研究非线性奇异系统受控不变分布问题.提出了非线性奇异系统受控不变分布的概念;讨论了受控不变分布的一些不变性质;给出了一个计算包含在输出核(ker(dh))内的最大受控不变分布的算法,并讨论了该算法的一些性质.最后给出一个计算包含在输出核内的最大受控不变分布的例子.     

A globally convergent algorithm based on imbedding and parametric optimization

The continuation method, well-established for the solution of nonlinear equations is extended to restricted optimization problems. Only the locally active restrictions are considered along the homotopy path. It is assumed that there are only finitely many critical points, i. e. that there are only finitely many changes of the index set of active restrictions. The globally convergent algorithm which we present proceeds in three stages:

1. Within each stability region, the solution is computed by the classical continuation method.
2. On the boundary of a stability region, a critical point \(\bar t\) is determined.
3. A new active index set is determined when \(\bar t\) is passed.

For the class of convex problems, the hypotheses for the convergence of the algorithm may be secured. The algorithm is applied to several examples.     

横切侵入性和横切不变性

由于面向方面语言的不知觉性和多量化特点,模块分析和模块推理比传统方法学更加困难.为了解决面向方面语言的横切安全和横切质量问题,使用前提条件和后验条件约束横切模块和被横切模块,然而在横切过程中寻找前提条件和后验条件的失败原因十分微妙和复杂.为了分析一个横切关注点的行为影响,程序员需要考虑方面本身和这个方面影响的系统其他部分.当几个方面编织在同一个切入点,危险干扰分析变得更加复杂.类似面向对象语言中的行为子类型概念,引入横切不变性概念.为了检查由于破坏横切不变性引起的行为错误和其他4种简单行为错误,基于软件行为契约提出一个横切不变性检测算法.为了形式化这个算法,提出Crosscutting Contract演算和一组契约求解规则,并通过定义和证明契约完备性来保证契约求解过程的正确性.还使用一个例子说明如何使用这些契约求解规则检测和分析行为错误.     

Optimal inputs and sensitivites for nonlinear process parameter estimation using imbedding techniques

It has been shown [2], [3] that for parameter estimation of a dynamical system with a limited number of measurements, the use of inputs maximizing the sensitivity of the states with respect to the parameters increases the accuracy of the estimation. In this correspondence the continuation method is used both for determining the optimal inputs and estimating the unknown parameters. A simple example demonstrates the approach.     

非线性定常系统及其定常Lyapunov函数的多项式等价类

非线性定常系统及其定常Ｌｙａｐｕｎｏｖ函数的多项式等价类苗原李春文杜继宏（清华大学自动化系北京１０００８４）关键词稳定性,非线性多项式系统,李亚普诺夫函数．收稿日期１９９５－０５－１６１引言李亚普诺夫第二方法作为处理系统稳定性问题的最主要的方法之一已...