Some algorithms of realistic statistics

To take account of influence of the measurement errors on the statistical procedures it is supposed in realistic statistics that statistical data are specified not by numbers but by intervals. The present, paper is the continuation of [–4]. We give a summary of the main assumptions of realistic statistics. We also suggest some rules of confidence estimation of the parameters and confirm them by a discussion of estimation of a median and variation coefficient. The interrelationships between metrological, methodical, statistical, and calculative errors are discussed. The realistic statistical approach to testing hypotheses is analyzed. Testing the hypothesis that the expectation equals zero in case of a normal sample with variance 1 as well as the one-sample Student test and the two-sample Smirnov test are considered as examples. Translated fromStatisticheskie Metody Otsenivaniya i Proverki Gipotez, pp. 77–86, Perm, 1991.     

Some algorithms for hemiequilibrium problems

In this paper, we suggest and analyze a class of iterative methods for solving hemiequilibrium problems using the auxiliary principle technique. We prove that the convergence of these new methods either requires partially relaxed strongly monotonicity or pseudomonotonicity, which is a weaker condition than monotonicity. Results obtained in this paper include several new and known results as special cases.     

Some remarks on greedy algorithms

Estimates are given for the rate of approximation of a function by means of greedy algorithms. The estimates apply to approximation from an arbitrary dictionary of functions. Three greedy algorithms are discussed: the Pure Greedy Algorithm, an Orthogonal Greedy Algorithm, and a Relaxed Greedy Algorithm.This research was supported by the Office of Naval Research Contract N0014-91-J1343.     

Some simple in-place merging algorithms

The theoretical presentation and analysis is given for two families of simple in-place merging algorithms and their limiting cases. The first family merges stably inO(k·n) time andO(n ^1/k ) additional space with a limiting case running inO(n logn) time and constant space. The second family merges unstably inO (k ·n) time andO(log ^k n) space with a limiting case running inO(nG(n)) time and constant space. HereG(n) is the leastk such thatF(k) n whereF(0)=1 andF(i)=2 ^F(i–1) fori1. Each algorithm gives rise to a corresponding merge sort.     

Some algorithms for semi-invariants of quivers

We present some theorems and algorithms for calculating perpendicular categories and locally semi-simple decompositions. We implemented a computer program TETIVA based on these algorithms and we offer this program for everybody's use.     

非线性最小二乘法的算法

本给出非线性最小二乘的优化条件和几何特征．     

Sequence searching and evaluation: a unified approach for aircraft arrival sequencing and scheduling problems

Arrival sequencing and scheduling (ASS) is an important part of air traffic control. In the literature, various formulations of the ASS problems have been established by taking different scheduling requirements into account, and various methods have been developed to cope with these ASS problems. However, it is usually uneasy to generalize a method designed for one ASS formulation to another, while an approach that is able to handle different ASS problems is of great significance since air traffic controllers may need to switch among different scheduling requirements in practice. Motivated by this observation, an approach that is applicable to a number of different problem formulations of ASS is proposed in this paper. Specifically, the ASS problems that include different objective functions and constraints are firstly abstracted as a constrained permutation-based problem. After that, a Sequence Searching and Evaluation (SSE) approach is developed for the constrained permutation-based problem. The SSE solves different ASS problems by separating the sequence searching in one stage using an Estimation of Distribution Algorithm framework, and evaluating sequences in the second stage. Experiment results show that SSE is capable of obtaining competitive solutions for a variety of ASS problems.     

Optimization of aircraft structural components by using nature-inspired algorithms and multi-fidelity approximations

In this work, a flat pressure bulkhead reinforced by an array of beams is designed using a suite of heuristic optimization methods (Ant Colony Optimization, Genetic Algorithms, Particle Swarm Optimization and LifeCycle Optimization), and the Nelder-Mead simplex direct search method. The compromise between numerical performance and computational cost is addressed, calling for inexpensive, yet accurate analysis procedures. At this point, variable fidelity is proposed as a tradeoff solution. The difference between the low-fidelity and high-fidelity models at several points is used to fit a surrogate that corrects the low-fidelity model at other points. This allows faster linear analyses during the optimization; whilst a reduced set of expensive non-linear analyses are run “off-line,” enhancing the linear results according to the physics of the structure. Numerical results report the success of the proposed methodology when applied to aircraft structural components. The main conclusions of the work are (i) the variable fidelity approach enabled the use of intensive computing heuristic optimization techniques; and (ii) this framework succeeded in exploring the design space, providing good initial designs for classical optimization techniques. The final design is obtained when validating the candidate solutions issued from both heuristic and classical optimization. Then, the best design can be chosen by direct comparison of the high-fidelity responses.     

Some biological sequence metrics

Some new metrics are introduced to measure the distance between biological sequences, such as amino acid sequences or nucleotide sequences. These metrics generalize a metric of Sellers, who considered only single deletions, mutations, and insertions. The present metrics allow, for example, multiple deletions and insertions and single mutations. They also allow computation of the distance among more than two sequences. Algorithms for computing the values of the metrics are given which also compute best alignments. The connection with the information theory approach of Reichert, Cohen, and Wong is discussed.     

Some parallel algorithms on interval graphs

Parallel algorithms are given for finding a maximum weighted clique, a maximum weighted independent set, a minimum clique cover, and a minimum weighted dominating set of an interval graph. Parallel algorithms are also given for finding a Hamiltonian circuit and the minimum bandwidth of a proper interval graph. The shared memory model (SMM) of parallel computers is used to obtain fast algorithms.     

Some convergence results for asynchronous algorithms

Resumé Nous présentons dans cet article des résultats de convergence des algorithmes asynchrones basés essentiellement sur la notion classique de contraction.Nous généralisons, en particulier, tous les résultats de convergence de ces algorithmes qui font l'hypothèse de contraction en norme vectorielle qui récemment a été très souvant utilisée.Par ailleurs, l'hypothèse de contraction en norme vectorielle peut se trouver difficile, voire impossible à vérifier pour certains problèmes qui peuvent être cependant abordés dans le cadre de la contraction classique que nous adoptons.

---

Some convergence results for asynchronous algorithms

Summary In this paper we present convergence results for the asynchronous algorithms based essentially on the notion of classical contraction.We generalize, in particular, all convergence results for those algorithms which are based on the vectorial norm hypothesis, in wide spread use recently.Certain problems, for which the vectorial norm hypothesis can be difficult or even impossible to verify, can nontheless be tackled within the scope of the classical contraction that we adopte.

     

Some inversion algorithms for discrete systems

Several algorithms are proposed to solve the inversion problem in the presence of information about the system state or the system output under certain additional assumptions (the wave model of the unknown input is assumed known). The problem of estimation from the output is solved by constructing state observers for a system of arbitrary relative order. Necessary conditions for the applicability of the proposed algorithms are identified. Error bounds of the approximation algorithms are estimated. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 119–126, 2004.     

Some performance tests of convex hull algorithms

The two-dimensional convex hull algorithms of Graham, Jarvis, Eddy, and Akl and Toussaint are tested on four different planar point distributions. Some modifications are discussed for both the Graham and Jarvis algorithms. Timings taken of FORTRAN implementations indicate that the Eddy and Akl-Toussaint algorithms are superior on uniform distributions of points in the plane. The Graham algorithm outperforms the others on those distributions where most of the points are on or near the boundary of the hull.     

A mathematical model and algorithms for the aircraft hangar maintenance scheduling problem

An aircraft hangar maintenance scheduling problem is studied, motivated by the aircraft heavy maintenance conducted in a hangar operated by an independent maintenance service company. The aircraft hangar maintenance scheduling problem in such context consists of determining a maintenance schedule with minimum penalty costs in fulfilling maintenance requests, and a series of hangar parking plans aligned with the maintenance schedule through the planning period. A mixed-integer linear programming (MILP) mathematical model, integrating the interrelations between the maintenance schedule and aircraft parking layout plans, is presented at first. In the model, the variation of parking capacity of the maintenance hangar and the blocking of the aircraft rolling in and out path are considered. Secondly, the model is enhanced by narrowing down the domain of the time-related decision variables to the possible rolling in and out operations time of each maintenance request. Thirdly, to obtain good quality feasible solutions for large scale instances, a rolling horizon approach incorporating the enhanced mathematical model is presented. The results of computational experiments are reported, showing: (i) the effectiveness of the event-based discrete time MILP model and (ii) the scalability of the rolling horizon approach that is able to provide good feasible solutions for large size instances covering a long planning period.     

Some numerical experiments with variable-storage quasi-Newton algorithms

This paper describes some numerical experiments with variable-storage quasi-Newton methods for the optimization of some large-scale models (coming from fluid mechanics and molecular biology). In addition to assessing these kinds of methods in real-life situations, we compare an algorithm of A. Buckley with a proposal by J. Nocedal. The latter seems generally superior, provided that careful attention is given to some nontrivial implementation aspects, which concern the general question of properly initializing a quasi-Newton matrix. In this context, we find it appropriate to use a diagonal matrix, generated by an update of the identity matrix, so as to fit the Rayleigh ellipsoid of the local Hessian in the direction of the change in the gradient.Also, a variational derivation of some rank one and rank two updates in Hilbert spaces is given.Work supported in part by FNRS (Fonds National de la Recherche Scientifique), Belgium.     

Some algorithms for the dynamic reconstruction of inputs

For the weight \(v_k \left( x \right) = \prod _{\alpha \in \mathbb{R}_ + } \left| {\left( {\alpha ,x} \right)} \right|^{2k\left( \alpha \right)}\) defined by a positive subsystem R ₊ of a finite root system R ? ? ^d and by a function k(α): R → ?₊ invariant under the reflection group generated by R, a sharp Jackson inequality in L ₂(? ^d ) is proved.     

Some algorithms for inversion of linear dynamic systems

We study the problem of inversion of linear finite-dimensional dynamic systems in terms of the output. For different types of systems we propose several algorithms for inversion. We study the stability of the algorithms with respect to various perturbations. Translated fromAlgoritmy Upravleniya i Identifikatsii, pp. 156–167, 1997.