SSOR-like methods for saddle point problems

Saddle point problems arise in a wide variety of applications in computational and engineering. The aim of this paper is to present a SSOR-like iterative method for solving the saddle point problems. Here the convergence of this method is studied and specifically, the spectral radius and the optimal relaxation parameter of the iteration matrix are also investigated. Numerical experiments show that the SSOR-like method with a proper preconditioning matrix is better than SOR-like method presented by Golub et al. [G.H. Golub, X. Wu, and J.-Y. Yuan, SOR-like methods for augmented systems, BIT 41 (2001), pp. 71–85].     

Analytical determination of optimal TWK due-dates in a job shop

The paper studies the operating characteristics of the total-work-content (TWK) due-date assignment method in a dynamic job shop. The due-date for each job is established by adding a multiple of the job's total processing-time to its arrival time at the shop. It is assumed that there will be penalty costs if the shop quotes excessively long due-dates compared with its competitors' and cannot complete the jobs exactly on their assigned due-dates. A cost model composed of these two opportunity cost components is used. The objective is to find the optimal processing-time multiple k ^? _p that will minimize the expected total cost per job. An analytical procedure is presented to derive the optimal solution and to show that k ^? _p is a unique absolute minimum point of the strictly convex cost functions included in the cost model. It is also shown that determination of the optimal processing-time multiple requires only information readily accessible in the shop. Under certain circumstances, k ^? _p can even be exclusively expressed in terms of the shop parameters, such as the number of machines in the shop, mean job arrival rate and processing-time. Moreover, the cost model is general since no specific distributions about the underlying random processes are assumed. As a result the model can be applied to an actual job shop situation and derivation of the optimal processing-time multiple becomes a simple process that can easily be implemented.     

取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界

3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0,如果在一个k-CNF公式中每个变量正负出现次数均为s,则称该公式是严格正则（k,2s）-CNF公式.受严格正则（k,2s）-CNF公式的结构特征启发,提出每个变量正负出现次数之差的绝对值均为d的严格d-正则（k,2s）-CNF公式,并使用新提出的SDRRK2S模型生成严格d-正则随机（k,2s）-CNF公式.取定整数5<s<11,模拟实验显示,严格d-正则随机（3,2s）-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此,立足于3-CNF公式的随机难解实例生成,研究了严格d-正则随机（3,2s）-SAT问题在s取定时的可满足临界.通过构造一个特殊随机实验和使用一阶矩方法,得到了严格d-正则随机（3,2s）-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.     

Optimum parameter for the SOR-like method for augmented systems

Recently, several proposals for the generalization of Young's SOR method to the saddle point problem or the augmented system has been presented. One of the most practical versions is the SOR-like method given by Golub et al., [(2001). SOR-like methods for augmented systems. BIT, 41, 71–85.], where the convergence and the determination of its optimum parameters were given. In this article, a full characterization of the spectral radius of the SOR-like iteration matrix is given, and an explicit expression for the optimum parameter is given in each case. The new results also lead to different results to that of Golub et al. Besides, it is shown that by the choices of the preconditioning matrix, the optimum SOR-like iteration matrix has no complex eigenvalues, therefore, it can be accelerated by semi-iterative methods.     

On convergence of splitting iteration methods for non-Hermitian positive-definite linear systems

A new splitting iteration method is presented for the system of linear equations when the coefficient matrix is a non-Hermitian positive-definite matrix. The spectral radius, the optimal parameter, and some norm properties of the iteration matrix for the new method are discussed in detail. Based on these results, the new method is convergent under reasonable conditions for any non-Hermitian positive-definite linear system. Finally, the numerical examples show that the new method is more effective than the Hermitian and skew-Hermitian splitting iterative (or positive-definite and skew-Hermitian splitting iterative) method in central processing unit time.     

求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n²),对Laplacian矩阵特征分解的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n²).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.     

Linear quadratic regulators with eigenvalue placement in a specified region

A linear optimal quadratic regulator is developed for optimally placing the closed-loop poles of multivariable continuous-time systems within the common region of an open sector, bounded by lines inclined at ±π/2k (k = 2 or 3) from the negative real axis with a sector angle ≤π/2, and the left-hand side of a line parallel to the imaginary axis in the complex s-plane. Also, a shifted sector method is presented to optimally place the closed-loop poles of a system in any general sector having a sector angle between π/2 and π. The optimal pole placement is achieved without explicitly utilizing the eigenvalues of the open-loop system. The design method is mainly based on the solution of a linear matrix Lyapunov equation and the resultant closed-loop system with its eigenvalues in the desired region is optimal with respect to a quadratic performance index.     

PID Stabilization of Retarded‐Type Time‐Delay System

An analytical method is proposed to construct the stabilizing PID region of a retarded‐type time‐delay system, based on Pontryagin's results and a generalization of the Hermite‐Biehler theorem. It is shown that the stable region in the (k_i, k_d)‐plane is made up of some convex polygons for a fixed k_p, and the whole region in the (k_p, k_i, k_d)‐space is comprised of some polyhedrons, each of which is mapped onto a real used string. Additionally, a method for determining the feasible k_p‐intervals is given in this paper. Two examples are employed to illustrate and verify the construction procedure of the stabilizing PID region in detail.     

PI‐PD controller design for time delay systems via the weighted geometrical center method

In this study, a PI‐PD controller tuning method is presented using the weighted geometrical center method, which is based on the calculation of the weighted geometric center of the stability region obtained by the stability boundary locus method. The proposed method for tuning of PI‐PD controller parameters (k_d,k_f,k_p and k_i ) is performed in three steps. In the first step, the (k_d,k_f) parameter region for the inner loop with PD controller is obtained, and then the weighted geometric center of this region is calculated. In the second step, the inner PD loop is reduced to a single block using the numerical values of (k_d,k_f) that are obtained in the first step. Then, the (k_p,k_i) values of the external loop with PI controller are determined by the same procedure. This tuning method has some advantages over other tuning methods in terms of simplicity and robustness. The simulation examples show that a PI‐PD controller designed using the proposed method provides good performance results when compared to other tuning methods presented in the literature.     

Design of reduced-order optimal estimators directly in the frequency domain

The frequency-domain design of optimal reduced-order estimators ((Caiman filters) for continuous-time linear time-invariant systems containing 0 ≤ k ≤ m noise-free output measurements is considered. In a direct frequency-domain approach to state feedback and estimation the ‘states’ of a system do not appear explicitly, and therefore we here focus our attention mainly on the frequency-domain characteristics of the optimal filter. By suitably modifying known time-domain results, a simple polynomial matrix equation can be derived from which the optimal filter parameters are obtained by spectral factorization. The equivalence between the time- and the frequency-domain results is established with the aid of a non-minimal representation of reduced-order observers.     

Stability of linear infinite-dimensional systems revisited

The paper is devoted to a study of stability questions for linear infinite-dimensional discrete-time and continuous-time systems. The concepts of power stability and l ^p Instability for a linear discrete-time system x _k+1 = Ax _k (where x _k ε X, X is a Banach space, A is linear and bounded) are introduced and studied. Relationships between these concepts and the inequality r(A) < 1, where r(A) denotes the spectral radius of A, are also given. The discrete-time results are used for a simple derivation of some well-known properties of exponentially stable and L^p-stable linear continuous-time systems described by [xdot](t) = Ax(t) (A generates here a strongly continuous semigroup of linear and bounded operators on X). Some remarks on norms related to stable systems are also included.     

Optimal Fourier filtering of a function that is strictly confined within a sphere

We present an alternative method to filter a distribution, that is strictly confined within a sphere of given radius rc, so that its Fourier transform is optimally confined within another sphere of radius kc. In electronic structure methods, it can be used to generate optimized pseudopotentials, pseudocore charge distributions, and pseudo atomic orbital basis sets.     

A TENSOR-THEORETIC ENHANCEMENT TO THE HILL CIPHER SYSTEM

The Hill matrix algorithm[3], published in 1929, is known for being the first purely algebraic cryptographic system and for starting the entire field of algebraic cryptology. In this paper, an operator derived from ring isomorphism theory is adapted for use in the Hill system which greatly increases the block size that a matrix can encrypt; specifically, a k×k invertible matrix over Z _n represents an invertible matrix of order k ³, which produces ciphertext blocks k ²-times as long as the original matrix could. This enhancement increases the Hill system's security considerably.     

Minimal symmetric Darlington synthesis

We consider the symmetric Darlington synthesis of a p × p rational symmetric Schur function S with the constraint that the extension is of size 2p × 2p. Under the assumption that S is strictly contractive in at least one point of the imaginary axis, we determine the minimal McMillan degree of the extension. In particular, we show that it is generically given by the number of zeros of odd multiplicity of I _p − SS*. A constructive characterization of all such extensions is provided in terms of a symmetric realization of S and of the outer spectral factor of I _p − SS*. The authors’s motivation for the problem stems from Surface Acoustic Wave filters where physical constraints on the electro-acoustic scattering matrix naturally raise this mathematical issue.     

Structured squaring down and zero assignment

The problem of zero assignment by squaring down is considered for a system of p-inputs, n-outputs and n-states (m?>?p), where not all outputs are free variables for design. We consider the case where a k-subset of outputs is preserved in the new output set, and the rest are recombined to produce a total new set of p-outputs. New invariants for the problem are introduced which include a new class of fixed zeros and the methodology of the global linearization, developed originally for the output feedback pole assignment problem, is applied to this restricted form of the squaring down problem. It is shown that the problem can be solved generically if (p???k)(m???p)?>?δ*, where k (k?p) is the number of fixed outputs and δ* is a system and compensation scheme invariant, which is defined as the restricted Forney degree.     

LQ regulator design method for system with delay based on spectral decomposition of the hamiltonian

A design method to construct an LQ regulator for a system with time-delay is proposed. It is based on a new technique for composing the solution of an infinite-dimensional Riccati equation using the spectral decomposition of the hamiltonian. This design method has the feature that the closed-loop poles can be calculated a priori from the open-loop poles and one scalar design parameter, so that we can choose the parameter to obtain an optimal control law which results in the desired degree of exponential stability of the closed-loop system.     

Optimal shape and position of the actuators for the stabilization of a string

The energy in a string subject to constant viscous damping k on a subset ω of length l>0 decays exponentially in time; we consider the problem of optimizing the decay rate for the ω which are the unions of at most N intervals. This rate is given by the spectral abscissa of the linear operator associated to the wave equation. We are interested in small values of k; therefore, we consider the derivative of the spectral abscissa at k=0. We prove that, except for the case , when the number of intervals is not fixed a priori an optimal domain does not exist. We study numerically the case of one or two intervals using a genetic algorithm. These numerical results are not intuitive. In particular, the optimal position of one interval is never at the middle of the string.     

All stabilizing PID controllers for time delay systems

This paper presents a method to compute the entire set of stabilizing PID controller parameters for an arbitrary (including unstable) linear time delay system. The main contribution is to handle the infinite number of stability boundaries in the (k_d,k_i)-plane for a fixed proportional gain k_p. For retarded open loops, it is shown that the stable region in the (k_d,k_i)-plane consists of convex polygons. Concerning neutral loops, a new phenomenon is introduced. For certain systems and certain k_p, the exact stable region in the (k_d,k_i)-plane can be described by the limit of a sequence of polygons with an infinite number of vertices. This sequence may be well approximated by convex polygons. Moreover, the paper describes a necessary condition for k_p-intervals potentially having a stable region in the (k_d,k_i)-plane. Thus, the set of stabilizing controller parameters can be calculated after gridding k_p in these intervals. A Matlab tool implementing the presented method is available.     

On the R-order of coupled sequences II

As in the preceding paper [3], the question whether some of the sequences {x _{n, i} } coupled by a system (3) of inequalities converge at least with a certain R-order τ is reduced to the nonnegative solvability of the system (4) of linear inequalities. Further, the optimal R-order τ implied by (3) is characterized as the spectral radius of a certain matrix composed of exponents appearing in (3).