Stochastic algorithms with armijo stepsizes for minimization of functions

Stochastic algorithms for optimization problems, where function evaluations are done by Monte Carlo simulations, are presented. At each iteratex _i, they draw a predetermined numbern(i) of sample points from an underlying probability space; based on these sample points, they compute a feasible-descent direction, an Armijo stepsize, and the next iteratex _i+1. For an appropriate optimality function , corresponding to an optimality condition, it is shown that, ifn(i) , then (x _i) 0, whereJ is a set of integers whose upper density is zero. First, convergence is shown for a general algorithm prototype: then, a steepest-descent algorithm for unconstrained problems and a feasible-direction algorithm for problems with inequality constraints are developed. A numerical example is supplied.     

Finite‐difference approximation for the u(k)‐derivative with O(hM−k+1) accuracy: An analytical expression

An approximation of function u(x) as a Taylor series expansion about a point x₀ at M points x_i, ～ i = 1,2,…,M is used where x_i are arbitrary‐spaced. This approximation is a linear system for the derivatives u^(k) with an arbitrary accuracy. An analytical expression for the inverse matrix A ^?1 where A = [A_ik] = (x_i ? x₀)^k is found. A finite‐difference approximation of derivatives u^(k) of a given function u(x) at point x₀ is derived in terms of the values u(x_i). © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Approximating Data in \mathfrak{R}^{n} by a Quadratic Underestimator with Specified Hessian Minimum and Maximum Eigenvalues

The problem of approximating m data points (x _i , y _i ) in , with a quadratic function q(x, p) with s parameters, m ≥ s, is considered. The parameter vector is to be determined so as to satisfy three conditions: (1) q(x, p) must underestimate all m data points, i.e. q(x _i , p) ≤ y _i , i=1,...,m. (2) The error of the approximation is to be minimized in the L1 norm. (3) The eigenvalues of H are to satisfy specified lower and upper bounds, where H is the Hessian of q(x, p) with respect to x. This is called the Quadratic Underestimator with Bounds on Eigenvalues (QUBE) problem. An algorithm for its solution (QUBE algorithm) is given and justified, and computational results presented. The QUBE algorithm has application to finding the global minimum of a basin (or funnel) shaped function with a large number of local minima. Such problems arise in computational biology where it is desired to find the global minimum of an energy surface, in order to predict native protein-ligand docking geometry (drug design) or protein structure. Computational results for a simulated docking energy surface, with n=15, are presented. It is shown that specifying a small condition number for H improves the ability of the underestimator to correctly predict the global minimum point.     

On Characterization of Best Approximation with Certain Constraints

SupposeKis the intersection of a finite number of closed half-spaces {K_i} in a Hilbert spaceX, andx∈X\K. Dykstra's cyclic projections algorithm is a known method to determine an approximate solution of the best approximation ofxfromK, which is denoted byP_K(x). Dykstra's algorithm reduces the problem to an iterative scheme which involves computing the best approximation from the individualK_i. It is known that the sequence {x_j} generated by Dykstra's method converges to the best approximationP_K(x). But since it is difficult to find the definite value of an upper bound of the error ‖x_j−P_K(x)‖, the applicability of the algorithm is restrictive. This paper introduces a new method, called thesuccessive approximate algorithm, by which one can generate a finite sequencex₀, x₁, …, x_kwithx_k=P_K(x). In addition, the error ‖x_j−P_K(x)‖ is monotone decreasing and has a definite upper bound easily to be determined. So the new algorithm is very applicable in practice.     

Highly accurate tables for elementary functions

In this article we describe a fast method to obtain highly accurate tables for all elementary functions by using Bresenham's algorithm. For nearly equally spaced table-points {x _i } we construct pairs {f(x _i ),g(x _i )} such thatf(x _i ) is a machine number andg(x _i ) is very close to an exactly representable number. By a random sampling in an interval centered onx _i we can even find a triplet of nearly machine numbers. The table method together with a polynomial approximation of the function near a table value provides last bit accuracy for more than 99.8% of the argument values without using extended precision calculations [3, 4, 10, 11].     

Kernels of derivations of polynomial rings and Casimir elements

We propose an algorithm for the evaluation of elements of the kernel of an arbitrary derivation of a polynomial ring. The algorithm is based on an analog of the well-known Casimir element of a finite-dimensional Lie algebra. By using this algorithm, we compute the kernels of Weitzenb?ck derivation d(x _i ) = x _i−1, d(x ₀) = 0, i = 0,…, n, for the cases where n ≤ 6.     

Two generalizations of Dykstra’s cyclic projections algorithm

Dykstra’s cyclic projections algorithm allows one to compute best approximations to any pointx in a Hilbert space from the intersectionC = ⋂ _l ^r C _i of a finite number of closed convex setsC _i , by reducing it to a sequence of best approximation problems from theindividual setsC _i . Here we present two generalizations of this algorithm. First we allow the number of setsC _i to beinfinite rather than finite; secondly, we allow arandom, rather than cyclic, ordering of the setsC _i . This author was supported by NSF Grant DMS-9303705.     

Some localized separation axioms and their implications

In a topological spaceX, a T₂-distinct pointx means that for anyyX xy, there exist disjoint open neighbourhoods ofx andy. Similarly, T₀-distinct points and T₁distinct points are defined. In a T_i-distinct point-setA, we assume that eachxA is a T _i -distinct point (i=0, 1, 2). In the present paper some implications of these notions which localize the T _i -separation axioms (i=0, 1, 2) requirement, are studied. Suitable variants of regularity and normality in terms of T₂-distinct points are shown hold in a paracompact space (without the assumption of any separation axioms). Later T₀-distinct points are used to give two characterizations of the R _D -axiom.¹ In the end, some simple results are presented including a condition under which an almost compact set is closed and a result regarding two continuous functions from a topological space into a Hausdorff space is sharpened. A result which relates a limit pointv to an -limit point is stated.     

Data‐Driven Optimal Transport

The problem of optimal transport between two distributions ρ(x) and μ(y) is extended to situations where the distributions are only known through a finite number of samples {x_i} and {y_j}. A weak formulation is proposed, based on the dual of the Kantorovich formulation, with two main modifications: replacing the expected values in the objective function by their empirical means over the {x_i} and {y_j}, and restricting the dual variables u(x) and v(y) to a suitable set of test functions adapted to the local availability of sample points. A procedure is proposed and tested for the numerical solution of this problem, based on a fluidlike flow in phase space, where the sample points play the role of active Lagrangian markers. © 2016 Wiley Periodicals, Inc.     

Coefficient Quantization in Banach Spaces

Let (e _i ) be a dictionary for a separable infinite-dimensional Banach space X. We consider the problem of approximation by linear combinations of dictionary elements with quantized coefficients drawn usually from a ‘finite alphabet’. We investigate several approximation properties of this type and connect them to the Banach space geometry of X. The existence of a total minimal system with one of these properties, namely the coefficient quantization property, is shown to be equivalent to X containing c ₀. We also show that, for every ε>0, the unit ball of every separable infinite-dimensional Banach space X contains a dictionary (x _i ) such that the additive group generated by (x _i ) is (3+ε)⁻¹-separated and 1/3-dense in X.      

A Dimensional Splitting Method for Quasilinear Hyperbolic Equations with Variable Coefficients

A numerical method is presented for the variable coefficient, nonlinear hyperbolic equation u _t + _i=1 ^d V _i(x, t)f _i(u) _{x i} = 0 in arbitrary space dimension for bounded velocities that are Lipschitz continuous in the x variable. The method is based on dimensional splitting and uses a recent front tracking method to solve the resulting one-dimensional non-conservative equations. The method is unconditionally stable, and it produces a subsequence that converges to the entropy solution as the discretization of time and space tends to zero. Four numerical examples are presented; numerical error mechanisms are illustrated for two linear equations, the efficiency of the method compared with a high-resolution TVD method is discussed for a nonlinear problem, and finally, applications to reservoir simulation are presented.     

The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences

Various applications involve assigning discrete label values to a collection of objects based on some pairwise noisy data. Due to the discrete—and hence nonconvex—structure of the problem, computing the optimal assignment (e.g., maximum‐likelihood assignment) becomes intractable at first sight. This paper makes progress towards efficient computation by focusing on a concrete joint alignment problem; that is, the problem of recovering n discrete variables x_i ∊ {1, …, m}, 1 ≤ i ≤ n, given noisy observations of their modulo differences {x_i — x_j mod m}. We propose a low‐complexity and model‐free nonconvex procedure, which operates in a lifted space by representing distinct label values in orthogonal directions and attempts to optimize quadratic functions over hypercubes. Starting with a first guess computed via a spectral method, the algorithm successively refines the iterates via projected power iterations. We prove that for a broad class of statistical models, the proposed projected power method makes no error—and hence converges to the maximum‐likelihood estimate—in a suitable regime. Numerical experiments have been carried out on both synthetic and real data to demonstrate the practicality of our algorithm. We expect this algorithmic framework to be effective for a broad range of discrete assignment problems.© 2018 Wiley Periodicals, Inc.     

A Second-Order Bundle Method Based on -Decomposition Strategy for a Special Class of Eigenvalue Optimizations

In the past decade, eigenvalue optimization has gained remarkable attention in various engineering applications. One of the main difficulties with numerical analysis of such problems is that the eigenvalues, considered as functions of a symmetric matrix, are not smooth at those points where they are multiple. We propose a new explicit nonsmooth second-order bundle algorithm based on the idea of the proximal bundle method on minimizing the arbitrary eigenvalue over an affine family of symmetric matrices, which is a special class of eigenvalue function–D.C. function. To the best of our knowledge, few methods currently exist for minimizing arbitrary eigenvalue function. In this work, we apply the -Lagrangian theory to this class of D.C. functions: the arbitrary eigenvalue function λ_i with affine matrix-valued mappings, where λ_i is usually not convex. We prove the global convergence of our method in the sense that every accumulation point of the sequence of iterates is stationary. Moreover, under mild conditions we show that, if started close enough to the minimizer x*, the proposed algorithm converges to x* quadratically. The method is tested on some constrained optimization problems, and some encouraging preliminary numerical results show the efficiency of our method.     

An Interval Analysis Approach to the EM Algorithm

Abstract

The EM algorithm is widely used in incomplete-data problems (and some complete-data problems) for parameter estimation. One limitation of the EM algorithm is that, upon termination, it is not always near a global optimum. As reported by Wu (1982), when several stationary points exist, convergence to a particular stationary point depends on the choice of starting point. Furthermore, convergence to a saddle point or local minimum is also possible. In the EM algorithm, although the log-likelihood is unknown, an interval containing the gradient of the EM q function can be computed at individual points using interval analysis methods. By using interval analysis to enclose the gradient of the EM q function (and, consequently, the log-likelihood), an algorithm is developed that is able to locate all stationary points of the log-likelihood within any designated region of the parameter space. The algorithm is applied to several examples. In one example involving the t distribution, the algorithm successfully locates (all) seven stationary points of the log-likelihood.     

A quadratic approximation method for minimizing a class of quasidifferentiable functions

Summary An unconstrained nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities arise from terms of the form max [f ₁(x), ...,f _n (x)], which may enter nonlinearly in the objective function. Local convex polyhedral upper approximations to the objective function are introduced. These approximations are used in an iterative method for solving the problem. The algorithm proceeds by solving quadratic programming subproblems to generate search directions. Approximate line searches ensure global convergence of the method to stationary points. The algorithm is conceptually simple and easy to implement. It generalizes efficient variable metric methods for minimax calculations.     

An Asymptotic Property of Schachermayer's Space under Renorming

Let X be a Banach space with closed unit ball B. Given k , X is said to be k-β, respectively, (k + 1)-nearly uniformly convex ((k + 1)-NUC), if for every ε > 0 there exists δ, 0 < δ < 1, so that for every x B and every ε-separated sequence (x_n) B there are indices (n_i)^k_{i = 1}, respectively, (n_i)^{k + 1}_{i = 1}, such that (1/(k + 1))||x + ∑^k_{i = 1} x_ni|| ≤ 1 − δ, respectively, (1/(k + 1))||∑^{k + 1}_{i = 1} x_ni|| ≤ 1 − δ. It is shown that a Banach space constructed by Schachermayer is 2-β, but is not isomorphic to any 2-NUC Banach space. Modifying this example, we also show that there is a 2-NUC Banach space which cannot be equivalently renormed to be 1-β.     

Integral approximation sequences

Letn linear formsL _i onm variables be given, normalized so that all coefficients have absolute value at most unity. Letw ₁, ...,w _m be real numbers andx ₁, ...,x _m be integers. We sayE _i =L _i (w ₁, ...,w _m )-L _i (x ₁, ...,x _m ) is the error in approximating thew's by thex's with respect to formL _i It is shown that given anyw's there is an integral approximation ofx's so that the errorsE _i are small-roughly that simultaneously for alli.     

A stochastic steepest-descent algorithm

A stochastic steepest-descent algorithm for function minimization under noisy observations is presented. Function evaluation is done by performing a number of random experiments on a suitable probability space. The number of experiments performed at a point generated by the algorithm reflects a balance between the conflicting requirements of accuracy and computational complexity. The algorithm uses an adaptive precision scheme to determine the number of random experiments at a point; this number tends to increase whenever a stationary point is approached and to decrease otherwise. Two rules are used to determine the number of random experiments at a point; one, in the inner loop of the algorithm, uses the magnitude of the observed gradient of the function to be minimized; and the other, in the outer-loop, uses a measure of accumulated errors in function evaluations at past points generated by the algorithm. Once a stochastic approximation of the function to be minimized is obtained at a point, the algorithm proceeds to generate the next point by using the steepest-descent deterministic methods of Armijo and Polak (Refs. 3, 4). Convergence of the algorithm to stationary points is demonstrated under suitable assumptions.     

Absolutely representing systems,uniform smoothness and type

An absolutely representing system (ARS) in a Banach space X is a set D ? X such that every vector x in X admits a representation by an absolutely convergent series x = Σ _i a _i x _i with (a _i ) ? R and (x _i ) ? D. We investigate some general properties of absolutely representing systems. In particular, absolutely representing systems in uniformly smooth and in B-convex Banach spaces are characterized via ?-nets of the unit balls. Every absolutely representing system in a B-convex Banach space is quick, i.e., in the representation above one can achieve ∥a _i x _i ∥ < cq ⁱ ∥x∥, i = 1, 2,… for some constants c > 0 and q ? (0,1).     

White noise eliminates instability

Let x₁,..., x_n be points in the d-dimensional Euclidean space E^d with || x_i-x_j|| ￡ 1\| x_{i}-x_{j}\| \le 1 for all 1 \leqq i,j \leqq n1 \leqq i,j \leqq n, where || .||\| .\| denotes the Euclidean norm. We ask for the maximum M(d,n) of \mathop?_i, j=1ⁿ|| x_i-x_j|| ²\textstyle\mathop\sum\limits _{i,\,j=1}^{n}\| x_{i}-x_{j}\| ^{2} (see [4]). This paper deals with the case d = 2. We calculate M(2, n) and show that the value M(2, n) is attained if and only if the points are distributed as evenly as possible among the vertices of a regular triangle of edge-length 1. Moreover we give an upper bound for the value \mathop?_i, j=1ⁿ|| x_i-x_j|| \textstyle\mathop\sum\limits _{i,\,j=1}^{n}\| x_{i}-x_{j}\| , where the points x₁,...,x_n are chosen under the same constraints as above.