收敛共轭梯度方法参数βk的条件

本文给出确定共轭梯度方法中参数βk范围的两个条件-条件Ⅰ和条件Ⅱ,它们都确保方法的全局收敛．在条件Ⅰ和Gilbert＆Nocedal（1992）引入的性质（*）下及在条件Ⅱ和Wolfe条件下,分别建立了共轭梯度算法的收敛性定理．     

不可微规划的极大熵不动点算法

本文将极大熵逼近方法和不动点计算方法有机地结合,提出了一种不可微规划计算方法．该方法同样也适用于求解可微规划,而后给出了该方法的收敛性     

A Learning Algorithm for the Control of Continuous Action Set-Point Regulator Systems

The convergence properties for reinforcement learning approaches, such as temporal differences and Q-learning, have been established under moderate assumptions for discrete state and action spaces. In practice, however, many systems have either continuous action spaces or a large number of discrete elements. This paper presents an approximate dynamic programming approach to reinforcement learning for continuous action set-point regulator problems, which learns near-optimal control policies based on scalar performance measures. The continuous-action space (CAS) algorithm uses derivative-free line search methods to obtain the optimal action in the continuous space. The theoretical convergence properties of the algorithm are presented. Several heuristic stopping criteria are investigated and practical application is illustrated by two example problems—the inverted pendulum balancing problem and the power system stabilization problem.     

Optimal Control of a Ship for Collision Avoidance Maneuvers

We consider a ship subject to kinematic, dynamic, and moment equations and steered via rudder under the assumptions that the rudder angle and rudder angle time rate are subject to upper and lower bounds. We formulate and solve four Chebyshev problems of optimal control, the optimization criterion being the maximization with respect to the state and control history of the minimum value with respect to time of the distance between two identical ships, one maneuvering and one moving in a predetermined way.Problems P1 and P2 deal with collision avoidance maneuvers without cooperation, while Problems P3 and P4 deal with collision avoidance maneuvers with cooperation. In Problems P1 and P3, the maneuvering ship must reach the final point with a given lateral distance, zero yaw angle, and zero yaw angle time rate. In Problems P2 and P4, the additional requirement of quasi-steady state is imposed at the final point.The above Chebyshev problems, transformed into Bolza problems via suitable transformations, are solved via the sequential gradient-restoration algorithm in conjunction with a new singularity avoiding transformation which accounts automatically for the bounds on rudder angle and rudder angle time rate.The optimal control histories involve multiple subarcs along which either the rudder angle is kept at one of the extreme positions or the rudder angle time rate is held at one of the extreme values. In problems where quasi-steady state is imposed at the final point, there is a higher number of subarcs than in problems where quasi-steady state is not imposed; the higher number of subarcs is due to the additional requirement that the lateral velocity and rudder angle vanish at the final point.     

A Shifted-Barrier Primal-Dual Algorithm Model for Linearly Constrained Optimization Problems

In this paper we describe a Newton-type algorithm model for solving smooth constrained optimization problems with nonlinear objective function, general linear constraints and bounded variables. The algorithm model is based on the definition of a continuously differentiable exact merit function that follows an exact penalty approach for the box constraints and an exact augmented Lagrangian approach for the general linear constraints. Under very mild assumptions and without requiring the strict complementarity assumption, the algorithm model produces a sequence of pairs converging quadratically to a pair where satisfies the first order necessary conditions and is a KKT multipliers vector associated to the linear constraints. As regards the behaviour of the sequence x ^k alone, it is guaranteed that it converges at least superlinearly. At each iteration, the algorithm requires only the solution of a linear system that can be performed by means of conjugate gradient methods. Numerical experiments and comparison are reported.     

The conjugacy problem for Dehn twist automorphisms of free groups

A Dehn twist automorphism of a group G is an automorphism which can be given (as specified below) in terms of a graph-of-groups decomposition of G with infinite cyclic edge groups. The classic example is that of an automorphism of the fundamental group of a surface which is induced by a Dehn twist homeomorphism of the surface. For , a non-abelian free group of finite rank n, a normal form for Dehn twist is developed, and it is shown that this can be used to solve the conjugacy problem for Dehn twist automorphisms of . Received: February 12, 1996.     

Schemata, Distributions and Graphical Models in Evolutionary Optimization

In this paper the optimization of additively decomposed discrete functions is investigated. For these functions genetic algorithms have exhibited a poor performance. First the schema theory of genetic algorithms is reformulated in probability theory terms. A schema defines the structure of a marginal distribution. Then the conceptual algorithm BEDA is introduced. BEDA uses a Boltzmann distribution to generate search points. From BEDA a new algorithm, FDA, is derived. FDA uses a factorization of the distribution. The factorization captures the structure of the given function. The factorization problem is closely connected to the theory of conditional independence graphs. For the test functions considered, the performance of FDA—in number of generations till convergence—is similar to that of a genetic algorithm for the OneMax function. This result is theoretically explained.     

A transfer algorithm for hierarchical clustering

Transfer algorithms are usually used to optimize an objective function that is defined on the set of partitions of a finite set X. In this paper we define an equivalence relation ? on the set of fuzzy equivalence relations on X and establish a bijection from the set of hierarchies on X to the set of equivalence classes with respect to ?. Thus, hierarchies can be identified with fuzzy equivalence relations and the transfer algorithm can be modified in order to optimize an objective function that is defined on the set of hierarchies on X.     

Complexity of linear programming

The complexity of linear programming is discussed in the “integer” and “real number” models of computation. Even though the integer model is widely used in theoretical computer science, the real number model is more useful for estimating an algorithm's running time in actual computation.Although the ellipsoid algorithm is a polynomial-time algorithm in the integer model, we prove that it has unbounded complexity in the real number model. We conjecture that there exists no polynomial-time algorithm for the linear inequalities problem in the real number model. We also conjecture that linear inequalities are strictly harder than linear equalities in all “reasonable” models of computation.     

一种改进的指针安全分析算法

指针的安全性是C语言程序中的常见问题,它严重影响到系统的安全性.针对指针静态分析中的精度问题,比较分析了目前常见的5种指针分析算法的优缺点,提出了一种基于流不敏感的改进指针静态分析算法.该算法是在Steensgaard算法的基础上,对程序的控制流图进行改进,通过该算法可以得到比常见的数据流不敏感算法更为精确的指针分析结果.在实验室开发的国内首款商用编译器中实现了该算法,实验结果表明该算法可以提高指针分析的精度.