Equivariant perturbation in Gomory and Johnson’s infinite group problem—III: foundations for the k-dimensional case with applications to $$ $$

We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, we present the general regular solution to Cauchy’s additive functional equation on restricted lower-dimensional convex domains. This provides a k-dimensional generalization of the so-called Interval Lemma, allowing us to deduce affine properties of the function from certain additivity relations. Next, we study the discrete geometry of additivity domains of piecewise linear functions, providing a framework for finite tests of minimality and extremality. We then give a theory of non-extremality certificates in the form of perturbation functions. We apply these tools in the context of minimal valid functions for the two-dimensional infinite group problem that are piecewise linear on a standard triangulation of the plane, under a regularity condition called diagonal constrainedness. We show that the extremality of a minimal valid function is equivalent to the extremality of its restriction to a certain finite two-dimensional group problem. This gives an algorithm for testing the extremality of a given minimal valid function.     

Light on the infinite group relaxation II: sufficient conditions for extremality,sequences, and algorithms

This is the second part of a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their groundbreaking papers titled Some continuous functions related to corner polyhedra I, II (Math Program 3:23–85, 1972a; Math Program 3:359–389, 1972b). The survey presents the infinite group problem in the modern context of cut generating functions. It focuses on the recent developments, such as algorithms for testing extremality and breakthroughs for the k-row problem for general \(k\ge 1\) that extend previous work on the single-row and two-row problems. The survey also includes some previously unpublished results; among other things, it unveils piecewise linear extreme functions with more than four different slopes. An interactive companion program, implemented in the open-source computer algebra package Sage, provides an updated compendium of known extreme functions.     

Light on the infinite group relaxation I: foundations and taxonomy

This is a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their groundbreaking papers titled Some continuous functions related to corner polyhedra I, II (Math Program 3:23–85, 359–389, 1972a, b). The survey presents the infinite group problem in the modern context of cut generating functions. It focuses on the recent developments, such as algorithms for testing extremality and breakthroughs for the k-row problem for general \(k\ge 1\) that extend previous work on the single-row and two-row problems. The survey also includes some previously unpublished results; among other things, it unveils piecewise linear extreme functions with more than four different slopes. An interactive companion program, implemented in the open-source computer algebra package Sage, provides an updated compendium of known extreme functions.     

Characterizing Convexity of a Function by Its Fréchet and Limiting Second-Order Subdifferentials

The Fréchet and limiting second-order subdifferentials of a proper lower semicontinuous convex function \(\varphi: \mathbb R^n\rightarrow\bar{\mathbb R}\) have a property called the positive semi-definiteness (PSD)—in analogy with the notion of positive semi-definiteness of symmetric real matrices. In general, the PSD is insufficient for ensuring the convexity of an arbitrary lower semicontinuous function φ. However, if φ is a C ^1,1 function then the PSD property of one of the second-order subdifferentials is a complete characterization of the convexity of φ. The same assertion is valid for C ¹ functions of one variable. The limiting second-order subdifferential can recognize the convexity/nonconvexity of piecewise linear functions and of separable piecewise C ² functions, while its Fréchet counterpart cannot.     

System Representations for the Paley–Wiener Space $$\mathcal {PW}_{\pi }^2$$

In this paper we study the approximation of stable linear time-invariant systems for the Paley–Wiener space \(\mathcal {PW}_{\pi }^2\), i.e., the set of bandlimited functions with finite \(L^2\)-norm, by convolution sums. It is possible to use either, the convolution sum where the time variable is in the argument of the bandlimited impulse response, or the convolution sum where the time variable is in the argument of the function, as an approximation process. In addition to the pointwise and uniform convergence behavior, the convergence behavior in the norm of the considered function space, i.e. the \(L^2\)-norm in our case, is important. While it is well-known that both convolution sums converge uniformly on the whole real axis, the \(L^2\)-norm of the second convolution sum can be divergent for certain functions and systems. We show that the there exist an infinite dimensional closed subspace of functions and an infinite dimensional closed subspace of systems, such that for any pair of function and system from these two sets, we have norm divergence.     

Locally piecewise affine functions and their order structure

Piecewise affine functions on subsets of \(\mathbb R^m\) were studied in Aliprantis et al. (Macroecon Dyn 10(1):77–99, 2006), Aliprantis et al. (J Econometrics 136(2):431–456, 2007), Aliprantis and Tourky (Cones and duality, 2007), Ovchinnikov (Beitr\(\ddot{\mathrm{a}}\)ge Algebra Geom 43:297–302, 2002). In this paper we study a more general concept of a locally piecewise affine function. We characterize locally piecewise affine functions in terms of components and regions. We prove that a positive function is locally piecewise affine iff it is the supremum of a locally finite sequence of piecewise affine functions. We prove that locally piecewise affine functions are uniformly dense in \(C(\mathbb R^m)\), while piecewise affine functions are sequentially order dense in \(C(\mathbb R^m)\). This paper is partially based on Adeeb (Locally piece-wise affine functions, 2014)     

On a system of piecewise linear functions with vanishing integrals on <Emphasis Type="Italic">R</Emphasis>

For an admissible sequence T we define an orthonormal system consisting of piecewise linear functions with vanishing integrals on R. Necessary and sufficient conditions on T are found for the corresponding system to be a basis in H¹(R).     

The Lipschitzianity of convex vector and set-valued functions

It is well known that every scalar convex function is locally Lipschitz on the interior of its domain in finite dimensional spaces. The aim of this paper is to extend this result for both vector functions and set-valued mappings acting between infinite dimensional spaces with an order generated by a proper convex cone C. Under the additional assumption that the ordering cone C is normal, we prove that a locally C-bounded C-convex vector function is Lipschitz on the interior of its domain by two different ways. Moreover, we derive necessary conditions for Pareto minimal points of vector-valued optimization problems where the objective function is C-convex and C-bounded. Corresponding results are derived for set-valued optimization problems.     

The number of energy levels of a particle in an MQW structure

A method is proposed for calculating the number of energy levels of a quantum particle moving in a one-dimensional piecewise constant potential field of a certain kind, which is called a multiple quantum well (MQW) structure. It consists of several layers, namely, of potential wells with a zero potential separated by walls with a potential U > 0. The external walls have an infinite width. The method is based on a recently obtained multilayer equation that makes it possible to calculate the eigenvalues of the energy E of a quantum particle in an arbitrary MQW structure. The equation has the form F _j ^* (E) = 0, where F _j ^* (E) is a rather complex function that is constructed from the given MQW structure and depends on the index j of an arbitrarily chosen bounded layer. The key property is that the functions F _j ^* (E) corresponding to the external bounded layers are strictly monotone on the intervals of their continuity. For internal bounded layers, these functions may not be monotone. The formula for the number of energy levels holds in the case of general position. This means that it is not valid for specially chosen well and wall widths (these cases are rather rare and are called resonant). An example is presented in which the number of energy levels does not increase when the potential well is doubled.     

The Gibbs phenomenon for general Franklin systems

The paper is devoted to the Gibbs phenomenon for series by general Franklin systems. The general Franklin system corresponding to a given dense sequence of points T = (t _n , n ≥ 0) in [0, 1] is a sequence of orthonormal piecewise linear functions with knots from T, that is, the nth function from the system has knots t ₀,..., t _n . The main result of this paper is that the Gibbs phenomenon for Fourier series by general Franklin systems occurs for almost all points of [0, 1].     

Fixed Points for the Multifractal Spectrum Map

For all continuous function g having a specific form that we call with increasing visibility, we construct a function f whose multifractal spectrum is such that \( d_f =g\circ f\). The function f is obtained as an infinite superposition of piecewise \(C^1\) functions, is also with increasing visibility, and is homogeneously multifractal; i.e., its restriction on any subinterval of \([0,1]\) has the same multifractal spectrum as the function f itself. In particular, we prove the existence of a function f which is its own multifractal spectrum; i.e., \(f=d_f\).     

First-Order Algorithms for Generalized Semi-Infinite Min-Max Problems

We present a first-order algorithm for solving semi-infinite generalized min-max problems which consist of minimizing a function f⁰(x) = F(¹(x), .... , ^m (x)), where F is a smooth function and each ⁱ is the maximum of an infinite number of smooth functions.In Section 3.3 of [17] Polak finds a methodology for solving infinite dimensional problems by expanding them into an infinite sequence of consistent finite dimensional approximating problems, and then using a master algorithm that selects an appropriate subsequence of these problems and applies a number of iterations of a finite dimensional optimization algorithm to each of these problems, sequentially. Our algorithm was constructed within this framework; it calls an algorithm by Kiwiel as a subroutine. The number of iterations of the Kiwiel algorithm to be applied to the approximating problems is determined by a test that ensures that the overall scheme retains the rate of convergence of the Kiwiel algorithm.Under reasonable assumptions we show that all the accumulation points of sequences constructed by our algorithm are stationary, and, under an additional strong convexity assumption, that the Kiwiel algorithm converges at least linearly, and that our algorithm also converges at least linearly, with the same rate constant bounds as Kiwiel's.     

Block characters of the symmetric groups

A block character of a finite symmetric group is a positive definite function which depends only on the number of cycles in a permutation. We describe the cone of block characters by identifying its extreme rays, and find relations of the characters to descent representations and the coinvariant algebra of ${\mathfrak{S}}_{n}$ . The decomposition of extreme block characters into the sum of characters of irreducible representations gives rise to certain limit shape theorems for random Young diagrams. We also study counterparts of the block characters for the infinite symmetric group ${\mathfrak{S}}_{\infty}$ , along with their connection to the Thoma characters of the infinite linear group GL _∞(q) over a Galois field.     

Vector spaces of non-extendable holomorphic functions

In this paper, we analyze the linear structure of the family H _e (G) of holomorphic functions on a domain G of the complex plane that are not analytically continuable beyond the boundary of G. We prove that H _e (G) contains, except for zero, a dense algebra; and, under appropriate conditions, the subfamily of H _e (G) consisting of boundary-regular functions contains dense vector spaces with maximal dimension as well as infinite dimensional closed vector spaces and large algebras. We also consider the case in which G is a domain of existence in a complex Banach space. The results obtained complete or extend a number of previous results by several authors.     

Lower estimates of circuit complexity in the basis of antichain functions

The antichain function is a characteristic function of an antichain in the Boolean cube. The set of antichain functions is an infinite complete basis. We study the computational complexity of Boolean functions over an antichain functional basis. In this paper we prove an asymptotic lower bound of order $\sqrt n $ for the computational complexity of a linear function, a majority function, and almost all Boolean functions of n variables.     

The Nöther and Riemann-Roch type theorems for piecewise algebraic curve

A piecewise algebraic curve is a curve determined by the zero set of a bivariate spline function. In this paper, the Nöther type theorems for C ^µ piecewise algebraic curves are obtained. The theory of the linear series of sets of places on the piecewise algebraic curve is also established. In this theory, singular cycles are put into the linear series, and a complete series of the piecewise algebraic curves consists of all effective ordinary cycles in an equivalence class and all effective singular cycles which are equivalent specifically to any effective ordinary cycle in the equivalence class. This theory is a generalization of that of linear series of the algebraic curve. With this theory and the fundamental theory of multivariate splines on smoothing cofactors and global conformality conditions, and the results on the general expression of multivariate splines, we get a formula on the index, the order and the dimension of a complete series of the irreducible C ^µ piecewise algebraic curves and the degree, the genus and the smoothness of the curves, hence the Riemann-Roch type theorem of the C ^µ piecewise algebraic curve is established.     

Generic results in classes of ultradifferentiable functions

Let E be a Denjoy–Carleman class of ultradifferentiable functions of Beurling type on the real line that strictly contains another class F of Roumieu type. We show that the set S of functions in E that are nowhere in the class F   is large in the topological sense (it is residual), in the measure theoretic sense (it is prevalent), and that S∪{0}$S\cup \{0\}$ contains an infinite dimensional linear subspace (it is lineable). Consequences for the Gevrey classes are given. Similar results are also obtained for classes of ultradifferentiable functions defined imposing conditions on the Fourier–Laplace transform of the function.     

Remarkable Haar spaces of multivariate piecewise polynomials

Some families of Haar spaces in \(\mathbb {R}^{d},~ d\ge 1,\) whose basis functions are d-variate piecewise polynomials, are highlighted. The starting point is a sequence of univariate piecewise polynomials, called Lobachevsky splines, arised in probability theory and asymptotically related to the normal density function. Then, it is shown that d-variate Lobachevsky splines can be expressed as products of Lobachevsky splines. All these splines have simple analytic expressions and subsets of them are suitable for scattered data interpolation, allowing efficient computation and plain error analysis.     

Constructive Solution of Inverse Parametric Linear/Quadratic Programming Problems

Parametric convex programming has received a lot of attention, since it has many applications in chemical engineering, control engineering, signal processing, etc. Further, inverse optimality plays an important role in many contexts, e.g., image processing, motion planning. This paper introduces a constructive solution of the inverse optimality problem for the class of continuous piecewise affine functions. The main idea is based on the convex lifting concept. Accordingly, an algorithm to construct convex liftings of a given convexly liftable partition will be put forward. Following this idea, an important result will be presented in this article: Any continuous piecewise affine function defined over a polytopic partition is the solution of a parametric linear/quadratic programming problem. Regarding linear optimal control, it will be shown that any continuous piecewise affine control law can be obtained via a linear optimal control problem with the control horizon at most equal to 2 prediction steps.     

A linear eigenvalue algorithm for the nonlinear eigenvalue problem

The Arnoldi method for standard eigenvalue problems possesses several attractive properties making it robust, reliable and efficient for many problems. The first result of this paper is a characterization of the solutions to an arbitrary (analytic) nonlinear eigenvalue problem (NEP) as the reciprocal eigenvalues of an infinite dimensional operator denoted ${\mathcal {B}}$ . We consider the Arnoldi method for the operator ${\mathcal {B}}$ and show that with a particular choice of starting function and a particular choice of scalar product, the structure of the operator can be exploited in a very effective way. The structure of the operator is such that when the Arnoldi method is started with a constant function, the iterates will be polynomials. For a large class of NEPs, we show that we can carry out the infinite dimensional Arnoldi algorithm for the operator ${\mathcal {B}}$ in arithmetic based on standard linear algebra operations on vectors and matrices of finite size. This is achieved by representing the polynomials by vector coefficients. The resulting algorithm is by construction such that it is completely equivalent to the standard Arnoldi method and also inherits many of its attractive properties, which are illustrated with examples.