In bounded-error estimation one is interested in characterizing the set S of all values of the parameters of a model which are consistent with the data in the sense that the corresponding errors fall between known pri...
详细信息
In bounded-error estimation one is interested in characterizing the set S of all values of the parameters of a model which are consistent with the data in the sense that the corresponding errors fall between known prior bounds. The problem treated here is the computation of a minimal volume ellipsoid guranteed to contain S. Although this ellipsoidal approach to parameter bounding was initially applied to models linear in their parameters, where the only error to be accounted for was an output error, it can be extended to deal with errors-in-variables problems. This makes it possible to consider models nonlinear in their parameters or dynamical models where both inputs and outputs are subject to bounded errors. Recursive algorithms are considered first. The basic algorithm of Fogel and Huang (1982), developed from the seminal work of Schweppe (1973) and modified as suggested by Belforte and co-workers (1985, 1990), is derived in detail, which makes it possible to clarify the nature of the tests needed. This algorithm is proved to be mathematically equivalent to a recursively optimal algorithm independently developed by Todd (1980) and Koenig and Pallaschke (1981) in the context of linear programming after the celebrated work of Khachiyan (1979). A recursive approach, also developed in this context, is suggested for errors-in-variables problems. Recursively optimal ellipsoids, however, are not globally optimal because of the approximations committed at each step. Using a methodology borrowed from experiment design, we obtain optimality conditions which can be used to derive a number of algorithms guaranteed to converge to the global optimum.
Through key examples and constructs, exact and approximate, complexity, computability, and solution of linear programming systems are reexamined in the light of Khachian's new notion of (approximate) solution. Alg...
详细信息
Through key examples and constructs, exact and approximate, complexity, computability, and solution of linear programming systems are reexamined in the light of Khachian's new notion of (approximate) solution. algorithms, basic theorems, and alternate representations are reviewed. It is shown that the Klee-Minty example hasnever been exponential for (exact) adjacent extreme point algorithms and that the Balinski-Gomory (exact) algorithm continues to be polynomial in cases where (approximate) ellipsoidal “centered-cutoff” algorithms (Levin, Shor, Khachian, Gacs-Lovasz) are exponential. By “model approximation,” both the Klee-Minty and the new J. Clausen examples are shown to be trivial (explicitly solvable) interval programming problems. A new notion of computable (approximate) solution is proposed together with ana priori regularization for linear programming systems. New polyhedral “constraint contraction” algorithms are proposed for approximate solution and the relevance of interval programming for good starts or exact solution is brought forth. It is concluded from all this that the “imposed problem ignorance” of past complexity research is deleterious to research progress on “computability” or “efficiency of computation.”
暂无评论