Tseng's algorithm finds a zero of the sum of a maximally monotone operator and a monotone continuous operator by evaluating the latter twice per iteration. In this paper, we modify Tseng's algorithm for findin...
详细信息
Tseng's algorithm finds a zero of the sum of a maximally monotone operator and a monotone continuous operator by evaluating the latter twice per iteration. In this paper, we modify Tseng's algorithm for finding a zero of the sum of three operators, where we add a cocoercive operator to the inclusion. Since the sum of a cocoercive and a monotone-Lipschitz operator is monotone and Lipschitz, we could use Tseng's method for solving this problem, but implementing both operators twice per iteration and without taking into advantage the cocoercivity property of one operator. Instead, in our approach, although the continuous monotone operator must still be evaluated twice, we exploit the cocoercivity of one operator by evaluating it only once per iteration. Moreover, when the cocoercive or continuous-monotone operators are zero it reduces to Tseng's algorithm or forward-backward splittings, respectively, unifying in this way both algorithms. In addition, we provide a preconditioned version of the proposed method including non-self-adjoint linear operators in the computation of resolvents and the single-valued operators involved. This approach allows us to also extend previous variable metric versions of the Tseng and forward-backward methods and simplify their conditions on the underlying metrics. We also exploit the case in which non-self-adjoint linear operators are triangular by blocks in the primal-dual product space for solving primal-dual composite monotone inclusions, obtaining Gauss-Seidel-type algorithms which generalize several primal-dual methods available in the literature. Finally we explore applications to the obstacle problem, empirical risk minimization, distributed optimization, and nonlinear programming and we illustrate the performance of the method via some numerical simulations.
A data assimilation problem for unsteady models is considered as a sequence of coupled inverse problems of reconstruction of the space-time structure of the state functions with various sets of measurement data. The d...
详细信息
A data assimilation problem for unsteady models is considered as a sequence of coupled inverse problems of reconstruction of the space-time structure of the state functions with various sets of measurement data. The data assimilation is carried out jointly with the identification of an additional unknown function, which is interpreted as a function of model uncertainty. A variational principle serves as the basis for constructing the algorithms. Various versions of the algorithms are presented and analyzed. Based on the principle of the residual, a computationally efficient algorithm for data assimilation in a locally one-dimensional case is constructed. A theoretical estimate of its performance is obtained. This algorithm is one of the main components of a data assimilation system based on a splitting scheme for unsteady three-dimensional transport and transformation models of atmospheric chemistry.
The problem of parallel algorithm development is considered. The main content of a solution presented is development of formal law of information formation on parallel algorithm structures. The way proposed of a solut...
详细信息
ISBN:
(纸本)9789663354125
The problem of parallel algorithm development is considered. The main content of a solution presented is development of formal law of information formation on parallel algorithm structures. The way proposed of a solution search is characterized initially by a single view on algorithmic and architectural subsystems of a parallel computation system. The main peculiarity of the solution presented is synthesis of general description of sequential and parallel algorithms for digital signal processing operations. The basis for solution presented is developed methodology of data decomposition. The main peculiarities of methodology presented are its functional nature and the general approach to data decomposition of any dimension. The basic steps of methodology presented are considered. The methodology is the basis for development of the formal model of the parallel computation organization. The synthesis method of composition form for digital signal processing basic operations is considered.
To detect an unknown element x* from a finite set S = {1, 2, ... , n} by asking group-testing queries is a classical combinatorial optimization problem. We consider a variation of the problem, what we call the liar se...
详细信息
To detect an unknown element x* from a finite set S = {1, 2, ... , n} by asking group-testing queries is a classical combinatorial optimization problem. We consider a variation of the problem, what we call the liar search game with small sets vertical bar n, e, <= k vertical bar and formulate it as follows: two players, say Paul and Carole, fix integers k >= 1, m > 0 and e >= 0 beforehand. Paul asks size restricted queries to find x*: "Is x* in A?", where A subset of S and vertical bar A vertical bar <= k. Carole answers them with "Yes" or "No" to tell whether x* belongs to A or not. Carole is permitted to lie at most e times. Paul wins if he finds x* within m rounds;otherwise Carole wins. Our goal is to determine the minimum value of m to assure Paul to win. Let f (n, e, <= k) = min{m vertical bar Paul wins the game [n, e, <= k] for the given integer m}. In this paper, we consider the sequential algorithms of the above game and obtain a tight bound L-upper(n, 1, <= k) such that f (n, 1, <= k) <= L-upper(n, 1, <= k) <= f (n, 1, <= k) + 1, and the exact value off (n, 1, <= k) for (1) n <= 2k + 1 and (2) n >= k(2) except for the case n = 15 and k = 3. Moreover, in the end of this paper, we conjecture the exact value off (n, 1, <= k) for general case and verify its correctness for k = infinity. (C) 2013 Elsevier B.V. All rights reserved.
We propose an extension of the behavioral theory of interactive sequential algorithms to deal with the following situation. A query is issued during a certain step, but the step ends before any reply is received. Late...
详细信息
We propose an extension of the behavioral theory of interactive sequential algorithms to deal with the following situation. A query is issued during a certain step, but the step ends before any reply is received. Later, a reply arrives, and later yet the algorithm makes use of this reply. By a persistent query, we mean a query for which a late reply might be used. Our proposal involves issuing, along with a persistent query, a location where a late reply is to be stored. After presenting our proposal in general terms, we discuss the modifications that it requires in the existing axiomatics of interactive sequential algorithms and in the existing syntax and semantics of abstract state machines. To make that discussion self-contained, we include a summary of this material before the modifications. Fortunately, only rather minor modifications are needed.
Abstract Let ( x ( t )) t ≥0 be a p -dimensional observable vector process ( p ≥ 1) with an input control process ( u ( t )) t ≥0 , described by the stochastic discrete time equation x(t + 1) = A(x(t))λ + u(t) + ...
详细信息
Abstract Let ( x ( t )) t ≥0 be a p -dimensional observable vector process ( p ≥ 1) with an input control process ( u ( t )) t ≥0 , described by the stochastic discrete time equation x(t + 1) = A(x(t))λ + u(t) + χ(t + 1), t ≥ 0, where the noises ξ( t ) form a sequence of zero mean random vectors having moments of all order; A( x ) is a linear matrix operator, A ( x ) : R p → R p x R q , q ≤ p and λ = (λ 1 , …, λ q )’ – vector of unknown parameters. In this paper we show how to approximate the process ( x ( t )) t ≥0 to the stable autoregressive process ( x 0 ( t )) t ≥0 with the given dynamic matrix parameter a, satisfying the equation x 0 (t + 1) = ax 0 (t) + χ(t + 1), t ≥ 0, by choosing the control process ( u ( t )) t ≥0 . More precisely, based on observation of ( x ( t )) t ≥0 , for given ε > 0 we construct an adaptive control procedure u ε = ( u ε ( t )) t ≥0 such that the corresponding observable process ( x ε ( t )) t ≥0 , x ε ( t ) = x ( t ) | u = u ε satisfies the following relations sup t≥0 E(x ɛ (t)) 2 ≤ L and sup t≥t ɛ E(x ɛ (t) - (x 0 (t)) 2 ≤ ɛ where L is some constant (independent of ε) and t ε is an unboundedly increasing as ε → 0 non-random function. The first relation ensures the stability of the object ( x ε ( t )). Examples of a scalar and two-dimensional autoregressive type linear models with unknown parameters are given. The rate ε −-1 ln ε −-1 of increase of t ε in both examples is obtained.
Abstract The problem of detecting the parameters change point in the autoregressive process is considered. The values of the process parameters before and after the change point are supposed to be unknown. The procedu...
详细信息
Abstract The problem of detecting the parameters change point in the autoregressive process is considered. The values of the process parameters before and after the change point are supposed to be unknown. The procedure of change point detection based on the sequential estimations of unknown parameters is proposed, procedure characteristics are studied. Results of numerical simulations are presented.
Intuitionistic proofs and PCF programs may be interpreted as functions between domains. or as strategies on games. The two kinds of interpretation are inherently different: static vs. dynamic, extensional vs. intentio...
详细信息
Intuitionistic proofs and PCF programs may be interpreted as functions between domains. or as strategies on games. The two kinds of interpretation are inherently different: static vs. dynamic, extensional vs. intentional. It is thus extremely instructive to compare and to connect them. In this article, we investigate the extensional content of the sequential algorithm hierarchy [-](SDS) introduced by Berry and Curien. We equip every sequential game [T](SDS) of the hierarchy with a realizability relation between plays and extensions. In this way, the sequential game [T](SDS) becomes a directed acyclic graph, instead of a tree. This enables to define a hypergraph [T](HC) on the extensions (or terminal leaves) of the game [T](SDS). We establish that the resulting hierarchy [-](HC) coincides with the strongly stable hierarchy introduced by Bucciarelli and Ehrhard. We deduce from this a game-theoretic proof of Ehrhard's collapse theorem, which states that the strongly stable hierarchy coincides with the extensional collapse of the sequential algorithm hierarchy. (c) 2005 Elsevier B.V. All rights reserved.
The comparison between optimal sequential and non-sequential fixed size sample (FSS) strategies in the problem of abrupt change detection and isolation is discussed. The general case of non-orthogonal Gaussian hypothe...
详细信息
The comparison between optimal sequential and non-sequential fixed size sample (FSS) strategies in the problem of abrupt change detection and isolation is discussed. The general case of non-orthogonal Gaussian hypotheses is considered. Each hypothesis is characterized by its mean vector (the change signature) and it is desirable to detect/isolate a change subject to the constraints on a prefixed time between false alarm and a maximum probability of false isolation. It is theoretically established that the performance of the proposed FSS algorithm is directly related to the mutual geometry between the hypotheses through the Kullback-Leibler information. It is shown that a simple FSS algorithm is almost as efficient as an optimal sequential one but in contrast to the sequential strategy, the FSS strategy can be easily used for monitoring in the case of variable structure systems.
We consider the problem of density estimation when the data is in the form of a continuous stream with no fixed length. In this setting, implementations of the usual methods of density estimation such as kernel densit...
详细信息
We consider the problem of density estimation when the data is in the form of a continuous stream with no fixed length. In this setting, implementations of the usual methods of density estimation such as kernel density estimation are problematic. We propose a method of density estimation for massive datasets that is based upon taking the derivative of a smooth curve that has been fit through a set of quantile estimates. To achieve this, a low-storage, single-pass, sequential method is proposed for simultaneous estimation of multiple quantiles for massive datasets that form the basis of this method of density estimation. For comparison, we also consider a sequential kernel density estimator. The proposed methods are shown through simulation study to perform well and to have several distinct advantages over existing methods.
暂无评论