ADMM for the SDP relaxation of the QAP

Semidefinite programming, SDP, relaxations have proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem, QAP, arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the current primal–dual interior point solvers in terms of both time and accuracy; and difficulty and high expense in adding cutting plane constraints. We propose using the alternating direction method of multipliers ADMM in combination with facial reduction, FR, to solve the SDP relaxation. This first order approach allows for: inexpensive iterations, a method of cheaply obtaining low rank solutions; and a trivial way of exploiting the FR for adding cutting plane inequalities. In fact, we solve the doubly nonnegative, DNN, relaxation that includes both the SDP and all the nonnegativity constraints. When compared to current approaches and current best available bounds we obtain robustness, efficiency and improved bounds.     

Some matrix functional equations

We investigate the pair of matrix functional equations G(x)F(y) = G(xy) and G(x)G(y) = F(y/x), featuring the two independent scalar variables x and y and the two N×N matrices F(z) andG(z) (with N an arbitrary positive integer and the elements of these two matrices functions of the scalar variable z). We focus on the simplest class of solutions, i.e., on matrices all of whose elements are analytic functions of the independent variable. While in the scalar (N = 1) case this pair of functional equations only possess altogether trivial constant solutions, in the matrix (N > 1) case there are nontrivial solutions. These solutions satisfy the additional pair of functional equations F(x)G(y) = G(y/x) andF(x)F(y) = F(xy), and an endless hierarchy of other functional equations featuring more than two independent variables.     

Searching for a Best Least Absolute Deviations Solution of an Overdetermined System of Linear Equations Motivated by Searching for a Best Least Absolute Deviations Hyperplane on the Basis of Given Data

We consider the problem of searching for a best LAD-solution of an overdetermined system of linear equations Xa=z, X∈?^m×n, m≥n, \(\mathbf{a}\in \mathbb{R}^{n}, \mathbf {z}\in\mathbb{R}^{m}\). This problem is equivalent to the problem of determining a best LAD-hyperplane x?a ^T x, x∈? ⁿ on the basis of given data \((\mathbf{x}_{i},z_{i}), \mathbf{x}_{i}= (x_{1}^{(i)},\ldots,x_{n}^{(i)})^{T}\in \mathbb{R}^{n}, z_{i}\in\mathbb{R}, i=1,\ldots,m\), whereby the minimizing functional is of the form

$F(\mathbf{a})=\|\mathbf{z}-\mathbf{Xa}\|_1=\sum_{i=1}^m|z_i-\mathbf {a}^T\mathbf{x}_i|.$

An iterative procedure is constructed as a sequence of weighted median problems, which gives the solution in finitely many steps. A criterion of optimality follows from the fact that the minimizing functional F is convex, and therefore the point a ^?∈? ⁿ is the point of a global minimum of the functional F if and only if 0∈?F(a ^?).

Motivation for the construction of the algorithm was found in a geometrically visible algorithm for determining a best LAD-plane (x,y)?αx+βy, passing through the origin of the coordinate system, on the basis of the data (x _i ,y _i ,z _i ),i=1,…,m.     

Rings of h-deformed differential operators

We describe the center of the ring Diff _h (n) of h-deformed differential operators of type A. We establish an isomorphism between certain localizations of Diff _h (n) and the Weyl algebra W _n , extended by n indeterminates.     

The commutator in equivalential algebras and Fregean varieties

A class \({\mathcal {K}}\) of algebras with a distinguished constant term 0 is called Fregean if congruences of algebras in \({\mathcal {K}}\) are uniquely determined by their 0-cosets and Θ _A (0, a) = Θ _A (0, b) implies a = b for all \({a, b \in {\bf A} \in \mathcal {K}}\) . The structure of Fregean varieties was investigated in a paper by P. Idziak, K. S?omczyńska, and A. Wroński. In particular, it was shown there that every congruence permutable Fregean variety consists of algebras that are expansions of equivalential algebras, i.e., algebras that form an algebraization of the purely equivalential fragment of the intuitionistic propositional logic. In this paper we give a full characterization of the commutator for equivalential algebras and solvable Fregean varieties. In particular, we show that in a solvable algebra from a Fregean variety, the commutator coincides with the commutator of its purely equivalential reduct. Moreover, an intrinsic characterization of the commutator in this setting is given.     

On the existence of strips inside domains convex in one direction

A plane domain Ω is convex in the positive direction if for every ω ∈ Ω, the entire half-line {ω + t: t ≥ 0} is contained in Ω. Suppose that h maps the unit disk onto such a domain Ω with the normalization h(0) = 0 and lim_t→∞h^?1(h(z) + t) = 1. We show that if ∠lim_z→?1 Re h(z) = ?∞ and ∠lim_z→?1(1 + z)h′(z) = ν ∈ (0, +∞), then Ω contains a maximal horizontal strip of width πν. We also prove a converse statement. These results provide a solution to a problem posed by Elin and Shoikhet in connection with semigroups of holomorphic functions.     

Congruence by Dissection of Topological Discs—An Elementary Approach to Tarski's Circle Squaring Problem

Let G be a group of affine transformations of the plane R ² and let the family F consist of all topological discs in R ² whose boundary is subject to some smoothness condition (general, rectifiable, piecewise C ¹ , piecewise C ² ). Are any two members D,E ∈ F congruent by dissection with respect to G such that all the pieces in the corresponding dissections of D and E belong to F as well? We give an affirmative answer if G contains all affine transformations and F consists of the discs whose boundary is piecewise C ¹ . An example shows that C ¹ cannot be replaced by C ² . Moreover, if G is either the group of equiaffine transformations or the group of similarities, then congruence by dissection of two convex discs D and E turns out to be essentially equivalent to congruence by dissection of the boundaries bd(D ) and bd(E ).     

Geometric Realizations of Lusztig’s Symmetries of Symmetrizable Quantum Groups

Let U be the quantum group and f be the Lusztig’s algebra associated with a symmetrizable generalized Cartan matrix. The algebra f can be viewed as the positive part of U. Lusztig introduced some symmetries T _i on U for all i ∈ I. Since T _i (f) is not contained in f, Lusztig considered two subalgebras _i f and ⁱ f of f for any i ∈ I, where _i f={x ∈ f | T _i (x) ∈ f} and \({^{i}\mathbf {f}}=\{x\in \mathbf {f}\,\,|\,\,T^{-1}_{i}(x)\in \mathbf {f}\}\). The restriction of T _i on _i f is also denoted by \(T_{i}:{_{i}\mathbf {f}}\rightarrow {^{i}\mathbf {f}}\). The geometric realization of f and its canonical basis are introduced by Lusztig via some semisimple complexes on the variety consisting of representations of the corresponding quiver. When the generalized Cartan matrix is symmetric, Xiao and Zhao gave geometric realizations of Lusztig’s symmetries in the sense of Lusztig. In this paper, we shall generalize this result and give geometric realizations of _i f, ⁱ f and \(T_{i}:{_{i}\mathbf {f}}\rightarrow {^{i}\mathbf {f}}\) by using the language ’quiver with automorphism’ introduced by Lusztig.     

On the homotopy type of (<Emphasis Type="Italic">n</Emphasis>-1)-connected (3<Emphasis Type="Italic">n</Emphasis>+1)-dimensional free chain Lie algebra

Let R be a subring ring of Q. We reserve the symbol p for the least prime which is not a unit in R; if R ?Q, then p=∞. Denote by DGL _n ^np , n≥1, the category of (n-1)-connected np-dimensional differential graded free Lie algebras over R. In [1] D. Anick has shown that there is a reasonable concept of homotopy in the category DGL _n ^np . In this work we intend to answer the following two questions: Given an object (L(V), ?) in DGL _n ³ⁿ⁺² and denote by S(L(V), ?) the class of objects homotopy equivalent to (L(V), ?). How we can characterize a free dgl to belong to S(L(V), ?)? Fix an object (L(V), ?) in DGL _n ³ⁿ⁺² . How many homotopy equivalence classes of objects (L(W), δ) in DGL _n ³ⁿ⁺² such that H _* (W, d′)?H _* (V, d) are there? Note that DGL _n ³ⁿ⁺² is a subcategory of DGL _n ^np when p>3. Our tool to address this problem is the exact sequence of Whitehead associated with a free dgl.     

Non-low<Subscript>2</Subscript>-ness and computable Lipschitz reducibility

In this paper, we prove that if a c.e. Turing degree d is non-low₂, then there are two left-c.e. reals β ₀, β ₁ in d, such that, if β ₀ is wtt-reducible to a left-c.e. real α, then β ₁ is not computable Lipschitz (cl-) reducible to α. As a corollary, d contains a left-c.e. real which is not cl-reducible to any complex (wtt-complete) left-c.e. real.     

<Emphasis Type="Bold">K</Emphasis><Subscript>0</Subscript> of Semiartinian Von Neumann Regular Rings. Direct Finiteness Versus Unit-Regularity

If R is a regular and semiartinian ring, it is proved that the following conditions are equivalent: (1) R is unit-regular, (2) every factor ring of R is directly finite, (3) the abelian group K _O(R) is free and admits a basis which is in a canonical one to one correspondence with a set of representatives of simple right R-modules. For the class of semiartinian and unit-regular rings the canonical partial order of K _O(R) is investigated. Starting from any partially ordered set I, a special dimension group G(I) is built and a large class of semiartinian and unit-regular rings is shown to have the corresponding K _O(R) order isomorphic to G(P r i m _R ), where P r i m _R is the primitive spectrum of R. Conversely, if I is an artinian partially ordered set having a finite cofinal subset, it is proved that the dimension group G(I) is realizable as K _O(R) for a suitable semiartinian and unit-regular ring R.     

Bounds for the number of points on curves over finite fields

Let U be a bounded open subset of ?^d, d ≥ 2 and f ∈ C(?U). The Dirichlet solution f^CU of the Dirichlet problem associated with the Laplace equation with a boundary condition f is not continuous on the closure ū of U in general if U is not regular but it is always Baire-one.Let H(U) be the space of all functions continuous on the closure ū and harmonic on U and F(H(U)) be the space of uniformly bounded absolutely convergent series of functions in H(U). We prove that f^CU can be obtained as a uniform limit of a sequence of functions in F(H(U)). Thus f^CU belongs to the subclass B_1/2 of Baire-one functions studied for example in [8]. This is not only an improvement of the result obtained in [10] but it also shows that the Dirichlet solution on the closure ū can share better properties than to be only a Baire-one function. Moreover, our proof is more elementary than that in [10].A generalization to the abstract context of simplicial function space on a metrizable compact space is provided.We conclude the paper with a brief discussion on the solvability of the abstract Dirichlet problem with a boundary condition belonging to the space of differences of bounded semicontinuous functions complementing the results obtained in [17].     

Calculation of Geometric Probabilities Using Covariogram of Convex Bodies

In the paper, a formula to calculate the probability that a random segment L(ω, u) in R ⁿ with a fixed direction u and length l lies entirely in the bounded convex body D ? R ⁿ (n ≥ 2) is obtained in terms of covariogram of the body D. For any dimension n ≥ 2, a relationship between the probability P(L(ω, u) ? D) and the orientation-dependent chord length distribution is also obtained. Using this formula, we obtain the explicit form of the probability P(L(ω, u) ? D) in the cases where D is an n-dimensional ball (n ≥ 2), or a regular triangle on the plane.     

Equations in finite fields with restricted solution sets. I (Character sums)

In earlier papers, for “large” (but otherwise unspecified) subsets A, B of Z _p and for h(x) ∈ Z _p [x], Gyarmati studied the solvability of the equations a + b = h(x), resp. ab = h(x) with a ∈ A, b ∈ B, x ∈ Z _p , and for large subsets A, B, C, D of Z _p Sárközy showed the solvability of the equations a + b = cd, resp. ab + 1 = cd with a ∈ A, b ∈ B, c ∈ C, d ∈ D. In this series of papers equations of this type will be studied in finite fields. In particular, in Part I of the series we will prove the necessary character sum estimates of independent interest some of which generalize earlier results.     

Curvature inequalities for operators of the Cowen–Douglas class

Let T be an operator tuple in the Cowen–Douglas class B _n (Ω) for Ω ? C ^m . The kernels Ker(T ? w) ^l , for w ∈ Ω, l = 1, 2, ···, define Hermitian vector bundles E _T ^l over Ω. We prove certain negativity of the curvature of E _T ^l . We also study the relation between certain curvature inequality and the contractive property of T when Ω is a planar domain.     

A sharp eigenvalue theorem for fractional elliptic equations

The invisibility graph I(X) of a set X ? R ^d is a (possibly infinite) graph whose vertices are the points of X and two vertices are connected by an edge if and only if the straight-line segment connecting the two corresponding points is not fully contained in X. We consider the following three parameters of a set X: the clique number ω(I(X)), the chromatic number χ(I(X)) and the convexity number γ(X), which is the minimum number of convex subsets of X that cover X.We settle a conjecture of Matou?ek and Valtr claiming that for every planar set X, γ(X) can be bounded in terms of χ(I(X)). As a part of the proof we show that a disc with n one-point holes near its boundary has χ(I(X)) ≥ log log(n) but ω(I(X)) = 3.We also find sets X in R⁵ with χ(X) = 2, but γ(X) arbitrarily large.     

Estimates for Wallis’ ratio and related functions

We present improvements of approximation formula for Wallis ratio related to a class of inequalities stated in [D.-J. Zhao, On a two-sided inequality involving Wallis’s formula, Math. Practice Theory, 34 (2004), 166-168], [Y. Zhao and Q. Wu, Wallis inequality with a parameter, J. Inequal. Pure Appl. Math., 7(2) (2006), Art. 56] and [C. Mortici, Completely monotone functions and the Wallis ratio, Applied Mathematics Letters, 25 (2012), 717-722]. Some sharp inequalities are obtained as a result of monotonicity of some functions involving gamma function.     

On Ramanujan sums over the Gaussian integers

This note deals with Ramanujan sums c _m (n) over the ring ?[i], in particular with asymptotics for sums of c _m (n) taken over both variables m, n.     

Bounded Equivalence of Hull Classes in Archimedean Lattice-Ordered Groups with Unit

A hull class in a category is an object class H for which each object has a unique minimal essential extension in H. This paper addresses the enormity of the collection of hull classes in the category W of Archimedean l-groups with distinguished weak order unit through consideration of the action on the hull classes of the bounded coreflection \(\textbf {W} \overset {B}\rightarrow \textbf {W}^{\ast }\) onto the subcategory where the units are strong. It is shown that hull classes go forth under B and back under B ^?1, that the B-equivalence class of a hull class in W always has a top, and that these B-equivalence classes are frequently not sets. The property “top” is related to various other properties that hull classes might have. This paper is the third by us on the complex taxonomy of hull classes in W, and more are planned.     

Cartesian Closed Extensions of Subcategories of CONT

In this paper we give a uniform way of proving cartesian closedness for many new subcategories of continuous posets. We define C-P to be the category of continuous posets whose D–completions are isomorphic to objects from C, where C is a subcategory of the category CONT of domains. The main result is that if C is a cartesian closed full subcategory of ALG _⊥ or BC, then C-P is also a cartesian closed subcategory of the category CONTP of continuous posets and Scott continuous functions. In particular, we have the following cartesian closed categories : BC-P, LAT-P, aL-P, aBC-P, B-P, aLAT-P, ω -B-P, ω -aLAT-P, etc.