Dampening controllers via a Riccati equation approach

An algorithm is presented which computes a state feedback for a standard linear system which not only stabilizes, but also dampens the closed-loop system dynamics. In other words, a feedback gain matrix is computed such that the eigenvalues of the closed-loop state matrix are within the region of the left half-plane where the magnitude of the real part of each eigenvalue is greater than that of the imaginary part, This may be accomplished by solving a damped algebraic Riccati equation and a degenerate Riccati equation. The solution to these equations are computed using numerically robust algorithms, Damped Riccati equations are unusual in that they may be formulated as an invariant subspace problem of a related periodic Hamiltonian system. This periodic Hamiltonian system induces two damped Riccati equations: one with a symmetric solution and another with a skew symmetric solution. These two solutions result in two different state feedbacks, both of which dampen the system dynamics, but produce different closed-loop eigenvalues, thus giving the controller designer greater freedom in choosing a desired feedback     

A new stochastic approach for solution of Riccati differential equation of fractional order

In this article, a stochastic technique has been developed for the solution of nonlinear Riccati differential equation of fractional order. Feed-forward artificial neural network is employed for accurate mathematical modeling and learning of its weights is made with heuristic computational algorithm based on swarm intelligence. In this scheme, particle swarm optimization is used as a tool for the rapid global search method, and simulating annealing for efficient local search. The scheme is equally capable of solving the integer order or fractional order Riccati differential equations. Comparison of results was made with standard approximate analytic, as well as, stochastic numerical solvers and exact solutions.     

H∞滤波问题数值求解的精细积分算法

有限时间H∞滤波的Riccati方程和滤波方程分别为非线性矩阵微分方程和线性变系 数微分方程,而且Riccati微分方程解的存在性还依赖于参数 γ-2,因此求这些方程的数值解一 般比较困难.按照结构力学与最优控制的模拟关系,Riccati方程解存在的临界参数 γ-2cr对应于 广义Rayleigh商的一阶本征值.因此可以用精细积分法结合扩展的Wittrick-Williams(W-W) 算法计算 γ-2cr .并求解Ricclati方程,滤波微分方程的解也可以由精细积分法计算.     

Bacterial Foraging Optimization Approach to Portfolio Optimization

In this paper we propose a heuristic approach based on bacterial foraging optimization (BFO) in order to find the efficient frontier associated with the portfolio optimization (PO) problem. The PO model with cardinality and bounding constraints is a mixed quadratic and integer programming problem for which no exact algorithms can solve in an efficient way. Consequently, various heuristic algorithms, such as genetic algorithms and particle swarm optimization, have been proposed in the past. This paper aims to examine the potential of a BFO algorithm in solving the PO problem. BFO is a new swarm intelligence technique that has been successfully applied to several real world problems. Through three operations, chemotaxis, reproduction, and elimination-dispersal, the proposed BFO algorithm can effectively solve a PO problem. The performance of the proposed approach was evaluated in computational tests on five benchmark data sets, and the results were compared to those obtained from existing heuristic algorithms. The proposed BFO algorithm is found to be superior to previous heuristic algorithms in terms of solution quality and time.     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

A structure-preserving Jacobi algorithm for quaternion Hermitian eigenvalue problems

A new real structure-preserving Jacobi algorithm is proposed for solving the eigenvalue problem of quaternion Hermitian matrix. By employing the generalized JRS-symplectic Jacobi rotations, the new quaternion Jacobi algorithm can preserve the symmetry and JRS-symmetry of the real counterpart of quaternion Hermitian matrix. Moreover, the proposed algorithm only includes real operations without dimension-expanding and is generally superior to the state-of-the-art algorithm. Numerical experiments are reported to indicate its efficiency and accuracy.     

基于多约束QoS路由算法综述

随着网络技术的不断发展,实时多媒体技术不断涌现。如何根据不同的服务提供不同的QoS保证,并保证网络资源的有效利用,便成为当前互联网的一个重要任务。对该问题的解决方法称为多约束最优路径（MCOP）问题,MCOP问题是一个NPC问题,求解MCOP问题的算法可分为精确、近似和启发式等算法。文章通过对目前所出现的算法按照精确算法和近似算法两大类进行分析,分析目前出现的算法的一些优缺点,并根据网路技术的发展趋势,对现行多约束路由算法在以后如何实现更加快速精确的路径计算提出几点展望。     

Constructive heuristic algorithms for the open shop problem

In this paper we consider constructive heuristic algorithms for the open shop problem with minimization of the schedule length. By means of investigations of the structure of a feasible solution two types of heuristic algorithms are developed: construction of a rank-minimal schedule by solving successively weighted maximum cardinality matching problems and construction of an approximate schedule by applying insertion techniques combined with beam search. All presented algorithms are tested on benchmark problems from the literature. Our computational results demonstrate the excellent solution quality of our insertion algorithm, especially for greater job and machine numbers. For 29 of 30 benchmark problems with at least 10 jobs and 10 machines we improve the best known values obtained by tabu search.     

Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms

An algorithm is presented in this paper for computing state-space balancing transformations directly from a state-space realization. The algorithm requires no "squaring up" or unnecessary matrix products. Various algorithmic aspects are discussed in detail. A key feature of the algorithm is the determination of a contragredient transformation through computing the singular value decomposition of a certain product of matrices without explicitly forming the product. Other contragredient transformation applications are also described. It is further shown that a similar approach may be taken, involving the generalized singular value decomposition, to the classical simultaneous diagonalization problem. These SVD-based simultaneous diagonalization algorithms provide a computational alternative to existing methods for solving certain classes of symmetric positive definite generalized eigenvalue problems.     

Numerical improvements for solving Riccati equations

In this paper, we discuss some ideas for improving the efficiency and accuracy of numerical methods for solving algebraic Riccati equations (AREs) based on invariant or deflating subspace methods. The focus is on AREs for which symmetric solutions exist, and our methods apply to both standard linear-quadratic-Gaussian (or H₂) AREs and to so-called H_∞-type AREs arising from either continuous-time or discrete-time models. The first technique is a new symmetric representation of a symmetric Riccati solution computed from an orthonormal basis of a certain invariant or deflating subspace. The symmetric representation does not require sign definiteness of the Riccati solution. The second technique relates to improving algorithm efficiency. Using a pencil-based approach, the solution of a Riccati equation can always be reformulated so that the deflating subspace whose basis is being sought corresponds to eigenvalues outside the unit circle. Thus, the natural tendency of the QZ algorithm to deflate these eigenvalues last, and hence, to appear in the upper left blocks of the appropriate pencils, then reduces the amount of reordering that must be done to a Schur form     

自由终端随机最优调节器的注记

本文讨论了无限时间自由终端随机最优调节器问题和其相应的广义代数R iccati方程解之间的关系.具体而言,本文证明了无限时间自由终端随机最优调节器对应着广义代数R iccati方程的最小非负解,该最小解的核空间等于随机系统的精确不能观子空间.另外本文指出了以往文献中关于广义代数R iccati方程最大解存在性的一个证明错误,并对错误进行了分析.     

Heuristics for scheduling in flowshops and flowline-based manufacturing cells to minimize the sum of weighted flowtime and weighted tardiness of jobs

The problem of scheduling in two different types of flowshops (all jobs available at time zero, different job availability times known a priori) and in flowline-based manufacturing cells is considered with the objective of minimizing the sum of weighted flowtime and weighted tardiness of jobs. First, heuristic preference relations are developed by the consideration of lower bounds on the completion times, operation due-dates, and weights for holding and tardiness of jobs. A heuristic algorithm for scheduling is then proposed by making use of the heuristic preference relations. Two more heuristic algorithms are developed by implementing an improvement scheme to enhance the quality of the solution given by the first heuristic algorithm. The proposed and the existing heuristics are evaluated with respect to the three problem classes under consideration by solving a large number of randomly generated problems. The results of an extensive computational investigation for various problem sizes are presented. It has been observed that all three proposed heuristics perform better than the existing heuristics in giving a solution of superior quality and that the first proposed heuristic yields a good solution by requiring a negligible CPU time. In addition, an experimental investigation is carried out to evaluate the effectiveness of the improvement scheme when implemented in the existing heuristics, and also the effectiveness of heuristics based on simulated annealing. The results are discussed in detail.     

Realization of bilinear stochastic systems

This note considers the problem of realization of bilinear stochastic systems (BLSR). First an explicit statement for the BLSR problem is presented. Next a realization algorithm is developed. In this algorithm the state vector is picked as a basis in the subspace obtained by projecting an appropriately defined past vector onto an appropriately defined future vector. Also, the realization algorithm involves solving a matrix nonlinear equation which is akin to the algebraic Riccati equation, except for one additional term.     

面向无线内容分发网络的树形拓扑生成算法

在无线内容分发网络中,为减轻骨干网络的传输压力,可将网络拓扑结构构建为以基站和Wi Fi接入点为根的若干棵最小生成树,并对生成树的深度和每个节点的度数进行约束。这种深度和度数约束的最小生成树问题是一个NP完全问题。针对该问题,首先提出能够生成优质近似解的启发式算法,该算法在不违反深度以及度数约束的情况下构建生成树,算法思想为在服务性节点相连的边中选择与当前生成树相连且权值最小的边加入生成树。然后在生成初始近似解的基础上采用定制的禁忌搜索算法和模拟退火算法对该近似解实施进一步优化。实验结果表明,在给定的约束条件下,禁忌搜索算法求得的解优于现有的遗传算法,在深度约束为4以及度数约束为10的条件下,解的改进幅度可达18.5%,所提算法的运行速度比遗传算法提高了10倍。     

Polynomial J-spectral factorization in minimal state space

By a specific choice of matrices in optimal LQ return difference equality, we develop a simple state-space algorithm for polynomial J-spectral factorization. For this purpose we solve a minimal-order algebraic Riccati equation, the order obtained by solving an Integer Linear Programming (ILP) problem. An example that cannot be solved by the existing algorithms illustrates our algorithm.     

A stochastic algorithm for makespan minimized multi-agent path planning in discrete space

Makespan minimized multi-agent path planning (MAPP) requires the minimization of the time taken by the slowest agents to reach its destination. The resulting minimax objective function is non-smooth and the search for an optimal solution in MAPP can be intractable. In this work, a maximum entropy function is adopted to approximate the minimax objective function. An iterative algorithm named probabilistic iterative makespan minimization (PIMM) is then proposed to approximate a makespan minimized MAPP solution by solving a sequence of computationally hard MAPP minimization problems with a linear objective function. At each iteration, a novel local search algorithm called probabilistic iterative path coordination (PIPC) is used to find a sufficiently good solution for each MAPP minimization problem. Experimental results from comparative studies with existing MAPP algorithms show that the proposed algorithm strikes a good tradeoff between the quality of the makespan minimized solution and the computational cost incurred.     

New iterative algorithm for algebraic Riccati equation related to H∞ control problem of singularly perturbed systems

We present the solution to the algebraic Riccati equation (ARE) with indefinite sign quadratic term related to the H_∞ control problem for singularly perturbed systems by means of a Kleinman type algorithm. The resulting algorithm is very efficient from the numerical point of view because the ARE is solvable even if the quadratic term has an indefinite sign. Moreover, the resulting iterative algorithm is quadratically convergent. We also present an algorithm for solving the generalized algebraic Lyapunov equation on the basis of the fixed point algorithm     

A Nonrecursive Solution Method for the Linear-Quadratic Optimal Control Problem with a Singular Transition Matrix

In the optimal linear regulator problem the control vector is usually determined by solving the algebraic matrix Riccati equation using successive substitutions. This, however, can be rather inefficient from a computational point of view. A nonrecursive method which requires that the transition matrix is nonsingular has been proposed by Vaughan (1970). In the present paper we present a nonrecursive solution to the matrix Riccati equation for the case that the transition matrix may be singular. We show that this procedure leads to the same numerical results as the standard iteration of the matrix Riccati equation.     

Probabilistic GRASP-Tabu Search algorithms for the UBQP problem

This paper presents two algorithms combining GRASP and Tabu Search for solving the Unconstrained Binary Quadratic Programming (UBQP) problem. We first propose a simple GRASP-Tabu Search algorithm working with a single solution and then reinforce it by introducing a population management strategy. Both algorithms are based on a dedicated randomized greedy construction heuristic and a tabu search procedure. We show extensive computational results on two sets of 31 large random UBQP instances and one set of 54 structured instances derived from the MaxCut problem. Comparisons with state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that the reinforced GRASP-Tabu Search algorithm is able to improve the previous best known results for 19 MaxCut instances.