一种具有遗忘特性的在线学习算法框架

基于凸优化中的对偶理论,提出了一种具有遗忘特性的在线学习算法框架。其中,Hinge函数的Fenchel对偶变换是将基本学习问题由批量学习转化为在线学习的关键。新的算法过程是通过以不同方式提升含有约束变量的对偶问题实现的:(1)梯度提升;(2)贪婪提升。回顾了以往的相关研究工作,并指出了与之的区别与联系。人造数据集和真实数据集上的实验结果证实了算法框架的有效性。算法可以很好地处理数据流中的分类面漂移问题,为设计和分析新的在线学习算法提供了一个新的思路。     

最大避障圆问题的提出与初探

提出了一个在有界区域内求对已知各障碍物的最大避障圆问题。首先给出此问题的数学描述,然后分析了当有界区域为圆域,并将各障碍物看成一个有限点集时,避障圆的基本性质,从而得到一种求最大避障圆的有效算法。     

有容量限制的运输问题

具有容量限制的运输问题可以用有界变量的线性规划问题求解,但是问题的规模往往变得很大,给求解带来不便。本文给出求解这一问题的表上作业法。     

一种新的运输问题对偶算法

本文给出求解运输问题的一种新的方法——运输问题对偶算法(仍是表上作业法)。最后给出的实例说明本文算法在解决某些问题时比[1]中方法简便。     

基于混合变量传递函数方法的圆柱壳屈曲分析

提出了一种分析正交各向异性圆柱壳和阶梯圆柱壳稳定性问题的混合变量传递函数方法。首先在壳体环向利用三角级数对位移变量进行展开 ,利用Fl櫣ｇｇｅ薄壳理论和变分原理 ,建立圆柱壳的平衡方程 ,找出对偶力变量 ,将平衡方程写成混合变量形式 ;通过定义混合状态变量 ,建立了系统的状态空间方程 ;然后利用传递函数方法 ,得到了具有任何轴对称边界条件轴压圆柱壳屈曲问题的解析解 ;最后通过位移连续和力平衡条件 ,得到了阶梯圆柱壳屈曲问题的解。理论解推导过程表明此方法在引入边界条件和进行阶梯圆柱壳求解时非常方便。算例分析的结果验证了本方法的正确性     

基于对偶四元数的航天器六自由度相对运动输入有界控制

利用对偶四元数的理论来分析航天器六自由度的相对运动,设计了一种考虑输入有界的姿轨一体化控制器。在介绍对偶数和对偶四元数的基础上推导六自由度相对运动的姿轨耦合模型;利用双曲正切函数绝对值小于1的特性来显式地构造有界控制器,分别设计两个相互耦合的自适应调节律来动态地改变控制器的输出,并基于李雅普诺夫稳定性理论严格证明了闭环系统的全局渐近稳定性;利用数学仿真实验来验证该控制器和控制力满足给定的约束条件,能够实现航天器六自由度相对运动的精确稳定控制,并且对模型参数不确定性和外界扰动具有鲁棒性。与其他方法相比,由该控制器计算得到的控制力矩器的收敛速度更快,输出的控制力矩和控制力的最大幅值更小,且消耗的能量也更少。     

基于拉格朗日松弛的航天测控调度上界求解算法

通过分析航天测控调度问题的测控需求,建立了航天测控调度0-1整数规划模型,运用拉格朗日松弛方法对模型中的设备约束和卫星约束进行了松弛,运用次梯度优化算法求得了拉格朗日对偶问题的上界.最后,通过对两个场景的试验分析,证明了运用次梯度优化算法求得的上界的有效性.     

求解压缩感知中信号重构问题的原始对偶算法

压缩感知理论(CS)是对信号压缩的同时进行感知的新理论,而如何通过有限的测量值准确地重构稀疏信号是压缩感知理论中的核心问题。为求解稀疏信号的重构问题,文章利用了一种基于邻近点算法的自适应一阶原始对偶算法,并证明了其全局收敛性,该算法通过研究l1范数最小化来求解信号重构问题。最后,对提出的算法进行数据仿真,并与压缩采样匹配追踪(CoSaMP)算法进行了对比,数据表明文章提出的算法计算速度更快。     

基于三维Hough变换的机载激光雷达平面地标提取

针对机载激光雷达点云数据中的平面地标检测问题,分析了以三维Hough变换为基础的传统的平面检测算法,指出其存在空间分割不一致问题,在检测法线垂向地标时出现"极点"现象。研究了三维Hough变换的空间完备分割条件,利用参数空间的对偶特性,提出了一种基于对偶空间分割的三维Hough变换算法,避免了空间不一致问题。仿真和实验证明,改进三维Hough变换算法在不增加计算量的同时,能够有效检测激光雷达点云中的平面地标。     

用线性规划法设计复系数FIR滤波器

讨论了在复Chebyshev逼近意义下设计复系数FIR滤波器问题。直接把复Chebyshev逼近问题离散化成有限维线性规划问题 ,再用单纯形法求解这种方法一直被认为只能设计实系数滤波器 ,而且计算量大、收敛速度慢。本文从直接离散化出发 ,推导出一种求解此问题的改进的单纯形算法 ,适用于设计复系数滤波器 ,极大地减小了计算量 ,提高了收敛速度。并证明了它与通过求解半无限线性规划的对偶问题而得到的改进的单纯形法是等价的。最后给出了算法的仿真结果     

A node covering algorithm

This paper describes a node covering algorithm, i.e., a procedure for finding a smallest set of nodes covering all edges of an arbitrary graph. The algorithm is based on the concept of a dual node-clique set, which allows us to identify partial covers associated with integer dual feasible solutions to the linear programming equivalent of the node covering problem. An initial partial cover with the above property is first found by a labeling procedure. Another labeling procedure then successively modifies the dual node-clique set, so that more and more edges are covered, i.e., the (primal) infeasibility of the solution is gradually reduced, while integrality and dual feasibility are preserved. When this cannot be continued, the problem is partitioned and the procedure applied to the resulting subproblems. While the steps of the algorithm correspond to sequences of dual simplex pivots, these are carried out implicitly, by labeling. The procedure is illustrated by examples, and some early computational experience is reported. We conclude with a discussion of potential improvements and extensions.     

A note on duality in homogeneous fractional programming

For a linear fractional programming problem, Sharma and Swarup have constructed a dual problem, also a linear fractional program, in which the objective functions of both primal and dual problems are the same. Craven and Mond have extended this result to a nonlinear fractional programming problem with linear constraints, and a dual problem for which the objective function is the same as that of the primal. This theorem is now further extended from linear to differentiable convex constraints.     

支持向量顺序回归机的线性规划算法

支持向量顺序回归机是标准支持向量分类机的一个推广，它是一个凸的二次规划问题。本文根据l1范数与l2范数等价关系和优化问题的对偶原理，把凸的二次规划转化成线性规划。由此提了支持向量顺序回归机的线性规划算法，进一步用数值实验验证了此算法的可行性和有效性。并与支持向量顺序回归机相比，它的运行时间缩短了，而且误差i不超过支持向量顺序回归机；     

An algorithm (GIPC2) for solving integer programming problems with separable nonlinear objective functions

This paper presents an algorithm for solving the integer programming problem possessing a separable nonlinear objective function subject to linear constraints. The method is based on a generalization of the Balas implicit enumeration scheme. Computational experience is given for a set of seventeen linear and seventeen nonlinear test problems. The results indicate that the algorithm can solve the nonlinear integer programming problem in roughly the equivalent time required to solve the linear integer programming problem of similar size with existing algorithms. Although the algorithm is specifically designed to solve the nonlinear problem, the results indicate that the algorithm compares favorably with the Branch and Bound algorithm in the solution of linear integer programming problems.     

A comparison of the primal-simplex and complementary pivot methods for linear programming

A comparison of the complementary pivot method of Lemke-Howson and the more commonly used primal-simplex method for solving linear programming problems in symmetric dual form has been made. In our tests the complementary pivot method shows a definite superiority over the simplex method both with regard to the number of iterations and computation time.     

A combination of Lagrangian relaxation and column generation for order batching in steelmaking and continuous‐casting production

This article considers the order batching problem in steelmaking and continuous‐casting production. The problem is to jointly specify the slabs needed to satisfy each customer order and group all the slabs of different customer orders into production batches. A novel mixed integer programming model is formulated for the problem. Through relaxing the order assignment constraints, a Lagrangian relaxation model is then obtained. By exploiting the relationship between Lagrangian relaxation and column generation, we develop a combined algorithm that contains nested double loops. At the inner loop, the subgradient method is applied for approximating the Lagrangian dual problem and pricing out columns of the master problem corresponding to the linear dual form of the Lagrangian dual problem. At the outer loop, column generation is employed to solve the master problem exactly and adjust Lagrangian multipliers. Computational experiments are carried out using real data collected from a large steel company, as well as on large‐scaled problem instances randomly generated. The results demonstrate that the combined algorithm can obtain tighter lower bound and higher quality solution within an acceptable computation time as compared to the conventional Lagrangian relaxation algorithm. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

球约束凸二次规划的一个算法

针对球约束凸二次规划问题,利用Lagrange对偶将其转化为无约束优化问题,然后运用单纯形法对其求解,获得原问题的最优解。最后,对文中给出的算法给出了论证。     

线性规划问题新解——改进大M法

借鉴两阶段法的求解思路,在用单纯形法求解线性规划问题时,对大M法进行改进,提出一种新的算法.这种改进后的算法可以有效克服原来两种算法的不足,既能降低理解难度,又能提高算法的效率,保证算法的全局收敛性.