Varying relaxation parameters in nonlinear successive overrelaxation

We derive here a generalization to nonlinear problems of the “free steering theorem” of Ostrowski on sufficient conditions for convergence of linear SOR with varying relaxation parameters.     

Massively parallel solution of quadratic programs via successive overrelaxation

Serial and parallel successive overrelaxation (SOR) solutions of specially structured large-scale quadratic programs with simple bounds are discussed. By taking advantage of the sparsity structure of the problem, the SOR algorithm was successfully implemented on two massively parallel Single-Instruction-Multiple-Data machines: a Connection Machine CM-2 and a MasPar MP-1. Computational results for the well known obstacle problems show the effectiveness of the algorithm. Problems with millions of variables have been solved in a few minutes on these massively parallel machines, and speed-ups of 90% or more were achieved.     

Preconditioned accelerated generalized successive overrelaxation method for solving complex symmetric linear systems

In this paper, by adopting the preconditioned technique for the accelerated generalized successive overrelaxation method (AGSOR) proposed by Edalatpour et al. (2015), we establish the preconditioned AGSOR (PAGSOR) iteration method for solving a class of complex symmetric linear systems. The convergence conditions, optimal iteration parameters and corresponding optimal convergence factor of the PAGSOR iteration method are determined. Besides, we prove that the spectral radius of the PAGSOR iteration method is smaller than that of the AGSOR one under proper restrictions, and its optimal convergence factor is smaller than that of the preconditioned symmetric block triangular splitting (PSBTS) one put forward by Zhang et al. (2018) recently. The spectral properties of the preconditioned PAGSOR matrix are also proposed. Numerical experiments illustrate the correctness of the theories and the effectiveness of the proposed iteration method and the preconditioner for the generalized minimal residual (GMRES) method.     

The convergence factor of the parallel Schwarz overrelaxation method for linear systems

After introducing the parallel Schwarz overrelaxation method for linear systems, we analyse the convergence factor of the method in detail. The optimal overrelaxation parameter ω of the method is discussed in this paper. Some examples are also shown.     

Generalized successive overrelaxation iterative method for a class of complex symmetric linear system of equations

In this paper, to solve a broad class of complex symmetric linear systems, we recast the complex system in a real formulation and apply the generalized successive overrelaxation (GSOR) iterative method to the equivalent real system. We then investigate its convergence properties and determine its optimal iteration parameter as well as its corresponding optimal convergence factor. In addition, the resulting GSOR preconditioner is used to precondition Krylov subspace methods such as the generalized minimal residual method for solving the real equivalent formulation of the system. Finally, we give some numerical experiments to validate the theoretical results and compare the performance of the GSOR method with the modified Hermitian and skew-Hermitian splitting iteration.     

A successive overrelaxation backpropagation algorithm forneural-network training

A variation of the classical backpropagation algorithm for neural network training is proposed, and convergence is established using the perturbation results of Mangasarian and Solodov (1994). The algorithm is similar to the successive overrelaxation (SOR) algorithm for systems of linear equations and linear complementary problems in using the most recently computed values of the weights to update the values on the remaining arcs     

A modified symmetric successive overrelaxation method for augmented systems

In this paper, we establish a modified symmetric successive overrelaxation (MSSOR) method, to solve augmented systems of linear equations, which uses two relaxation parameters. This method is an extension of the symmetric SOR (SSOR) iterative method. The convergence of the MSSOR method for augmented systems is studied. Numerical examples show that the new method is an efficient method.     

Three-part splittings and Varga's type extensions of the successive overrelaxation (SOR) theory

Varga, in his excellent book [4] and in a later paper of his [5], extended the SOR theory in various directions by having considered the well known Ostrowski-Reich theorem as a starting point. In this paper we extend the theory by considering three-part splittings of Varga's type, where one of the basic parts is negative definite instead of being positive definite. Thus we are able to construct SOR-type schemes which converge for all the values of the overrelaxation parameter ω which do not belong to the familiar interval [0,2]. Then by following a similar but more complicated analysis, than that in [5], we are able to obtain the corresponding optimum schemes in the various possible cases.     

Alternating splitting waveform relaxation method and its successive overrelaxation acceleration

For the large sparse implicit linear initial value problem, we present a block successive overrelaxation scheme for the alternating direction implicit waveform relaxation method to further accelerate its convergence speed, and discuss the convergence property of the resulting iteration method in detail. Numerical implementations about several non-Hermitian implicit linear initial value problems show that the alternating direction implicit waveform relaxation method is very effective, and the block successive overrelaxation technique really accelerates its convergence speed.     

连续超松弛支持向量机回归算法应用研究

支持向量回归问题的研究,对函数拟合(回归逼近)具有重要的理论和应用意义.借鉴分类问题的有效算法,将其推广到回归问题中来,针对用于分类问题的SOR支持向量机有效算法,提出了SORR支持向量回归算法.在若干不同维数的数据集上,对SORR算法、ASVR算法和LibSVM算法进行数值试验,并进行比较分析.数值实验结果表明,SORR算法是有效的,与当前流行的支持向量机回归算法相比,在回归精度和学习速度上都有一定的优势.     

SORR回归算法在胆固醇测定中的应用

借鉴分类问题的算法,推广到回归问题中去,针对用于分类问题的SOR(successive overrelaxation for support vector)支持向量机算法,提出SORR(successive overrelaxation for support vector regression)支持向量回归算法,并应用于医学上三类血浆脂蛋白(VLDL、LDL、HDL)测定样本中胆固醇的含量。数值实验表明:SORR算法有效,与标准的支持向量回归SVR算法相比,保持了相同的回归精度,提高了学习速度,为临床上测定胆固醇含量提供新的有效方法。     

Global and local convergence of a penalty-free method for nonlinear programming

We present a class of trust region algorithms that do not use any penalty function or a filter for nonlinear equality constrained optimization. In each iteration, the infeasibility is controlled by a progressively decreasing upper limit and trial steps are computed by a Byrd–Omojokun-type trust region strategy. Measures of optimality and infeasibility are computed, whose relationship serves as a criterion on which the algorithm decides which one to focus on improving. As a result, the algorithm keeps a balance between the improvements on optimality and feasibility even if no restoration phase which is required by filter methods is used. The framework of the algorithm ensures the global convergence without assuming regularity or boundedness on the iterative sequence. By using a second order correction strategy, Marato’s effect is avoided and fast local convergence is shown. The preliminary numerical results are reported.     

Global external linearization of nonlinear systems via feedback

This note presents necessary conditions and sufficient conditions for an affine nonlinear system to be globally feedback equivalent to a controllable linear system over an open subsetVof Rⁿ. WhenVequals Rⁿ, necessary and sufficient conditions are obtained.     

基于鞅论的灰狼优化算法全局收敛性分析

灰狼优化(grey wolf optimization,GWO)算法是一种基于群体智能的随机优化算法,已成功地应用于许多复杂的优化问题的求解.尽管GWO算法有很多改进形式,但缺少严谨的收敛性分析,导致改进后的算法不具备理论支撑.对此,运用鞅论分析其收敛性.首先,根据GWO算法原理建立其基本的数学模型,通过定义灰狼状态空间及灰狼群状态空间,建立GWO算法的Markov链模型,并分析该算法的Markov性质;其次,介绍鞅理论,推导出一个上鞅作为最优适应度值的群进化序列;然后,运用上鞅收敛定理,并结合其Markov性质对GWO算法进行收敛性分析,证明GWO算法能以1的可能性达到全局收敛;最后,通过数值实验验证其收敛性能.实验结果表明,GWO算法具有全局收敛性强、计算耗时较低、寻优精度高等特点.     

Convergence of recursive adaptive and identification procedures via weak convergence theory

Results and concepts in the theory of weak convergence of a sequence of probability measures are applied to convergence problems for a variety of recursive adaptive (stochastic approximation-like) methods. Similar techniques have had wide applicability in areas of operations research and in some other areas in stochastic control. It is quite likely that they will play a much more important role in control theory than they do at present, since they allow relatively simple and natural proofs for many types of convergence and approximation problems. Part of the aim of the paper is tutorial: to introduce the ideas and to show how they might be applied. Also, many of the results are new, and they can all be generalized in many directions.     

Robust nonlinear feedback design via quantifier elimination theory

In this note symbolic-computation methods are used to design simple, fixed-structure, robust controllers for nonlinear systems. Design specifications are reduced to logically quantified polynomial inequalities. The quantifier-elimination (QE) software package QEPCAD is used to eliminate quantifiers on state and plant parameters, to obtain regions of admissible controllers parameters, that guarantee robust stability and performance. Copyright © 1999 John Wiley & Sons, Ltd.     

New construction of highly nonlinear resilient S-boxes via linear codes

Highly nonlinear resilient functions play a crucial role in nonlinear combiners which are usual hardware oriented stream ciphers. During the past three decades, the main idea of construction of highly nonlinear resilient functions are benefited from concatenating a large number of affine subfunctions. However, these resilient functions as core component of ciphers usually suffered from the guess and determine attack or algebraic attack since the n-variable nonlinear Boolean functions can be easily given rise to partial linear relations by fixing at most n/2 variables of them. How to design highly nonlinear resilient functions (S-boxes) without concatenating a large number of n/2 variables affine subfunctions appears to be an important task. In this article, a new construction of highly nonlinear resilient functions is proposed. These functions consist of two classes subfunctions. More specially, the first class (nonlinear part) contains both the bent functions with 2 k variables and some affine subfunctions with n/2 − k variables which are attained by using [ n/2 − k, m, d] disjoint linear codes. The second class (linear part) includes some linear subfunctions with n/2 variables which are attained by using [ n/2, m, d] disjoint linear codes. It is illustrated that these resilient functions have high nonlinearity and high algebraic degree. In particular, It is different from previous well-known resilient S-boxes, these new S-boxes cannot be directly decomposed into some affine subfunctions with n/2 variables by fixing at most n/2 variables. It means that the S-boxes (vectorial Boolean functions) which use these resilient functions as component functions have more favourable cryptography properties against the guess and determine attack or algebraic attacks.     

LTI approximation of nonlinear systems via signal distribution theory

L₂ and L₁ optimal linear time-invariant (LTI) approximation of discrete-time nonlinear systems, such as nonlinear finite impulse response (NFIR) systems, is studied via a signal distribution theory motivated approach. The use of a signal distribution theoretic framework facilitates the formulation and analysis of many system modelling problems, including system identification problems. Specifically, a very explicit solution to the L₂ (least squares) LTI approximation problem for NFIR systems is obtained in this manner. Furthermore, the L₁ (least absolute deviations) LTI approximation problem for NFIR systems is essentially reduced to a linear programming problem. Active LTI modelling emphasizes model quality based on the intended use of the models in linear controller design. Robust stability and LTI approximation concepts are studied here in a nonlinear systems context. Numerical examples are given illustrating the performance of the least squares (LS) method and the least absolute deviations (LAD) method with LTI models against nonlinear unmodelled dynamics.     

Optimization of segment-wise linear structures via optimal control theory

Rozvany et al. [J. Engng Mech. ASCE 114 (1988)] have recently derived optimality conditions via the cost gradient (Prager-Shield) method for the optimization of plastically designed beams with linear segmentation. Although the analytical method is applicable to any number of beam segments and degree of redundancies, it may not be as convenient to use when these are large. This prompted the authors to develop a numerical method which not only complements Rozvany's analytical method but also extends the work on beams to plates and segments which are piecewise constant, linear, quadratic or any order of variation. The numerical approach, based on optimal control theory, gives results to within 1% of the exact solution for the considered beam and plate examples.