A NONMONOTONE TRUST REGION ALGORITHM FOR NONLINEAR OPTIMIZATION SUBJECT TO GENERAL CONSTRAINTS

In this paper we present a nonmonotone trust region algorithm for general nonlinear constrained optimization problems. The main idea of this paper is to combine Yuan's technique[1] with a nonmonotone method similar to Ke and Han [2]. This new algorithm may not only keep the robust properties of the algorithm given by Yuan, but also have some advantages led by the nonmonotone technique. Under very mild conditions, global convergence for the algorithm is given. Numerical experiments demonstrate the efficiency of the algorithm.     

A Nonmonotone Trust Region Algorithm for Nonlinear Optimization Subject to General Constraints

In this paperwe present a nonmonotone trust region algorthm for general nonlinear constrained optimization problems.The main idea of this paper is to combine Yuan‘‘‘‘s technique[1]with a nonmonotone method similar to Ke and Han[2].This new algorithm may not only keep the robust properties of the algorithm given by Yuan,but also have some advantages led by the nonmonotone technique.Under very mild conditions,global convergence for the algorithm is given.Numerical experiments demostrate the efficency of the algorithm.     

Phase retrieval from local measurements: Improved robustness via eigenvector-based angular synchronization

We improve a phase retrieval approach that uses correlation-based measurements with compactly supported measurement masks [30]. Our approach admits deterministic measurement constructions together with a robust, fast recovery algorithm that consists of solving a system of linear equations in a lifted space, followed by finding an eigenvector (e.g., via an inverse power iteration). Theoretical reconstruction error guarantees from [30] are improved as a result for the new and more robust reconstruction approach proposed herein. Numerical experiments demonstrate robustness and computational efficiency that compete with other approaches on large problems. Along the way, we show that this approach also trivially extends to phase retrieval problems based on windowed Fourier measurements.     

Robustness of Mann's algorithm for nonexpansive mappings

Mann's algorithm is proved robust in the sense that appropriately small perturbations do not alter the convergence of the algorithm. We prove this for nonexpansive mappings in a Banach space setting, which extends the initial work of Combettes [P.L. Combettes, On the numerical robustness of the parallel projection method in signal synthesis, IEEE Signal Process. Lett. 8 (2001) 45-47] where projections are considered in the Hilbert space framework.     

An effective method for computing regression quantiles

Regression quantiles were introduced in Koenker & Bassett[7] as quantities of interest in developing robust estimationprocedures. They can be computed by linear programming combinedwith post optimality techniques. Here an effective alternativeis presented based on the reduced gradient algorithm for l₁fitting as described in [8] combined with a piecewise linearhomotopy. There is a close connection between the two approaches(the new method essentially describes what is going on in thelinear programming), but it is argued that the new approachis preferable. Its robustness as a computational procedure isillustrated by several examples which give rise to a varietyof different behaviours.     

A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems

The inverse-free preconditioned Krylov subspace method of Golub and Ye [G.H. Golub, Q. Ye, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comp. 24 (2002) 312-334] is an efficient algorithm for computing a few extreme eigenvalues of the symmetric generalized eigenvalue problem. In this paper, we first present an analysis of the preconditioning strategy based on incomplete factorizations. We then extend the method by developing a block generalization for computing multiple or severely clustered eigenvalues and develop a robust black-box implementation. Numerical examples are given to illustrate the analysis and the efficiency of the block algorithm.     

A hybrid approach to 3-level FETI

Finite Element Tearing and Interconnecting (FETI) methods are nonoverlapping domain decomposition methods which have been proven to be very robust and parallel scalable for a class of elliptic partial differential equations. These methods are also called dual domain decomposition methods since the continuity accross the subdomain boundaries is enforced by Lagrange multipliers and, after elimination of the primal variables, the remaining Schur complement system is solved iteratively in the Lagrange multiplier space using a Krylov space method. Domain decomposition methods iterating on the primal variables are called primal substructuring methods. FETI and FETI–DP methods are different members of the family of dual domain decomposition methods. Their standard versions have in common that the local subproblems and a small global problem are solved exactly by a direct method, essentially representing two different levels within the algorithm. Several extensions of dual and primal iterative substructuring beyond two levels have been proposed in the past, see, e.g., [7] for FETI–DP, and, e.g., Tu [13,12,11] or [9] and [1] for BDDC. In the present article, a hybrid FETI/FETI–DP method is considered and some numerical results are presented. It is noted that independently, there is ongoing research on hybrid FETI methods by Jungho Lee of the Courant Institute. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

不等式约束二次规划的一新算法

文献[1]提出了一般等式约束非线性规划问题一种求解途径．文献[2]应用这一途径给出了等式约束二次规划问题的一种算法，本文在文献[1]和[2]的基础上对不等式约束二次规划问题提出了一种新算法．     

一个结构简单的约束变尺度算法

本文我们考虑具有线性约束凹函数的最优化问题，利用我们的算法和变尺度修正公式，提出了一个结构简单的组合算法，并在「２」，「３」和「４」同样的假设条件下，证明了该算法的收敛性和超线性收敛速度，从而使该算法比原有各算法更具实用性。     

"求线性规划问题可行基的一种方法"的注记

文[2]通过两个反例的计算,认为文[1]所提出的求LP可行基的方法有不妥之处,并对[1]的方法中主要步骤作了修正。本文对[1]的算法中轴心项的选取作进一步说明,对[2]中所提出的反例以[1]中算法进行计算与[2]对比分析,说明[2]中的反例并不成立。     

On some sequential simultaneous confidence intervals procedures

Summary The purpose of this paper is two-fold: (i) to extend the simultaneous confidence intervals procedures (SCIP) of Healy [7] along the lines of Chow and Robbins [3] and (ii) to develop certain robust non-parametric SCIP based on the results of Sen [10] and Sen and Ghosh [11]; the allied efficiency results are also presented. Work supported by the National Institutes of Health, Grant GM-12868.     

三维七元线性码的重量谱与改进的遗传算法

[n,3,7]线性码的重量谱与其差序列是一一对应的。本文改进了[1]结构4的条件（iv),从而得到了不满足链条件的[n,3;7]线性码的差序列的充要条件,并应用改进的遗传算法搜索满足链条件的[n,3;7]线性码的差序列,取得了较好的结果。     

Robust portfolio modeling with incomplete cost information and project interdependencies

Robust portfolio modeling (RPM) [Liesiö, J., Mild, P., Salo, A., 2007. Preference programming for robust portfolio modeling and project selection. European Journal of Operational Research 181, 1488–1505] supports project portfolio selection in the presence of multiple evaluation criteria and incomplete information. In this paper, we extend RPM to account for project interdependencies, incomplete cost information and variable budget levels. These extensions lead to a multi-objective zero-one linear programming problem with interval-valued objective function coefficients for which all non-dominated solutions are determined by a tailored algorithm. The extended RPM framework permits more comprehensive modeling of portfolio problems and provides support for advanced benefit–cost analyses. It retains the key features of RPM by providing robust project and portfolio recommendations and by identifying projects on which further attention should be focused. The extended framework is illustrated with an example on product release planning.     

Robust estimation of periodic autoregressive processes in the presence of additive outliers

This paper suggests a robust estimation procedure for the parameters of the periodic AR (PAR) models when the data contains additive outliers. The proposed robust methodology is an extension of the robust scale and covariance functions given in, respectively, Rousseeuw and Croux (1993) [28], and Ma and Genton (2000) [23] to accommodate periodicity. These periodic robust functions are used in the Yule-Walker equations to obtain robust parameter estimates. The asymptotic central limit theorems of the estimators are established, and an extensive Monte Carlo experiment is conducted to evaluate the performance of the robust methodology for periodic time series with finite sample sizes. The quarterly Fraser River data was used as an example of application of the proposed robust methodology. All the results presented here give strong motivation to use the methodology in practical situations in which periodically correlated time series contain additive outliers.     

A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time

We describe a randomized algorithm for computing the trapezoidal decomposition of a simple polygon. Its expected running time is linear in the size of the polygon. By a well-known and simple linear time reduction, this implies a linear time algorithm for triangulating a simple polygon. Our algorithm is considerably simpler than Chazelle's [3] celebrated optimal deterministic algorithm. The new algorithm can be viewed as a combination of Chazelle's algorithm and of simple nonoptimal randomized algorithms due to Clarkson et al. [6], [7], [9] and to Seidel [20]. As in Chazelle's algorithm, it is indispensable to include a bottom-up preprocessing phase, in addition to the actual top-down construction. An essential new idea is the use of random sampling on subchains of the initial polygonal chain, rather than on individual edges as is normally done. Received April 18, 2000, and in revised form December 7, 2000. Online publication June 20, 2001.     

A successful algorithm for the undirected Hamiltonian path problem

In this paper a polynomial algorithm called the Minram algorithm is presented which finds a Hamiltonian Path in an undirected graph with high frequency of success for graphs up to 1000 nodes. It first reintroduces the concept described in [13] and then explains the algorithm. Computational comparison with the algorithm by Posa [10] is given.It is shown that a Hamiltonian Path is a spanning arborescence with zero ramification index. Given an undirected graph, the Minram algorithm starts by finding a spanning tree which defines a unique spanning arborescence. By suitable pivots it locates a locally minimal value of the ramification index. If this local minima corresponds to zero ramification index then the algorithm is considered to have ended successfully, else a failure is reported.Computational performance of the algorithm on randomly generated Hamiltonian graphs is given. The random graphs used as test problems were generated using the procedure explained in Section 6.1. Comparison with our version of the Posa algorithm which we call Posa-ran algorithm [10] is also made.     

一个新的BFGS信赖域算法

本文对于无约束最优化问题提出了一个新的BFGS信赖域算法.利用BFGS方法和信赖域方法,提出了改进的BFGS信赖域方法.推广了文献[3,5]中的两种算法,得到一个新的BFGS信赖域算法,在适当条件下证明了算法的全局收敛性.     

Generalization and acceleration of an algorithm of Sebastião e Silva and its duals

Summary In this paper, we extend Householder's [4] generalization of an algorithm of Sebastião e Silva [11] by adding a new elimination rule for defining the sequences which converge to the factors of the given polynomial. We then present the dual algorithm and show that the dual algorithm becomes equivalent to the direct algorithm in the generalized form. Next, we give accelerated forms of these algorithms which are quadratically convergent. We also study the relation of these methods to other methods.     

正定可对称化矩阵与预对称迭代算法

１．问题的提出 我们引入正定可对称化矩阵定义的背景是为了研究求解二阶椭圆型非自共轭方程的离散迭代有效算法、这类方程的椭圆型是本质的分析性质。是由二阶项决定的,在离散方程中表现为正定性;非自共轭性则是由方程中的一阶项引起的,在相当广泛一类问题中可通过变量代换化为自共轭。因此,我们称这类问题为正定可对称化问题。 例１．高维二阶常系数椭圆型方程其中 Ａ为常系数正定对称（ｓ．ｐ．ｄ）阵, 为正交阵, Ｄ是对角元素为正的对角阵。 先作变量代换,通过演算,偏微分方程对于新变量变成这里进而令可将原非自共轭偏微分算子…