New Extensions of Popoviciu’s Inequality

Popoviciu’s inequality is extended to the framework of h-convexity and also to convexity with respect to a pair of quasi-arithmetic means. Several applications are included.

     

Analytic continuation of the exponential transform from convex cavities

The analytic continuation of the exponential transform of a domain in Rn is proved under some global geometric assumptions on the boundary. Two approximation schemes of the continued transform (one based on a Taylor series truncation, the other on a global eigenfunction expansion) are also discussed.     

Hierarchical approach for survivable network design

A central design challenge facing network planners is how to select a cost-effective network configuration that can provide uninterrupted service despite edge failures. In this paper, we study the Survivable Network Design (SND) problem, a core model underlying the design of such resilient networks that incorporates complex cost and connectivity trade-offs. Given an undirected graph with specified edge costs and (integer) connectivity requirements between pairs of nodes, the SND problem seeks the minimum cost set of edges that interconnects each node pair with at least as many edge-disjoint paths as the connectivity requirement of the nodes. We develop a hierarchical approach for solving the problem that integrates ideas from decomposition, tabu search, randomization, and optimization. The approach decomposes the SND problem into two subproblems, Backbone design and Access design, and uses an iterative multi-stage method for solving the SND problem in a hierarchical fashion. Since both subproblems are NP-hard, we develop effective optimization-based tabu search strategies that balance intensification and diversification to identify near-optimal solutions. To initiate this method, we develop two heuristic procedures that can yield good starting points. We test the combined approach on large-scale SND instances, and empirically assess the quality of the solutions vis-à-vis optimal values or lower bounds. On average, our hierarchical solution approach generates solutions within 2.7% of optimality even for very large problems (that cannot be solved using exact methods), and our results demonstrate that the performance of the method is robust for a variety of problems with different size and connectivity characteristics.     

The Landscape of the Spiked Tensor Model

We consider the problem of estimating a large rank-one tensor u ^⊗k ∈ (ℝⁿ)^⊗k , k ≥ 3 , in Gaussian noise. Earlier work characterized a critical signal-to-noise ratio λ  _Bayes = O(1) above which an ideal estimator achieves strictly positive correlation with the unknown vector of interest. Remarkably, no polynomial-time algorithm is known that achieved this goal unless λ ≥ Cn^{(k − 2)/4} , and even powerful semidefinite programming relaxations appear to fail for 1 ≪ λ ≪ n^{(k − 2)/4} . In order to elucidate this behavior, we consider the maximum likelihood estimator, which requires maximizing a degree-k homogeneous polynomial over the unit sphere in n dimensions. We compute the expected number of critical points and local maxima of this objective function and show that it is exponential in the dimensions n , and give exact formulas for the exponential growth rate. We show that (for λ larger than a constant) critical points are either very close to the unknown vector u or are confined in a band of width Θ(λ^{−1/(k − 1)}) around the maximum circle that is orthogonal to u . For local maxima, this band shrinks to be of size Θ(λ^{−1/(k − 2)}) . These “uninformative” local maxima are likely to cause the failure of optimization algorithms. © 2019 Wiley Periodicals, Inc.     

A linear assignment approach for the least-squares protein morphing problem

This work addresses the computation of free-energy differences between protein conformations by using morphing (i.e., transformation) of a source conformation into a target conformation. To enhance the morphing procedure, we employ permutations of atoms: we seek to find the permutation σ that minimizes the mean-square distance traveled by the atoms. Instead of performing this combinatorial search in the space of permutations, we show that the best permutation can be found by solving a linear assignment problem. We demonstrate that the use of such optimal permutations significantly improves the efficiency of the free-energy computation.     

Immediate extensions of filtered rings

Summary A separated filtered ring has a maximally complete immediate extension. This is an analogue of Krull Theorem from valuation ring theory in the frame of filtered rings.

---

Riassunto Un anello separato filtrato ha una immediata estensione massimale completa. Questo risultato è un analogo del teorema di Krull della teoria degli anelli di valutazione nell’ambito degli anelli filtrati.