Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints

The well known DIRECT (DIviding RECTangles) algorithm for global optimization requires bound constraints on variables and does not naturally address additional linear or nonlinear constraints. A feasible region defined by linear constraints may be covered by simplices, therefore simplicial partitioning may tackle linear constraints in a very subtle way. In this paper we demonstrate this advantage of simplicial partitioning by applying a recently proposed deterministic simplicial partitions based DISIMPL algorithm for optimization problems defined by general linear constraints (Lc-DISIMPL). An extensive experimental investigation reveals advantages of this approach to such problems comparing with different constraint-handling methods, proposed for use with DIRECT. Furthermore the Lc-DISIMPL algorithm gives very competitive results compared to a derivative-free particle swarm algorithm (PSwarm) which was previously shown to give very promising results. Moreover, DISIMPL guarantees the convergence to the global solution, whereas the PSwarm algorithm sometimes fails to converge to the global minimum.     

Characterization Theorems for the Quantum White Noise Gross Laplacian and Applications

This paper reports on the characterization of the quantum white noise (QWN) Gross Laplacian based on nuclear algebra of white noise operators acting on spaces of entire functions with \(\theta \)-exponential growth of minimal type. First, we use extended techniques of rotation invariance operators, the commutation relations with respect to the QWN-derivatives and the QWN-conservation operator. Second, we employ the new concept of QWN-convolution operators. As application, we study and characterize the powers of the QWN-Gross Laplacian. As for their associated Cauchy problem it is solved using a QWN-convolution and Wick calculus.     

Computability-theoretic and proof-theoretic aspects of partial and linear orderings

Szpilrajn’s Theorem states that any partial orderP=〈S,<p〉 has a linear extensionP=〈S,<L〉. This is a central result in the theory of partial orderings, allowing one to define, for instance, the dimension of a partial ordering. It is now natural to ask questions like “Does a well-partial ordering always have a well-ordered linear extension?” Variations of Szpilrajn’s Theorem state, for various (but not for all) linear order typesτ, that ifP does not contain a subchain of order typeτ, then we can chooseL so thatL also does not contain a subchain of order typeτ. In particular, a well-partial ordering always has a well-ordered extension.We show that several effective versions of variations of Szpilrajn’s Theorem fail, and use this to narrow down their proof-theoretic strength in the spirit of reverse mathematics.     

Application of Reduced-set Pareto-Lipschitzian Optimization to truss optimization

In this paper, a recently proposed global Lipschitz optimization algorithm Pareto-Lipschitzian Optimization with Reduced-set (PLOR) is further developed, investigated and applied to truss optimization problems. Partition patterns of the PLOR algorithm are similar to those of DIviding RECTangles (DIRECT), which was widely applied to different real-life problems. However here a set of all Lipschitz constants is reduced to just two: the maximal and the minimal ones. In such a way the PLOR approach is independent of any user-defined parameters and balances equally local and global search during the optimization process. An expanded list of other well-known DIRECT-type algorithms is used in investigation and experimental comparison using the standard test problems and truss optimization problems. The experimental investigation shows that the PLOR algorithm gives very competitive results to other DIRECT-type algorithms using standard test problems and performs pretty well on real truss optimization problems.     

A new global optimization method for a symmetric Lipschitz continuous function and the application to searching for a globally optimal partition of a one-dimensional set

In this paper, we consider a global optimization problem for a symmetric Lipschitz continuous function \(g:[a,b]^k\rightarrow {\mathbb {R}}\), whose domain \([a,b]^k\subset {\mathbb {R}}^k\) consists of k! hypertetrahedrons of the same size and shape, in which function g attains equal values. A global minimum can therefore be searched for in one hypertetrahedron only, but then this becomes a global optimization problem with linear constraints. Apart from that, some known global optimization algorithms in standard form cannot be applied to solving the problem. In this paper, it is shown how this global optimization problem with linear constraints can easily be transformed into a global optimization problem on hypercube \([0,1]^k\), for the solving of which an applied DIRECT algorithm in standard form is possible. This approach has a somewhat lower efficiency than known global optimization methods for symmetric Lipschitz continuous functions (such as SymDIRECT or DISIMPL), but, on the other hand, this method allows for the use of publicly available and well developed computer codes for solving a global optimization problem on hypercube \([0,1]^k\) (e.g. the DIRECT algorithm). The method is illustrated and tested on standard symmetric functions and very demanding center-based clustering problems for the data that have only one feature. An application to the image segmentation problem is also shown.     

Improved scheme for selection of potentially optimal hyper-rectangles in <Emphasis FontCategory="NonProportional">DIRECT</Emphasis>

We consider a box-constrained global optimization problem with a Lipschitz-continuous objective function and an unknown Lipschitz constant. The well known derivative-free global-search DIRECT (DIvide a hyper-RECTangle) algorithm performs well solving such problems. However, the efficiency of the DIRECT algorithm deteriorates on problems with many local optima and when the solution with high accuracy is required. To overcome these difficulties different regimes of global and local search are introduced or the algorithm is combined with local optimization. In this paper we investigate a different direction of improvement of the DIRECT algorithm and propose a new strategy for the selection of potentially optimal rectangles, what does not require any additional parameters or local search subroutines. An extensive experimental investigation reveals the effectiveness of the proposed enhancements.     

Low-rank matrix completion using nuclear norm minimization and facial reduction

We consider a global optimization problem for Lipschitz-continuous functions with an unknown Lipschitz constant. Our approach is based on the well-known DIRECT (DIviding RECTangles) algorithm and motivated by the diagonal partitioning strategy. One of the main advantages of the diagonal partitioning scheme is that the objective function is evaluated at two points at each hyper-rectangle and, therefore, more comprehensive information about the objective function is considered than using the central sampling strategy used in most DIRECT-type algorithms. In this paper, we introduce a new DIRECT-type algorithm, which we call BIRECT (BIsecting RECTangles). In this algorithm, a bisection is used instead of a trisection which is typical for diagonal-based and DIRECT-type algorithms. The bisection is preferable to the trisection because of the shapes of hyper-rectangles, but usual evaluation of the objective function at the center or at the endpoints of the diagonal are not favorable for bisection. In the proposed algorithm the objective function is evaluated at two points on the diagonal equidistant between themselves and the endpoints of a diagonal. This sampling strategy enables reuse of the sampling points in descendant hyper-rectangles. The developed algorithm gives very competitive numerical results compared to the DIRECT algorithm and its well know modifications.     

<Emphasis FontCategory="NonProportional">pyomo.dae</Emphasis>: a modeling and automatic discretization framework for optimization with differential and algebraic equations

We describe pyomo.dae, an open source Python-based modeling framework that enables high-level abstract specification of optimization problems with differential and algebraic equations. The pyomo.dae framework is integrated with the Pyomo open source algebraic modeling language, and is available at http://www.pyomo.org. One key feature of pyomo.dae is that it does not restrict users to standard, predefined forms of differential equations, providing a high degree of modeling flexibility and the ability to express constraints that cannot be easily specified in other modeling frameworks. Other key features of pyomo.dae are the ability to specify optimization problems with high-order differential equations and partial differential equations, defined on restricted domain types, and the ability to automatically transform high-level abstract models into finite-dimensional algebraic problems that can be solved with off-the-shelf solvers. Moreover, pyomo.dae users can leverage existing capabilities of Pyomo to embed differential equation models within stochastic and integer programming models and mathematical programs with equilibrium constraint formulations. Collectively, these features enable the exploration of new modeling concepts, discretization schemes, and the benchmarking of state-of-the-art optimization solvers.     

Numerical Computation of Galois Groups

The Galois/monodromy group of a family of geometric problems or equations is a subtle invariant that encodes the structure of the solutions. We give numerical methods to compute the Galois group and study it when it is not the full symmetric group. One algorithm computes generators, while the other studies its structure as a permutation group. We illustrate these algorithms with examples using a Macaulay2 package we are developing that relies upon Bertini to perform monodromy computations.     

On Einstein extensions of nilpotent metric Lie algebras

The main result of the article is as follows: If a nilpotent noncommutative metric Lie algebra (n, Q) is such that the operator Id ? trace(Ric) / trace(Ric²) Ric is positive definite then every Einstein solvable extension of (n, Q) is standard. We deduce several consequences of this assertion. In particular, we prove that all Einstein solvmanifolds of dimension at most 7 are standard.     

Reverse mathematics,well-quasi-orders,and Noetherian spaces

A quasi-order Q induces two natural quasi-orders on \({\mathcal{P}(Q)}\), but if Q is a well-quasi-order, then these quasi-orders need not necessarily be well-quasi-orders. Nevertheless, Goubault-Larrecq (Proceedings of the 22nd Annual IEEE Symposium 4 on Logic in Computer Science (LICS’07), pp. 453–462, 2007) showed that moving from a well-quasi-order Q to the quasi-orders on \({\mathcal{P}(Q)}\) preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on \({\mathcal{P}(Q)}\) are Noetherian, which means that they contain no infinite strictly descending sequences of closed sets. We analyze various theorems of the form “if Q is a well-quasi-order then a certain topology on (a subset of) \({\mathcal{P}(Q)}\) is Noetherian” in the style of reverse mathematics, proving that these theorems are equivalent to ACA₀ over RCA₀. To state these theorems in RCA₀ we introduce a new framework for dealing with second-countable topological spaces.     

Monoids of non-halting programs with tests

In order to study the axiomatization of the if-then-else construct over possibly non-halting programs and tests, the notion of C-sets was introduced in the literature by considering the tests from an abstract C-algebra. This paper extends the notion of C-sets to C-monoids which include the composition of programs as well as composition of programs with tests. For the class of C-monoids where the C-algebras are adas a canonical representation in terms of functional C-monoids is obtained.     

Solving linear optimization over arithmetic constraint formula

Since Balas extended the classical linear programming problem to the disjunctive programming (DP) problem where the constraints are combinations of both logic AND and OR, many researchers explored this optimization problem under various theoretical or application scenarios such as generalized disjunctive programming (GDP), optimization modulo theories (OMT), robot path planning, real-time systems, etc. However, the possibility of combining these differently-described but form-equivalent problems into a single expression remains overlooked. The contribution of this paper is two folded. First, we convert the linear DP/GDP model, linear-arithmetic OMT problem and related application problems into an equivalent form, referred to as the linear optimization over arithmetic constraint formula (LOACF). Second, a tree-search-based algorithm named RS-LPT is proposed to solve LOACF. RS-LPT exploits the techniques of interval analysis and nonparametric estimation for reducing the search tree and lowering the number of visited nodes. Also, RS-LPT alleviates bad construction of search tree by backtracking and pruning dynamically. We evaluate RS-LPT against two most common DP/GDP methods, three state-of-the-art OMT solvers and the disjunctive transformation based method on optimization benchmarks with different types and scales. Our results favor RS-LPT as compared to existing competing methods, especially for large scale cases.     

Volume in General Metric Spaces

A central question in the geometry of finite metric spaces is how well can an arbitrary metric space be “faithfully preserved” by a mapping into Euclidean space. In this paper we present an algorithmic embedding which obtains a new strong measure of faithful preservation: not only does it (approximately) preserve distances between pairs of points, but also the volume of any set of \(k\) points. Such embeddings are known as volume preserving embeddings. We provide the first volume preserving embedding that obtains constant average volume distortion for sets of any fixed size. Moreover, our embedding provides constant bounds on all bounded moments of the volume distortion while maintaining the best possible worst-case volume distortion. Feige, in his seminal work on volume preserving embeddings defined the volume of a set \(S = \{v_1, \ldots , v_k \}\) of points in a general metric space: the product of the distances from \(v_i\) to \(\{ v_1, \dots , v_{i-1} \}\) , normalized by \(\tfrac{1}{(k-1)!}\) , where the ordering of the points is that given by Prim’s minimum spanning tree algorithm. Feige also related this notion to the maximal Euclidean volume that a Lipschitz embedding of \(S\) into Euclidean space can achieve. Syntactically this definition is similar to the computation of volume in Euclidean spaces, which however is invariant to the order in which the points are taken. We show that a similar robustness property holds for Feige’s definition: the use of any other order in the product affects volume \(^{1/(k-1)}\) by only a constant factor. Our robustness result is of independent interest as it presents a new competitive analysis for the greedy algorithm on a variant of the online Steiner tree problem where the cost of buying an edge is logarithmic in its length. This robustness property allows us to obtain our results on volume preserving embedding.     

Hochschild (co)homology of Yoneda algebras of reconstruction algebras of type A 1

The reconstruction algebra is a generalization of the preprojective algebra, and plays important roles in algebraic geometry and commutative algebra. We consider the homological property of this class of algebras by calculating the Hochschild homology and Hochschild cohomology. Let Λ _t be the Yoneda algebra of a reconstruction algebra of type A ₁ over a field k. In this paper, a minimal projective bimodule resolution of Λ _t is constructed, and the k-dimensions of all Hochschild homology and cohomology groups of Λ _t are calculated explicitly.     

A Quadratically Convergent Algorithm for Structured Low-Rank Approximation

Structured Low-Rank Approximation is a problem arising in a wide range of applications in Numerical Analysis and Engineering Sciences. Given an input matrix \(M\), the goal is to compute a matrix \(M'\) of given rank \(r\) in a linear or affine subspace \(E\) of matrices (usually encoding a specific structure) such that the Frobenius distance \(\left\| M-M' \right\| \) is small. We propose a Newton-like iteration for solving this problem, whose main feature is that it converges locally quadratically to such a matrix under mild transversality assumptions between the manifold of matrices of rank \(r\) and the linear/affine subspace \(E\). We also show that the distance between the limit of the iteration and the optimal solution of the problem is quadratic in the distance between the input matrix and the manifold of rank \(r\) matrices in \(E\). To illustrate the applicability of this algorithm, we propose a Maple implementation and give experimental results for several applicative problems that can be modeled by Structured Low-Rank Approximation: univariate approximate GCDs (Sylvester matrices), low-rank matrix completion (coordinate spaces) and denoising procedures (Hankel matrices).     

Orthogonality in \ell _p-spaces and its bearing on ordered Banach spaces

We introduce a notion of \(p\) -orthogonality in a general Banach space for \(1 \le p \le \infty \) . We use this concept to characterize \(\ell _p\) -spaces among Banach spaces and also among complete order smooth \(p\) -normed spaces as (ordered) Banach spaces with a total \(p\) -orthonormal set (in the positive cone). We further introduce a notion of \(p\) -orthogonal decomposition in order smooth \(p\) -normed spaces. We prove that if the \(\infty \) -orthogonal decomposition holds in an order smooth \(\infty \) -normed space, then the \(1\) -orthogonal decomposition holds in the dual space. We also give an example to show that the above said decomposition may not be unique.     

Branched Polymers and Hyperplane Arrangements

We generalize the construction of connected branched polymers and the notion of the volume of the space of connected branched polymers studied by Brydges and Imbrie (Ann Math, 158:1019–1039, 2003), and Kenyon and Winkler (Am Math Mon, 116(7):612–628, 2009) to any central hyperplane arrangement $\mathcal{A }$ A . The volume of the resulting configuration space of connected branched polymers associated to the hyperplane arrangement $\mathcal{A }$ A is expressed through the value of the characteristic polynomial of $\mathcal{A }$ A at 0. We give a more general definition of the space of branched polymers, where we do not require connectivity, and introduce the notion of q-volume for it, which is expressed through the value of the characteristic polynomial of $\mathcal{A }$ A at $-q$ ? q . Finally, we relate the volume of the space of branched polymers to broken circuits and show that the cohomology ring of the space of branched polymers is isomorphic to the Orlik–Solomon algebra.     

On the measurability of the conic sections’ family in the projective space<Emphasis FontCategory="NonProportional">P</Emphasis><Subscript>3</Subscript><Subscript>3</Subscript>

In this paper we prove that the non degenerate conic sections’ family in the projective spaceP ₃ is measurable.