Mixed sensitivity minimization problems with rationall 1-optimal solutions

Up to this time, the only known method to solve the discrete-time mixed sensitivity minimization problem inl ¹ has been to use a certain infinite-dimensional linear programming approach, presented by Dahleh and Pearson in 1988 and later modified by Mendlovitz. That approach does not give in general true optimal solutions; only suboptimal ones are obtained. Here, for the first time, the truel ¹-optimal solutions are found for some mixed sensitivity minimization problems. In particular, Dahleh and Pearson construct an 11h order suboptimal compensator for a certain second-order plan with first-order weight functions; it is shown that the unique optimal compensator for that problem is rational and of order two. The author discovered this fact when trying out a new scheme of solving the infinite-dimensional linear programming system. This scheme is of independent interest, because when it is combined with the Dahleh-Pearson-Mendlovitz scheme, it gives both an upper bound and a lower bound on the optimal performance; hence, it provides the missing error bound that enables one to truncate the solution. Of course, truncation is appropriate only if the order of the optimal compensator is too high. This may indeed be the case, as is shown with an example where the order of the optimal compensator can be arbitrarily high.     

A new technique of using homotopy analysis method for solving high‐order nonlinear differential equations

In this paper, a new technique of homotopy analysis method (HAM) is proposed for solving high‐order nonlinear initial value problems. This method improves the convergence of the series solution, eliminates the unneeded terms and reduces time consuming in the standard homotopy analysis method (HAM) by transform the nth‐order nonlinear differential equation to a system of n first‐order equations. Second‐ and third‐ order problems are solved as illustration examples of the proposed method. Copyright © 2010 John Wiley & Sons, Ltd.     

Higher order Galerkin methods in time for free surface flows

In many engineering applications, free surface or two-phase flows are discretized in time with an explicit decoupling of geometry and fluid flow. Such a strategy leads to a capillary CFL condition of the form [3]. For the case of surface tension dominated flows (i.e. high Weber number We) this can dictate infeasibly small time steps. As an alternative we suggest a Galerkin method in time based on the discontinuous Galerkin method of first order (dG(1)). For this choice, an energy estimate can be proved [7], so unconditional stability of the method is given. While for ODEs or parabolic PDEs the method is of third order at the discrete points in time t_n [4], in the case of free surface flows second order convergence can still be achieved. Numerical examples using the Arbitrary Lagrangian Eulerian (ALE) method for both capillary one-phase and two-phase flow demonstrate this convergence order. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Eulerian–Lagrangian Weighted Essentially Nonoscillatory scheme for nonlinear conservation laws

We develop a formally high order Eulerian–Lagrangian Weighted Essentially Nonoscillatory (EL‐WENO) finite volume scheme for nonlinear scalar conservation laws that combines ideas of Lagrangian traceline methods with WENO reconstructions. The particles within a grid element are transported in the manner of a standard Eulerian–Lagrangian (or semi‐Lagrangian) scheme using a fixed velocity v. A flux correction computation accounts for particles that cross the v‐traceline during the time step. If v = 0, the scheme reduces to an almost standard WENO5 scheme. The CFL condition is relaxed when v is chosen to approximate either the characteristic or particle velocity. Excellent numerical results are obtained using relatively long time steps. The v‐traceback points can fall arbitrarily within the computational grid, and linear WENO weights may not exist for the point. A general WENO technique is described to reconstruct to any order the integral of a smooth function using averages defined over a general, nonuniform computational grid. Moreover, to high accuracy, local averages can also be reconstructed. By re‐averaging the function to a uniform reconstruction grid that includes a point of interest, one can apply a standard WENO reconstruction to obtain a high order point value of the function. © 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 651–680, 2017     

Preemptive scheduling of interval orders is polynomial

In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.     

A fast algorithm for the evaluation of heat potentials

Numerical methods for solving the heat equation via potential theory have been hampered by the high cost of evaluating heat potentials. When M points are used in the discretization of the boundary and N time steps are computed, an amount of work of the order O(N²M²) has traditionally been required. In this paper, we present an algorithm which requires an amount of work of the order O(NM), and we observe speedups of five orders of magnitude for large-scale problems. Thus, the method makes it possible to solve the heat equation by potential theory in practical situations.     

Sooner and Later Waiting Time Problems Based on a Dependent Sequence

This paper introduces a new concept: a binary sequence of order (k,r), which is an extension of a binary sequence of order k and a Markov dependent sequence. The probability functions of the sooner and later waiting time random variables are derived in the binary sequence of order (k,r). The probability generating functions of the sooner and later waiting time distributions are also obtained. Extensions of these results to binary sequence of order (g,h) are also presented.     

High‐order characteristic‐tracking strategy for simulation of a nonlinear advection–diffusion equation

In this study, new high‐order backward semi‐Lagrangian methods are developed to solve nonlinear advection–diffusion type problems, which are realized using high‐order characteristic‐tracking strategies. The proposed characteristic‐tracking strategies are second‐order L‐stable and third‐order L(α)‐stable methods, which are based on a classical implicit multistep method combined with a error‐correction method. We also use backward differentiation formulas and the fourth‐order finite‐difference scheme for diffusion problem discretization in the temporal and spatial domains, respectively. To demonstrate the adaptability and efficiency of these time‐discretization strategies, we apply these methods to nonlinear advection–diffusion type problems such as the viscous Burgers' equation. Through simulations, not only the temporal and spatial accuracies are numerically evaluated but also the proposed methods are shown to be superior to the compared existing characteristic‐tracking methods under the same rates of convergence in terms of accuracy and efficiency. Finally, we have shown that the proposed method well preserves the energy and mass when the viscosity coefficient becomes zero.     

Avoiding Medvedev reductions inside a linear order

While every endpointed interval I in a linear order J is, considered as a linear order in its own right, trivially Muchnik-reducible to J itself, this fails for Medvedev-reductions. We construct an extreme example of this: a linear order in which no endpointed interval is Medvedev-reducible to any other, even allowing parameters, except when the two intervals have finite difference. We also construct a scattered linear order which has many endpointed intervals Medvedev-incomparable to itself; the only other known construction of such a linear order yields an ordinal of extremely high complexity, whereas this construction produces a low-level-arithmetic example. Additionally, the constructions here are “coarse” in the sense that they lift to other uniform reducibility notions in place of Medvedev reducibility itself.     

HIGH ORDER KÄHLER MODULES OF NONCOMMUTATIVE RING EXTENSIONS

We construct the high order Kähler modules of noncommutative ring extensions B/A and show their fundamental properties. Our Kähler modules represent not only high order left derivations for one-sided modules but also high order central derivations for bimodules, which are usual derivations. This new viewpoint enables us to prove new results which were not known even though B is an algebra over a commutative ring A. Our results are the decomposition of Kähler modules by an idempotent element, exact sequences of Kähler modules, the Kähler modules of factor rings, and the relation to separable extensions. In particular, our exact sequences of high order Kähler modules were not known even though B is commutative.     

Learning formation control for fractional‐order multiagent systems

In this paper, we use 2 iterative learning control schemes (P‐type and PI‐type) with an initial learning rule to achieve the formation control of linear fractional‐order multiagent systems. To realize the finite‐time consensus, we assume repeatable operation environments as well as a fixed but directed communication topology for the fractional‐order multiagent systems. Both P‐type and PI‐type update laws are applied to generate the control commands for each agent. It is strictly proved that all agents are driven to achieve an asymptotical consensus as the iteration number increases. Two examples are simulated to verify the effectiveness of the proposed algorithms.     

Space‐time spectral method for two‐dimensional semilinear parabolic equations

In this paper, a high‐order accurate numerical method for two‐dimensional semilinear parabolic equations is presented. We apply a Galerkin–Legendre spectral method for discretizing spatial derivatives and a spectral collocation method for the time integration of the resulting nonlinear system of ordinary differential equations. Our formulation can be made arbitrarily high‐order accurate in both space and time. Optimal a priori error bound is derived in the L²‐norm for the semidiscrete formulation. Extensive numerical results are presented to demonstrate the convergence property of the method, show our formulation have spectrally accurate in both space and time. John Wiley & Sons, Ltd.     

Multiple orders per job batch scheduling with incompatible jobs

The multiple orders per job (MOJ) scheduling problem is presented for the batch-processing environment such as that exemplified by diffusion ovens. A mixed-integer programming formulation is presented for the incompatible job family case wherein only jobs that belong to the same family may be grouped together in a production batch. This optimization formulation is tested through an extensive experimental design with the objective of minimizing total weighted tardiness (maximizing on-time delivery performance). Optimal solutions are achievable for this initial set of 6-to-12 order problems, but it is noted that the optimization model takes an unreasonable amount of computation time, which suggests the need for heuristic development to support the analysis of larger, more practical MOJ batch scheduling problems. A number of simple heuristic approaches are investigated in an attempt to find near-optimal solutions in a reasonable amount of computation time. It is seen that a combination of the heuristics produces near-optimal solutions for small order problems. Further testing proves that these heuristic combinations are the best for large order problems as well.     

A weighted occupation time for a class of measured-valued branching processes

Summary A weighted occupation time is defined for measure-valued processes and a representation for it is obtained for a class of measure-valued branching random motions on R ^d. Considered as a process in its own right, the first and second order asymptotics are found as time t. Specifically the finiteness of the total weighted occupation time is determined as a function of the dimension d, and when infinite, a central limit type renormalization is considered, yielding Gaussian or asymmetric stable generalized random fields in the limit. In one Gaussian case the results are contrasted in high versus low dimensions.Research supported in part by Natural Sciences and Engineering Research Council of Canada     

On a McKean‐Vlasov Stochastic Integro‐differential Evolution Equation of Sobolev‐Type

Abstract

We establish the global existence and uniqueness of mild solutions for a class of first‐order abstract stochastic Sobolev‐type integro‐differential equations in a real separable Hilbert space in which we allow the nonlinearities at a given time t to depend not only on the state of the solution at time, t, but also on the corresponding probability distribution at time t. Results concerning the continuous dependence of solutions on the initial data and almost sure exponential stability, as well as an extension of the existence result to the case in which the classical initial condition is replaced by a so‐called nonlocal initial condition, are also discussed. Finally, an example is provided to illustrate the applicability of the general theory.     

Variable-priority queue and doughnut routing

This paper proposes a new data structure called a variable-priority queue. The queue supports, in addition to the ordinary queue operations, an operation MIN to find an item of minimum key and three operations to change keys of items. Any sequence of these m operations can be processed in O(m) time. Furthermore, as its application, this paper presents two efficient algorithms for network problems. The first finds multicommodity flows in cycles in linear time. The second, using the first, finds edge-disjoint paths connecting terminal pairs in a doughnut-shaped grid. The grid is bounded by two nested rectangles, and terminals are specified on the two rectangular boundaries outside the four corners. If there are k terminal pairs and all the terminals are ordered in clockwise order around rectangles, then the algorithm decides in O(k) time whether there are edge-disjoint paths connecting terminals in the grid, and actually finds edge-disjoint paths in O(k log k) time.     

Batch sizing and job sequencing on a single machine

We study a single-machine scheduling problem in which the items to be processed have to be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between consecutive batches. For any fixed, but arbitrary item sequence, we present an algorithm that finds a sequence of batches such that the total flow time of the items is minimized; we prove that for a set ofn items, the algorithm runs inO(n) time. We show that, among all sequences, the one leading to the minimum flow time has the items in non-decreasing order of running times. Thus, the optimal algorithm for the combined problem, called thebatch-sizing problem, runs inO(n logn) time. We also prove that this algorithm yields an improved solution to a scheduling problem recently studied by Baker [1].     

Fully implicit time discretization for a free surface flow problem

One of the challenges in the numerics of free surface flows is the coupling of the flow field to the geometry of the domain. The most simple approach is an explicit decoupling, i.e. computing the flow field with geometrical information of a prior time step and then updating the geometry. This widely used approach leads to a severe CFL condition of the type , which may prescribe infinitesimally small time step sizes in the interesting case of a small Weber number (i.e. high surface tension). A semi-implicit approach utilizing the fact that , where x^k is a parametrization of the capillary boundary Γ, is also available [1]. This approach can be proven to be unconditionally stable but is of first order only. It also suffers from relatively strong numerical dissipation. We present a fully implicit approach using a backward differentiation formula to achieve a time discretization method that is of second order and only minimally dissipative. A numerical example of an oscillating drop showing very low numerical dissipation and second order convergence as well as numerical evidence for the stability of the method is presented. Since the method requires the solution of a highly nonlinear coupled system, possible preconditioners for this system are discussed, including a lower order decoupling. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A high‐order B‐spline collocation scheme for solving a nonhomogeneous time‐fractional diffusion equation

A high‐accuracy numerical approach for a nonhomogeneous time‐fractional diffusion equation with Neumann and Dirichlet boundary conditions is described in this paper. The time‐fractional derivative is described in the sense of Riemann‐Liouville and discretized by the backward Euler scheme. A fourth‐order optimal cubic B‐spline collocation (OCBSC) method is used to discretize the space variable. The stability analysis with respect to time discretization is carried out, and it is shown that the method is unconditionally stable. Convergence analysis of the method is performed. Two numerical examples are considered to demonstrate the performance of the method and validate the theoretical results. It is shown that the proposed method is of order O(Δx⁴ + Δt^{2 ? α}) convergence, where α ∈ (0,1) . Moreover, the impact of fractional‐order derivative on the solution profile is investigated. Numerical results obtained by the present method are compared with those obtained by the method based on standard cubic B‐spline collocation method. The CPU time for present numerical method and the method based on cubic B‐spline collocation method are provided.