A sampled normal form for feedback linearization

This paper discusses the problem of preserving approximated feedback linearization under digital control. Starting from a partially feedback linearizable affine continuous-time dynamics, a digital control procedure which maintains the dimension of the maximally feedback linearizable part up to any order of approximation with respect to the sampling period is proposed. The result is based on the introduction of a sampled normal form, a canonical structure which naturally appears when studying feedback linearization.This work was supported by an Italian 40% M.U.R.S.T. grant and a French M.E.N.-D.R.E.D. grant.     

Non-regular feedback linearization of nonlinear systems via a normal form algorithm

In this paper, the problem of non-regular static state feedback linearization of affine nonlinear systems is considered. First of all, a new canonical form for non-regular feedback linear systems is proposed. Using this form, a recursive algorithm is presented, which yields a condition for single input linearization. Then the left semi-tensor product of matrices is introduced and several new properties are developed. Using the recursive framework and new matrix product, a formula is presented for normal form algorithm. Based on it, a set of conditions for single-input (approximate) linearizability is presented.     

On manipulator control by exact linearization

Comments on the application to rigid link manipulators of geometric control theory, resolved acceleration control, operational space control, and nonlinear decoupling theory are given, and the essential unity of these techniques for externally linearizing and decoupling end effector dynamics is discussed. Exploiting the fact that the mass matrix of a rigid link manipulator is positive definite, and the fact that there is an independent input for each degree of freedom, it is shown that a necessary and sufficient condition for a locally externally linearizing and output decoupling feedback law to exist is that the end effector Jacobian matrix be nonsingular     

A normal form algorithm for the Brieskorn lattice

This article describes a normal form algorithm for the Brieskorn lattice of an isolated hypersurface singularity. It is the basis of efficient algorithms to compute the Bernstein–Sato polynomial, the complex monodromy, and Hodge-theoretic invariants of the singularity such as the spectral pairs and good bases of the Brieskorn lattice. The algorithm is a variant of Buchberger’s normal form algorithm for power series rings using the idea of partial standard bases and adic convergence replacing termination.     

纵列式无人直升机建模及其精确线性化方法研究

利用牛顿-欧拉法对纵列式无人直升机的近似悬停模态进行数学建模，得出标准仿射非线性状态方程，然后应用状态反馈精确线性化方法进行设计．仿真结果表明，系统输出可稳定跟踪给定信号．     

一种高效的分辨函数范式转换算法*

基于分辨矩阵获取一个决策表所有约简的过程实质上是一个将分辨函数从合取范式转换为析取范式的过程,其效率对于属性约简算法性能至关重要。依据人工范式转换的运行机制,充分利用合取运算和析取运算的吸收率,并借助队列结构,提出了一种面向分辨函数的范式转换算法。该算法易于理解,实现简便。仿真实验表明算法能够高效地完成范式转换。     

Automatic differentiation and nonlinear controller design by exact linearization

Various modern algorithms for controller design are based on differential-geometric concepts. A method of particular importance is called exact linearization via feedback. In this case, the implementation of the controller requires the computation of Lie derivatives, which have been computed symbolically. This can be very time consuming. We present a new computation method relying on automatic differentiation.     

A linearization algorithm for optimizing control systems subject to singular value inequalities

The design of feedback linear multivariable systems subject to inequality constraints frequently leads to nonlinear programming problems involving singular values of matrix transfer functions. We present a readily implementable and globally convergent algorithm for solving such problems. It exploits the structure inherent in singular values differently than do other existing methods.     

从合取范式到析取范式的转换研究

为了解决粗糙集分辨函数的计算、概念格中内涵缩减的计算、逻辑程序设计的规则简化等问题,抽象出了从合取范式到析取范式转换这一核心问题。提出了利用极小覆盖来实现从合取范式到析取范式的转换,给出了一个增量式的算法。为了扩大范式转换的使用范围,定义了伪合取范式,并给出伪合取范式到析取范式的转换方法。     

Robustness analysis of exact feedforward linearization based on differential flatness

A methodology to analyze robustness with respect to parametric uncertainty for exact feedforward linearization based on differential flatness is presented. The analysis takes into consideration the tracking error equation and thereafter makes use of a stability result by Kelemen coupled with results issued from interval analysis theory.     

Point stabilization of mobile robots via state-space exact feedback linearization

In this paper, we solve the point stabilization of mobile robots via state-space exact feedback linearization. The state-space exact feedback linearization has not been possible in the past for the point stabilization of mobile robots due to the restricted mobility caused by nonholonomic constraints. Under some proposed coordinates, however, the point stabilization problem can be exactly transformed into the problem of controlling a linear time-invariant system. Thus, using well-established linear control theory, the point stabilization of robots can be easily formulated.     

Position control of a PM stepper motor by exact linearization

The authors consider the position control of a permanent magnet (PM) stepper motor using the exact linearization method. This nonlinear controller takes into account the full dynamics of the stepper motor. In particular, the phase shift between voltage and current in each phase is automatically taken into account. The feedback linearization controller makes the stepper motor into a fast accurate positioning system. The authors consider the feedback linearization technique for the PM stepper motor and show, when the detent torque is neglected, how it quite naturally leads to the well-known DQ transformation of electric machine theory. The authors indicate how constant load torques may be asymptotically rejected by using a nonlinear observer     

An exact algorithm for minimum distortion embedding

Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5^n+o(n). This is the first algorithm breaking the trivial n!-barrier.     

基于分段线性的原油混输调度全局优化算法研究

随着激烈的市场竞争,原油混输调度问题成为炼油企业提高核心竞争力的重要环节。有效的原油混输调度策略能够在保证成品油质量的同时,快速响应市场竞争,节约成本,提高收益。本文使用了混合整数非线性规划(MINLP)模型来描述原油混输调度问题,并且对模型进行了与实际操作更为相符的改进,提出了基于分段线性化的求解非凸混合整数非线性规划问题的算法。将非凸的双线性项进行分段线性化可以使非凸的混合整数非线性规划模型近似等价为1个凸的混合整数二次规划(MIQCP)模型,通过使用凸二次规划基于的分支定界算法得到调度问题的近似全局最优解,实现原油混输调度中从港口油轮,到输油管道或存储罐,最后到达分离单元过程的卸载、存储等过程的优化操作。本文通过6个实例验证了文中改进的模型和提出的算法的有效性。结果表明,本文改进的模型和提出的算法可以获得原油混输调度问题的有效调度方案,解决分离单元(CDU)上料不连续、罐内与上料浓度不一致的问题,而且本算法求得的近似全局最优解可以保证在12%的范围内。     

A cone complementarity linearization algorithm for staticoutput-feedback and related problems

This paper describes a linear matrix inequality (LMI)-based algorithm for the static and reduced-order output-feedback synthesis problems of nth-order linear time-invariant (LTI) systems with n_u (respectively, n_y) independent inputs (respectively, outputs). The algorithm is based on a “cone complementarity” formulation of the problem and is guaranteed to produce a stabilizing controller of order m⩽n-max(n_u,n_y), matching a generic stabilizability result of Davison and Chatterjee (1971). Extensive numerical experiments indicate that the algorithm finds a controller with order less than or equal to that predicted by Kimura's generic stabilizability result (m⩽n-n_u-n_y+1). A similar algorithm can be applied to a variety of control problems, including robust control synthesis     

An exact algorithm for a Vehicle-and-Driver Scheduling Problem

This article introduces a combinatorial optimization problem that consists of assigning tasks to machines and operators, and sequencing the tasks assigned to each one. Two configurations exist. Machines alternate configurations, while the operators must start and finish the process in the same configuration. Moreover, machines and operator have limited capacities. The sequencing of the tasks must guarantee that each one is performed by a machine and an operator at the same time, and it is determined in order to minimize an overall cost function. Two critical aspects of the problem are the need of synchronizing the machine and the operator performing each task, and the need of minimizing the changeovers, which are pairs of tasks done consecutively by the same machine but by different operators. The problem is modeled as a vehicle routing problem with two types of vehicles and with two depots. We propose a mixed integer programming formulation, and introduce valid inequalities to strengthen its linear programming relaxation. We describe separation routines for these inequalities and design a branch-and-cut algorithm for the problem. The algorithm is tested on a set of benchmark instances showing that it is able to solve to optimality instances with up to 50 customers.     

An exact algorithm for the knapsack sharing problem

In this paper, we develop an exact algorithm for solving the knapsack sharing problem. The algorithm is a new version of the method proposed in Hifi and Sadfi (J. Combin. Optim. 6 (2002) 35). It seems quite efficient in the sense that it solves quickly some large problem instances. Its main principle consists of (i) finding a good set of capacities, representing a set of critical elements, using a heuristic approach, and (ii) varying the values of the obtained set in order to stabilize the optimal solution of the problem. Then, by exploiting dynamic programming properties, we obtain good equilibrium which lead to significant improvements. The performance of the proposed algorithm, based on a set of medium and large problem instances, is compared to the standard version of Hifi and Sadfi (2002). Encouraging results have been obtained.     

An exact subexponential-time lattice algorithm for Asian options

Asian options are popular financial derivative securities. Unfortunately, no exact pricing formulas exist for their price under continuous-time models. Asian options can also be priced on the lattice, which is a discretized version of the continuous- time model. But only exponential-time algorithms exist if the options are priced on the lattice without approximations. Although efficient approximation methods are available, they lack accuracy guarantees in general. This paper proposes a novel lattice structure for pricing Asian options. The resulting pricing algorithm is exact (i.e., without approximations), converges to the value under the continuous-time model, and runs in subexponential time. This is the first exact, convergent lattice algorithm to break the long-standing exponential-time barrier. An early version of this paper appeared in the Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004. T.-S. Dai was supported in part by NSC grant 94-2213-E-033-024. Y.-D. Lyuu was supported in part by NSC grant 94-2213-E-002-088.     

A new DSATUR-based algorithm for exact vertex coloring

This paper describes a new exact algorithm PASS for the vertex coloring problem based on the well known DSATUR algorithm. At each step DSATUR maximizes saturation degree to select a new candidate vertex to color, breaking ties by maximum degree w.r.t. uncolored vertices. Later Sewell introduced a new tiebreaking strategy, which evaluated available colors for each vertex explicitly. PASS differs from Sewell in that it restricts its application to a particular set of vertices. Overall performance is improved when the new strategy is applied selectively instead of at every step. The paper also reports systematic experiments over 1500 random graphs and a subset of the DIMACS color benchmark.