Finite Element Differential–Algebraic Systems for Eddy Current Problems

Finite element discretization of some time-dependent eddy current problems yields ordinary differential–algebraic systems with large sparse matrices. Properties and stability of these systems are analyzed for two classes of eddy current problems: (i) two-dimensional coupled field-circuit problems with arbitrary external circuit connections between conductors; (ii) 2.5-dimensional problems characterized by axisymmetric geometry and non-axisymmetric excitation. Extension of the analysis to many other formulations of eddy current problems in 2D and 3D is straightforward.     

Solving the linear matroid parity problem as a sequence of matroid intersection problems

In this paper, we present an O(r ⁴ n) algorithm for the linear matroid parity problem. Our solution technique is to introduce a modest generalization, the non-simple parity problem, and identify an important subclass of non-simple parity problems called easy parity problems which can be solved as matroid intersection problems. We then show how to solve any linear matroid parity problem parametrically as a sequence of easy parity problems.In contrast to other algorithmic work on this problem, we focus on general structural properties of dual solutions rather than on local primal structures. In a companion paper, we develop these ideas into a duality theory for the parity problem.     

A theory of pseudo-differential boundary value problems with discontinuous conditions I

Summary The paper deals with mixed boundary value problems and transmission problems for elliptic differential and pseudo-differential operators. These problems are considered as elements of an algebra (where is the considered domain, x=, YX a submanifold of codimension 1, where the conditions have a jump, and x is a certain compactification of X/Y), the elements of which are described on a symbolic level. By means of additional conditions (of trace and potential type, with respect to Y) a given mixed problem is extended to an operator, and the Fredholm property of is established under an ellipticity condition, the parametrix is constructed on symbolic level and ind is expressed. In the second part the authors also study classes of special cases, namely differential operators of second and higher order with mixed boundary conditions for dim 2, where explicit index expressions are derived.     

Reasoning about sequences of memory states

Motivated by the verification of programs with pointer variables, we introduce a temporal logic whose underlying assertion language is the quantifier-free fragment of separation logic and the temporal logic on the top of it is the standard linear-time temporal logic LTL. We analyze the complexity of various model-checking and satisfiability problems for , considering various fragments of separation logic (including pointer arithmetic), various classes of models (with or without constant heap), and the influence of fixing the initial memory state. We provide a complete picture based on these criteria. Our main decidability result is pspace-completeness of the satisfiability problems on the record fragment and on a classical fragment allowing pointer arithmetic. -completeness or -completeness results are established for various problems by reducing standard problems for Minsky machines, and underline the tightness of our decidability results.     

Topology optimization of multi-purpose structures

Whilst most of the literature on topology optimization of structures deals with so-called selfadjoint problems involving highly idealized, single-purpose structures, this paper discusses topology optimization of multi-purpose structures which concerns nonselfadjoint problems. General methods based on the so-called layout theory, application to trusses and perforated plates and computational difficulties are discussed.     

Linearization of boundary eigenvalue problems

It is shown that certain eigenvalue problems for ordinary differential operators with boundary conditions depending holomorphically on the eigenvalue parameter can be linearized by making use of the theory of operator colligations. As examples, first order systems with boundary conditions depending polynomially on and Sturm-Liouville problems with -holomorphic boundary conditions are considered.     

Heuristic Control of a Constraint-Based Algorithm for the Preemptive Job-Shop Scheduling Problem

In the recent years, constraint programming has been applied to a wide variety of academic and industrial non-preemptive scheduling problems, i.e., problems in which activities cannot be interrupted. In comparison, preemptive scheduling problems have received almost no attention from both the Operations Research and the Artificial Intelligence community. Motivated by the needs of a specific application, we engaged in a study of the applicability of constraint programming techniques to preemptive scheduling problems. This paper presents the algorithms we developed and the results we obtained on the preemptive variant of the famous job-shop scheduling problem. Ten heuristic search strategies, combined with two different constraint propagation techniques, are presented, and compared using two well-known series of job-shop scheduling instances from the literature. The best combination, which relies on limited discrepancy search and on edge-finding techniques, is shown to provide excellent solutions to the preemptive job-shop scheduling problem. A mean relative distance to the optimal solution of 0.32% is achieved in five minutes, on instances with 10 jobs and 10 machines (100 activities).     

Counterexamples to the well-posedness of transmission boundary value problems for the Laplacian

In this note we show that the well-posedness range for transmission boundary value problems for the Laplacian in the class of Lipschitz domains established by Escauriaza and Mitrea (2004) is sharp. Our approach relies on Mellin transform techniques for singular integrals naturally associated with the transmission problems and on a careful analysis of the spectra of such singular integrals.

     

Sharply localized pointwise and estimates for finite element methods for quasilinear problems

We establish pointwise and estimates for finite element methods for a class of second-order quasilinear elliptic problems defined on domains in . These estimates are localized in that they indicate that the pointwise dependence of the error on global norms of the solution is of higher order. Our pointwise estimates are similar to and rely on results and analysis techniques of Schatz for linear problems. We also extend estimates of Schatz and Wahlbin for pointwise differences in pointwise errors to quasilinear problems. Finally, we establish estimates for the error in , where is a subdomain. These negative norm estimates are novel for linear as well as for nonlinear problems. Our analysis heavily exploits the fact that Galerkin error relationships for quasilinear problems may be viewed as perturbed linear error relationships, thus allowing easy application of properly formulated results for linear problems.

     

A Unified Gradient Flow Approach to Constrained Nonlinear Optimization Problems

This paper presents a unified gradient flow approach to nonlinear constrained optimization problems. This method is based on a continuous gradient flow reformulation of constrained optimization problems and on a two level time discretization of the gradient flow equation with a splitting parameter . The convergence of the scheme is analyzed and it is shown that the scheme becomes first order when [0, 1] and second order when = 1 and the time discretization step length is sufficiently large. Numerical experiments for continuous, discrete and mixed discrete optimization problems were performed, and the numerical results show that the approach is effective for solving these problems.     

Implementation and Test of Auction Methods for Solving Generalized Network Flow Problems with Separable Convex Cost

We describe the implementation and testing of two methods, based on the auction approach, for solving the problem of minimizing a separable convex cost subject to generalized network flow conservation constraints. The first method is the -relaxation method of Ref. 1; the second is an extension of the auction sequential/shortest path algorithm for ordinary network flow to generalized network flow. We report test results on a large set of randomly generated problems with varying topology, arc gains, and cost function. Comparison with the commercial code CPLEX on linear/quadratic cost problems and with the public-domain code PPRN on nonlinear cost ordinary network problems are also made. The test results show that the auction sequential/shortest path algorithm is generally fastest for solving quadratic cost problems and mixed linear/nonlinear cost problems with arc gain range near 1. The -relaxation method is generally fastest for solving nonlinear cost ordinary network problems and mixed linear/nonlinear cost problems with arc gain range away from 1. CPLEX is generally fastest for solving linear cost and mixed linear/quadratic cost problems with arc gain range near 1.     

A recent significant growth condition in optimal control theory

In 1934, Tonelli proved, for free problems withn=1, that the trajectories of a minimizing sequence are equiabsolutely continuous provided a pointwise growth condition is satisfied everywhere except at the points of an exceptional set where an additional mild hypothesis is required, condition (T). The author extended this result to optimal control problems by the use of a uniform growth condition, called (), which is equivalent to Tonelli's pointwise growth condition for free problems with convex integrand (Refs. 4–5, 10). More recently, condition (), or condition (), which is equivalent to () for optimal control problems, was replaced by the much weaker condition () in existence theorems for optimal control problems (Refs. 1–2).In the present paper, we show that this same combination of growth condition () and condition (T) at the points of the exceptional set is actually a special case of the growth condition (), which does not use the concept of the exceptional set.     

Simultaneously least favorable experiments

Summary We continue our investigation into robust finite experiments and decision problems which we started in part I. We give a short derivation of the Huber-Strassen theorem, and also a proof of a new result on the existence of simultaneously least favorable experiments for contaminated classification problems. The main effort goes into the development of tools which allow us to apply the general results of part I. The principal device needed for our derivations is a reparametrization of decision spaces and a corresponding lift of loss functions which we call standard loss functions (in analogy to standard experiments). Non robust decision theory which deals with linear functionals (expectations) does not need this device, but robust theory based on sublinear functionals (upper expectations) does.     

Completeness of systems of functions,quasianalyticity and subharmonic majorants

In the paper one investigates completeness questions for certain frequently encountered systems of entire functions (for example, the completeness of the system of all entire functions of order not exceeding a given number ) in -spaces (for example, in C(E), E being a closed subset of R). Dual problems are the problems regarding the quasianatyticity of classes of functions, having Fourier transforms supported on a thin set. These latter problems are solved with the use of potential theory technique and with the aid of the investigation of conformal mappings of the upper half-plane onto special comb-like domains.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 170, pp. 102–156, 1989.     

The approximate spectral projection method

In this paper we develop a general method for investigating the spectral asymptotics for various differential and pseudo-differential operators and their boundary value problems, and consider many of the problems posed when this method is applied to mathematical physics and mechanics. Among these problems are the Schrödinger operator with growing, decreasing and degenerating potential, the Dirac operator with decreasing potential, the quasi-classical spectral asymptotics for Schrödinger and Dirac operators, the linearized Navier-Stokes equation, the Maxwell system, the system of reactor kinetics, the eigenfrequency problems of shell theory, and so on. The method allows us to compute the principal term of the spectral asymptotics (and, in the case of Douglis-Nirenberg elliptic operators, also their following terms) with the remainder estimate close to that for the sharp remainder.     

General Purpose Heuristics for Integer Programming—Part II

In spite of the many special purpose heuristics for specific classes of integer programming (IP) problems, there are few developments that focus on general purpose integer programming heuristics. This stems partly from the perception that general purpose methods are likely to be less effective than specialized procedures for specific problems, and partly from the perception that there is no unifying theoretical basis for creating general purpose heuristics. Still, there is a general acknowledgment that methods which are not limited to solving IP problems on a class by class basis, but which apply to a broader range of problems, have significant value. We provide a theoretical framework and associated explicit proposals for generating general purpose IP heuristics. Our development, makes use of cutting plane derivations that also give a natural basis for marrying heuristics with exact branch and cut methods for integer programming problems.     

Nonparametric bandit methods

Bandits are a finite collection of random variables. Bandit problems are Markov decision problems in which, at each decision time, the decision maker selects a random variable (referred to as a bandit arm) and observes an outcome. The selection is based on the observation history. The objective is to sequentially choose arms so as to minimize growth (with decision time) rate of the number of suboptimal selections.The appellation bandit refers to mechanical gambling machines, and the tradition stems from the question of allocating competing treatments to a sequence of patients having the same disease. Our motivation is machine learning in which a game-playing or assembly-line adjusting computer is faced with a sequence of statistically-similar decision problems and, as resource, has access to an expanding data base relevant to these problems.The setting for the present study is nonparametric and infinite horizon. The central aim is to relate a methodology which postulates finite moments or, alternatively, bounded bandit arms. Under these circumstances, strategies proposed are shown to be asymptotically optimal and converge at guaranteed rates. In the bounded-arm case, the rate is optimal.We extend the theory to the case in which the bandit population is infinite, and share some computational experience.     

Numerical approximations and regularizations of Riccati equations arising in hyperbolic dynamics with unbounded control operators

This paper provides an approximation theory for numerical computations of the solutions to algebraic Riccati equations arising in hyperbolic, boundary control problems. One of the difficulties in the approximation theory for Riccati equations is that many attractive numerical methods (such as standard finite elements) do not satisfy a uniform stabilizability condition, which is necessary for the stability of the approximate Riccati solutions. To deal with these problems, a regularizationapproximation technique, based on the introduction of special artificial terms to the dynamics of the original model, is proposed. The need for this regularization appears to be a distinct feature of hyperbolic (hyperbolic-like) equations, rather than parabolic (parabolic-like) problems where the smoothing effect of the dynamics is beneficial for the convergence and stability properties of approximate solutions to the associated Riccati equations (see [14]). The ultimate result demonstrates that the regularized, finite-dimensional feedback control yields near optimal performance and that the corresponding Riccati solution satisfies all the desired convergence properties. The general theory is illustrated by an example of a boundary control problem associated with the Kirchoff plate model. Some numerical results are provided for the given example.     

Cost Based Filtering for the Constrained Knapsack Problem

We present cost based filtering methods for Knapsack Problems (KPs). Cost based filtering aims at fixing variables with respect to the objective function. It is an important technique when solving complex problems such as Quadratic Knapsack Problems, or KPs with additional constraints (Constrained Knapsack Problems (CKPs)). They evolve, e.g., when Constraint Based Column Generation is applied to appropriate optimization problems. We develop new reduction algorithms for KP. They are used as propagation routines for the CKP with (nlogn) preprocessing time and (n) time per call. This sums up to an amortized time (n) for (logn) incremental calls where the subsequent problems may differ with respect to arbitrary sets of necessarily included and excluded items.