HERBRAND’s Fundamental Theorem in the Eyes of JEAN VAN HEIJENOORT

Using Heijenoort??s unpublished generalized rules of quantification, we discuss the proof of Herbrand??s Fundamental Theorem in the form of Heijenoort??s correction of Herbrand??s ??False Lemma?? and present a didactic example. Although we are mainly concerned with the inner structure of Herbrand??s Fundamental Theorem and the questions of its quality and its depth, we also discuss the outer questions of its historical context and why Bernays called it ??the central theorem of predicate logic?? and considered the form of its expression to be ??concise and felicitous??.     

ParNes: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

In this article, we propose an algorithm, nesta-lasso, for the lasso problem, i.e., an underdetermined linear least-squares problem with a 1-norm constraint on the solution. We prove under the assumption of the restricted isometry property (rip) and a sparsity condition on the solution, that nesta-lasso is guaranteed to be almost always locally linearly convergent. As in the case of the algorithm nesta, proposed by Becker, Bobin, and Candès, we rely on Nesterov’s accelerated proximal gradient method, which takes $O(\sqrt {1/\varepsilon })$ iterations to come within $\varepsilon > 0$ of the optimal value. We introduce a modification to Nesterov’s method that regularly updates the prox-center in a provably optimal manner. The aforementioned linear convergence is in part due to this modification. In the second part of this article, we attempt to solve the basis pursuit denoising (bpdn) problem (i.e., approximating the minimum 1-norm solution to an underdetermined least squares problem) by using nesta-lasso in conjunction with the Pareto root-finding method employed by van den Berg and Friedlander in their spgl1 solver. The resulting algorithm is called parnes. We provide numerical evidence to show that it is comparable to currently available solvers.     

LIM is not slim

In this paper LIM, a recently proposed impartial combinatorial ruleset, is analyzed. A formula to describe the $\mathcal G $ -values of LIM positions is given, by way of analyzing an equivalent combinatorial ruleset LIM’, closely related to the classical nim. Also, an enumeration of $\mathcal P $ -positions of LIM with $n$ stones, and its relation to the Ulam-Warburton cellular automaton, is presented.     

A new greedy algorithm for the quadratic assignment problem

The classical greedy algorithm for discrete optimization problems where the optimal solution is a maximal independent subset of a finite ground set of weighted elements, can be defined in two ways which are dual to each other. The Greedy-In where a solution is constructed from the empty set by adding the next best element, one at a time, until we reach infeasibility, and the Greedy-Out where starting from the ground set we delete the next worst element, one at a time, until feasibility is reached. It is known that while the former provides an approximation ratio for maximization problems, its worst case performance is not bounded for minimization problems, and vice-versa for the later. However the Greedy-Out algorithm requires an oracle for checking the existence of a maximal independent subset which for most discrete optimization problems is a difficult task. In this work we present a Greedy-Out algorithm for the quadratic assignment problem by providing a combinatorial characterization of its solutions.     

Markov Limid processes for representing and solving renewal problems

In this paper a new tool for simultaneous optimisation of decisions on multiple time scales is presented. The tool combines the dynamic properties of Markov decision processes with the flexible and compact state space representation of LImited Memory Influence Diagrams (Limids). A temporal version of Limids, TemLimids, is defined by adding time-related functions to utility nodes. As a result, expected discounted utility, as well as expected relative utility might be used as optimisation criteria in TemLimids. Optimisation proceeds as in ordinary Limids. A sequence of such TemLimids can be used to model a Markov Limid Process, where each TemLimid represents a macro action. Algorithms are presented to find optimal plans for a sequence of such macro actions. Use of algorithms is illustrated based on an extended version of an example from pig production originally used to introduce the Limid concept.     

Memetic algorithms and hyperheuristics applied to a multiobjectivised two-dimensional packing problem

Packing problems are np-hard problems with several practical applications. A variant of a 2d Packing Problem (2dpp) was proposed in the gecco 2008 competition session. In this paper, Memetic Algorithms (mas) and Hyperheuristics are applied to a multiobjectivised version of the 2dpp. Multiobjectivisation is the reformulation of a mono-objective problem into a multi-objective one. The main aim of multiobjectivising the 2dpp is to avoid stagnation in local optima. First generation mas refers to hybrid algorithms that combine a population-based global search with an individual learning process. A novel first generation ma is proposed, and an original multiobjectivisation method is applied to the 2dpp. In addition, with the aim of facilitating the application of such first generation mas from the point of view of the parameter setting, and of enabling their usage in parallel environments, a parallel hyperheuristic is also applied. Particularly, the method applied here is a hybrid approach which combines a parallel island-based model and a hyperheuristic. The main objective of this work is twofold. Firstly, to analyse the advantages and drawbacks of a set of first generation mas. Secondly, to attempt to avoid those drawbacks by applying a parallel hyperheuristic. Moreover, robustness and scalability analyses of the parallel scheme are included. Finally, we should note that our methods improve on the current best-known solutions for the tested instances of the 2dpp.     

The odd side of torsion geometry

We introduce and study a notion of ‘Sasaki with torsion structure’ (st ) as an odd-dimensional analogue of Kähler with torsion geometry (kt ). These are normal almost contact metric manifolds that admit a unique compatible connection with \( 3 \) -form torsion. Any odd-dimensional compact Lie group is shown to admit such a structure; in this case, the structure is left-invariant and has closed torsion form. We illustrate the relation between st structures and other generalisations of Sasaki geometry, and we explain how some standard constructions in Sasaki geometry can be adapted to this setting. In particular, we relate the st structure to a kt structure on the space of leaves and show that both the cylinder and the cone over an st manifold are kt , although only the cylinder behaves well with respect to closedness of the torsion form. Finally, we introduce a notion of ‘ \( G \) -moment map’. We provide criteria based on equivariant cohomology ensuring the existence of these maps and then apply them as a tool for reducing st structures.     

Factorization of Lipschitz functions and absolute convergence of Vilenkin-Fourier series

LetG be a Vilenkin group (i.e., an infinite, compact, metrizable, zero-dimensional Abelian group). Our main result is a factorization theorem for functions in the Lipschitz spaces \(\mathfrak{L}\mathfrak{i}\mathfrak{p}\) (α,p; G). As colloraries of this theorem, we obtain (i) an extension of a factorization theorem ofY. Uno; (ii) a convolution formula which says that \(\mathfrak{L}\mathfrak{i}\mathfrak{p} (\alpha , r; G) = \mathfrak{L}\mathfrak{i}\mathfrak{p} (\beta , l; G)*\mathfrak{L}\mathfrak{i}\mathfrak{p} (\alpha - \beta , r; G)\) for 0<β<α<∞ and 1≤r≤∞; and (iii) an analogue, valid for allG, of a classical theorem ofHardy andLittlewood. We also present several results on absolute convergence of Fourier series defined onG, extending a theorem ofC. W. Onneweer and four results ofN. Ja. Vilenkin andA. I. Rubinshtein. The fourVilenkin-Rubinshtein results are analogues of classical theorems due, respectively, toO. Szász, S. B. Bernshtein, A. Zygmund, andG. G. Lorentz.     

Generalized impartial games

A complete mathematical theory of NIM type games have been developed byBouton [1902],Sprague [1935/36] andGrundy [1939]. The NIM type games are a special class of combinatorial games, called the impartial games. “Impartial” means that, at any stage, the set of legal moves is independent of whose turn it is to move. The outcome of an impartial game is that the first player either wins or loses. The results ofBouton, Sprague andGrundy are now generalized to a wider class of games which allow tie-positions. This wider class of games are defined on digraphs. It is proved that the games defined on a given digraph are all impartial games (without tie-positions) iff the birthday function (also called the terminal distance function) exists on this digraph.     

RENS

This article introduces rens, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programs (MINLPs). It uses a sub-MINLP to explore the set of feasible roundings of an optimal solution $\bar{x}$ of a linear or nonlinear relaxation. The sub-MINLP is constructed by fixing integer variables $x_j$ with $\bar{x} _{j} \in \mathbb {Z}$ and bounding the remaining integer variables to $x_{j} \in \{ \lfloor \bar{x} _{j} \rfloor , \lceil \bar{x} _{j} \rceil \}$ . We describe two different applications of rens: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver. We use the former to compare different kinds of relaxations and the impact of cutting planes on the so-called roundability of the corresponding optimal solutions. We further utilize rens to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price framework scip. Finally, we study the impact of rens when it is applied as a primal heuristic inside scip. All experiments were performed on three publicly available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLP s, using solely software which is available in source code. It turns out that for these problem classes 60 to 70 % of the instances have roundable relaxation optima and that the success rate of rens does not depend on the percentage of fractional variables. Last but not least, rens applied as primal heuristic complements nicely with existing primal heuristics in scip.     

A mean field model for a class of garbage collection algorithms in flash-based solid state drives

Garbage collection (GC) algorithms play a key role in reducing the write amplification in flash-based solid state drives, where the write amplification affects the lifespan and speed of the drive. This paper introduces a mean field model to assess the write amplification and the distribution of the number of valid pages per block for a class $\mathcal {C}$ of GC algorithms. Apart from the Random GC algorithm, class $\mathcal {C}$ includes two novel GC algorithms: the $d$ -Choices GC algorithm, that selects $d$ blocks uniformly at random and erases the block containing the least number of valid pages among the $d$ selected blocks, and the Random++ GC algorithm, that repeatedly selects another block uniformly at random until it finds a block with a lower than average number of valid blocks. Using simulation experiments, we show that the proposed mean field model is highly accurate in predicting the write amplification (for drives with $N=50{,}000$ blocks). We further show that the $d$ -Choices GC algorithm has a write amplification close to that of the Greedy GC algorithm even for small $d$ values, e.g., $d = 10$ , and offers a more attractive trade-off between its simplicity and its performance than the Windowed GC algorithm introduced and analyzed in earlier studies. The Random++ algorithm is shown to be less effective as it is even inferior to the FIFO algorithm when the number of pages $b$ per block is large (e.g., for $b \ge 64$ ).     

Parallel stochastic gradient algorithms for large-scale matrix completion

This paper develops Jellyfish, an algorithm for solving data-processing problems with matrix-valued decision variables regularized to have low rank. Particular examples of problems solvable by Jellyfish include matrix completion problems and least-squares problems regularized by the nuclear norm or $\gamma _2$ -norm. Jellyfish implements a projected incremental gradient method with a biased, random ordering of the increments. This biased ordering allows for a parallel implementation that admits a speed-up nearly proportional to the number of processors. On large-scale matrix completion tasks, Jellyfish is orders of magnitude more efficient than existing codes. For example, on the Netflix Prize data set, prior art computes rating predictions in approximately 4 h, while Jellyfish solves the same problem in under 3 min on a 12 core workstation.     

Projective curves with maximal regularity and applications to syzygies and surfaces

We first show that the union of a projective curve with one of its extremal secant lines satisfies the linear general position principle for hyperplane sections. We use this to give an improved approximation of the Betti numbers of curves ${{\mathcal C}\subset \mathbb P^r_K}$ of maximal regularity with ${{\rm deg}\, {\mathcal C}\leq 2r -3}$ . In particular we specify the number and degrees of generators of the vanishing ideal of such curves. We apply these results to study surfaces ${X \subset \mathbb P^r_K}$ whose generic hyperplane section is a curve of maximal regularity. We first give a criterion for ??an early descent of the Hartshorne-Rao function?? of such surfaces. We use this criterion to give a lower bound on the degree for a class of these surfaces. Then, we study surfaces ${X \subset\mathbb P^r_K}$ for which ${h^1(\mathbb P^r_K, {\mathcal I}_X(1))}$ takes a value close to the possible maximum deg X ? r +?1. We give a lower bound on the degree of such surfaces. We illustrate our results by a number of examples, computed by means of Singular, which show a rich variety of occuring phenomena.     

Geometric Generalisations of shake and rattle

A geometric analysis of the shake and rattle methods for constrained Hamiltonian problems is carried out. The study reveals the underlying differential geometric foundation of the two methods, and the exact relation between them. In addition, the geometric insight naturally generalises shake and rattle to allow for a strictly larger class of constrained Hamiltonian systems than in the classical setting. In order for shake and rattle to be well defined, two basic assumptions are needed. First, a nondegeneracy assumption, which is a condition on the Hamiltonian, i.e., on the dynamics of the system. Second, a coisotropy assumption, which is a condition on the geometry of the constrained phase space. Non-trivial examples of systems fulfilling, and failing to fulfill, these assumptions are given.     

Computational experience with advanced implementation of decomposition algorithms for linear programming

This paper reports computational experience with the codesDecompsx andLift which are built on IBM's MPSX/370 LP software for large-scale structured programs.Decompsx is an implementation of the Dantzig-Wolfe decomposition algorithm for block-angular LP's.Lift is an implementation of a nested decomposition algorithm for staircase and block-triangular LP's. A diverse collection of test problems drawn from real applications is used to test these codes, including multinational energy models and global economic models.     

A variance-based method to rank input variables of the Mesh Adaptive Direct Search algorithm

The Mesh Adaptive Direct Search algorithm (Mads) algorithm is designed for nonsmooth blackbox optimization problems in which the evaluation of the functions defining the problems are expensive to compute. The Mads algorithm is not designed for problems with a large number of variables. The present paper uses a statistical tool based on variance decomposition to rank the relative importance of the variables. This statistical method is then coupled with the Mads algorithm so that the optimization is performed either in the entire space of variables or in subspaces associated with statistically important variables. The resulting algorithm is called Stats-Mads and is tested on bound constrained test problems having up to 500 variables. The numerical results show a significant improvement in the objective function value after a fixed budget of function evaluations.     

The weighted Grammar constraint

We introduce the WeightedGrammar constraint and propose propagation algorithms based on the CYK parser and the Earley parser. We show that the traces of these algorithms can be encoded as a weighted negation normal form (WNNF), a generalization of NNF that allows nodes to carry weights. Based on this connection, we prove the correctness and complexity of these algorithms. Specifically, these algorithms enforce domain consistency on the WeightedGrammar constraint in time O(n ³). Further, we propose that the WNNF constraint can be decomposed into a set of primitive arithmetic constraint without hindering propagation.     

О скорсти сходимости рядов фурье двумерных функций ограниченной вариации

S. A. Telyakovskii [12] generalized a theorem of Bojani? [2] on the quantitative version of the Dirichlet-Jordan test, well-known in the classical Fourier analysis. Our goal is to extend Telyakovskii’s theorem from single to double Fourier series of functions in two variables that are of bounded variation in the sense of Hardy and Krause. The related theorems of Hardy [5] and Móricz [7] for such functions are corollaries of our Theorem proved in this paper.     

Clonal selection: an immunological algorithm for global optimization over continuous spaces

In this research paper we present an immunological algorithm (IA) to solve global numerical optimization problems for high-dimensional instances. Such optimization problems are a crucial component for many real-world applications. We designed two versions of the IA: the first based on binary-code representation and the second based on real values, called opt-IMMALG01 and opt-IMMALG, respectively. A large set of experiments is presented to evaluate the effectiveness of the two proposed versions of IA. Both opt-IMMALG01 and opt-IMMALG were extensively compared against several nature inspired methodologies including a set of Differential Evolution algorithms whose performance is known to be superior to many other bio-inspired and deterministic algorithms on the same test bed. Also hybrid and deterministic global search algorithms (e.g., DIRECT, LeGO, PSwarm) are compared with both IA versions, for a total 39 optimization algorithms.The results suggest that the proposed immunological algorithm is effective, in terms of accuracy, and capable of solving large-scale instances for well-known benchmarks. Experimental results also indicate that both IA versions are comparable, and often outperform, the state-of-the-art optimization algorithms.