Optimality of Euler-integral information for solving a scalar autonomous ode

We study the minimum error of algorithms for solving a scalar autonomous ODE. Information is defined asn evaluations of functionals of the right hand sidef. These functionals can be linear or nonlinear and continuous. Euler-integral information is defined and its optimality is proved in a class of regularf.     

Minimum asymptotic error of algorithms for solving ODE

We deal with algorithms for solving systems z′(x) = f(x, z(x)), x ε [0, c], z(0) = η where f has r continuous bounded derivatives in [0, c) × ^s. We consider algorithms whose sole dependence on f is through the values of n linear continuous functionals at f. We show that if these functionals are defined by partial derivatives off then, roughly speaking, the error of an algorithm (for a fixed f) cannot converge to zero faster than n^−r as n → +∞. This minimal error is achieved by the Taylor algorithm. If arbitrary linear continuous functionals are allowed, then the error cannot converge to zero faster than n^−(r+1) as n → +∞. This minimal error is achieved by the Taylor-integral algorithm which uses integrals of f.     

On algorithms for estimating computable error bounds for approximate periodic solutions of an autonomous delay differential equation

Machine tool chatter has been characterized as isolated periodic solutions or limit cycles of delay differential equations. Determining the amplitude and frequency of the limit cycle is sometimes crucial to understanding and controlling the stability of machining operations. In Gilsinn [Gilsinn DE. Computable error bounds for approximate periodic solutions of autonomous delay differential equations, Nonlinear Dyn 2007;50:73–92] a result was proven that says that, given an approximate periodic solution and frequency of an autonomous delay differential equation that satisfies a certain non-criticality condition, there is an exact periodic solution and frequency in a computable neighborhood of the approximate solution and frequency. The proof required the estimation of a number of parameters and the verification of three inequalities. In this paper the details of the algorithms will be given for estimating the parameters required to verify the inequalities and to compute the final approximation errors. An application will be given to a Van der Pol oscillator with delay in the non-linear terms.     

On optimal algorithms for the joint replenishment problem

In this paper, we demonstrate that the algorithm for determining the optimal strict cyclic policy for the Joint Replenishment Problem suggested by Fung and Ma¹ does not guarantee an optimal solution. We propose a modification that will ensure that the algorithm obtains the optimal strict cyclic policy. We then perform a comprehensive computational study to compare the modified Fung and Ma algorithm with other optimal algorithms for the problem. The study reveals that the optimal algorithm of Viswanathan² is computationally more efficient than other methods.     

Galerkin method and optimal error algorithms in hilbert spaces

Summary We consider operator equations of the formLu=f, whereL belongs to the class of linear, bounded (by a constantM) and coercive (with a constantm) operators from a Hilbert spaceV onto its dualV ^* andf belongs to a Hilbert spaceWV ^*. We study optimality of the Galerkin methodP _n ^* Lu _n =P _n ^* f, whereu _n V _n ,V _n is subspace ofV, P _n is the orthogonal projector ontoV _n andP _n ^* is dual toP _n . We show that the Galerkin method is quasi optimal independently of the choice of the subspaceV _n and the spaceW ifM>m. In the caseM=m, optimality of the method depends strongly on the choice ofV _n andW. Therefore we define a new algorithm which is always optimal (independently of the choice ofV _n andW and relations betweenM andm).     

On optimal triangular meshes for minimizing the gradient error

Summary Construction of optimal triangular meshes for controlling the errors in gradient estimation for piecewise linear interpolation of data functions in the plane is discussed. Using an appropriate linear coordinate transformation, rigorously optimal meshes for controlling the error in quadratic data functions are constructed. It is shown that the transformation can be generated as a curvilinear coordinate transformation for anyC data function with nonsingular Hessian matrix. Using this transformation, a construction of nearly optimal meshes for general data functions is described and the error equilibration properties of these meshes discussed. In particular, it is shown that equilibration of errors is not a sufficient condition for optimality. A comparison of meshes generated under several different criteria is made, and their equilibrating properties illustrated.This work was supported by the Natural Sciences and Engineering Research Council of Canada, by the Information Technology Research Centre, which is funded by the Province of Ontario, by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marietta Energy Systems, Inc., and through an appointment to the U.S. Department of Energy Postgraduate Research Program administered by Oak Ridge Associated Universities     

On DC optimization algorithms for solving minmax flow problems

We formulate minmax flow problems as a DC optimization problem. We then apply a DC primal-dual algorithm to solve the resulting problem. The obtained computational results show that the proposed algorithm is efficient thanks to particular structures of the minmax flow problems.     

Parallel algorithms for solving nonlinear two-point boundary-value problems which arise in optimal control

This paper describes a collection of parallel optimal control algorithms which are suitable for implementation on an advanced computer with the facility for large-scale parallel processing. Specifically, a parallel nongradient algorithm and a parallel variablemetric algorithm are used to search for the initial costate vector that defines the solution to the optimal control problem. To avoid the computational problems sometimes associated with simultaneous forward integration of both the state and costate equations, a parallel shooting procedure based upon partitioning of the integration interval is considered. To further speed computations, parallel integration methods are proposed. Application of this all-parallel procedure to a forced Van der Pol system indicates that convergence time is significantly less than that required by highly efficient serial procedures.This research was supported in part by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-77-3418.     

On optimal integration algorithms for functions with a known number of extrema

Translated from Programmnoe Obespechenie i Modeli Issledovaniya Operatsii, pp. 177–185, 1986.     

On the Kleinrock-Nilsson problem of optimal scheduling algorithms for time-shared systems

We seek to minimize the mean-squared deviation of a waiting time function from a desired response function over the class of waiting time functions satisfying the Kleinrock-Nilsson necessary conditions. We will characterize analytically the optimal policy as the minimum majorant in the appropriate class of the cumulative response to go. We will show that, in general, the monotonicity necessary condition results in optimal policies which depend in some sense on the future and are anticipating.Part of this paper was completed at Bell Laboratories, Naperville, Illinois.Part of this paper was completed at the University of Kentucky, Lexington, Kentucky. This author was supported by an NSF grant and the Alfred P. Sloan Foundation.     

On conditions for the convergence of algorithms in optimal control problems

We obtain sufficient conditions for the convergence of iteration algorithms in Banach spaces. These conditions imply the weak convergence of subsequences to the set of solutions. Bibliography: 4 titles. Translated fromObchyslyuval'na ta Prykladna Matematyka, No. 81 1997, pp. 70–71.     

Lipschitz regularity for scalar minimizers of autonomous simple integrals

We prove Lipschitz regularity for a minimizer of the integral , defined on the class of the AC functions having x(a)=A and x(b)=B. The Lagrangian may have L(s,) nonconvex (except at ξ=0), while may be non-lsc, measurability sufficing for ξ≠0 provided, e.g., L^**() is lsc at (s,0) s. The essential hypothesis (to yield Lipschitz minimizers) turns out to be local boundedness of the quotient φ/ρ() (and not of L^**() itself, as usual), where φ(s)+ρ(s)h(ξ) approximates the bipolar L^**(s,ξ) in an adequate sense. Moreover, an example of infinite Lavrentiev gap with a scalar 1-dim autonomous (but locally unbounded) lsc Lagrangian is presented.     

On an optimal method for solving an inverse Stefan problem

An algorithm optimal in order is proposed for solving an inverse Stefan problem. We also give some exact estimates of accuracy of this method.     

On the convergence problem of a certain variant of the successive-approximation method for solving optimal control problems

The paper is devoted to the convergence problem of one of the modifications of the successive-approximation method for solving optimal control problems. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 23, Optimal Control, 2005.     

Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

Simplex-inspired algorithms for solving a class of convex programming problems

We consider a class of convex programming problems whose objective function is given as a linear function plus a convex function whose arguments are linear functions of the decision variables and whose feasible region is a polytope. We show that there exists an optimal solution to this class of problems on a face of the constraint polytope of dimension not more than the number of arguments of the convex function. Based on this result, we develop a method to solve this problem that is inspired by the simplex method for linear programming. It is shown that this method terminates in a finite number of iterations in the special case that the convex function has only a single argument. We then use this insight to develop a second algorithm that solves the problem in a finite number of iterations for an arbitrary number of arguments in the convex function. A computational study illustrates the efficiency of the algorithm and suggests that the average-case performance of these algorithms is a polynomial of low order in the number of decision variables. The work of T. C. Sharkey was supported by a National Science Foundation Graduate Research Fellowship. The work of H. E. Romeijn was supported by the National Science Foundation under Grant No. DMI-0355533.     

Parallel algorithms for solving retrieval equations

Translated from Vychislitel'nye Kompleksy i Modelirovanie Slozhnykh Sistem, pp. 28–36, Moscow State University, 1989.     

Projection algorithms for solving a system of general variational inequalities

In this paper, we introduce and consider a new system of general variational inequalities involving four different operators. Using the projection operator technique, we suggest and analyze some new explicit iterative methods for this system of variational inequalities. We also study the convergence analysis of the new iterative method under certain mild conditions. Since this new system includes the system of variational inequalities involving three operators, variational inequalities and related optimization problems as special cases, results obtained in this paper continue to hold for these problems. Our results can be viewed as a refinement and improvement of the previously known results for variational inequalities.