A simple scheme for generating nearly uniform distribution of antipodally symmetric points on the unit sphere

A variant of the Thomson problem, which is about placing a set of points uniformly on the surface of a sphere, is that of generating uniformly distributed points on the sphere that are endowed with antipodal symmetry, i.e., if x is an element of the point set then -x is also an element of that point set. Point sets with antipodal symmetry are of special importance to many scientific and engineering applications. Although this type of point sets may be generated through the minimization of a slightly modified electrostatic potential, the optimization procedure becomes unwieldy when the size of the point set increases beyond a few thousands. Therefore, it is desirable to have a deterministic scheme capable of generating this type of point set with near uniformity. In this work, we will present a simple deterministic scheme to generate nearly uniform point sets with antipodal symmetry.     

给定密度随机数的生成的通用方法与球面和球体上均匀随机向量的生成法

本文首先介绍基于垂直概率密度表示的,给定密度函数的随机数生成的通用方法;然后介绍球面及球体上均匀随机向量的生成算法。     

Distributing points uniformly on the unit sphere under a mirror reflection symmetry constraint

Uniformly distributed point sets on the unit sphere with and without symmetry constraints have been found useful in many scientific and engineering applications. Here, a novel variant of the Thomson problem is proposed and formulated as an unconstrained optimization problem. While the goal of the Thomson problem is to find the minimum energy configuration of N electrons constrained on the surface of the unit sphere, this novel variant imposes a new symmetry constraint – mirror reflection symmetry with the x–y plane as the plane of symmetry. Qualitative features of the two-dimensional projection of the optimal configurations are briefly mentioned and compared to the ground-state configurations of the two dimensional system of charged particles laterally confined by a parabolic potential well.     

On methods for generating uniform random points on the surface of a sphere

Some methods for generating random points uniformly distributed on the surface of ann-sphere have been proposed to simulate spherical processes on computer. A standard method is to normalize random points inside of the sphere, see M. Muller [5]. Improved methods were given by J. M. Cook [1] and G. Marsaglia [4] in three and four dimensions, and computational methods in higher dimensions by J. S. Hicks and R. F. Wheeling [3] and M. Sibuya [6]. In this paper we shall offer direct methods for generating uniform random points on the surface of a unitn-sphere, which can be easily combined with Marsaglia's idea for getting more improved methods. Our method in even dimensions was obtained by M. Sibuya [6], but a differential-geometric view-point will make analyses simpler, even in odd dimensions.     

On Gruber’s problem concerning uniform distribution on the sphere

In this note we give a partial answer to a problem posed by Peter Gruber on the determination of uniform distribution of a sequence of points on the three-dimensional sphere from its appropriate behavior on caps.     

Using QR Decomposition to Obtain a New Instance of Mesh Adaptive Direct Search with Uniformly Distributed Polling Directions

The purpose of this paper is to introduce a new instance of the Mesh Adaptive Direct Search (Mads) class of algorithms, which utilizes a more uniform distribution of poll directions than do other common instances, such as OrthoMads and LtMads. Our new implementation, called QrMads, bases its poll directions on an equal area partitioning of the n-dimensional unit sphere and the QR decomposition to obtain an orthogonal set of directions. While each instance produces directions which are dense in the limit, QrMads directions are more uniformly distributed in the unit sphere. This uniformity is the key to enhanced performance in higher dimensions and for constrained problems. The trade-off is that QrMads is no longer deterministic and at each iteration the set of polling directions is no longer orthogonal. Instead, at each iteration, the poll directions are only ‘nearly orthogonal,’ becoming increasingly closer to orthogonal as the mesh size decreases. Finally, we present a variety of test results on smooth, nonsmooth, unconstrained, and constrained problems and compare them to OrthoMads on the same set of problems.     

Canonical Duality Theory and Solutions to Constrained Nonconvex Quadratic Programming

This paper presents a perfect duality theory and a complete set of solutions to nonconvex quadratic programming problems subjected to inequality constraints. By use of the canonical dual transformation developed recently, a canonical dual problem is formulated, which is perfectly dual to the primal problem in the sense that they have the same set of KKT points. It is proved that the KKT points depend on the index of the Hessian matrix of the total cost function. The global and local extrema of the nonconvex quadratic function can be identified by the triality theory [11]. Results show that if the global extrema of the nonconvex quadratic function are located on the boundary of the primal feasible space, the dual solutions should be interior points of the dual feasible set, which can be solved by deterministic methods. Certain nonconvex quadratic programming problems in {\open {R}}^{n} can be converted into a dual problem with only one variable. It turns out that a complete set of solutions for quadratic programming over a sphere is obtained as a by-product. Several examples are illustrated.     

The Complexity of Upward Drawings on Spheres

Although there is a linear time algorithm to decide whether an ordered set has an upward drawing on a surface topologically equivalence to a sphere, we shall prove that the decision problem whether an ordered set has an upward drawing on a sphere is NP-complete. The proof involves the investigation of the surface topology of ordered sets highlighting especially their saddle points. It echoes the recent, important result due to A. Garg and R. Tamassia (1995) that upward planarity testing is NP-complete, for which we give a new proof.     

Strong convergence of composite iterative methods for equilibrium problems and fixed point problems

We introduce a new composite iterative scheme by viscosity approximation method for finding a common point of the set of solutions of an equilibrium problem and the set of fixed points of a nonexpansive mapping in a Hilbert space. It is proved that the sequence generated by the iterative scheme converges strongly to a common point of the set of solutions of an equilibrium problem and the set of fixed points of a nonexpansive mapping. Our results substantially improve the corresponding results of Takahashi and Takahashi [A. Takahashi, W. Takahashi, Viscosity approximation methods for equilibrium problems and fixed point problems in Hilbert spaces, J. Math. Anal. Appl. 331 (2007) 506-515]. Essentially a new approach for finding solutions of equilibrium problems and the fixed points of nonexpansive mappings is provided.     

Stochastic averaging with a flattened Hamiltonian: A Markov process on a stratified space (a whiskered sphere)

We consider a random perturbation of a 2-dimensional Hamiltonian ODE. Under an appropriate change of time, we identify a reduced model, which in some aspects is similar to a stochastically averaged model. The novelty of our problem is that the set of critical points of the Hamiltonian has an interior. Thus we can stochastically average outside this set of critical points, but inside we can make no model reduction. The result is a Markov process on a stratified space which looks like a whiskered sphere (i.e, a 2-dimensional sphere with a line attached). At the junction of the sphere and the line, glueing conditions identify the behavior of the Markov process.

     

Potential flow past a porous body with a core of different permeability

It is well known that a uniform flow past a non-permeable rigid body does not exert a total force upon the surface of the body, however this is not the case when the body is permeable. Power et. al. (1984, 1986) first solved the problem of uniform potential flow past a two-dimensional permeable circular cylinder, with constant permeability, and found that the exterior flow exerts a drag force upon the surface of the cylinder independent of its size and secondly the problem when the uniform potential flow past a porous sphere, with constant permeability, in this case the exterior flow exerts a drag force on the sphere which is linearly dependent on the radius of the sphere. Here we will present the solution of two problems, a uniform potential flow past a porous circular cylinder and past a porous sphere, for each case the porous body is composed of two materials with different permeabilities. In both cases the total force exerted by the exterior flow upon the body is dependent on the thickness of the porous materials, and in the limit when the two permeabilities are equal, the previous results, circular cylinder and sphere, with constant permeability, are recovered. Atlhough, the mathematics involved in the solution of the present problem is simple, due to the nice boundary geometry of the bodies, the final expression for the total force found in each case is quite interesting on the way it depends on the permeability relation, in particular, in the limiting cases of a porous body with solid or hollow core.     

The Multi-Handler Knapsack Problem under Uncertainty

The Multi-Handler Knapsack Problem under Uncertainty is a new stochastic knapsack problem where, given a set of items, characterized by volume and random profit, and a set of potential handlers, we want to find a subset of items which maximizes the expected total profit. The item profit is given by the sum of a deterministic profit plus a stochastic profit due to the random handling costs of the handlers. On the contrary of other stochastic problems in the literature, the probability distribution of the stochastic profit is unknown. By using the asymptotic theory of extreme values, a deterministic approximation for the stochastic problem is derived. The accuracy of such a deterministic approximation is tested against the two-stage with fixed recourse formulation of the problem. Very promising results are obtained on a large set of instances in negligible computing time.     

Rolling of a non-homogeneous ball over a sphere without slipping and twisting

Consider the problem of rolling a dynamically asymmetric balanced ball (the Chaplygin ball) over a sphere. Suppose that the contact point has zero velocity and the projection of the angular velocity to the normal vector of the sphere equals zero. This model of rolling differs from the classical one. It can be realized, in some approximation, if the ball is rubber coated and the sphere is absolutely rough. Recently, J. Koiller and K. Ehlers pointed out the measure and the Hamiltonian structure for this problem. Using this structure we construct an isomorphism between this problem and the problem of the motion of a point on a sphere in some potential field. The integrable cases are found.      

Spherical Distribution of 5 Points with Maximal Distance Sum

In this paper, we consider the problem of spherical distribution of 5 points, that is, how to configure 5 points on the unit sphere such that the mutual distance sum is maximal. It is conjectured that the sum of distances is maximal if the 5 points form a bipyramid distribution with two points positioned at opposite poles of the sphere and the other three positioned uniformly on the equator. We study this problem using interval methods and related techniques, and give a computer-assisted proof.     

On degeneracy and collapsing in the construction of the set of objective values in a multiple objective linear program

In this paper an algorithm is developed to generate all nondominated extreme points and edges of the set of objective values of a multiple objective linear program. The approach uses simplex tableaux but avoids generating unnecessary extreme points or bases of extreme points. The procedure is based on, and improves, an algorithm Dauer and Liu developed for this problem. Essential to this approach is the work of Gal and Kruse on the neighborhood problem of determining all extreme points of a convex polytope that are adjacent to a given (degenerate) extreme point of the set. The algorithm will incorporate Gal's degeneracy graph approach to the neighborhood problem with Dauer's objective space analysis of multiple objective linear programs.     

Implementing pure adaptive search for global optimization using Markov chain sampling

The Pure Adaptive Search (PAS) algorithm for global optimization yields a sequence of points, each of which is uniformly distributed in the level set corresponding to its predecessor. This algorithm has the highly desirable property of solving a large class of global optimization problems using a number of iterations that increases at most linearly in the dimension of the problem. Unfortunately, PAS has remained of mostly theoretical interest due to the difficulty of generating, in each iteration, a point uniformly distributed in the improving feasible region. In this article, we derive a coupling equivalence between generating an approximately uniformly distributed point using Markov chain sampling, and generating an exactly uniformly distributed point with a certain probability. This result is used to characterize the complexity of a PAS-implementation as a function of (a) the number of iterations required by PAS to achieve a certain solution quality guarantee, and (b) the complexity of the sampling algorithm used. As an application, we use this equivalence to show that PAS, using the so-called Random ball walk Markov chain sampling method for generating nearly uniform points in a convex region, can be used to solve most convex programming problems in polynomial time.     

A new version of the ergodic method of Yu. V. Linnik in number theory

A new version of a known method of analytic number theory is developed. This version is demonstrated with a very simple model example — the problem on the asymptotically uniform distribution of integer points of a sphere with respect to a given modulus.This paper is a reworking of §5 of survey [6].Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 50, pp. 179–186, 1975.     

Uniform grid approximation of nonsmooth solutions with improved convergence for a singularly perturbed convection-diffusion equation with characteristic layers

A mixed boundary value problem for a singularly perturbed elliptic convection-diffusion equation with constant coefficients in a square domain is considered. Dirichlet conditions are specified on two sides orthogonal to the flow, and Neumann conditions are set on the other two sides. The right-hand side and the boundary functions are assumed to be sufficiently smooth, which ensures the required smoothness of the desired solution in the domain, except for neighborhoods of the corner points. Only zero-order compatibility conditions are assumed to hold at the corner points. The problem is solved numerically by applying an inhomogeneous monotone difference scheme on a rectangular piecewise uniform Shishkin mesh. The inhomogeneity of the scheme lies in that the approximating difference equations are not identical at different grid nodes but depend on the perturbation parameter. Under the assumptions made, the numerical solution is proved to converge ?-uniformly to the exact solution in a discrete uniform metric at an O(N ^?3/2ln² N) rate, where N is the number of grid nodes in each coordinate direction.     

Spherical basis functions and uniform distribution of points on spheres

The main purpose of the present paper is to employ spherical basis functions (SBFs) to study uniform distribution of points on spheres. We extend Weyl's criterion for uniform distribution of points on spheres to include a characterization in terms of an SBF. We show that every set of minimal energy points associated with an SBF is uniformly distributed on the spheres. We give an error estimate for numerical integration based on the minimal energy points. We also estimate the separation of the minimal energy points.