A posteriori joint detection of reference fragments in a quasi-periodic sequence

The problem of joint detection of quasi-periodic reference fragments (of given size) in a numerical sequence and its partition into segments containing series of recurring reference fragments is solved in the framework of the a posteriori approach. It is assumed that (i) the number of desired fragments is not known, (ii) an ordered reference tuple of sequences to be detected is given, (iii) the index of the sequence member corresponding to the beginning of a fragment is a deterministic (not random) value, and (iv) a sequence distorted by an additive uncorrelated Gaussian noise is available for observation. It is established that the problem consists of testing a set of hypotheses about the mean of a random Gaussian vector. The cardinality of the set grows exponentially as the vector dimension (i.e., the sequence length) increases. It is shown that the search for a maximum-likelihood hypothesis is equivalent to the search for arguments that minimize an auxiliary objective function. It is proved that the minimization problem for this function can be solved in polynomial time. An exact algorithm for its solution is substantiated. Based on the solution to an auxiliary extremum problem, an efficient a posteriori algorithm producing an optimal (maximum-likelihood) solution to the partition and detection problem is proposed. The results of numerical simulation demonstrate the noise stability of the algorithm.     

Joint detection of a given number of reference fragments in a quasi-periodic sequence and its partition into segments containing series of identical fragments

The problem of joint a posteriori detection of reference fragments in a quasi-periodic sequence and its partition into segments containing series of recurring fragments from the reference tuple is solved. It is assumed that (i) an ordered reference tuple of sequences to be detected is given, (ii) the number of desired fragments is known, (iii) the index of the sequence term corresponding to the beginning of a fragment is a deterministic (not random) value, and (iv) a sequence distorted by an additive uncorrelated Gaussian noise is available for observation. It is established that the problem consists in testing a set of hypotheses about the mean of a random Gaussian vector. The cardinality of the set grows exponentially as the vector dimension (i.e., the sequence length) increases. An efficient a posteriori algorithm producing a maximum-likelihood optimal solution to the problem is substantiated. Time and space complexity bounds related to the parameters of the problem are derived. The results of numerical simulation are presented.     

Optimal detection of a recurring tuple of reference fragments in a quasiperiodic sequence

An a posteriori (off-line) approach to solving the problem of maximum-likelihood detection of a recurring tuple containing reference fragments in a numerical quasiperiodic sequence is studied. The case is analyzed where (1) the total number of fragments in a sequence is unknown; (2) the index of a sequence term corresponding to the beginning of a fragment is a deterministic (not random) value; (3) a sequence distorted by additive uncorrelated Gaussian noise is available for observation. It is shown that the problem under consideration is reduced to testing a set of simple hypotheses about the mean of a random Gaussian vector. The cardinality of this totality grows exponentially as the vector dimension (i.e., the length of the sequence under study) increases. It is established that searching for a maximum-likelihood hypothesis is equivalent to finding arguments that yield a maximum for an auxiliary objective function. It is shown that maximizing the objective function reduces to solving a special optimization problem, which is proved to be solvable in polynomial time. An exact algorithm for solving this problem, which underlies the optimal (maximum-likelihood) detection algorithm for a recurring tuple, is substantiated. The kernel of the exact algorithm is an algorithm for solving a special (basic) optimization problem. Results of numerical simulations are presented.     

A recognition problem for a vector alphabet generating a sequence with a quasiperiodic structure

An off-line recognition problem is analyzed for a vector alphabet generating sequences with quasiperiodic vector fragments that coincide with alphabet vectors. It is shown that the solution of this problem reduces to solving a special optimization problem. It is proved that the problem considered is solvable in polynomial time, and an algorithm for its exact solution is justified. The algorithm ensures the maximum likelihood recognition of a vector alphabet for the case of additive noise which is a Gaussian sequence of independent random values having an identical distribution.     

Off-line detection of a quasi-periodically recurring fragment in a numerical sequence

The paper considers a nontraditional—combinatorial—approach to solving the problem of a posteriori (off-line) noise-proof detection of a recurring fragment in a numerical sequence. Results are presented concerning the complexity, classification, and justification of algorithms for solving discrete extremal problems to which, within the combinatorial approach, some possible variants of this problem are reduced in the case when repetitions are quasi-periodic and the noise is additive.     

On a version of the problem of choosing a vector subset

The NP-completeness is proved of the problem of choosing some subset of “similar” vectors. One of the variants of the a posteriori (off-line) noise-proof detection problem of an unknown repeating vector in a numeric sequence can be reduced to this problem in the case of additive noise. An approximation polynomial algorithm with a guaranteed performance bound is suggested for this problem in the case of a fixed space dimension.     

On parameter estimation for cusp-type signals

We consider the problem of parameter estimation by continuous time observations of a deterministic signal in white Gaussian noise. It is supposed that the signal has a cusp-type singularity. The properties of the maximum-likelihood and Bayesian estimators are described in the asymptotics of small noise. Special attention is paid to the problem of parameter estimation in the situation of misspecification in regularity, i.e., when the statistician supposes that the observed signal has this singularity, but the real signal is smooth. The rate and the asymptotic distribution of the maximum-likelihood estimator in this situation are described.     

Hierarchical entropy analysis for biological signals

We develop a hierarchical entropy (HE) method to quantify the complexity of a time series based on hierarchical decomposition and entropy analysis. The proposed method is applied to the Gaussian white noise and the 1/f noise. We prove that the difference frequency components of the Gaussian white noise with the same scale factor have the same value of entropies, and the values decline as the scale factor increases. We also apply the HE method to the 1/f noise, and prove mathematically that a lower frequency component of a 1/f noise is also a 1/f noise and verify numerically that a higher frequency component of a 1/f random vector is approximately equal to a Gaussian random vector. The theoretical results are confirmed by numerical results. Moreover, we show that the HE method is an efficient method to analyze heartbeat signals by applying it to the cardiac interbeat interval time series of healthy young and elderly subjects, congestive heart failure (CHF) subjects and atrial fibrillation (AF) subjects.     

A general result in stochastic optimal control of nonlinear discrete-time systems with quadratic performance criteria

It is known that the optimal controller for a linear dynamic system disturbed by additive, independently distributed in time, not necessarily Gaussian, noise is a linear function of the state variables if the performance criterion is the expected value of a quadratic form. This result is known to hold also when the noise is Gaussian and is multiplied by a linear function of the state and/or control variables.In this paper it is proved that the optimal controller for a discrete-time linear dynamic system with quadratic performance criterion is a linear function of the state variables when the additive random vector is a nonlinear function of the state and/or control variables and not necessarily Gaussian noise which is independently distributed in time, provided only that the mean value of the random vector is zero (there is no loss of generality in assuming this) and the covariance matrix of the random vector is a quadratic function of the state and/or control variables. The above-mentioned known results emerge as special cases and certain nonlinear other special cases are exhibited.     

M-ary signal detection via a bistable system in the presence of Lévy noise

We study the problem of the M-ary signal detection via a bistable detector in the presence of Lévy noise. Based on the numerical solution of the space-fractional Fokker–Planck equation, the theoretical bit error rate is defined and used in the optimal detector design. The accuracy of the theoretical results are verified by the Monte Carlo simulations. It is shown that, with the same noise intensity, the optimal bistable detector performs better with the decreasing Lévy index α. Therefore, Lévy noise plays a more positive role in the nonlinear M-ary signal detection problem, compared to Gaussian noise.     

A finite differences method for a two-dimensional nonlinear hyperbolic equation in a class of discontinuous functions

A numerical scheme is proposed for a scalar two-dimensional nonlinear first-order wave equation with both continuous and piecewise continuous initial conditions. It is typical of such problems to assume formal solutions with discontinuities at unknown locations, which justifies the search for a scheme that does not rely on the regularity of the solution. To this end, an auxiliary problem which is equivalent to, but has more advantages then, the original system is formulated and shown that regularity of the solution of the auxiliary problem is higher than that of the original system. An efficient numerical algorithm based on the auxiliary problem is derived. Furthermore, some results of numerical experiments of physical interest are presented.     

Pattern search ranking and selection algorithms for mixed variable simulation-based optimization

The class of generalized pattern search (GPS) algorithms for mixed variable optimization is extended to problems with stochastic objective functions. Because random noise in the objective function makes it more difficult to compare trial points and ascertain which points are truly better than others, replications are needed to generate sufficient statistical power to draw conclusions. Rather than comparing pairs of points, the approach taken here augments pattern search with a ranking and selection (R&S) procedure, which allows for comparing many function values simultaneously. Asymptotic convergence for the algorithm is established, numerical issues are discussed, and performance of the algorithm is studied on a set of test problems.     

Convexity and optimization with copulæ structured probabilistic constraints

Probability constraints play a key role in optimization problems involving uncertainties. These constraints request that an inequality system depending on a random vector has to be satisfied with a high enough probability. In specific settings, copulæ can be used to model the probabilistic constraints with uncertainty on the left-hand side. In this paper, we provide eventual convexity results for the feasible set of decisions under local generalized concavity properties of the constraint mappings and involved copulæ. The results cover all Archimedean copulæ. We consider probabilistic constraints wherein the decision and random vector are separated, i.e. left/right-hand side uncertainty. In order to solve the underlying optimization problem, we propose and analyse convergence of a regularized supporting hyperplane method: a stabilized variant of generalized Benders decomposition. The algorithm is tested on a large set of instances involving several copulæ among which the Gaussian copula. A Numerical comparison with a (pure) supporting hyperplane algorithm and a general purpose solver for non-linear optimization is also presented.     

Image process in imaging through a scattering medium using fs electronic holography

Aimed at imaging technology through scattering medium using fs electronic holography, a set of image process algorithm is put forward. This algorithm can be divided into three stages. First, every hologram is pre-processed, whose contrast is enhanced. Second, the first-order spatial spectrum is low-pass-filtered through a two-step process, so that high-frequency noise can be removed. Finally, many reconstructed images are ensemble-averaged. This stage can smooth random noise and is advantageous to restraining the speckle noise of image. The operation of this algorithm shows that all of processes in the three stages have obvious effects on improving image quality.     

Optimization of Molecular Similarity Index with Applications to Biomolecules

Molecular similarity index measures the similarity between two molecules. Computing the optimal similarity index is a hard global optimization problem. Since the objective function value is very hard to compute and its gradient vector is usually not available, previous research has been based on non-gradient algorithms such as random search and the simplex method. In a recent paper, McMahon and King introduced a Gaussian approximation so that both the function value and the gradient vector can be computed analytically. They then proposed a steepest descent algorithm for computing the optimal similarity index of small molecules. In this paper, we consider a similar problem. Instead of computing atom-based derivatives, we directly compute the derivatives with respect to the six free variables describing the relative positions of the two molecules.. We show that both the function value and gradient vector can be computed analytically and apply the more advanced BFGS method in addition to the steepest descent algorithm. The algorithms are applied to compute the similarities among the 20 amino acids and biomolecules like proteins. Our computational results show that our algorithm can achieve more accuracy than previous methods and has a 6-fold speedup over the steepest descent method.     

Finding an inner estimation of the solution set of a fuzzy linear system

In this paper, we consider the problem of finding an inner estimation of the solution set of a fuzzy linear system with a real-valued coefficient matrix and a fuzzy-valued right-hand side vector. The proposed idea is based on the utilization of interval Gaussian elimination procedure to produce an inner estimation of the solutions set. To this end, firstly we apply interval Gaussian elimination procedure to obtain the solution set of a fuzzy linear system and secondly, by limiting it via solving a crisp linear system, we find an inner estimation of the solutions set, such that it satisfies the related fuzzy linear system. Finally, several numerical examples are given to show the efficiency and ability of our method.     

A least-distance programming procedure for minimization problems under linear constraints

In this paper, an algorithm is developed for solving a nonlinear programming problem with linear contraints. The algorithm performs two major computations. First, the search vector is determined by projecting the negative gradient of the objective function on a polyhedral set defined in terms of the gradients of the equality constraints and the near binding inequality constraints. This least-distance program is solved by Lemke's complementary pivoting algorithm after eliminating the equality constraints using Cholesky's factorization. The second major calculation determines a stepsize by first computing an estimate based on quadratic approximation of the function and then finalizing the stepsize using Armijo's inexact line search. It is shown that any accumulation point of the algorithm is a Kuhn-Tucker point. Furthermore, it is shown that, if an accumulation point satisfies the second-order sufficiency optimality conditions, then the whole sequence of iterates converges to that point. Computational testing of the algorithm is presented.     

求解log—最优组合投资问题的一个自适应算法及其理论分析

本文给出了一个求解log－最优组合投资问题的自适应算法,它是一个变型的随机逼近方法。该问题是一个约束优化问题,因此,采用基于约束流形的梯度上升方向替代常规梯度上升方向,在一些合理的假设下证明了算法的收敛性并进行了渐近稳定性分析。最后,本文将该算法应用于上海证券交易所提供的实际数据的log-最优组合投资问题求解,获得了理想的数值模拟结果。     

Robust optimization of noisy blackbox problems using the Mesh Adaptive Direct Search algorithm

Blackbox optimization problems are often contaminated with numerical noise, and direct search methods such as the Mesh Adaptive Direct Search (MADS) algorithm may get stuck at solutions artificially created by the noise. We propose a way to smooth out the objective function of an unconstrained problem using previously evaluated function evaluations, rather than resampling points. The new algorithm, called Robust-MADS is applied to a collection of noisy analytical problems from the literature and on an optimization problem to tune the parameters of a trust-region method.     

LQG量测反馈最优控制的精细积分

对于线性二次型高斯(LQG)量测反馈最优控制问题,提出了精细积分解法。根据分离性原理,LQG控制问题可以分成为最优状态反馈控制问题以及最优状态估计问题,即:离线计算的两套黎卡提微分方程的求解以及状态向量的时变微分方程的在线积分解。该算法不仅适用于求解二点边值问题及其相应的黎卡提微分方程,也适用于求解状态估计的时变微分方程。精细积分高精度的特点,对控制和估计都是有利的。数值算例表明了算法的高精度及有效性。