D.C. programming approach for multicommodity network optimization problems with step increasing cost functions

We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x ^* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x^*)-LB)/{f(x^*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained.     

Fast generalized cross validation using Krylov subspace methods

The task of fitting smoothing spline surfaces to meteorological data such as temperature or rainfall observations is computationally intensive. The generalized cross validation (GCV) smoothing algorithm, if implemented using direct matrix techniques, is O(n ³) computationally, and memory requirements are O(n ²). Thus, for data sets larger than a few hundred observations, the algorithm is prohibitively slow. The core of the algorithm consists of solving series of shifted linear systems, and iterative techniques have been used to lower the computational complexity and facilitate implementation on a variety of supercomputer architectures. For large data sets though, the execution time is still quite high. In this paper we describe a Lanczos based approach that avoids explicitly solving the linear systems and dramatically reduces the amount of time required to fit surfaces to sets of data.      

Resolvent estimates in W−1,p related to strongly coupled‐linear parabolic systems with coupled nonsmooth capacities

We investigate linear parabolic systems with coupled nonsmooth capacities and mixed boundary conditions. We prove generalized resolvent estimates in W^{?1, p} spaces. The method is an appropriate modification of a technique introduced by Agmon to obtain L^p estimates for resolvents of elliptic differential operators in the case of smooth boundary conditions. Moreover, we establish an existence and uniqueness result. Copyright © 2007 John Wiley & Sons, Ltd.     

Inner Generalized Inverses with Prescribed Idempotents

We define and characterize inner generalized inverses with prescribed idempotents. These classes of generalized inverses are natural algebraic extension of generalized inverses of linear operators with prescribed range and kernel. We consider the reverse order rule for inner generalized inverses of elements of a ring, some perturbation bounds, and we construct an iterative method for computing a (p, q)-inner inverse in Banach algebras.     

Linear problem of tracking a given motion under an integral constraint on control

We consider the problem of optimally tracking a given vector function by means of a generalized projection of the trajectory of a linear controlled object with an integral constraint on the control. The deviation from a given motion is measured in the metric of the space C ^m [0, T] of continuous vector functions of appropriate dimension m. We describe a constructive method for solving this optimization problem with a given accuracy.     

Generalized delaunay triangulation for planar graphs

We introduce the notion of generalized Delaunay triangulation of a planar straight-line graphG=(V, E) in the Euclidean plane and present some characterizations of the triangulation. It is shown that the generalized Delaunay triangulation has the property that the minimum angle of the triangles in the triangulation is maximum among all possible triangulations of the graph. A general algorithm that runs inO(|V|²) time for computing the generalized Delaunay triangulation is presented. When the underlying graph is a simple polygon, a divide-and-conquer algorithm based on the polygon cutting theorem of Chazelle is given that runs inO(|V| log |V|) time.Supported in part by the National Science Foundation under Grants DCR 8420814 and ECS 8340031.     

Gr?bner bases in difference-differential modules and difference-differential dimension polynomials

In this paper we extend the theory of Gr?bner bases to difference-differential modules and present a new algorithmic approach for computing the Hilbert function of a finitely generated difference-differential module equipped with the natural filtration. We present and verify algorithms for constructing these Gr?bner bases counterparts. To this aim we introduce the concept of “generalized term order” on ℕ ^m ×ℤ ⁿ and on difference-differential modules. Using Gr?bner bases on difference-differential modules we present a direct and algorithmic approach to computing the difference-differential dimension polynomials of a difference-differential module and of a system of linear partial difference-differential equations. This work was supported by the National Natural Science Foundation of China (Grant No. 60473019) and the KLMM (Grant No. 0705)     

On a linear problem of tracing a given motion

In the present paper, we consider the problem on the optimal tracing of a given vector function with the use of a generalized projection of the trajectory of a linear plant. The deviation of a given motion is measured in the metric C ^m [0, T] of continuous vector functions of the corresponding dimension m. We suggest an efficient method for the construction of an approximate solution of this optimization problem with given accuracy.     

Limiting subgradients of minimal time functions in Banach spaces

The paper mostly concerns the study of generalized differential properties of the so-called minimal time functions associated, in particular, with constant dynamics and arbitrary closed target sets in control theory. Functions of this type play a significant role in many aspects of optimization, control theory, and Hamilton–Jacobi partial differential equations. We pay the main attention to computing and estimating limiting subgradients of the minimal value functions and to deriving the corresponding relations for Fréchet type ε-subgradients in arbitrary Banach spaces.     

Randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen–Loève expansion

We describe randomized algorithms for computing the dominant eigenmodes of the generalized Hermitian eigenvalue problem Ax = λBx, with A Hermitian and B Hermitian and positive definite. The algorithms we describe only require forming operations Ax,Bx and B^?1x and avoid forming square roots of B (or operations of the form, B^1/2x or B^?1/2x). We provide a convergence analysis and a posteriori error bounds and derive some new results that provide insight into the accuracy of the eigenvalue calculations. The error analysis shows that the randomized algorithm is most accurate when the generalized singular values of B^?1A decay rapidly. A randomized algorithm for the generalized singular value decomposition is also provided. Finally, we demonstrate the performance of our algorithm on computing an approximation to the Karhunen–Loève expansion, which involves a computationally intensive generalized Hermitian eigenvalue problem with rapidly decaying eigenvalues. Copyright © 2015 John Wiley & Sons, Ltd.     

SUPERCRITICAL SEMILINEAR WAVE EQUATION WITH NON-NEGATIVE POTENTIAL

We prove a weighted L ^∞ estimate for the solution to the linear wave equation with a smooth positive time independent potential. The proof is based on application of generalized Fourier transform for the perturbed Laplace operator and a finite dependence domain argument. We apply this estimate to prove the existence of global small data solution to supercritical semilinear wave equations with potential.     

Cutting Plane Algorithms for Nonlinear Semi-Definite Programming Problems with Applications

We will propose an outer-approximation (cutting plane) method for minimizing a function f X subject to semi-definite constraints on the variables XR ⁿ. A number of efficient algorithms have been proposed when the objective function is linear. However, there are very few practical algorithms when the objective function is nonlinear. An algorithm to be proposed here is a kind of outer-approximation(cutting plane) method, which has been successfully applied to several low rank global optimization problems including generalized convex multiplicative programming problems and generalized linear fractional programming problems, etc. We will show that this algorithm works well when f is convex and n is relatively small. Also, we will provide the proof of its convergence under various technical assumptions.     

GLMMLasso: An Algorithm for High-Dimensional Generalized Linear Mixed Models Using ℓ1-Penalization

We propose an ?₁-penalized algorithm for fitting high-dimensional generalized linear mixed models (GLMMs). GLMMs can be viewed as an extension of generalized linear models for clustered observations. Our Lasso-type approach for GLMMs should be mainly used as variable screening method to reduce the number of variables below the sample size. We then suggest a refitting by maximum likelihood based on the selected variables only. This is an effective correction to overcome problems stemming from the variable screening procedure that are more severe with GLMMs than for generalized linear models. We illustrate the performance of our algorithm on simulated as well as on real data examples. Supplementary materials are available online and the algorithm is implemented in the R package glmmixedlasso.     

An efficient algorithm for the three-dimensional diameter problem

We explore a new approach for computing the diameter of n points in \Bbb R ³ that is based on the restriction of the furthest-point Voronoi diagram to the convex hull. We show that the restricted Voronoi diagram has linear complexity. We present a deterministic algorithm with O(nlog ² n) running time. The algorithm is quite simple and is a good candidate to be implemented in practice. Using our approach the chromatic diameter and all-furthest neighbors in \Bbb R ³ can be found in the same running time. Received February 18, 2000, and in revised form June 27, 2000. Online publication January 17, 2001.     

Computing Eigenelements of Real Symmetric Matrices via Optimization

In certain circumstances, it is advantageous to use an optimization approach in order to solve the generalized eigenproblem, Ax = Bx, where A and B are real symmetric matrices and B is positive definite. In particular, this is the case when the matrices A and B are very large the computational cost, prohibitive, of solving, with high accuracy, systems of equations involving these matrices. Usually, the optimization approach involves optimizing the Rayleigh quotient.We first propose alternative objective functions to solve the (generalized) eigenproblem via (unconstrained) optimization, and we describe the variational properties of these functions.We then introduce some optimization algorithms (based on one of these formulations) designed to compute the largest eigenpair. According to preliminary numerical experiments, this work could lead the way to practical methods for computing the largest eigenpair of a (very) large symmetric matrix (pair).     

Nonsingular systems of generalized Sylvester equations: An algorithmic approach

We consider the uniqueness of solution (i.e., nonsingularity) of systems of r generalized Sylvester and ?‐Sylvester equations with n×n coefficients. After several reductions, we show that it is sufficient to analyze periodic systems having, at most, one generalized ?‐Sylvester equation. We provide characterizations for the nonsingularity in terms of spectral properties of either matrix pencils or formal matrix products, both constructed from the coefficients of the system. The proposed approach uses the periodic Schur decomposition and leads to a backward stable O(n³r) algorithm for computing the (unique) solution.     

A second-order accurate numerical method for a fractional wave equation

We study a generalized Crank–Nicolson scheme for the time discretization of a fractional wave equation, in combination with a space discretization by linear finite elements. The scheme uses a non-uniform grid in time to compensate for the singular behaviour of the exact solution at t = 0. With appropriate assumptions on the data and assuming that the spatial domain is convex or smooth, we show that the error is of order k ² + h ², where k and h are the parameters for the time and space meshes, respectively.     

Computation of certain continuous integrals in the space of continuous functions defined on a compact set

We give formulas for computing integrals of functionals that are functions of linear and quadratic functionals with respect to generalized Wiener measure in the sense of J. Kuelbs in the space of continuous functions defined on a compact set.Translated fromMatematicheskie Melody i Fiziko-Mekhanicheskie Polya, Issue 34, 1991, pp. 35–39.     

On the Generalized Drazin Inverse and Generalized Resolvent

We investigate the generalized Drazin inverse and the generalized resolvent in Banach algebras. The Laurent expansion of the generalized resolvent in Banach algebras is introduced. The Drazin index of a Banach algebra element is characterized in terms of the existence of a particularly chosen limit process. As an application, the computing of the Moore-Penrose inverse in >C ^*-algebras is considered. We investigate the generalized Drazin inverse as an outer inverse with prescribed range and kernel. Also, 2 × 2 operator matrices are considered. As corollaries, we get some well-known results.