An Optimal Algorithm for Bound and Equality Constrained Quadratic Programming Problems with Bounded Spectrum

An implementation of the recently proposed semi-monotonic augmented Lagrangian algorithm for solving the large convex bound and equality constrained quadratic programming problems is considered. It is proved that if the algorithm is applied to the class of problems with uniformly bounded spectrum of the Hessian matrix, then the algorithm finds an approximate solution at O(1) matrix-vector multiplications. The optimality results are presented that do not depend on conditioning of the matrix which defines the equality constraints. Theory covers also the problems with dependent constraints. Theoretical results are illustrated by numerical experiments.     

改进的正则化模型在图像恢复中的应用

目的 由拟合项与正则项组成的海森矩阵,如果不具有特殊结构,其逆矩阵计算比较困难,为克服此缺点,提出一种海森矩阵可分块对角化的牛顿投影迭代算法。方法 首先,用L₂范数描述拟合项,用自变量是有界变差函数的复合函数刻画正则项,建立能量泛函正则化模型。其次,引入势函数,将正则化模型转化为增广能量泛函。再次,构造预条件矩阵,使得海森矩阵可分块对角化。最后,为防止牛顿投影迭代算法收敛到局部最优解,采用回溯线性搜索算法和改进的Barzilai-Borwein步长更新准则使得算法全局收敛。结果 针对图像去模糊正则化模型容易使边缘平滑和产生阶梯效应“两难”问题,提出一种新的正则化模型和牛顿投影迭代算法。仿真结果表明,“两难”问题通过本文算法得到了很好的解决。结论 与其他正则化图像去模糊模型相比,本文算法明显改善图像的质量,如有效地保护图像的边缘,抑制阶梯效应,相对偏差和误差较小,较高的峰值信噪比和结构相似测度。     

A hybrid approach to constrained global optimization

In this paper, we propose a novel hybrid global optimization method to solve constrained optimization problems. An exact penalty function is first applied to approximate the original constrained optimization problem by a sequence of optimization problems with bound constraints. To solve each of these box constrained optimization problems, two hybrid methods are introduced, where two different strategies are used to combine limited memory BFGS (L-BFGS) with Greedy Diffusion Search (GDS). The convergence issue of the two hybrid methods is addressed. To evaluate the effectiveness of the proposed algorithm, 18 box constrained and 4 general constrained problems from the literature are tested. Numerical results obtained show that our proposed hybrid algorithm is more effective in obtaining more accurate solutions than those compared to.     

基于稀疏表示的OFDM信号的DOA估计

针对正交频分复用（OFDM）, 宽带信号波达方向(DOA)估计问题, 提出一种基于宽带信号协方差矩阵稀疏表示的DOA估计方法。该方法是在协方差矩阵主对角线下对左下角三角形元素按各条对角线取平均值后形成一个新的向量, 然后将该向量写成冗余字典形式。在冗余字典下对信号进行稀疏性约束形成二阶锥约束优化问题, 再用工具箱SeDuMi来实现DOA估计。理论分析和仿真结果表明, 该方法在低信噪比和少快拍数下分辨率很高, 是一种有效的宽带信号DOA估计算法, 此方法优于基于高阶累积量算法和宽带聚焦算法的DOA估计方法。     

采用改进Levenberg-Marquardt法的快速弹性运动估计

弹性运动估计是近年来出现的一种有效的时间维视频预测编码技术,但其基于高斯-牛顿法的优化求解仍存在计算量高、收敛不稳定的问题.为此提出一种基于改进Levenberg-Marquardt（L-M）法的弹性运动估计算法.首先,根据弹性基函数和黑塞矩阵的数值对称性,给出了L-M黑塞矩阵的快速计算方法,将其计算量降低了62.5%.其次,通过理论和实验分析发现,L-M对角矩阵阻尼系数的更新因子对弹性运动估计性能有明显影响,进而采用最近2次迭代的搜索步长的平方商自适应地确定更新因子,并对该阻尼系数进行正、负交替更新.实验结果表明,对于具有不同空间分辨率和场景特点的视频序列,算法始终能够保持较高的估计精度,运动补偿的平均峰值信噪比较之基于块平移模型的全搜索和基于改进高斯-牛顿法的弹性运动估计分别提高2.54dB、1.77dB.并且,所提算法收敛速度快,一般只需1~2次迭代就能取得高于传统弹性运动估计和块平移全搜索的峰值信噪比.     

Stochastic radial basis function algorithms for large-scale optimization involving expensive black-box objective and constraint functions

This paper presents a new algorithm for derivative-free optimization of expensive black-box objective functions subject to expensive black-box inequality constraints. The proposed algorithm, called ConstrLMSRBF, uses radial basis function (RBF) surrogate models and is an extension of the Local Metric Stochastic RBF (LMSRBF) algorithm by Regis and Shoemaker (2007a) [1] that can handle black-box inequality constraints. Previous algorithms for the optimization of expensive functions using surrogate models have mostly dealt with bound constrained problems where only the objective function is expensive, and so, the surrogate models are used to approximate the objective function only. In contrast, ConstrLMSRBF builds RBF surrogate models for the objective function and also for all the constraint functions in each iteration, and uses these RBF models to guide the selection of the next point where the objective and constraint functions will be evaluated. Computational results indicate that ConstrLMSRBF is better than alternative methods on 9 out of 14 test problems and on the MOPTA08 problem from the automotive industry (Jones, 2008 [2]). The MOPTA08 problem has 124 decision variables and 68 inequality constraints and is considered a large-scale problem in the area of expensive black-box optimization. The alternative methods include a Mesh Adaptive Direct Search (MADS) algorithm (Abramson and Audet, 2006 [3]; Audet and Dennis, 2006 [4]) that uses a kriging-based surrogate model, the Multistart LMSRBF algorithm by Regis and Shoemaker (2007a) [1] modified to handle black-box constraints via a penalty approach, a genetic algorithm, a pattern search algorithm, a sequential quadratic programming algorithm, and COBYLA (Powell, 1994 [5]), which is a derivative-free trust-region algorithm. Based on the results of this study, the results in Jones (2008) [2] and other approaches presented at the ISMP 2009 conference, ConstrLMSRBF appears to be among the best, if not the best, known algorithm for the MOPTA08 problem in the sense of providing the most improvement from an initial feasible solution within a very limited number of objective and constraint function evaluations.     

Iterative weighted least squares algorithms for neural networks classifiers

This paper discusses learning algorithms of layered neural networks from the standpoint of maximum likelihood estimation. At first we discuss learning algorithms for the most simple network with only one neuron. It is shown that Fisher information of the network, namely minus expected values of Hessian matrix, is given by a weighted covariance matrix of input vectors. A learning algorithm is presented on the basis of Fisher's scoring method which makes use of Fisher information instead of Hessian matrix in Newton's method. The algorithm can be interpreted as iterations of weighted least squares method. Then these results are extended to the layered network with one hidden layer. Fisher information for the layered network is given by a weighted covariance matrix of inputs of the network and outputs of hidden units. Since Newton's method for maximization problems has the difficulty when minus Hessian matrix is not positive definite, we propose a learning algorithm which makes use of Fisher information matrix, which is non-negative, instead of Hessian matrix. Moreover, to reduce the computation of full Fisher information matrix, we propose another algorithm which uses only block diagonal elements of Fisher information. The algorithm is reduced to an iterative weighted least squares algorithm in which each unit estimates its own weights by a weighted least squares method. It is experimentally shown that the proposed algorithms converge with fewer iterations than error back-propagation (BP) algorithm.     

Total pressure losses minimization in turbomachinery cascades using the exact Hessian

A method for the design of turbomachinery cascades with minimum total pressure losses, subject to constraints on the minimum blade thickness and flow turning, is presented. It is based on the Newton–Lagrange method which requires the computation of first- and second-order sensitivities of the objective function and the constraints, with respect to the design variables. The computation of the exact Hessian of the function which expresses the difference in total pressure between the inlet to and the outlet from the cascade, is new in the literature. To compute the Hessian, the direct differentiation of the viscous flow equations is used for the first-order sensitivities of the functional and the flow-related constraints, followed by the discrete adjoint method. Since the objective function is defined along boundaries other than those controlled by the design variables, it is challenging to investigate the significance of all terms comprising the exact second-order sensitivity expressions. All these terms were temporarily computed using automatic differentiation and those which proved to be significant are hand-differentiated to minimize CPU cost and memory requirements. Insignificant terms are eliminated, giving rise to the so-called “exact” Hessian matrix. An “exactly” initialized quasi-Newton method was also programmed and tested. In the latter, at the first cycle, the exact gradients and Hessians are computed and used; during the subsequent optimization cycles, the discrete adjoint method provides the exact gradient whereas the Hessian is updated as in quasi-Newton methods. The comparison of the efficiency of the aforementioned methods depends on the number of design variables used; the “exactly” initialized quasi-Newton method constantly outperforms its conventional variant in terms of CPU cost, particularly in non-convex and/or constrained optimization problems.     

An asymmetry algorithm based on parameter transformation for Hessian matrix

An asymmetry algorithm recognition model, which is presented based on Hessian matrix transform by adjusting the diagonal parameter of Hessian matrix and which does not change the positive semi-definite characteristic, increases or decreases the distance between positive class or negative class and hyperplane on the asymmetry sample set and realizes our intention for separating the small samples more precisely. The experiment indicates that we cannot simply fix the diagonal parameter of Hessian matrix but must dynamically adjust the diagonal weight coefficient for controlling the number of error-divided samples. This modified asymmetry learning algorithm is more superior than the traditional standard SVM method and can recognize DNA sequence and its mean recognition rate comes to 93.3%.     

求解最优潮流KKT系统的一类新模型及算法设计

电力工业的市场化改革对最优潮流(optim al pow er flow,OPF)的计算精度和速度提出了更高的要求.本文针对OPF模型中存在大量的无功界约束的特性,把一般非线性不等式约束和界约束分开处理,通过引入一个对角矩阵和非线性互补函数,建立了与OPF问题的K arush-Kuhn-Tucker(KKT)系统等价的约束非光滑方程新模型.进一步,基于新建立的模型,提出了一类具有理论上收敛性保证的投影半光滑N ew ton型算法.相对于传统的解OPF的KKT系统和非线性互补函数方法,新方法一方面保持了非线性互补函数法无需识别有效集的优点,同时又减少了问题的维数,且投影计算保持了无功界约束的可行性.IEEE多个算例的数值试验显示本文所提出的模型和算法具有较好的计算效果.     

Nonlinear model predictive control of the strip temperature in an annealing furnace

A nonlinear model predictive controller is designed for the strip temperature in a combined direct- and indirect-fired strip annealing furnace. Based on a tailored first-principles dynamical model and the estimated current system state, the receding horizon controller selects optimal trajectories for both the fuel supply and the strip velocity so that the strip temperature is controlled to its desired target temperature. The controller additionally maximizes the throughput and minimizes the energy consumption. In the control algorithm, the dynamic optimization problem with equality constraints is numerically solved by using the Gauss–Newton method. The gradient and the approximated Hessian matrix of the objective function are analytically computed using an adjoint-based method. The capabilities of the proposed controller are demonstrated for a validated high-fidelity simulation model of an industrial annealing furnace.     

快速对角阵权系数协方差交叉融合容积卡尔曼滤波器

针对互协方差信息未知的多传感器系统,本文提出了一种快速对角阵权系数协方差交叉融合算法(FDCI).本文首先提出了一种对角阵权系数协方差交叉融合(DCI)方案,并证明了所提出DCI算法在融合估计精度上高于经典批处理CI融合(BCI)算法.在此基础之上,针对非线性等复杂的互协方差未知的多传感器系统,提出FDCI算法,并证明了所提出FDCI算法的无偏性及鲁棒精度. FDCI融合算法虽然在融合估计精度上低于DCI,但FDCI无需进行多权系数的非线性代价函数的优化问题,进而大大降低了计算负担,提高了系统的实时性.最后,结合容积卡尔曼滤波算法(CKF)提出了快速对角阵权系数协方差交叉融合容积卡尔曼滤波算法.仿真实例验证了所提出算法的正确性和有效性.     

基于牛顿法的并行优化算法

针对非线性数值优化问题,提出一种在分布式环境下的基于牛顿法的并行算法。引入松弛变量,将不等式约束转换为等式约束,利用广义拉格朗日乘子将约束优化问题转换为无约束子优化问题。为了并行地求解这些子优化问题,将Newton迭代法中的Hessian矩阵进行适当的分裂,采用简单迭代法求解Newton法中的线性方程组。在理论上对该算法进行了收敛性分析。在HP rx2600集群上进行的数值实验结果表明并行效率达90%以上。     

基于自适应罚函数的QPSO算法的代谢通量评估*

针对代谢通量评估问题属于带约束的优化问题,其目标函数是一个非线性、不可微的并且存在多个局部最小点的复杂函数,提出了使用自适应罚函数的量子粒子群优化算法来解决这个问题。通过自适应罚函数的方法解决约束条件,然后使用QPSO算法最小化内部代谢通量。用此算法评估谷氨酸棒杆菌的内部代谢通量并与传统的优化算法来比较,实验结果证明了该算法的可行性和有效性。     

Incomplete series expansion for function approximation

We present an incomplete series expansion (ISE) as a basis for function approximation. The ISE is expressed in terms of an approximate Hessian matrix, which may contain second, third, and even higher order “main” or diagonal terms, but which excludes “interaction” or off-diagonal terms. From the ISE, a family of approximation functions may be derived. The approximation functions may be based on an arbitrary number of previously sampled points, and any of the function and gradient values at suitable previously sampled points may be enforced when deriving the approximation functions. When function values only are enforced, the storage requirements are minimal. However, irrespective of the conditions enforced, the approximate Hessian matrix is a sparse diagonal matrix. In addition, the resultant approximations are separable. Hence, the proposed approximation functions are very well-suited for use in gradient-based sequential approximate optimization requiring computationally expensive simulations; a typical example is structural design problems with many design variables and constraints. We derived a wide selection of approximations from the family of ISE approximating functions; these include approximations based on the substitution of reciprocal and exponential intervening variables. A comparison with popular approximating functions previously proposed illustrates the accuracy and flexibility of the new family of approximation functions. In fact, a number of popular approximating functions previously proposed for structural optimization applications derive from our ISE. Based on the similarly named paper presented at the Sixth World Congress on Structural and Multidisciplinary Optimization, Rio de Janeiro, Brazil, May 2005     

启动子序列的非均衡检测识别算法

通过改进Hessian矩阵对角参数,调整支持向量机中超平面的位移,将数据量少的样本从两类非均衡样本中进行分离,结合隐马尔可夫随机迭代,实验发现,不能简单固定Hessian矩阵的对角参数,而必须加之以可调整的权系数才能控制错分的样本数.对启动子序列进行识别,平均识别率达到92.8%.     

A portable and scalable algorithm for a class of constrained combinatorial optimization problems

This paper presents a portable and scalable approach for a class of constrained combinatorial optimization problems (CCOPs) which requires to satisfy a set of constraints and to optimize and objective function simultaneously. In particular, this paper is focused on the class of CCOPs that admits a representation in terms of a square matrix of constraints C.The algorithm consists of a hybrid neural-genetic algorithm, formed by a Hopfield Neural Network (HNN) which solves the problem's constraints, and a Genetic Algorithm (GA) for optimizing the objective function. This separated management of constraints and optimization procedures makes the proposed algorithm scalable and robust. The portability of the algorithm is given by the fact that the HNN dynamics depends only on the matrix C of constraints.We show these properties of scalability and portability by solving three different CCOPs with our algorithm, the frequency assignment problem in a mobile telecommunications network, the reduction of the interference in satellite systems and the design of FPGAs with segmented channel routing architecture. We compare our results with previous approaches to these problems, obtaining very good results in all of them.     

蒸馏与换热协同的约束多目标在线操作优化方法

针对蒸馏装置与换热网络间缺乏协同优化导致的分馏精度差和能耗高的问题,提出了一种基于代理模型的约束多目标在线协同操作优化方法.为了解决蒸馏装置与换热网络操作参数协同优化时存在的计算耗时和约束的问题,构建Kriging代理模型来近似目标函数和约束条件,提出了基于随机欠采样和Adaboost的分类代理模型（RUSBoost）来解决类别不平衡的收敛判定预测问题.提出了基于多阶段自适应约束处理的代理模型的模型管理方法,该方法采用基于参考向量激活状态的最大化改善期望准则和可行概率准则更新机制来平衡优化初始阶段种群的多样性和可行性,采用支配参考点的置信下限准则更新机制加快收敛速度.通过不断与机理模型交互来在线更新代理模型,实现在线操作优化.通过测试函数和仿真实例验证了本文方法的有效性.     

基于随机牛顿算法的离散系统自适应参数估计

针对一类离散系统,提出一种基于随机牛顿算法的自适应参数估计新框架,相较于已有的参数估计算法,所提出方法仅要求系统满足有限激励条件,而非传统的持续激励条件.所提出算法的核心思想在于通过对原始代价函数的修正,在使用当前时刻误差信息的基础上融入历史误差信息,进而通过对历史信息和历史激励的复用使得持续激励条件转化为有限激励条件;然后,为了解决传统算法收敛速度慢的问题并避免潜在的病态问题,采用随机牛顿算法推导出参数自适应律,并引入含有历史信息的海森矩阵作为时变学习增益,保证参数估计误差指数收敛;最后,基于李雅普诺夫稳定性理论给出不同激励条件下所提出算法的收敛性结论和证明,并通过对比仿真验证所提出算法的有效性和优越性.     

A particle filter via constrained sampling for nonlinear dynamic systems

This article is concentrated on the particle filtering problem for nonlinear systems with nonlinear equality constraints. Considering the constraint information incorporated into filters can improve the state estimation accuracy, we propose an adaptive constrained particle filter via constrained sampling. First, in order to obtain particles drawn from the constrained important density function, we construct and solve a general optimization function theoretically fusing equality constraints and the importance density function. Furthermore, to reduce the computation time caused by the number of particles, the constrained Kullback‐Leiler distance sampling method is given to online adapt the number of particles needed for state estimation. A simulation study in the context of road‐confined vehicle tracking demonstrates that the proposed filter outperforms the typical constrained ones for equality constrained dynamic systems.