Concave-Convex Adaptive Rejection Sampling

We describe a method for generating independent samples from univariate density functions using adaptive rejection sampling without the log-concavity requirement. The method makes use of the fact that many functions can be expressed as a sum of concave and convex functions. Using a concave-convex decomposition, we bound the log-density by separately bounding the concave and convex parts using piecewise linear functions. The upper bound can then be used as the proposal distribution in rejection sampling. We demonstrate the applicability of the concave-convex approach on a number of standard distributions and describe an application to the efficient construction of sequential Monte Carlo proposal distributions for inference over genealogical trees. Computer code for the proposed algorithms is available online.     

First and second-order optimality conditions using approximations for vector equilibrium problems with constraints

We consider various kinds of solutions to nonsmooth vector equilibrium problems with functional constraints. By using first and second-order approximations as generalized derivatives, we establish both necessary and sufficient optimality conditions. Our first-order conditions are shown to be applicable in many cases, where existing ones cannot be used. The second-order conditions are new.     

Approximation accuracy, gradient methods, and error bound for structured convex optimization

Convex optimization problems arising in applications, possibly as approximations of intractable problems, are often structured and large scale. When the data are noisy, it is of interest to bound the solution error relative to the (unknown) solution of the original noiseless problem. Related to this is an error bound for the linear convergence analysis of first-order gradient methods for solving these problems. Example applications include compressed sensing, variable selection in regression, TV-regularized image denoising, and sensor network localization.     

Efficient unconditionally stable numerical schemes for a modified phase field crystal model with a strong nonlinear vacancy potential

We consider numerical approximations for a modified phase field crystal model with a strong nonlinear vacancy potential. Based on the invariant energy quadratization approach and stabilized strategies, we develop linear, unconditionally energy stable numerical schemes using the first-order Euler method, the second-order backward differentiation formulas and the second-order Crank–Nicolson method, respectively. We rigorously prove the unconditional energy stability, the mass conservation of these three numerical schemes and carry out error estimates in time for the first-order numerical scheme. Various numerical experiments in 2D and 3D are carried out to validate the accuracy, energy stability, mass conservation, and efficiency of the proposed schemes.     

Error bounds for approximations of traces of products of truncated Toeplitz operators

The paper establishes error orders for integral limit approximations to the traces of products of truncated Toeplitz operators generated by integrable real symmetric functions defined on the real line. These approximations and the corresponding error bounds are of importance in the statistical analysis of continuous-time stationary processes (asymptotic distributions and large deviations of Toeplitz type quadratic functionals, estimation of the spectrum, etc.). The results improve the rates obtained by the authors (in an earlier paper). An explicit second-order asymptotic expansion is found for the trace of a product of two truncated Toeplitz operators generated by the spectral densities of continuous-time stationary fractional Riesz-Bessel motions. The order of magnitude of the second term in this expansion is shown to depend on the long-memory parameters of the processes. The second-order term provides a substantially better approximation to the original functional, as compared with the first-order approximation. M. Ginovyan research was partially supported by National Science Foundation Grant #DMS-0706786.     

An inexact spectral bundle method for convex quadratic semidefinite programming

We present an inexact spectral bundle method for solving convex quadratic semidefinite optimization problems. This method is a first-order method, hence requires much less computational cost in each iteration than second-order approaches such as interior-point methods. In each iteration of our method, we solve an eigenvalue minimization problem inexactly, and solve a small convex quadratic semidefinite program as a subproblem. We give a proof of the global convergence of this method using techniques from the analysis of the standard bundle method, and provide a global error bound under a Slater type condition for the problem in question. Numerical experiments with matrices of order up to 3000 are performed, and the computational results establish the effectiveness of this method.     

Detection of C2‐singularities using uniform spline approximations

For the detection of C²‐singularities, we present lower estimates for the error in Schoenberg variation‐diminishing spline approximation with equidistant knots in terms of the classical second‐order modulus of smoothness. To this end, we investigate the behaviour of the iterates of the Schoenberg operator. In addition, we show an upper bound of the second‐order derivative of these iterative approximations. Finally, we provide an example of how to detect singularities based on the decay rate of the approximation error.     

A proximal gradient descent method for the extended second-order cone linear complementarity problem

We consider an extended second-order cone linear complementarity problem (SOCLCP), including the generalized SOCLCP, the horizontal SOCLCP, the vertical SOCLCP, and the mixed SOCLCP as special cases. In this paper, we present some simple second-order cone constrained and unconstrained reformulation problems, and under mild conditions prove the equivalence between the stationary points of these optimization problems and the solutions of the extended SOCLCP. Particularly, we develop a proximal gradient descent method for solving the second-order cone constrained problems. This method is very simple and at each iteration makes only one Euclidean projection onto second-order cones. We establish global convergence and, under a local Lipschitzian error bound assumption, linear rate of convergence. Numerical comparisons are made with the limited-memory BFGS method for the unconstrained reformulations, which verify the effectiveness of the proposed method.     

The nonexistence of spurious solutions to discrete,two-point boundary value problems

We investigate difference equations which arise as discrete approximations to two-point boundary value problems for systems of second-order, ordinary differential equations. We formulate conditions under which all solutions to the discrete problem satisfy certain a priori bounds which are independent of the step-size. As a result, the nonexistence of spurious solutions are guaranteed. Some existence and convergence theorems for solutions to the discrete problem are also presented.     

Extremum conditions for a nonsmooth function in terms of exhausters and coexhausters

The notions of upper and lower exhausters and coexhausters are discussed and necessary conditions for an unconstrained extremum of a nonsmooth function are derived. The necessary conditions for a minimum are formulated in terms of an upper exhauster (coexhauster) and the necessary conditions for a maximum are formulated in terms of a lower exhauster (coexhauster). This involves the problem of transforming an upper exhauster (coexhauster) into a lower exhauster (coexhauster) and vice versa. The transformation is carried out by means of a conversion operation (converter). Second-order approximations obtained with the help of second-order (upper and lower) coexhausters are considered. It is shown how a secondorder upper coexhauster can be converted into a lower coexhauster and vice versa. This problem is reduced to using a first-order conversion operator but in a space of a higher dimension. The obtained result allows one to construct second-order methods for the optimization of nonsmooth functions (Newton-type methods).     

Simulation of the Matrix Bingham–von Mises–Fisher Distribution,With Applications to Multivariate and Relational Data

Orthonormal matrices play an important role in reduced-rank matrix approximations and the analysis of matrix-valued data. A matrix Bingham–von Mises–Fisher distribution is a probability distribution on the set of orthonormal matrices that includes linear and quadratic terms in the log-density, and arises as a posterior distribution in latent factor models for multivariate and relational data. This article describes rejection and Gibbs sampling algorithms for sampling from this family of distributions, and illustrates their use in the analysis of a protein–protein interaction network. Supplemental materials, including code and data to generate all of the numerical results in this article, are available online.     

A posteriori error analysis of the discontinuous finite element methods for first order hyperbolic problems

In this paper, we consider the a posteriori error analysis of discontinuous Galerkin finite element methods for the steady and nonsteady first order hyperbolic problems with inflow boundary conditions. We establish several residual-based a posteriori error estimators which provide global upper bounds and a local lower bound on the error. Further, for nonsteady problem, we construct a fully discrete discontinuous finite element scheme and derive the a posteriori error estimators which yield global upper bound on the error in time and space. Our a posteriori error analysis is based on the mesh-dependent a priori estimates for the first order hyperbolic problems. These a posteriori error analysis results can be applied to develop the adaptive discontinuous finite element methods.     

Exact Worst-Case Convergence Rates of the Proximal Gradient Method for Composite Convex Minimization

We study the worst-case convergence rates of the proximal gradient method for minimizing the sum of a smooth strongly convex function and a non-smooth convex function, whose proximal operator is available. We establish the exact worst-case convergence rates of the proximal gradient method in this setting for any step size and for different standard performance measures: objective function accuracy, distance to optimality and residual gradient norm. The proof methodology relies on recent developments in performance estimation of first-order methods, based on semidefinite programming. In the case of the proximal gradient method, this methodology allows obtaining exact and non-asymptotic worst-case guarantees that are conceptually very simple, although apparently new. On the way, we discuss how strong convexity can be replaced by weaker assumptions, while preserving the corresponding convergence rates. We also establish that the same fixed step size policy is optimal for all three performance measures. Finally, we extend recent results on the worst-case behavior of gradient descent with exact line search to the proximal case.     

Analysis of a subdomain‐based error estimator for finite element approximations of elliptic problems

In this article we analyze a subdomain residual error estimator for finite element approximations of elliptic problems. It is obtained by solving local problems on patches of elements in weighted spaces and provides an upper bound on the energy norm of the error when the local problems are solved in sufficiently enriched discrete spaces. A guaranteed lower bound on the error is also derived by a simple postprocess of the solutions to the local problems. Numerical tests show very good effectivity indices for both the upper and lower bounds and a strong reliability of this estimator even for coarse meshes. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 165–192, 2004     

Gradient Estimate of the Heat Kernel on Modified Graphs

We obtain a condition on the modification of graphs which guarantees the preservation of the Gaussian upper bound for the gradient of the heat kernel.      

First-order L1-convergence for relaxation approximations to conservation laws

We derive a first-order rate of L¹-convergence for stiff relaxation approximations to its equilibrium solutions, i.e., piecewise smooth entropy solutions with finitely many discontinuities for scalar, convex conservation laws. The piecewise smooth solutions include initial central rarefaction waves, initial shocks, possible spontaneous formation of shocks in a future time, and interactions of all these patterns. A rigorous analysis shows that the relaxation approximations to approach the piecewise smooth entropy solutions have L¹-error bound of O(ε|log ε| + ε), where ε is the stiff relaxation coefficient. The first-order L¹-convergence rate is an improvement on the error bound. If neither central rarefaction waves nor spontaneous shocks occur, the error bound is improved to O(ε). © 1998 John Wiley & Sons, Inc.     

The aliasing error in recovery of nonbandlimited signals by prefiltering and sampling

In this paper, we study the aliasing error when a nonbandlimited function is reconstructed by means of prefiltering and sampling. We give the optimal upper bound for the mean aliasing error and show that the error bound can be minimized by a suitable filter.     

Contingent derivatives and regularization for noncoercive inverse problems

Abstract

We study the inverse problem of parameter identification in noncoercive variational problems that commonly appear in applied models. We examine the differentiability of the set-valued parameter-to-solution map using the first-order and the second-order contingent derivatives. We explore the inverse problem using the output least-squares and the modified output least-squares objectives. By regularizing the noncoercive variational problem, we obtain a single-valued regularized parameter-to-solution map and investigate its smoothness and boundedness. We also consider optimization problems using the output least-squares and the modified output least-squares objectives for the regularized variational problem. We give a complete convergence analysis showing that for the output least-squares and the modified output least-squares, the regularized minimization problems approximate the original optimization problems suitably. We also provide the first-order and the second-order adjoint method for the computation of the first-order and the second-order derivatives of the output least-squares objective. We provide discrete formulas for the gradient and the Hessian calculation and present numerical results.     

Nordsieck representation of DIMSIMs

A new representation for diagonally implicit multistage integration methods (DIMSIMs) is derived in which the vector of external stages directly approximates the Nordsieck vector. The methods in this formulation are zero-stable for any choice of variable mesh. They are also easy to implement since changing step-size corresponds to a simple rescaling of the vector of external approximations. The paper contains an analysis of local truncation error and of error accumulation in a variable step-size situation. This revised version was published online in June 2006 with corrections to the Cover Date.     

空心球体在内外压力作用下的有限位移问题

利用逐次逼近法求解了这个边值问题.我们找到一次解和二次解,从而获致位移场,应变场和应力场的二级近似公式.