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.     

An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization

Powerful response surface methods based on kriging and radial basis function (RBF) interpolation have been developed for expensive, i.e. computationally costly, global nonconvex optimization. We have implemented some of these methods in the solvers rbfSolve and EGO in the TOMLAB Optimization Environment (http://www.tomopt.com/tomlab/). In this paper we study algorithms based on RBF interpolation. The practical performance of the RBF algorithm is sensitive to the initial experimental design, and to the static choice of target values. A new adaptive radial basis interpolation (ARBF) algorithm, suitable for parallel implementation, is presented. The algorithm is described in detail and its efficiency is analyzed on the standard test problem set of Dixon–Szegö. Results show that it outperforms the published results of rbfSolve and several other solvers.     

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.     

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].     

Analysis of algorithms for an online version of the convoy movement problem

In the convoy movement problem (CMP), a set of convoys must be routed from specified origins to destinations in a transportation network, represented by an undirected graph. Two convoys may not cross each other on the same edge while travelling in opposing directions, a restriction referred to as blocking. However, convoys are permitted to follow each other on the same edge, with a specified headway separating them, but no overtaking is permitted. Further, the convoys to be routed are distinguished based on their length. Particle convoys have zero length and are permitted to traverse an edge simultaneously, whereas convoys with non-zero length have to follow each other, observing a headway. The objective is to minimize the total time taken by convoys to travel from their origins to their destinations, given the travel constraints on the edges. We consider an online version of the CMP where convoy demands arise dynamically over time. For the special case of particle convoys, we present an algorithm that has a competitive ratio of 3 in the worst case and (5/2) on average. For the particle convoy problem, we also present an alternate, randomized algorithm that provides a competitive ratio of (√13?1). We then extend the results to the case of convoys with length, which leads to an algorithm with an O(T+CL) competitive ratio, where T={Max _e t(e)}/{Min _e t(e)}, C is the maximum congestion (the number of distinct convoy origin–destination pairs that use any edge e) and L={Max _c L(c)}/{Min _c L(c)}; here L(c)>0 represents the time-headway to be observed by any convoy that follows c and t(e) represents the travel time for a convoy c on edge e.     

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.     

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 FFTRR-based fast direct algorithms for complex inhomogeneous biharmonic problems with applications to incompressible flows

We develop analysis-based fast and accurate direct algorithms for several biharmonic problems in a unit disk derived directly from the Green’s functions of these problems and compare the numerical results with the “decomposition” algorithms (see Ghosh and Daripa, IMA J. Numer. Anal. 36(2), 824–850 [17]) in which the biharmonic problems are first decomposed into lower order problems, most often either into two Poisson problems or into two Poisson problems and a homogeneous biharmonic problem. One of the steps in the “decomposition algorithm” as discussed in Ghosh and Daripa (IMA J. Numer. Anal. 36(2), 824–850 [17]) for solving certain biharmonic problems uses the “direct algorithm” without which the problem can not be solved. Using classical Green’s function approach for these biharmonic problems, solutions of these problems are represented in terms of singular integrals in the complex z?plane (the physical plane) involving explicitly the boundary conditions. Analysis of these singular integrals using FFT and recursive relations (RR) in Fourier space leads to the development of these fast algorithms which are called FFTRR based algorithms. These algorithms do not need to do anything special to overcome coordinate singularity at the origin as often the case when solving these problems using finite difference methods in polar coordinates. These algorithms have some other desirable properties such as the ease of implementation and parallel in nature by construction. Moreover, these algorithms have O(logN) complexity per grid point where N ² is the total number of grid points and have very low constant behind this order estimate of the complexity. Performance of these algorithms is shown on several test problems. These algorithms are applied to solving viscous flow problems at low and moderate Reynolds numbers and numerical results are presented.     

A note on commuting automorphisms of some finite <Emphasis Type="Italic">p</Emphasis>-groups

An automorphism α of a group G is called a commuting automorphism if each element x in G commutes with its image α(x) under α. Let A(G) denote the set of all commuting automorphisms of G. Rai [Proc. Japan Acad., Ser. A 91 (5), 57–60 (2015)] has given some sufficient conditions on a finite p-group G such that A(G) is a subgroup of Aut(G) and, as a consequence, has proved that, in a finite p-group G of co-class 2, where p is an odd prime, A(G) is a subgroup of Aut(G). We give here very elementary and short proofs of main results of Rai.     

The limit absorption principle and homogenization procedure for periodic elliptic operators

For a periodic matrix elliptic operator \(A_\varepsilon \) with (x ?-dependent) rapidly oscillating coefficients, a certain analog of the limit absorption principle is proved. It is shown that the bordered resolvent 〈x〉^?1/2?· (\(A_\varepsilon \) ? (η ± i? ^σ )I)^?1〈x〉^?1/2?· has a limit in the operator norm in L ₂ as ? → 0 provided that η > 0, · > 0, and 0 < σ < 1/2.     

Globally convergent Jacobi methods for positive definite matrix pairs

The paper derives and investigates the Jacobi methods for the generalized eigenvalue problem A x = λ B x, where A is a symmetric and B is a symmetric positive definite matrix. The methods first “normalize” B to have the unit diagonal and then maintain that property during the iterative process. The global convergence is proved for all such methods. That result is obtained for the large class of generalized serial strategies from Hari and Begovi? Kova? (Trans. Numer. Anal. (ETNA) 47, 107–147, 2017). Preliminary numerical tests confirm a high relative accuracy of some of those methods, provided that both matrices are positive definite and the spectral condition numbers of Δ _A AΔ _A and Δ _B BΔ _B are small, for some nonsingular diagonal matrices Δ _A and Δ _B .     

New error bounds for linear complementarity problems of Nekrasov matrices and <Emphasis Type="Italic">B</Emphasis>-Nekrasov matrices

New error bounds for the linear complementarity problems are given respectively when the involved matrices are Nekrasov matrices and B-Nekrasov matrices. Numerical examples are given to show that the new bounds are better respectively than those provided by García-Esnaola and Peña (Numer. Algor. 67(3), 655–667, 2014 and Numer. Algor. 72(2), 435–445, 2016) in some cases.     

On derivation of Euler–Lagrange equations for incompressible energy-minimizers

We prove that any distribution q satisfying the grad-div system \({\nabla q={\rm div}\,{\bf f}}\) for some tensor \({{\bf f}=(f^i_j), \,f^i_j\in h^r(U)\,(1\leq r < \infty}\)) -the local Hardy space; q is in h ^r and q is locally represented by the sum of singular integrals of \({f^i_j}\) with Calderón-Zygmund kernel. As a consequence, we prove the existence and the local representation of the hydrostatic pressure p (modulo constant) associated with incompressible elastic energy-minimizing deformation u satisfying \({|\nabla{\bf u}|^2,\,|{\rm cof}\,\nabla{\bf u}|^2\in h^1}\). We also derive the system of Euler–Lagrange equations for volume preserving local minimizers u that are in the space \({K^{1,3}_{\rm loc}}\) [defined in (1.2)]—partially resolving a long standing problem. In two dimensions we prove partial C ^1,α regularity of weak solutions provided their gradient is in L ³ and p is Hölder continuous.     

Variations of Landau’s theorem for p-regular and p-singular conjugacy classes

The well-known Landau’s theorem states that, for any positive integer k, there are finitely many isomorphism classes of finite groups with exactly k (conjugacy) classes. We study variations of this theorem for p-regular classes as well as p-singular classes. We prove several results showing that the structure of a finite group is strongly restricted by the number of p-regular classes or the number of p-singular classes of the group. In particular, if G is a finite group with O_p(G) = 1 then |G/F(G)|_p' is bounded in terms of the number of p-regular classes of G. However, it is not possible to prove that there are finitely many groups with no nontrivial normal p-subgroup and kp-regular classes without solving some extremely difficult number-theoretic problems (for instance, we would need to show that the number of Fermat primes is finite).     

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.     

Invariant generalized ideal classes – structure theorems for <Emphasis Type="BoldItalic">p</Emphasis>-class groups in <Emphasis Type="BoldItalic">p</Emphasis>-extensions

We give, in sections 2 and 3, an english translation of: Classes généralisées invariantes, J. Math. Soc. Japan, 46, 3 (1994), with some improvements and with notations and definitions in accordance with our book: Class Field Theory: From Theory to Practice, SMM, Springer-Verlag, 2nd corrected printing 2005. We recall, in section 4, some structure theorems for finite \(\mathbb {Z}_{p}[G]\)-modules (\(G \simeq \mathbb {Z}/p\,\mathbb {Z}\)) obtained in: Sur les ?-classes d’idéaux dans les extensions cycliques relatives de degré premier ?, Annales de l’Institut Fourier, 23, 3 (1973). Then we recall the algorithm of local normic computations which allows to obtain the order and (potentially) the structure of a p-class group in a cyclic extension of degree p. In section 1973, we apply this to the study of the structure of relative p-class groups of Abelian extensions of prime to p degree, using the Thaine–Ribet–Mazur–Wiles–Kolyvagin ‘principal theorem’, and the notion of ‘admissible sets of prime numbers’ in a cyclic extension of degree p, from: Sur la structure des groupes de classes relatives, Annales de l’Institut Fourier, 43, 1 (1993). In conclusion, we suggest the study, in the same spirit, of some deep invariants attached to the p-ramification theory (as dual form of non-ramification theory) and which have become standard in a p-adic framework. Since some of these techniques have often been rediscovered, we give a substantial (but certainly incomplete) bibliography which may be used to have a broad view on the subject.     

On Measure Contraction Property without Ricci Curvature Lower Bound

Measure contraction properties M C P (K, N) are synthetic Ricci curvature lower bounds for metric measure spaces which do not necessarily have smooth structures. It is known that if a Riemannian manifold has dimension N, then M C P (K, N) is equivalent to Ricci curvature bounded below by K. On the other hand, it was observed in Rifford (Math. Control Relat. Fields 3(4), 467–487 2013) that there is a family of left invariant metrics on the three dimensional Heisenberg group for which the Ricci curvature is not bounded below. Though this family of metric spaces equipped with the Harr measure satisfy M C P (0,5). In this paper, we give sufficient conditions for a 2n+1 dimensional weakly Sasakian manifold to satisfy M C P (0, 2n + 3). This extends the above mentioned result on the Heisenberg group in Rifford (Math. Control Relat. Fields 3(4), 467–487 2013).     

Eigenvalue estimates for submanifolds with bounded <Emphasis Type="BoldItalic">f</Emphasis>-mean curvature

In this paper, we obtain an extrinsic low bound to the first non-zero eigenvalue of the f-Laplacian on complete noncompact submanifolds of the weighted Riemannian manifold (H ^m (?1),e^?f dv) with respect to the f-mean curvature. In particular, our results generalize those of Cheung and Leung in Math. Z. 236 (2001) 525–530.     

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.     

Spectral properties for layer potentials associated to the Stokes equation in Lipschitz domains

In this paper, we consider the spectral properties of the double layer potentials K and \({\tilde{K}}\) related to the traction boundary value problem and the slip boundary value problem, respectively, of the Stokes equations in a bounded Lipschitz domain Ω in R ⁿ . We show the invertibility of λI ? K and \({\lambda I - \tilde{K}}\) in L ²(?Ω) for \({\lambda \in {\bf R}{\setminus} [-\frac 12, \frac12]}\). As an application, we study the transmission problems of the Stokes equations.