Isospectral flow method for nonnegative inverse eigenvalue problem with prescribed structure

The nonnegative inverse eigenvalue problem is that given a family of complex numbers λ={λ₁,…,λ_n}, find a nonnegative matrix of order n with spectrum λ. This problem is difficult and remains unsolved partially. In this paper, we focus on its generalization that the reconstructed nonnegative matrices should have some prescribed entries. It is easy to see that this new problem will come back to the common nonnegative inverse eigenvalue problem if there is no constraint of the locations of entries. A numerical isospectral flow method which is developed by hybridizing the optimization theory and steepest descent method is used to study the reconstruction. Moreover, an error estimate of the numerical iteration for ordinary differential equations on the matrix manifold is presented. After that, a numerical method for the nonnegative symmetric inverse eigenvalue problem with prescribed entries and its error estimate are considered. Finally, the approaches are verified by the numerical test results.     

Studying Non-negative Factorizations with Tools from Linear Algebra over a Semiring

We develop the technique useful for studying the problem of factoring nonnegative matrices. We illustrate our method, based on the tools from linear algebra over a semiring, by applying it to studying the problem of existence of a rank-three matrix with full nonnegative rank equal to n.     

Inverse Hyperbolic Problems with Time-Dependent Coefficients

We consider the inverse problem for the second order self-adjoint hyperbolic equation in a bounded domain in R ⁿ with lower order terms depending analytically on the time variable. We prove that, assuming the BLR condition, the time-dependent Dirichlet-to-Neumann operator prescribed on a part of the boundary uniquely determines the coefficients of the hyperbolic equation up to a diffeomorphism and a gauge transformation. As a by-product we prove a similar result for the nonself-adjoint hyperbolic operator with time-independent coefficients.     

A smoothing Newton-type method for solving the <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> spectral estimation problem with lower and upper bounds

This paper discusses the L ₂ spectral estimation problem with lower and upper bounds. To the best of our knowledge, it is unknown if the existing methods for this problem have superlinear convergence property or not. In this paper we propose a nonsmooth equation reformulation for this problem. Then we present a smoothing Newton-type method for solving the resulting system of nonsmooth equations. Global and local superlinear convergence of the proposed method are proved under some mild conditions. Numerical tests show that this method is promising.     

A block coordinate gradient descent method for regularized convex separable optimization and covariance selection

We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ ₁-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated as BCGD) for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n³/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807–1827, 2009; SIAM J Matrix Anal Appl 31:2000–2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for large-scale covariance selection problems with constraints.     

Nonnegative solutions of an elliptic equation with a singular potential

We study the behavior of nonnegative solutions of the Dirichlet problem for a linear elliptic equation with a singular potential in the ball B = B(0,R) ⊂ R ⁿ (n ≥ 3), R ≤ 1. We find an exact condition on the potential ensuring the existence or absence of a nonnegative solution of that problem.     

Parametric Method for Global Optimization

This paper considers constrained and unconstrained parametric global optimization problems in a real Hilbert space. We assume that the gradient of the cost functional is Lipschitz continuous but not smooth. A suitable choice of parameters implies the linear or superlinear (supergeometric) convergence of the iterative method. From the numerical experiments, we conclude that our algorithm is faster than other existing algorithms for continuous but nonsmooth problems, when applied to unconstrained global optimization problems. However, because we solve 2n + 1 subproblems for a large number n of independent variables, our algorithm is somewhat slower than other algorithms, when applied to constrained global optimization.This work was partially supported by the NATO Outreach Fellowship - Mathematics 219.33.We thank Professor Hans D. Mittelmann, Arizona State University, for cooperation and support.     

Constructing integral matrices with given line sums

D. Gale, in 1957 and H.J. Ryser, in 1963, independently proved the famous Gale–Ryser theorem on the existence of (0, 1)–matrices with prescribed row and column sums. Around the same time, in 1968, Mirsky solved the more general problem of finding conditions for the existence of a nonnegative integral matrix with entries less than or equal to p and prescribed row and column sums. Using the results of Mirsky, Brualdi shows that a modified version of the domination condition of Gale–Ryser is still necessary and sufficient for the existence of a matrix under the same constraints. In this article we prove another extension of Gale–Ryser’s domination condition. Furthermore we present a method to build nonnegative integral matrices with entries less than or equal to p and prescribed row and column sums.     

An application of <Emphasis Type="Italic">H</Emphasis>-differentiability to nonnegative and unrestricted generalized complementarity problems

This paper deals with nonnegative nonsmooth generalized complementarity problem, denoted by GCP(f,g). Starting with H-differentiable functions f and g, we describe H-differentials of some GCP functions and their merit functions. We show how, under appropriate conditions on H-differentials of f and g, minimizing a merit function corresponding to f and g leads to a solution of the generalized complementarity problem. Moreover, we generalize the concepts of monotonicity, P ₀-property and their variants for functions and use them to establish some conditions to get a solution for generalized complementarity problem. Our results are generalizations of such results for nonlinear complementarity problem when the underlying functions are C ¹, semismooth, and locally Lipschitzian.     

Marching schemes for inverse acoustic scattering problems

Summary For the numerical solution of inverse Helmholtz problems the boundary value problem for a Helmholtz equation with spatially variable wave number has to be solved repeatedly. For large wave numbers this is a challenge. In the paper we reformulate the inverse problem as an initial value problem, and describe a marching scheme for the numerical computation that needs only n² log n operations on an n × n grid. We derive stability and error estimates for the marching scheme. We show that the marching solution is close to the low-pass filtered true solution. We present numerical examples that demonstrate the efficacy of the marching scheme.     

On the inverse and the dual index of a tree

The inverse of a graph with the spectrum λ ₁, λ ₁, …λ _n (λ ₁≠0) is a graph with the spectrum 1/λ₁,1/λ₂,…,1/λ _n ,.We present a purely graph-theoretic construction of the inverse ol a tree with a perfect matening. We apply this method for deriving results concerning the least nonnegative eigenvalue of a tree (called the dual index of a tree), including the best possible upper bound for the dual index of a tree in terms of a the number of its vertices.     

A conformal mapping algorithm for the Bernoulli free boundary value problem

We propose a new numerical method for the solution of the Bernoulli free boundary value problem for harmonic functions in a doubly connected domain D in where an unknown free boundary Γ₀ is determined by prescribed Cauchy data on Γ₀ in addition to a Dirichlet condition on the known boundary Γ₁. Our main idea is to involve the conformal mapping method as proposed and analyzed by Akduman, Haddar, and Kress for the solution of a related inverse boundary value problem. For this, we interpret the free boundary Γ₀ as the unknown boundary in the inverse problem to construct Γ₀ from the Dirichlet condition on Γ₀ and Cauchy data on the known boundary Γ₁. Our method for the Bernoulli problem iterates on the missing normal derivative on Γ₁ by alternating between the application of the conformal mapping method for the inverse problem and solving a mixed Dirichlet–Neumann boundary value problem in D. We present the mathematical foundations of our algorithm and prove a convergence result. Some numerical examples will serve as proof of concept of our approach. Copyright © 2015 John Wiley & Sons, Ltd.     

关于非负对称矩阵的近似逆矩阵

本文研究了非负对称矩阵的近似逆矩阵问.利用矩阵S=(s_i,j)去近似它的逆矩阵方法,获得了近似误差的一个显式上界,并且证明了近似逆的误差对于很大的n一致地具有阶1/（n-1）².     

Perron's method for second order hyperbolic PDE. Part III

We continue Part I of this paper. Here, in Part III, comparison principles are proved for nonsmooth sub and super solutions (with nonsmooth Cauchy data) of semilinear hyperbolic PDE in compact regular domains of R⁺×R⁺ when n?3, and existence of a nonsmooth solution to the nonsmooth Cauchy problem is proved by a Perron-like method.     

The inverse Fermat–Weber problem

Given n points in the plane with nonnegative weights, the inverse Fermat–Weber problem consists in changing the weights at minimum cost such that a prespecified point in the plane becomes the Euclidean 1-median. The cost is proportional to the increase or decrease of the corresponding weight. In case that the prespecified point does not coincide with one of the given n points, the inverse Fermat–Weber problem can be formulated as linear program. We derive a purely combinatorial algorithm which solves the inverse Fermat–Weber problem with unit cost using O(n) greedy-like iterations where each of them can be done in constant time if the points are sorted according to their slopes. If the prespecified point coincides with one of the given n points, it is shown that the corresponding inverse problem can be written as convex problem and hence is solvable in polynomial time to any fixed precision.     

On the coupling of regularization techniques and the boundary element method for a hemivariational inequality modelling a delamination problem

In this paper, we couple regularization techniques of nondifferentiable optimization with the h‐version of the boundary element method (h‐BEM) to solve nonsmooth variational problems arising in contact mechanics. As a model example, we consider the delamination problem. The variational formulation of this problem leads to a hemivariational inequality with a nonsmooth functional defined on the contact boundary. This problem is first regularized and then discretized by an h‐BEM. We prove convergence of the h‐BEM Galerkin solution of the regularized problem in the energy norm, provide an a priori error estimate and give a numerical examples. Copyright © 2016 John Wiley & Sons, Ltd.     

Inverse median location problems with variable coordinates

Given n points in \mathbbR^d{\mathbb{R}^d} with nonnegative weights, the inverse 1-median problem with variable coordinates consists in changing the coordinates of the given points at minimum cost such that a prespecified point in \mathbbR^d{\mathbb{R}^d} becomes the 1-median. The cost is proportional to the increase or decrease of the corresponding point coordinate. If the distances between points are measured by the rectilinear norm, the inverse 1-median problem is NP{\mathcal{NP}}-hard, but it can be solved in pseudo-polynomial time. Moreover, a fully polynomial time approximation scheme exists in this case. If the point weights are assumed to be equal, the corresponding inverse problem can be reduced to d continuous knapsack problems and is therefore solvable in O(nd) time. In case that the squared Euclidean norm is used, we derive another efficient combinatorial algorithm which solves the problem in O(nd) time. It is also shown that the inverse 1-median problem endowed with the Chebyshev norm in the plane is NP{\mathcal{NP}}-hard. Another pseudo-polynomial algorithm is developed for this case, but it is shown that no fully polynomial time approximation scheme does exist.