A note on submodular function minimization by Chubanov’s LP algorithm

Recently Dadush et al. (2017) have devised a polynomial submodular function minimization (SFM) algorithm based on their LP algorithm. In the present note we also show a weakly polynomial algorithm for SFM based on the recently developed linear programming feasibility algorithm of Chubanov (2017) to stimulate further research on SFM.     

Optimal search efficiency of Barker’s algorithm with an exponential fitness function

Markov Chain Monte Carlo (MCMC) methods may be employed to search for a probability distribution over a bounded space of function arguments to estimate which argument(s) optimize(s) an objective function. This search-based optimization requires sampling the suitability, or fitness, of arguments in the search space. When the objective function or the fitness of arguments vary with time, significant exploration of the search space is required. Search efficiency then becomes a more relevant measure of the usefulness of an MCMC method than traditional measures such as convergence speed to the stationary distribution and asymptotic variance of stationary distribution estimates. Search efficiency refers to how quickly prior information about the search space is traded-off for search effort savings. Optimal search efficiency occurs when the entropy of the probability distribution over the space during search is maximized. Whereas the Metropolis case of the Hastings MCMC algorithm with fixed candidate generation is optimal with respect to asymptotic variance of stationary distribution estimates, this paper proves that Barker’s case is optimal with respect to search efficiency if the fitness of the arguments in the search space is characterized by an exponential function. The latter instance of optimality is beneficial for time-varying optimization that is also model-independent.     

Robinson’s implicit function theorem and its extensions

S. M. Robinson published in 1980 a powerful theorem about solutions to certain “generalized equations” corresponding to parameterized variational inequalities which could represent the first-order optimality conditions in nonlinear programming, in particular. In fact, his result covered much of the classical implicit function theorem, if not quite all, but went far beyond that in ideas and format. Here, Robinson’s theorem is viewed from the perspective of more recent developments in variational analysis as well as some lesser-known results in the implicit function literature on equations, prior to the advent of generalized equations. Extensions are presented which fully cover such results, translating them at the same time to generalized equations broader than variational inequalities. Robinson’s notion of first-order approximations in the absence of differentiability is utilized in part, but even looser forms of approximation are shown to furnish significant information about solutions.     

Pillai’s generalized function

The distribution of values of Pillai’s function over the ring of Gauss integers $ \mathbb{Z}\left[ i \right] $ is studied. The asymptotic formulas for the summators $ {\varSigma_{{N\left( \alpha \right)\leq x}}}\frac{{g\left( \alpha \right)}}{{{N^{\alpha }}\left( \alpha \right)}} $ , where $ a\in \mathbb{R} $ , are found.     

Absolutely monotonic functions related to Euler’s gamma function and Barnes’ double and triple gamma function

It is shown that the remainders in asymptotic expansions of the logarithm of Barnes double and triple gamma function and Euler’s gamma function are Laplace transformations of positive multiples of absolutely monotonic functions. Applications concerning positivity of sums involving Bernoulli numbers are given.     

Absolutely monotonic functions related to Euler’s gamma function and Barnes’ double and triple gamma function

It is shown that the remainders in asymptotic expansions of the logarithm of Barnes double and triple gamma function and Euler’s gamma function are Laplace transformations of positive multiples of absolutely monotonic functions. Applications concerning positivity of sums involving Bernoulli numbers are given.     

The Buchstab’s function and the operational Tau Method

In this article we discuss some aspects of operational Tau Method on delay differential equations and then we apply this method on the differential delay equation defined byw(u) = 1/u for 1 ≤u ≤ 2 and(uw(u))′ = w(u-1) foru ≥ 2, which was introduced by Buchstab. As Khajah et al.[l] applied the Recursive Tau Method on this problem, they had to apply that Method under theMathematica software to get reasonable accuracy. We present very good results obtained just by applying the Operational Tau Method using a Fortran code. The results show that we can obtain as much accuracy as is allowed by the Fortran compiler and the machine-limitations. The easy applications and reported results concerning the Operational Tau are again confirming the numerical capabilities of this Method to handle problems in different applications.     

The two-time Green’s function and the diagram technique

Based on constructing the equations of motion for the two-time Green’s functions, we discuss calculating the dynamical spin susceptibility and correlation functions in the Heisenberg model. Using a Mori-type projection, we derive an exact Dyson equation with the self-energy operator in the form of a multiparticle Green’s function. Calculating the self-energy operator in the mode-coupling approximation in the ferromagnetic phase, we reproduce the results of the temperature diagram technique, including the correct formula for low-temperature magnetization. We also consider calculating the spin fluctuation spectrum in the paramagnetic phase in the framework of the method of equations of motion for the relaxation function.     

One modification of Gomory’s algorithm

The problem of constructing optimum cuts in the Gomory method for integer linear programming (ILP) problems is considered. Algorithms for finding cuts are described, and their complexity is assessed. The modified Gomory algorithm is compared to a standard Gomory algorithm.     

Complex Euler’s groups and values of Euler’s function at complex integer Gauss points

The complex Euler group is defined associating to an integer complex number z the multiplicative group of the complex integers residues modulo z, relatively prime to z. This group is calculated for z=(3+0i) ⁿ : it is isomorphic to the product of three cyclic group or orders (8, 3 ⁿ⁻¹ and 3 ⁿ⁻¹).     

Barvinok’s naive algorithm in Distance Geometry

In 1997, A. Barvinok gave a probabilistic algorithm to derive a near-feasible solution of a quadratically (equation) constrained problem from its semidefinite relaxation. We generalize this algorithm to handle matrix variables instead of vectors, and to handle two-sided inequalities instead of equations. We derive a heuristic for the distance geometry problem, and showcase its computational performance on a set of instances related to protein conformation.     

Modification of Karmarkar’s projective scaling algorithm

This paper presents a new conversion technique of the standard linear programming problem into a homogenous form desired for the Karmarkar’s algorithm, where we employed the primal–dual method. The new converted linear programming problem provides initial basic feasible solution, simplex structure, and homogenous matrix. Apart from the transformation, Hooker’s method of projected direction is employed in the Karmarkar’s algorithm and the modified algorithm is presented. The modified algorithm has a faster convergence with a suitable choice of step size.     

Dougall’s $$_5F_4$$ sum and the WZ algorithm

We show how to prove the examples of a paper by Chu and Zhang using the WZ algorithm.     

Zhang’s Conjecture and the Effective Bogomolov Conjecture over function fields

We prove the Effective Bogomolov Conjecture, and so the Bogomolov Conjecture, over a function field of characteristic 0 by proving Zhang’s Conjecture about certain invariants of metrized graphs. In the function field case, these conjectures were previously known to be true only for curves of good reduction, for curves of genus at most 4 and a few other special cases. We also either verify or improve the previous results. We relate the invariants involved in Zhang’s Conjecture to the tau constant of metrized graphs. Then we use and extend our previous results on the tau constant. By proving another Conjecture of Zhang, we obtain a new proof of the slope inequality for Faltings heights on moduli space of curves.     

Compactness and Vitali’s compactness criterion in vector-valued F-seminormed function spaces

Results of compactness for vector-valued F-seminormed function spaces and a general Vitali’s compactness criterion under the W-property are exhibited.

     

Breaking tweakable enciphering schemes using Simon’s algorithm

We show the applicability of Simon’s period finding quantum algorithm to the cryptanalysis of several tweakable enciphering schemes (TESs), namely, CMC, EME, XCB, TET and FAST. For all of the five TESs, we show distinguishing attacks, while for XCB, TET and FAST, the attacks reveal portions of the secret keys

     

A constraint-reduced variant of Mehrotra’s predictor-corrector algorithm

Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm²)\mathcal{O}(nm^{2}) operations per iteration. When n≫m it is often the case that at each iteration most of the constraints are not very relevant for the construction of a good update and could be ignored to achieve computational savings. This idea was considered in the 1990s by Dantzig and Ye, Tone, Kaliski and Ye, den Hertog et al. and others. More recently, Tits et al. proposed a simple “constraint-reduction” scheme and proved global and local quadratic convergence for a dual-feasible primal-dual affine-scaling method modified according to that scheme. In the present work, similar convergence results are proved for a dual-feasible constraint-reduced variant of Mehrotra’s predictor-corrector algorithm, under less restrictive nondegeneracy assumptions. These stronger results extend to primal-dual affine scaling as a limiting case. Promising numerical results are reported.