Calculation of Posterior Bounds Given Convex Sets of Prior Probability Measures and Likelihood Functions

Abstract

This article presents alternatives and improvements to Lavine's algorithm, currently the most popular method for calculation of posterior expectation bounds induced by sets of probability measures. First, methods from probabilistic logic and Walley's and White-Snow's algorithms are reviewed and compared to Lavine's algorithm. Second, the calculation of posterior bounds is reduced to a fractional programming problem. From the unifying perspective of fractional programming, Lavine's algorithm is derived from Dinkelbach's algorithm, and the White-Snow algorithm is shown to be similar to the Charnes-Cooper transformation. From this analysis, a novel algorithm for expectation bounds is derived. This algorithm provides a complete solution for the calculation of expectation bounds from priors and likelihood functions specified as convex sets of measures. This novel algorithm is then extended to handle the situation where several independent identically distributed measurements are available. Examples are analyzed through a software package that performs robust inferences and that is publicly available.     

Nonlinear Smoothing and the EM Algorithm for Positive Integral Equations of the First Kind

We study a modification of the EMS algorithm in which each step of the EMS algorithm is preceded by a nonlinear smoothing step of the form , where S is the smoothing operator of the EMS algorithm. In the context of positive integral equations (à la positron emission tomography) the resulting algorithm is related to a convex minimization problem which always admits a unique smooth solution, in contrast to the unmodified maximum likelihood setup. The new algorithm has slightly stronger monotonicity properties than the original EM algorithm. This suggests that the modified EMS algorithm is actually an EM algorithm for the modified problem. The existence of a smooth solution to the modified maximum likelihood problem and the monotonicity together imply the strong convergence of the new algorithm. We also present some simulation results for the integral equation of stereology, which suggests that the new algorithm behaves roughly like the EMS algorithm. Accepted 1 April 1997     

Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem

Eigenvalues and eigenvectors of a large sparse symmetric matrix A can be found accurately and often very quickly using the Lanczos algorithm without reorthogonalization. The algorithm gives essentially correct information on the eigensystem of A, although it does not necessarily give the correct multiplicity of multiple, or even single, eigenvalues. It is straightforward to determine a useful bound on the accuracy of every eigenvalue given by the algorithm. The initial behavior of the algorithm is surprisingly good: it produces vectors spanning the Krylov subspace of a matrix very close to A until this subspace contains an exact eigenvector of a matrix very close to A, and up to this point the effective behavior of the algorithm for the eigenproblem is very like that of the Lanczos algorithm using full reorthogonalization. This helps to explain the remarkable behavior of the basic Lanczos algorithm.     

Acceleration of the EM algorithm using the vector epsilon algorithm

The expectation–maximization (EM) algorithm is a very general and popular iterative computational algorithm to find maximum likelihood estimates from incomplete data and broadly used to statistical analysis with missing data, because of its stability, flexibility and simplicity. However, it is often criticized that the convergence of the EM algorithm is slow. The various algorithms to accelerate the convergence of the EM algorithm have been proposed. The vector ε algorithm of Wynn (Math Comp 16:301–322, 1962) is used to accelerate the convergence of the EM algorithm in Kuroda and Sakakihara (Comput Stat Data Anal 51:1549–1561, 2006). In this paper, we provide the theoretical evaluation of the convergence of the ε-accelerated EM algorithm. The ε-accelerated EM algorithm does not use the information matrix but only uses the sequence of estimates obtained from iterations of the EM algorithm, and thus it keeps the flexibility and simplicity of the EM algorithm.     

Simplicial approximation of solutions to the nonlinear complementarity problem with lower and upper bounds

Ideas of a simplicial variable dimension restart algorithm to approximate zero points onR ⁿ developed by the authors and of a linear complementarity problem pivoting algorithm are combined to an algorithm for solving the nonlinear complementarity problem with lower and upper bounds. The algorithm can be considered as a modification of the2n-ray zero point finding algorithm onR ⁿ . It appears that for the new algorithm the number of linear programming pivot steps is typically less than for the2n-ray algorithm applied to an equivalent zero point problem. This is caused by the fact that the algorithm utilizes the complementarity conditions on the variables. This work is part of the VF-program “Equilibrium and Disequilibrium in Demand and Supply,” which has been approved by the Netherlands Ministry of Education and Sciences.     

A constrained optimization approach to solving certain systems of convex equations

This research presents a new constrained optimization approach for solving systems of nonlinear equations. Particular advantages are realized when all of the equations are convex. For example, a global algorithm for finding the zero of a convex real-valued function of one variable is developed. If the algorithm terminates finitely, then either the algorithm has computed a zero or determined that none exists; if an infinite sequence is generated, either that sequence converges to a zero or again no zero exists. For solving n-dimensional convex equations, the constrained optimization algorithm has the capability of determining that the system of equations has no solution. Global convergence of the algorithm is established under weaker conditions than previously known and, in this case, the algorithm reduces to Newton’s method together with a constrained line search at each iteration. It is also shown how this approach has led to a new algorithm for solving the linear complementarity problem.     

A penalty continuation method for the ∓∞ solution of overdetermined linear systems

A new algorithm for the ∓_∞ solution of overdetermined linear systems is given. The algorithm is based on the application of quadratic penalty functions to a primal linear programming formulation of the ∓_∞ problem. The minimizers of the quadratic penalty function generate piecewise-linear non-interior paths to the set of ∓_∞ solutions. It is shown that the entire set of ∓_∞ solutions is obtained from the paths for sufficiently small values of a scalar parameter. This leads to a finite penalty/continuation algorithm for ∓_∞ problems. The algorithm is implemented and extensively tested using random and function approximation problems. Comparisons with the Barrodale-Phillips simplex based algorithm and the more recent predictor-corrector primal-dual interior point algorithm are given. The results indicate that the new algorithm shows a promising performance on random (non-function approximation) problems.     

Reduction Algorithm for the NPMLE for the Distribution Function of Bivariate Interval-Censored Data

This article considers computational aspects of the nonparametric maximum likelihood estimator (NPMLE) for the distribution function of bivariate interval-censored data. The computation of the NPMLE consists of a parameter reduction step and an optimization step. This article focuses on the reduction step and introduces two new reduction algorithms: the Tree algorithm and the HeightMap algorithm. The Tree algorithm is mentioned only briefly. The HeightMap algorithm is discussed in detail and also given in pseudo code. It is a fast and simple algorithm of time complexityO(n²). This is an order faster than the best known algorithm thus far by Bogaerts and Lesaffre. We compare the new algorithms to earlier algorithms in a simulation study, and demonstrate that the new algorithms are significantly faster. Finally, we discuss how the HeightMap algorithm can be generalized to d-dimensional data with d > 2. Such a multivariate version of the HeightMap algorithm has time complexity O(n^d).     

A note to the paper “An efficient algorithm for linear programming” of V Ch Venkaiah

In Venkaiah [1] an algorithm for solving linear optimization problems based on the idea of the projective algorithm of Karmarkar, is proposed. The essential simplification in the new algorithm is the use of a fixed projection operator. In this way the algorithm requires onlyO(n ² ) operations to obtain a sufficient exact solution. In this note it is shown that in some special cases the algorithm of Venkaiah yields a feasible solution that is far from the optimal one.     

On the internal stepsize of an extrapolation algorithm for IVP in ODE

We propose an extrapolation algorithm for initial value problems in ordinary differential equations. In the algorithm, an appropriately chosen stepsizeH is divided into smaller stepsizes by a sequence and a new stopping rule is proposed. The sequences applied to the algorithm are Romberg {2,4,8,16,32,...}, Bulirsch {2,4,6,8,16...} and Harmonic {2,4,6,8,10,12,...} types. The proposed algorithm is compared numerically with the algorithm introduced by Stoer. In view of the accuracy of numerical solutions, the relatively small number of calculations, the stability and reliability of the algorithm, we found that the algorithm with the Romberg sequence is the best.     

An Arbitrary Starting Variable Dimension Algorithm for Computing an Integer Point of a Simplex

An arbitrary starting variable dimension algorithm is proposed to compute an integer point of an n-dimensional simplex. It is based on an integer labeling rule and a triangulation of Rⁿ. The algorithm consists of two interchanging phases. The first phase of the algorithm is a variable dimension algorithm, which generates simplices of varying dimensions,and the second phase of the algorithm forms a full-dimensional pivoting procedure, which generates n-dimensional simplices. The algorithm varies from one phase to the other. When the matrix defining the simplex is in the so-called canonical form, starting at an arbitrary integer point, the algorithm within a finite number of iterations either yields an integer point of the simplex or proves that no such point exists.     

Polynomial Convergence of Second-Order Mehrotra-Type Predictor-Corrector Algorithms over Symmetric Cones

This paper presents an extension of the variant of Mehrotra’s predictor–corrector algorithm which was proposed by Salahi and Mahdavi-Amiri (Appl. Math. Comput. 183:646–658, 2006) for linear programming to symmetric cones. This algorithm incorporates a safeguard in Mehrotra’s original predictor–corrector algorithm, which keeps the iterates in the prescribed neighborhood and allows us to get a reasonably large step size. In our algorithm, the safeguard strategy is not necessarily used when the affine scaling step behaves poorly, which is different from the algorithm of Salahi and Mahdavi-Amiri. We slightly modify the maximum step size in the affine scaling step and extend the algorithm to symmetric cones using the machinery of Euclidean Jordan algebras. Based on the Nesterov–Todd direction, we show that the iteration-complexity bound of the proposed algorithm is , where r is the rank of the associated Euclidean Jordan algebras and ε>0 is the required precision.     

Fast Nonparametric Density-Based Clustering of Large Datasets Using a Stochastic Approximation Mean-Shift Algorithm

Mean-shift is an iterative procedure often used as a nonparametric clustering algorithm that defines clusters based on the modal regions of a density function. The algorithm is conceptually appealing and makes assumptions neither about the shape of the clusters nor about their number. However, with a complexity of O(n²) per iteration, it does not scale well to large datasets. We propose a novel algorithm which performs density-based clustering much quicker than mean shift, yet delivering virtually identical results. This algorithm combines subsampling and a stochastic approximation procedure to achieve a potential complexity of O(n) at each step. Its convergence is established. Its performances are evaluated using simulations and applications to image segmentation, where the algorithm was tens or hundreds of times faster than mean shift, yet causing negligible amounts of clustering errors. The algorithm can be combined with existing approaches to further accelerate clustering.     

Invariant G2V algorithm for computing SAGBI-Gröbner bases

Faugère and Rahmany have presented the invariant F5 algorithm to compute SAGBI-Grbner bases of ideals of invariant rings. This algorithm has an incremental structure, and it is based on the matrix version of F5 algorithm to use F5 criterion to remove a part of useless reductions. Although this algorithm is more efficient than the Buchberger-like algorithm, however it does not use all the existing criteria (for an incremental structure) to detect superfluous reductions. In this paper, we consider a new algorithm, namely, invariant G2V algorithm, to compute SAGBI-Grbner bases of ideals of invariant rings using more criteria. This algorithm has a new structure and it is based on the G2V algorithm; a variant of the F5 algorithm to compute Grbner bases. We have implemented our new algorithm in Maple , and we give experimental comparison, via some examples, of performance of this algorithm with the invariant F5 algorithm.     

Local convergence of the method of multipliers for variational and optimization problems under the noncriticality assumption

We present an efficient algorithm to find an optimal fiber orientation in composite materials. Within a two-scale setting fiber orientation is regarded as a function in space on the macrolevel. The optimization problem is formulated within a function space setting which makes the imposition of smoothness requirements straightforward and allows for rather general convex objective functionals. We show the existence of a global optimum in the Sobolev space H ¹(Ω). The algorithm we use is a one level optimization algorithm which optimizes with respect to the fiber orientation directly. The costly solve of a big number of microlevel problems is avoided using coordinate transformation formulas. We use an adjoint-based gradient type algorithm, but generalizations to higher-order schemes are straightforward. The algorithm is tested for a prototypical numerical example and its behaviour with respect to mesh independence and dependence on the regularization parameter is studied.     

A complementary variant of Lemke's method for the linear complementary problem

An algorithm for the linear complementarity problem is developed which uses principal pivots only. The algorithm is shown to be equivalent to Lemke's algorithm. The advantage of the proposed algorithm is that infeasibility tests may be made after each principal pivot. One such test is equivalent to a check whether the matrix satisfies the “plus” condition of copositive plus matrices or the condition of classL ₂ of Eaves.     

A descent algorithm for nonsmooth convex optimization

This paper presents a new descent algorithm for minimizing a convex function which is not necessarily differentiable. The algorithm can be implemented and may be considered a modification of the ε-subgradient algorithm and Lemarechal's descent algorithm. Also our algorithm is seen to be closely related to the proximal point algorithm applied to convex minimization problems. A convergence theorem for the algorithm is established under the assumption that the objective function is bounded from below. Limited computational experience with the algorithm is also reported.     

A parametric approach for solving a class of generalized quadratic-transformable rank-two nonconvex programs

The aim of this paper is to propose a solution algorithm for a particular class of rank-two nonconvex programs having a polyhedral feasible region. The algorithm is based on the so-called “optimal level solutions” method. Various global optimality conditions are discussed and implemented in order to improve the efficiency of the algorithm.     

Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm

In this paper we give a new convergence analysis of a projective scaling algorithm. We consider a long-step affine scaling algorithm applied to a homogeneous linear programming problem obtained from the original linear programming problem. This algorithm takes a fixed fraction λ≤2/3 of the way towards the boundary of the nonnegative orthant at each iteration. The iteration sequence for the original problem is obtained by pulling back the homogeneous iterates onto the original feasible region with a conical projection, which generates the same search direction as the original projective scaling algorithm at each iterate. The recent convergence results for the long-step affine scaling algorithm by the authors are applied to this algorithm to obtain some convergence results on the projective scaling algorithm. Specifically, we will show (i) polynomiality of the algorithm with complexities of O(nL) and O(n ² L) iterations for λ<2/3 and λ=2/3, respectively; (ii) global covnergence of the algorithm when the optimal face is unbounded; (iii) convergence of the primal iterates to a relative interior point of the optimal face; (iv) convergence of the dual estimates to the analytic center of the dual optimal face; and (v) convergence of the reduction rate of the objective function value to 1−λ.