Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem

M-convex functions, introduced by Murota (Adv. Math. 124 (1996) 272; Math. Prog. 83 (1998) 313), enjoy various desirable properties as “discrete convex functions.” In this paper, we propose two new polynomial-time scaling algorithms for the minimization of an M-convex function. Both algorithms apply a scaling technique to a greedy algorithm for M-convex function minimization, and run as fast as the previous minimization algorithms. We also specialize our scaling algorithms for the resource allocation problem which is a special case of M-convex function minimization.     

A capacity scaling algorithm for M-convex submodular flow

This paper presents a faster algorithm for the M-convex submodular flow problem, which is a generalization of the minimum-cost flow problem with an M-convex cost function for the flow-boundary, where an M-convex function is a nonlinear nonseparable discrete convex function on integer points. The algorithm extends the capacity scaling approach for the submodular flow problem by Fleischer, Iwata and McCormick (2002) with the aid of a novel technique of changing the potential by solving maximum submodular flow problems.Mathematics Subject Classification (1991): 90C27A preliminary version of this paper has appeared in Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization (IPCO X), LNCS 3064, Springer-Verlag, 2004, pp. 352–367.     

Proximity theorems of discrete convex functions

A proximity theorem is a statement that, given an optimization problem and its relaxation, an optimal solution to the original problem exists in a certain neighborhood of a solution to the relaxation. Proximity theorems have been used successfully, for example, in designing efficient algorithms for discrete resource allocation problems. After reviewing the recent results for L-convex and M-convex functions, this paper establishes proximity theorems for larger classes of discrete convex functions, L₂-convex functions and M₂-convex functions, that are relevant to the polymatroid intersection problem and the submodular flow problem.Mathematics Subject Classification (2000): 90C27, 05B35     

Induction of M-convex functions by linking systems

Induction (or transformation) by bipartite graphs is one of the most important operations on matroids, and it is well known that the induction of a matroid by a bipartite graph is again a matroid. As an abstract form of this fact, the induction of a matroid by a linking system is known to be a matroid.M-convex functions are quantitative extensions of matroidal structures, and they are known as discrete convex functions. As with matroids, it is known that the induction of an M-convex function by networks generates an M-convex function. As an abstract form of this fact, this paper shows that the induction of an M-convex function by linking systems generates an M-convex function. Furthermore, we show that this result also holds for M-convex functions on constant-parity jump systems. Previously known operations such as aggregation, splitting, and induction by networks can be understood as special cases of this construction.     

Notes on L-/M-convex functions and the separation theorems

The concepts of L-convex function and M-convex function have recently been introduced by Murota as generalizations of submodular function and base polyhedron, respectively, and discrete separation theorems are established for L-convex/concave functions and for M-convex/concave functions as generalizations of Frank’s discrete separation theorem for submodular/supermodular set functions and Edmonds’ matroid intersection theorem. This paper shows the equivalence between Murota’s L-convex functions and Favati and Tardella’s submodular integrally convex functions, and also gives alternative proofs of the separation theorems that provide a geometric insight by relating them to the ordinary separation theorem in convex analysis. Received: November 27, 1997 / Accepted: December 16, 1999?Published online May 12, 2000     

Conjugacy relationship between M-convex and L-convex functions in continuous variables

By extracting combinatorial structures in well-solved nonlinear combinatorial optimization problems, Murota (1996,1998) introduced the concepts of M-convexity and L-convexity to functions defined over the integer lattice. Recently, Murota–Shioura (2000, 2001) extended these concepts to polyhedral convex functions and quadratic functions in continuous variables. In this paper, we consider a further extension to more general convex functions defined over the real space, and provide a proof for the conjugacy relationship between general M-convex and L-convex functions.Mathematics Subject Classification (1991): 90C10, 90C25, 90C27, 90C35This work is supported by Grant-in-Aid of the Ministry of Education, Culture, Sports, Science and Technology of Japan     

Cone superadditivity of discrete convex functions

A function f is said to be cone superadditive if there exists a partition of R ⁿ into a family of polyhedral convex cones such that f(z?+?x) + f(z?+?y) ≤ f(z) + f(z?+?x?+?y) holds whenever x and y belong to the same cone in the family. This concept is useful in nonlinear integer programming in that, if the objective function is cone superadditive, the global minimality can be characterized by local optimality criterion involving Hilbert bases. This paper shows cone superadditivity of L-convex and M-convex functions with respect to conic partitions that are independent of particular functions. L-convex and M-convex functions in discrete variables (integer vectors) as well as in continuous variables (real vectors) are considered.     

Extension of M-Convexity and L-Convexity to Polyhedral Convex Functions

The concepts of M-convex and L-convex functions were proposed by Murota in 1996 as two mutually conjugate classes of discrete functions over integer lattice points. M/L-convex functions are deeply connected with the well-solvability in nonlinear combinatorial optimization with integer variables. In this paper, we extend the concept of M-convexity and L-convexity to polyhedral convex functions, aiming at clarifying the well-behaved structure in well-solved nonlinear combinatorial optimization problems in real variables. The extended M/L-convexity often appears in nonlinear combinatorial optimization problems with piecewise-linear convex cost. We investigate the structure of polyhedral M-convex and L-convex functions from the dual viewpoint of analysis and combinatorics and provide some properties and characterizations. It is also shown that polyhedral M/L-convex functions have nice conjugacy relationships.     

Approximation of a function of two variables by a product of functions of one variable on a given domain

We are concerned with the problem of uniform approximation of a continuous function of two variables by a product of continuous functions of one variable on some domain D. This problem have been examined so far only on a rectangular domain D = U × V, where U and V are compact sets. An algorithm to give a solution of this problem in the discrete case is available. We put forward an algorithm which in certain cases allows one to construct an approximate solution of the problem on a given domain (not necessarily rectangular). This approximate solution is built in the form of interpolating natural splines, which in turn are constructed by means of discrete approximation. Depending on the degree of the splines, the problem can be solved in classes of functions with appropriate degree of smoothness.     

An algorithm for the estimation of a regression function by continuous piecewise linear functions

The problem of the estimation of a regression function by continuous piecewise linear functions is formulated as a nonconvex, nonsmooth optimization problem. Estimates are defined by minimization of the empirical L ₂ risk over a class of functions, which are defined as maxima of minima of linear functions. An algorithm for finding continuous piecewise linear functions is presented. We observe that the objective function in the optimization problem is semismooth, quasidifferentiable and piecewise partially separable. The use of these properties allow us to design an efficient algorithm for approximation of subgradients of the objective function and to apply the discrete gradient method for its minimization. We present computational results with some simulated data and compare the new estimator with a number of existing ones.     

An asymptotically optimal Schur complement reduction for the Stokes equation

Summary. In this paper we develop an efficient Schur complement method for solving the 2D Stokes equation. As a basic algorithm, we apply a decomposition approach with respect to the trace of the pressure. The alternative stream function-vorticity reduction is also discussed. The original problem is reduced to solving the equivalent boundary (interface) equation with symmetric and positive definite operator in the appropriate trace space. We apply a mixed finite element approximation to the interface operator by iso triangular elements and prove the optimal error estimates in the presence of stabilizing bubble functions. The norm equivalences for the corresponding discrete operators are established. Then we propose an asymptotically optimal compression technique for the related stiffness matrix (in the absence of bubble functions) providing a sparse factorized approximation to the Schur complement. In this case, the algorithm is shown to have an optimal complexity of the order , q = 2 or q = 3, depending on the geometry, where N is the number of degrees of freedom on the interface. In the presence of bubble functions, our method has the complexity arithmetical operations. The Schur complement interface equation is resolved by the PCG iterations with an optimal preconditioner. Received March 20, 1996 / Revised version received October 28, 1997     

Estimation of the distribution of random shifts deformation

Consider discrete values of functions shifted by unobserved translation effects, which are independent realizations of a random variable with unknown distribution μ modeling the variability in the response of each individual. Our aim is to construct a nonparametric estimator of the density of these random translation deformations using semiparametric preliminary estimates of the shifts. Based on the results of Dalalyan et al. [7], semiparametric estimators are obtained in our discrete framework and their performance studied. From these estimates we construct a nonparametric estimator of the target density. Both rates of convergence and an algorithm to construct the estimator are provided.      

Discrete Jacobi sub‐equation method for nonlinear differential–difference equations

We will propose a unified algebraic method to construct Jacobi elliptic function solutions to differential–difference equations (DDEs). The solutions to DDEs in terms of Jacobi elliptic functions sn, cn and dn have a unified form and can be presented through solving the associated algebraic equations. To illustrate the effectiveness of this method, we apply the algorithm to some physically significant DDEs, including the discrete hybrid equation, semi‐discrete coupled modified Korteweg–de Vries and the discrete Klein–Gordon equation, thereby generating some new exact travelling periodic solutions to the discrete Klein–Gordon equation. A procedure is also given to determine the polynomial expansion order of Jacobi elliptic function solutions to DDEs. Copyright © 2010 John Wiley & Sons, Ltd.     

Global optimization and simulated annealing

In this paper we are concerned with global optimization, which can be defined as the problem of finding points on a bounded subset of ⁿ in which some real valued functionf assumes its optimal (maximal or minimal) value.We present a stochastic approach which is based on the simulated annealing algorithm. The approach closely follows the formulation of the simulated annealing algorithm as originally given for discrete optimization problems. The mathematical formulation is extended to continuous optimization problems, and we prove asymptotic convergence to the set of global optima. Furthermore, we discuss an implementation of the algorithm and compare its performance with other well-known algorithms. The performance evaluation is carried out for a standard set of test functions from the literature.     

The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences

Various applications involve assigning discrete label values to a collection of objects based on some pairwise noisy data. Due to the discrete—and hence nonconvex—structure of the problem, computing the optimal assignment (e.g., maximum‐likelihood assignment) becomes intractable at first sight. This paper makes progress towards efficient computation by focusing on a concrete joint alignment problem; that is, the problem of recovering n discrete variables x_i ∊ {1, …, m}, 1 ≤ i ≤ n, given noisy observations of their modulo differences {x_i — x_j mod m}. We propose a low‐complexity and model‐free nonconvex procedure, which operates in a lifted space by representing distinct label values in orthogonal directions and attempts to optimize quadratic functions over hypercubes. Starting with a first guess computed via a spectral method, the algorithm successively refines the iterates via projected power iterations. We prove that for a broad class of statistical models, the proposed projected power method makes no error—and hence converges to the maximum‐likelihood estimate—in a suitable regime. Numerical experiments have been carried out on both synthetic and real data to demonstrate the practicality of our algorithm. We expect this algorithmic framework to be effective for a broad range of discrete assignment problems.© 2018 Wiley Periodicals, Inc.     

Computation of discrete logarithms in prime fields

The presumed difficulty of computing discrete logarithms in finite fields is the basis of several popular public key cryptosystems. The secure identification option of the Sun Network File System, for example, uses discrete logarithms in a field GF(p) with p a prime of 192 bits. This paper describes an implementation of a discrete logarithm algorithm which shows that primes of under 200 bits, such as that in the Sun system, are very insecure. Some enhancements to this system are suggested.     

Analyzing the Complexity of Finding Good Neighborhood Functions for Local Search Algorithms

A drawback to using local search algorithms to address NP-hard discrete optimization problems is that many neighborhood functions have an exponential number of local optima that are not global optima (termed L-locals). A neighborhood function η is said to be stable if the number of L-locals is polynomial. A stable neighborhood function ensures that the number of L-locals does not grow too large as the instance size increases and results in improved performance for many local search algorithms. This paper studies the complexity of stable neighborhood functions for NP-hard discrete optimization problems by introducing neighborhood transformations. Neighborhood transformations between discrete optimization problems consist of a transformation of problem instances and a corresponding transformation of solutions that preserves the ordering imposed by the objective function values. In this paper, MAX Weighted Boolean SAT (MWBS), MAX Clause Weighted SAT (MCWS), and Zero-One Integer Programming (ZOIP) are shown to be NPO-complete with respect to neighborhood transformations. Therefore, if MWBS, MCWS, or ZOIP has a stable neighborhood function, then every problem in NPO has a stable neighborhood function. These results demonstrate the difficulty of finding effective neighborhood functions for NP-hard discrete optimization problems.This research is supported in part by the Air Force Office of Scientific Research (F49620-01-1-0007, FA9550-04-1-0110).     

Expansion of functions in a Fourier-Chebyshev series by shifted Chebyshev polynomials of the first kind

The paper considers an algorithm that develops functions in a Fourier—Chebyshev series by shifted Chebyshev polynomials of the first kind. The relationship of the algorithm with Fourier transform and discrete cosine transform is established.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 73, pp. 25–27, 1992.     

Positively curved graphs

This paper consists of two halves. In the first half of the paper, we consider real-valued functions f whose domain is the vertex set of a graph G and that are Lipschitz with respect to the graph distance. By placing a uniform distribution on the vertex set, we treat as a random variable. We investigate the link between the isoperimetric function of G and the functions f that have maximum variance or meet the bound established by the subgaussian inequality. We present several results describing the extremal functions, and use those results to (a) resolve a conjecture by Bobkov, Houdré, and Tetali characterizing the extremal functions of the subgaussian inequality of the odd cycle and (b) provide a construction that gives a partial negative answer to a question by Alon, Boppana, and Spencer on the relationship between maximum variance functions and the isoperimetric function of product graphs. While establishing a discrete analogue of the curved Brunn-Minkowski inequality for the discrete hypercube, Ollivier and Villani suggested several avenues for research. We resolve them in the second half of the paper as follows:

• They propose that a bound on t-midpoints can be obtained by repeated application of the bound on midpoints, if the original sets are convex. We construct a specific example where this reasoning fails, and then prove our construction is general by characterizing the convex sets in the discrete hypercube.
• A second proposed technique to bound t-midpoints involves new results in concentration of measure. We follow through on this proposal, with heavy use on results from the first half of the paper.
• We show that the curvature of the discrete hypercube is not positive or zero, but we also give a result indicating that it may satisfy a weaker version of curvature.