A parameterized proximal point algorithm for separable convex optimization

In this paper, we develop a parameterized proximal point algorithm (P-PPA) for solving a class of separable convex programming problems subject to linear and convex constraints. The proposed algorithm is provable to be globally convergent with a worst-case O(1 / t) convergence rate, where t denotes the iteration number. By properly choosing the algorithm parameters, numerical experiments on solving a sparse optimization problem arising from statistical learning show that our P-PPA could perform significantly better than other state-of-the-art methods, such as the alternating direction method of multipliers and the relaxed proximal point algorithm.     

Minimizing finite sums with the stochastic average gradient

We analyze the stochastic average gradient (SAG) method for optimizing the sum of a finite number of smooth convex functions. Like stochastic gradient (SG) methods, the SAG method’s iteration cost is independent of the number of terms in the sum. However, by incorporating a memory of previous gradient values the SAG method achieves a faster convergence rate than black-box SG methods. The convergence rate is improved from \(O(1/\sqrt{k})\) to O(1 / k) in general, and when the sum is strongly-convex the convergence rate is improved from the sub-linear O(1 / k) to a linear convergence rate of the form \(O(\rho ^k)\) for \(\rho < 1\). Further, in many cases the convergence rate of the new method is also faster than black-box deterministic gradient methods, in terms of the number of gradient evaluations. This extends our earlier work Le Roux et al. (Adv Neural Inf Process Syst, 2012), which only lead to a faster rate for well-conditioned strongly-convex problems. Numerical experiments indicate that the new algorithm often dramatically outperforms existing SG and deterministic gradient methods, and that the performance may be further improved through the use of non-uniform sampling strategies.     

<Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript>-Approximation of the Integrated Density of States for Schrödinger Operators with Finite Local Complexity

We study spectral properties of Schrödinger operators on \({\mathbb R^d}\) . The electromagnetic potential is assumed to be determined locally by a colouring of the lattice points in \({\mathbb Z^d}\) , with the property that frequencies of finite patterns are well defined. We prove that the integrated density of states (spectral distribution function) is approximated by its finite volume analogues, i.e. the normalised eigenvalue counting functions. The convergence holds in the space L ^p (I) where I is any finite energy interval and 1 ≤ p < ∞ is arbitrary.     

On power deformations of univalent functions

For an analytic function f (z) on the unit disk |z| < 1 with f (0) = f′(0) ? 1 = 0 and f (z) ≠ 0, 0 < |z| < 1, we consider the power deformation f _c (z) = z(f (z)/z) ^c for a complex number c. We determine those values c for which the operator \({f \mapsto f_c}\) maps a specified class of univalent functions into the class of univalent functions. A little surprisingly, we will see that the set is described by the variability region of the quantity zf′(z)/ f (z), |z| < 1, for most of the classes that we consider in the present paper. As an unexpected by-product, we show boundedness of strongly spirallike functions.     

Dyson’s partition ranks and their multiplicative extensions

We study the Dyson rank function N(r, 3; n), the number of partitions of n with rank \(\equiv r \pmod 3\). We investigate the convexity of these functions. We extend N(r, 3; n) multiplicatively to the set of partitions, and we determine the maximum value when taken over all partitions of size n.     

Prime and composite integers close to powers of a number

We prove that, for any real numbers ξ ≠ 0 and ν, the sequence of integer parts [ξ2 ⁿ  + ν], n = 0, 1, 2, . . . , contains infinitely many composite numbers. Moreover, if the number ξ is irrational, then the above sequence contains infinitely many elements divisible by 2 or 3. The same holds for the sequence [ξ( ? 2) ⁿ  + ν _n ], n = 0, 1, 2, . . . , where ν ₀, ν ₁, ν ₂, . . . all lie in a half open real interval of length 1/3. For this, we show that if a sequence of integers x ₁, x ₂, x ₃, . . . satisfies the recurrence relation x _n+d  = cx _n  + F(x _n+1, . . . , x _n+d-1) for each n  ≥  1, where c ≠ 0 is an integer, \({F(z_1,\dots,z_{d-1}) \in \mathbb {Z}[z_1,\dots,z_{d-1}],}\) and lim _{n→ ∞}|x _n | = ∞, then the number |x _n | is composite for infinitely many positive integers n. The proofs involve techniques from number theory, linear algebra, combinatorics on words and some kind of symbolic computation modulo 3.     

A note on a mixed routing and scheduling problem on a grid graph

We consider a particular case of the Fleet Quickest Routing Problem (FQRP) on a grid graph of m × n nodes that are placed in m levels and n columns. Starting nodes are placed at the first (bottom) level, and nodes of arrival are placed at the mth level. A feasible solution of FQRP consists in n Manhattan paths, one for each vehicle, such that capacity constraints are respected. We establish m*, i.e. the number of levels that ensures the existence of a solution to FQRP in any possible permutation of n destinations. In particular, m* is the minimum number of levels sufficient to solve any instance of FQRP involving n vehicles, when they move in the ways that the literature has until now assumed. Existing algorithms give solutions that require, for some values of n, more levels than m*. For this reason, we provide algorithm CaR, which gives a solution in a graph m* × n, as a minor contribution.     

Conditional equations for quadratic functions

We consider quadratic functions f that satisfy the additional equation y² f(x) =  x² f(y) for the pairs \({ (x,y) \in \mathbb{R}^2}\) that fulfill the condition P(x, y) =  0 for some fixed polynomial P of two variables. If P(x, y) =  ax +  by +  c with \({ a , b , c \in \mathbb{R}}\) and \({(a^2 + b^2)c \neq 0}\) or P(x,y) =  x ⁿ ? y with a natural number \({n \geq 2}\), we prove that f(x) =  f(1) x² for all \({x \in \mathbb{R}}\). Some related problems, admitting quadratic functions generated by derivations, are considered as well.     

Acceleration of convergence of general linear sequences by the Shanks transformation

The Shanks transformation is a powerful nonlinear extrapolation method that is used to accelerate the convergence of slowly converging, and even diverging, sequences {A _n }. It generates a two-dimensional array of approximations \({A^{(j)}_n}\) to the limit or anti-limit of {A _n } defined as solutions of the linear systems

$A_l=A^{(j)}_n +\sum^{n}_{k=1}\bar{\beta}_k(\Delta A_{l+k-1}),\ \ j\leq l\leq j+n,$

where \({\bar{\beta}_{k}}\) are additional unknowns. In this work, we study the convergence and stability properties of \({A^{(j)}_n}\) , as j → ∞ with n fixed, derived from general linear sequences {A _n }, where \({{A_n \sim A+\sum^{m}_{k=1}\zeta_k^n\sum^\infty_{i=0} \beta_{ki}n^{\gamma_k-i}}}\) as n → ∞, where ζ _k  ≠ 1 are distinct and |ζ ₁| = ... = |ζ _m | = θ, and γ _k  ≠ 0, 1, 2, . . .. Here A is the limit or the anti-limit of {A _n }. Such sequences arise, for example, as partial sums of Fourier series of functions that have finite jump discontinuities and/or algebraic branch singularities. We show that definitive results are obtained with those values of n for which the integer programming problems

$\begin{array}{ll}{\quad\quad\quad\quad\max\limits_{s_1,\ldots,s_m}\sum\limits_{k=1}^{m}\left[(\Re\gamma_k)s_k-s_k(s_k-1)\right],}\\ {{\rm subject\,to}\,\, s_1\geq0,\ldots,s_m\geq0\quad{\rm and}\quad \sum\limits_{k=1}^{m} s_k = n,}\end{array}$

have unique (integer) solutions for s ₁, . . . , s _m . A special case of our convergence result concerns the situation in which \({{\Re\gamma_1=\cdots=\Re\gamma_m=\alpha}}\) and n = mν with ν = 1, 2, . . . , for which the integer programming problems above have unique solutions, and it reads \({A^{(j)}_n-A=O(\theta^j\,j^{\alpha-2\nu})}\) as j → ∞. When compared with A _j ? A = O(θ ^j j ^α ) as j → ∞, this result shows that the Shanks transformation is a true convergence acceleration method for the sequences considered. In addition, we show that it is stable for the case being studied, and we also quantify its stability properties. The results of this work are the first ones pertaining to the Shanks transformation on general linear sequences with m > 1.

     

Approximation of almost Sahoo–Riedel’s points by Sahoo–Riedel’s points

In this paper, we present an extention of Hyers–Ulam stability of Sahoo–Riedel’s points for real-valued differentiable functions on [a, b] and then we obtain stability results of Flett’s points for functions in the class of continuously differentiable functions on [a, b] with f′(a) = f′(b).     

Time-dependent analysis of an <Emphasis Type="Italic">M</Emphasis> / <Emphasis Type="Italic">M</Emphasis> / <Emphasis Type="Italic">c</Emphasis> preemptive priority system with two priority classes

We analyze the time-dependent behavior of an M / M / c priority queue having two customer classes, class-dependent service rates, and preemptive priority between classes. More particularly, we develop a method that determines the Laplace transforms of the transition functions when the system is initially empty. The Laplace transforms corresponding to states with at least c high-priority customers are expressed explicitly in terms of the Laplace transforms corresponding to states with at most \(c - 1\) high-priority customers. We then show how to compute the remaining Laplace transforms recursively, by making use of a variant of Ramaswami’s formula from the theory of M / G / 1-type Markov processes. While the primary focus of our work is on deriving Laplace transforms of transition functions, analogous results can be derived for the stationary distribution; these results seem to yield the most explicit expressions known to date.     

Extendability of Contractible Configurations for Nowhere-Zero Flows and Modulo Orientations

Let H be a connected graph and G be a supergraph of H. It is trivial that for any k-flow (D, f) of G, the restriction of (D, f) on the edge subset E(G / H) is a k-flow of the contracted graph G / H. However, the other direction of the question is neither trivial nor straightforward at all: for any k-flow \((D',f')\) of the contracted graph G / H, whether or not the supergraph G admits a k-flow (D, f) that is consistent with \((D',f')\) in the edge subset E(G / H). In this paper, we will investigate contractible configurations and their extendability for integer flows, group flows, and modulo orientations. We show that no integer flow contractible graphs are extension consistent while some group flow contractible graphs are also extension consistent. We also show that every modulo \((2k+1)\)-orientation contractible configuration is also extension consistent and there are no modulo (2k)-orientation contractible graphs.     

Approximate identities on some homogeneous Banach spaces

We study convergence of approximate identities on some complete semi-normed or normed spaces of locally L ^p functions where translations are isometries, namely Marcinkiewicz spaces \({\mathcal{M}^{p}}\) and Stepanoff spaces \({\mathcal{S}^p}\), 1 ≤ p < ∞, as well as others where translations are not isometric but bounded (the bounded p-mean spaces M ^p ) or even unbounded (\({M^{p}_{0}}\)). We construct a function f that belongs to these spaces and has the property that all approximate identities \({\phi_\varepsilon * f}\) converge to f pointwise but they never converge in norm.     

Fast separation for the three-index assignment problem

A critical step in a cutting plane algorithm is separation, i.e., establishing whether a given vector x violates an inequality belonging to a specific class. It is customary to express the time complexity of a separation algorithm in the number of variables n. Here, we argue that a separation algorithm may instead process the vector containing the positive components of x,  denoted as supp(x),  which offers a more compact representation, especially if x is sparse; we also propose to express the time complexity in terms of |supp(x)|. Although several well-known separation algorithms exploit the sparsity of x,  we revisit this idea in order to take sparsity explicitly into account in the time-complexity of separation and also design faster algorithms. We apply this approach to two classes of facet-defining inequalities for the three-index assignment problem, and obtain separation algorithms whose time complexity is linear in |supp(x)| instead of n. We indicate that this can be generalized to the axial k-index assignment problem and we show empirically how the separation algorithms exploiting sparsity improve on existing ones by running them on the largest instances reported in the literature.     

A partially isochronous splitting algorithm for three-block separable convex minimization problems

During the last decade, the state-of-the-art alternating direction method of multipliers (ADMM) has successfully been used to solve many two-block separable convex minimization problems arising from several applied areas such as signal/image processing and statistical and machine learning. It however remains an interesting problem of how to implement ADMM to three-block separable convex minimization problems as required by the situation where many objective functions in the above-mentioned areas are actually more conveniently decomposed to the sum of three convex functions, due also to the observation that the straightforward extension of ADMM from the two-block case to the three-block case is apparently not convergent. In this paper, we shall introduce a new algorithm that is called a partially isochronous splitting algorithm (PISA) in order to implement ADMM for the three-block separable model. The main idea of our algorithm is to incorporate only one proximal term into the last subproblem of the extended ADMM so that the resulting algorithm maximally inherits the promising properties of ADMM. A remarkable superiority over the extended ADMM is that we can simultaneously solve two of the subproblems, thereby taking advantages of the separable structure and parallel architectures. Theoretically, we will establish the global convergence of our algorithm under standard conditions, and also the O(1/t) rate of convergence in both ergodic and nonergodic senses, where t is the iteration counter. The computational competitiveness of our algorithm is shown by numerical experiments on an application to the well-tested robust principal component analysis model.     

Cardinality of the Ellis semigroup on compact metric countable spaces

Let E(X, f) be the Ellis semigroup of a dynamical system (X, f) where X is a compact metric space. We analyze the cardinality of E(X, f) for a compact countable metric space X. A characterization when E(X, f) and \(E(X,f)^* = E(X,f) \setminus \{ f^n : n \in \mathbb {N}\}\) are both finite is given. We show that if the collection of all periods of the periodic points of (X, f) is infinite, then E(X, f) has size \(2^{\aleph _0}\). It is also proved that if (X, f) has a point with a dense orbit and all elements of E(X, f) are continuous, then \(|E(X,f)| \le |X|\). For dynamical systems of the form \((\omega ^2 +1,f)\), we show that if there is a point with a dense orbit, then all elements of \(E(\omega ^2+1,f)\) are continuous functions. We present several examples of dynamical systems which have a point with a dense orbit. Such systems provide examples where \(E(\omega ^2+1,f)\) and \(\omega ^2+1\) are homeomorphic but not algebraically homeomorphic, where \(\omega ^2+1\) is taken with the usual ordinal addition as semigroup operation.     

Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization

Recently, the alternating direction method of multipliers (ADMM) has found many efficient applications in various areas; and it has been shown that the convergence is not guaranteed when it is directly extended to the multiple-block case of separable convex minimization problems where there are m ≥ 3 functions without coupled variables in the objective. This fact has given great impetus to investigate various conditions on both the model and the algorithm’s parameter that can ensure the convergence of the direct extension of ADMM (abbreviated as “e-ADMM”). Despite some results under very strong conditions (e.g., at least (m ? 1) functions should be strongly convex) that are applicable to the generic case with a general m, some others concentrate on the special case of m = 3 under the relatively milder condition that only one function is assumed to be strongly convex. We focus on extending the convergence analysis from the case of m = 3 to the more general case of m ≥ 3. That is, we show the convergence of e-ADMM for the case of m ≥ 3 with the assumption of only (m ? 2) functions being strongly convex; and establish its convergence rates in different scenarios such as the worst-case convergence rates measured by iteration complexity and the globally linear convergence rate under stronger assumptions. Thus the convergence of e-ADMM for the general case of m ≥ 4 is proved; this result seems to be still unknown even though it is intuitive given the known result of the case of m = 3. Even for the special case of m = 3, our convergence results turn out to be more general than the existing results that are derived specifically for the case of m = 3.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

Special properties of Hurwitz series rings

In this paper, we study some properties of the Hurwitz series ring HR (resp. Hurwitz polynomial ring hR), such as the flatness or the faithful flatness of HR / (f) (resp. hR / (f)), the strongly Hopfian property and the radical property of HR (resp. hR). We give some sufficient and necessary conditions for HR / (f) (resp. hR / (f)) to be flat or faithful flat. We also prove that the strongly Hopfian property transfer between R and HR (resp. hR), and some radicals of HR can be determined in terms of those of R, in case R satisfies some additional conditions.     

On solvability of f(p(x)) = q(f(x)) for given real functions p,q

We investigate the solvability of functional equations f(p(x)) =  q(f(x)) for given functions p and q which are partially or completely defined on the set of all real numbers. For these investigations, we use methods for constructions of homomorphisms of mono-unary algebras. We can present a simple characterisation of solvability of the above equation in the case that p, q are strictly increasing and continuous functions. It gives, on the one hand, a practical use for a class of functional equations. On the other hand, it is a contribution to questions on topological conjugacy of monotonous real functions.