Identifying initial condition of the Rayleigh‐Stokes problem with random noise

We investigate a backward problem for the Rayleigh‐Stokes problem, which aims to determine the initial status of some physical field such as temperature for slow diffusion from its present measurement data. This problem is well‐known to be ill‐posed because of the rapid decay of the forward process. We construct a regularized solution using the filter regularization method in the Gaussian random noise. Under some a priori assumptions on the exact solution, we establish the expectation between the exact solution and the regularized solution in the L² and H^m norms.     

Study of optimal control problems on the half-line by the averaging method

We justify the application of the averaging method to optimal control problems for systems of differential equations on the half-line. For optimal control problems for systems of differential equations linear in the control, we prove the existence of optimal controls for the exact and averaged problems. We show that an optimal control in the averaged problem is ɛ-optimal in the exact problem.     

Faster least squares approximation

Least squares approximation is a technique to find an approximate solution to a system of linear equations that has no exact solution. In a typical setting, one lets n be the number of constraints and d be the number of variables, with n >> d{n \gg d}. Then, existing exact methods find a solution vector in O(nd ²) time. We present two randomized algorithms that provide accurate relative-error approximations to the optimal value and the solution vector of a least squares approximation problem more rapidly than existing exact algorithms. Both of our algorithms preprocess the data with the Randomized Hadamard transform. One then uniformly randomly samples constraints and solves the smaller problem on those constraints, and the other performs a sparse random projection and solves the smaller problem on those projected coordinates. In both cases, solving the smaller problem provides relative-error approximations, and, if n is sufficiently larger than d, the approximate solution can be computed in O(nd ln d) time.     

Exact Jackson–Stechkin-type inequalities for 2π-periodic functions in L 2 and widths of some classes of functions

We consider the problem of finding exact inequalities for the best approximations of periodic differentiable functions by trigonometric polynomials and the m-order moduli of continuity in the space L ₂ and present their applications. For some classes of functions defined by the indicated moduli of continuity, we calculate the exact values of n-widths in the space L ₂.     

Error estimate in L2 of a covolume method for the generalized Stokes problem

We investigate an L²‐error estimate of a covolume scheme for the Stokes problem recently introduced by Chou (Math Comp 66 (1997), 85–104). We show the error in L² norm is of second order provided the exact velocity is in H ³ and the exact pressure is in H². © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

New Models of the Generalized Minimum Spanning Tree Problem

We consider a generalization of the Minimum Spanning Tree Problem, called the Generalized Minimum Spanning Tree Problem, denoted by GMST. It is known that the GMST problem is NP-hard. We present a stronger result regarding its complexity, namely, the GMST problem is NP-hard even on trees as well an exact exponential time algorithm for the problem based on dynamic programming. We describe new mixed integer programming models of the GMST problem, mainly containing a polynomial number of constraints. We establish relationships between the polytopes corresponding to their linear relaxations. Based on a new model of the GMST we present a solution procedure that solves the problem to optimality for graphs with nodes up to 240. We discuss the advantages of our method in comparison with earlier methods.     

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.     

A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem

We are concerned with the exact solution of a graph optimization problem known as minimum linear arrangement (MinLA). Define the length of each edge of a graph with respect to a linear ordering of the graph vertices. Then, the MinLA problem asks for a vertex ordering that minimizes the sum of edge lengths. MinLA has several practical applications and is NP-Hard. We present a mixed 0-1 linear programming formulation of the problem, which led to fast optimal solutions for dense graphs of sizes up to n = 23.     

Approximate Solutions of Continuous Dispersion Problems

The problem of positioning p points so as to maximize the minimum distance between them has been studied in both location theory (as the continuous p-dispersion problem) and the design of computer experiments (as the maximin distance design problem). This problem can be formulated as a nonlinear program, either exactly or approximately. We consider formulations of both types and demonstrate that, as p increases, it becomes dramatically more expensive to compute solutions of the exact formulation than to compute solutions of the approximate formulation.     

Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs

Graham and Pollak [2] proved that n – 1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of K_n decompose. Tverberg [6], using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for two related decomposition problems, in which we wish to partition the arcs/edges of complete digraphs/multigraphs into a minimum number of arc/edge-disjoint complete bipartite subgraphs of appropriate natures. We obtain exact results for the digraph problem, which was posed by Lundgren and Maybee [4]. We also obtain exact results for the decomposition of complete multigraphs with exactly two edges connecting every pair of distinct vertices.     

Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method

An alternate formulation of the classical vehicle routing problem with stochastic demands (VRPSD) is considered. We propose a new heuristic method to solve the problem, based on the Cross-Entropy method. In order to better estimate the objective function at each point in the domain, we incorporate Monte Carlo sampling. This creates many practical issues, especially the decision as to when to draw new samples and how many samples to use. We also develop a framework for obtaining exact solutions and tight lower bounds for the problem under various conditions, which include specific families of demand distributions. This is used to assess the performance of the algorithm. Finally, numerical results are presented for various problem instances to illustrate the ideas.     

The Wirtinger-Steklov inequality between the norm of a periodic function and the norm of the positive cutoff of its derivative

We prove that there is no single uniform tight frame in Euclidean (unitary) space such that a solution of the ℓ ₁-norm minimization problem for the frame representation is attained on the frame coefficients. Then we find an exact solution of the ℓ ₁-minimization problem for the Mercedes-Benz frame in ℝ ^N . We also give some examples of connections between optimization problems of various types.     

The Exterior Dirichlet Problem for the Biharmonic Equation: Solutions with Bounded Dirichlet Integral

We study the unique solvability of the Dirichlet problem for the biharmonic equation in the exterior of a compact set under the assumption that a generalized solution of this problem has a bounded Dirichlet integral with weight |x|^a. Depending on the value of the parameter ^a,a we prove uniqueness theorems or present exact formulas for the dimension of the solution space of the Dirichlet problem.     

Fault tolerant forwarding and optical indexes: A design theory approach

We study the problem of designing fault tolerant routings in both complete and complete bipartite optical networks. We show that this problem has strong connections to various fundamental problems in design theory. Using a design theory approach, we find optimal f‐fault tolerant arc‐forwarding indexes for all complete networks and all complete balanced bipartite networks. Similarly, we find almost exact values for f‐fault tolerant optical indexes for these networks. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Optimal Recovery Methods for Solutions of the Dirichlet Problem that are Exact on Subspaces of Spherical Harmonics

We consider the optimal recovery problem for the solution of the Dirichlet problem for the Laplace equation in the unit d-dimensional ball on a sphere of radius ρ from a finite collection of inaccurately specified Fourier coefficients of the solution on a sphere of radius r, 0 < r < ρ < 1. The methods are required to be exact on certain subspaces of spherical harmonics.

     

Estimates of deviations from exact solutions of initial boundary value problems for the wave equation

We derive computable upper bounds of the difference between an exact solution of the initial boundary value problem for a linear hyperbolic equation and any function in a space-time cylinder that belongs to the respective energy class. We prove that the bounds vanish if and only if the approximate solution coincides with the exact one. Bibliography: 13 titles. Dedicated to the jubilee of dear Nina Nikolaevna Uraltseva Translated from Problemy Matematicheskogo Analiza, 41, May 2009, pp. 93–106.     

The Exactness Property of the Vector Exact l1 Penalty Function Method in Nondifferentiable Invex Multiobjective Programming

In this article, the vector exact l₁ penalty function method used for solving nonconvex nondifferentiable multiobjective programming problems is analyzed. In this method, the vector penalized optimization problem with the vector exact l₁ penalty function is defined. Conditions are given guaranteeing the equivalence of the sets of (weak) Pareto optimal solutions of the considered nondifferentiable multiobjective programming problem and of the associated vector penalized optimization problem with the vector exact l₁ penalty function. This equivalence is established for nondifferentiable invex vector optimization problems. Some examples of vector optimization problems are presented to illustrate the results established in the article.     

Dividing profits three ways: Exactness vs. consensuality

A rule for 3-way division of profits based on peer evaluation reports is impartial if the calculation of each partner’s share ignores her report, exact if it never allocates more or less than the profit to be shared, and consensual if it respects evaluations when the partners’ reports are in agreement. We use a calculus of variations technique to solve exactly a simple version of the problem of finding a 3-way exact, impartial division function of minimal average deviation from consensuality. We also give approximate solutions to three versions of the problem using a numerical analysis technique that is widely applicable.     

An exact approach for the maximum concurrent k-splittable flow problem

We consider the maximization of a multicommodity flow throughput in presence of constraints on the maximum number of paths to be used. Such an optimization problem is strongly NP-hard, and is known in the literature as the maximum routable demand fraction variant of the k-splittable flow problem. Here we propose an exact approach based on branch and bound rules and on an arc-flow mixed integer programming formulation of the problem. Computational results are provided, and a comparison with a standard commercial solver is proposed.     

The stressed state of a thermosensitive annular plate of variable thickness

We find an exact solution of the problem of displacements and stresses in a polar-orthotropic annular plate of variable thickness with physico-mechanical properties of the material depending on temperature. The solutions are obtained as generalized and degenerate hypergeometric functions.Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, Issue 33, 1991, pp. 42–45.