Integer programming as projection

We generalise polyhedral projection (Fourier–Motzkin elimination) to integer programming (IP) and derive from this an alternative perspective on IP that parallels the classical theory. We first observe that projection of an IP yields an IP augmented with linear congruence relations and finite-domain variables, which we term a generalised IP. The projection algorithm can be converted to a branch-and-bound algorithm for generalised IP in which the search tree has bounded depth (as opposed to conventional branching, in which there is no bound). It also leads to valid inequalities that are analogous to Chvátal–Gomory cuts but are derived from congruences rather than rounding, and whose rank is bounded by the number of variables. Finally, projection provides an alternative approach to IP duality. It yields a value function that consists of nested roundings as in the classical case, but in which ordinary rounding is replaced by rounding to the nearest multiple of an appropriate modulus, and the depth of nesting is again bounded by the number of variables. For large perturbations of the right-hand sides, the value function is shift periodic and can be interpreted economically as yielding “average” shadow prices.     

Logical analysis of numerical data

“Logical analysis of data” (LAD) is a methodology developed since the late eighties, aimed at discovering hidden structural information in data sets. LAD was originally developed for analyzing binary data by using the theory of partially defined Boolean functions. An extension of LAD for the analysis of numerical data sets is achieved through the process of “binarization” consisting in the replacement of each numerical variable by binary “indicator” variables, each showing whether the value of the original variable is above or below a certain level. Binarization was successfully applied to the analysis of a variety of real life data sets. This paper develops the theoretical foundations of the binarization process studying the combinatorial optimization problems related to the minimization of the number of binary variables. To provide an algorithmic framework for the practical solution of such problems, we construct compact linear integer programming formulations of them. We develop polynomial time algorithms for some of these minimization problems, and prove NP-hardness of others. The authors gratefully acknowledge the partial support by the Office of Naval Research (grants N00014-92-J1375 and N00014-92-J4083).     

On perfect nonlinear functions

An Erratum has been published for this article in Journal of Combinatorial Designs 14: 82–82, 2006 . We give the equivalence between perfect nonlinear functions and appropriate splitting semi‐regular relative difference sets, construct a class of splitting relative difference sets by using Galois rings and bent functions, and prove that there exists a 4‐phase perfect nonlinear function if and only if the number of input variables is at least twice the number of output variables. © 2005 Wiley Periodicals, Inc.     

On the fractional chromatic number of monotone self-dual Boolean functions

We compute the exact fractional chromatic number for several classes of monotone self-dual Boolean functions. We characterize monotone self-dual Boolean functions in terms of the optimal value of an LP relaxation of a suitable strengthening of the standard IP formulation for the chromatic number. We also show that determining the self-duality of a monotone Boolean function is equivalent to determining the feasibility of a certain point in a polytope defined implicitly.     

Bounding a class of nonconvex linearly-constrained resource allocation problems via the surrogate dual

We consider a class of problems of resource allocation under economies of scale, namely that of minimizing a lower semicontinuous, isotone, and explicitly quasiconcave cost function subject to linear constraints. An important class of algorithms for the linearly constrained minimization of nonconvex cost functions utilize the branch and bound approach, using convex underestimating cost functions to compute the lower bounds.We suggest instead the use of the surrogate dual problem to bound subproblems. We show that the success of the surrogate dual in fathoming subproblems in a branch and bound algorithm may be determined without directly solving the surrogate dual itself, but that a simple test of the feasibility of a certain linear system of inequalities will suffice. This test is interpreted geometrically and used to characterize the extreme points and extreme rays of the optimal value function's level sets.Research partially supported by NSF under grant # ENG77-06555.     

Entropy and set cardinality inequalities for partition‐determined functions

A new notion of partition‐determined functions is introduced, and several basic inequalities are developed for the entropies of such functions of independent random variables, as well as for cardinalities of compound sets obtained using these functions. Here a compound set means a set obtained by varying each argument of a function of several variables over a set associated with that argument, where all the sets are subsets of an appropriate algebraic structure so that the function is well defined. On the one hand, the entropy inequalities developed for partition‐determined functions imply entropic analogues of general inequalities of Plünnecke‐Ruzsa type. On the other hand, the cardinality inequalities developed for compound sets imply several inequalities for sumsets, including for instance a generalization of inequalities proved by Gyarmati, Matolcsi and Ruzsa (2010). We also provide partial progress towards a conjecture of Ruzsa (2007) for sumsets in nonabelian groups. All proofs are elementary and rely on properly developing certain information‐theoretic inequalities. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 399–424, 2012     

Measuring the level sets of anisotropic homogeneous functions

In this note we investigate some basic properties of the level sets of functions which are homogeneous with respect to nonisotropic dilations. In particular we obtain a formula for the volume of the level sets in terms of the area on the level surfaces. We relate the results to some well known mean value formulas for solutions of PDE’s.     

Classical symmetric functions in superspace

We present the basic elements of a generalization of symmetric function theory involving functions of commuting and anticommuting (Grassmannian) variables. These new functions, called symmetric functions in superspace, are invariant under the diagonal action of the symmetric group on the sets of commuting and anticommuting variables. In this work, we present the superspace extension of the classical bases, namely, the monomial symmetric functions, the elementary symmetric functions, the completely symmetric functions, and the power sums. Various basic results, such as the generating functions for the multiplicative bases, Cauchy formulas, involution operations as well as the combinatorial scalar product are also generalized.     

D sets and IP rich sets in countable,cancellative abelian semigroups

We give combinatorial characterizations of IP rich sets (IP sets that remain IP upon removal of any set of zero upper Banach density) and D sets (members of idempotent ultrafilters, all of whose members have positive upper Banach density) in a general countable, cancellative abelian semigroup. We then show that the family of IP rich sets strictly contains the family of D sets.     

Construction of Lyapunov functions by the method of localization of invariant compact sets

We suggest a new method for constructing Lyapunov functions for autonomous systems of differential equations. The method is based on the construction of a family of sets whose boundaries have the properties typical of the level surfaces of Lyapunov functions. These sets are found by the method of localization of invariant compact sets. For the resulting Lyapunov function and its derivative, we find analytical expressions via the localizing functions occurring in the specification of the above-mentioned sets. An example of a system with a degenerate equilibrium is considered.     

Quasi-concave functions on meet-semilattices

This paper deals with maximization of set functions defined as minimum values of monotone linkage functions. In previous research, it has been shown that such a set function can be maximized by a greedy type algorithm over a family of all subsets of a finite set. In this paper, we extend this finding to meet-semilattices.We show that the class of functions defined as minimum values of monotone linkage functions coincides with the class of quasi-concave set functions. Quasi-concave functions determine a chain of upper level sets each of which is a meet-semilattice. This structure allows development of a polynomial algorithm that finds a minimal set on which the value of a quasi-concave function is maximum. One of the critical steps of this algorithm is a set closure. Some examples of closure computation, in particular, a closure operator for convex geometries, are considered.     

Phase Space of Collective Variables and the Zubarev Transition Function

We study the completeness of the transition function J(ρ ? \(\hat \rho \)) to the infinite set of collective variables {ρk}. Zubarev first introduced this transition function in statistical physics. We propose complete forms for the Jacobians of transitions to the corresponding sets of collective variables in problems in the theory of electrolyte solutions, the Ising model, and the first-order phase transition. We analyze the methods and calculation results in the phase spaces of collective variables of the partition functions of these systems.     

Positive solutions of nonlinear beam equations with time and space singularities

We consider the existence and multiplicity of positive solutions to a nonlinear fourth-order two-point boundary value problem. The nonlinear term may be singular with respect to both the time and space variables. In mechanics, the problem describes the deformation of an elastic beam fixed at the left and supported at the right by sliding clamps. By introducing height functions of the nonlinear term on some bounded sets and considering integrations of these height functions, several local existence theorems are obtained.     

Epigraphical and Uniform Convergence of Convex Functions

We examine when a sequence of lsc convex functions on a Banach space converges uniformly on bounded sets (resp. compact sets) provided it converges Attouch-Wets (resp. Painlevé-Kuratowski). We also obtain related results for pointwise convergence and uniform convergence on weakly compact sets. Some known results concerning the convergence of sequences of linear functionals are shown to also hold for lsc convex functions. For example, a sequence of lsc convex functions converges uniformly on bounded sets to a continuous affine function provided that the convergence is uniform on weakly compact sets and the space does not contain an isomorphic copy of .

     

Suggested research topics in sensitivity and stability analysis for semi-infinite programming problems

We suggest several important research topics for semi-infinite programs whose problem functions and index sets contain parameters that are subject to perturbation. These include optimal value and optimal solution sensitivity and stability properties and penalty function approximation techniques. The approaches proposed are a natural carryover from parametric nonlinear programming, with emphasis on practical applicability and computability.Research supported by National Science Foundation Grant SES 8722504 and Grant ECS-86-19859 and Grant N00014-89-J-1537, Office of Naval Research.     

Objective function and logarithmic barrier function properties in convex programming: level sets,solution attainment and strict convexity *

We give several results, some new and some old, but apparently overlooked, that provide useful characterizations of barrier functions and their relationship to problem function properties. In particular, we show that level sets of a barrier function are bounded if and only if feasible level sets of the objective function are bounded and we obtain conditions that imply solution existence, strict convexity or a positive definite Hessian of a barrier function. Attention is focused on convex programs and the logarithmic barrier function. Such results suggest that it would seem possible to extend many recent complexity results by relaxing feasible set compactness to the feasible objective function level set boundedness assumption.     

Mayer and optimal stopping stochastic control problems with discontinuous cost

We study two classes of stochastic control problems with semicontinuous cost: the Mayer problem and optimal stopping for controlled diffusions. The value functions are introduced via linear optimization problems on appropriate sets of probability measures. These sets of constraints are described deterministically with respect to the coefficient functions. Both the lower and upper semicontinuous cases are considered. The value function is shown to be a generalized viscosity solution of the associated HJB system, respectively, of some variational inequality. Dual formulations are given, as well as the relations between the primal and dual value functions. Under classical convexity assumptions, we prove the equivalence between the linearized Mayer problem and the standard weak control formulation. Counter-examples are given for the general framework.     

Minimizing Increasing Star-shaped Functions Based on Abstract Convexity

We study a broad class of increasing non-convex functions whose level sets are star shaped with respect to infinity. We show that these functions (we call them ISSI functions) are abstract convex with respect to the set of min-type functions and exploit this fact for their minimization. An algorithm is proposed for solving global optimization problems with an ISSI objective function and its numerical performance is discussed.     

Solving discrete linear bilevel optimization problems using the optimal value reformulation

In this article, we consider two classes of discrete bilevel optimization problems which have the peculiarity that the lower level variables do not affect the upper level constraints. In the first case, the objective functions are linear and the variables are discrete at both levels, and in the second case only the lower level variables are discrete and the objective function of the lower level is linear while the one of the upper level can be nonlinear. Algorithms for computing global optimal solutions using Branch and Cut and approximation of the optimal value function of the lower level are suggested. Their convergence is shown and we illustrate each algorithm via an example.     

Finding nonnormal bent functions

The question if there exist nonnormal bent functions was an open question for several years. A Boolean function in n variables is called normal if there exists an affine subspace of dimension n/2 on which the function is constant. In this paper we give the first nonnormal bent function and even an example for a nonweakly normal bent function. These examples belong to a class of bent functions found in [J.F. Dillon, H. Dobbertin, New cyclic difference sets with Singer parameters, in: Finite Fields and Applications, to appear], namely the Kasami functions. We furthermore give a construction which extends these examples to higher dimensions. Additionally, we present a very efficient algorithm that was used to verify the nonnormality of these functions.