Trigonometric approximation of optimal periodic control problemsfor systems with inertial controllers

A constrained optimal periodic control (OPC) problem for nonlinear systems with inertial controllers is considered. A sequence of approximate problems containing trigonometric polynomials for approximation of the state, control, and functions in the state equations and in the optimality criterion is formulated. Sufficient conditions for a sequence of nearly optimal solutions of approximate problems to be norm-convergent to the basic problem optimal solution are derived. It is pointed out that the direct approximation approach in the space of state and control combined with the finite-dimensional optimization methods such as the space covering and gradient-type methods makes probable the finding of the global optimum for OPC problems     

Optimal stopping of Markov processes: Hilbert space theory,approximation algorithms, and an application to pricing high-dimensionalfinancial derivatives

The authors develop a theory characterizing optimal stopping times for discrete-time ergodic Markov processes with discounted rewards. The theory differs from prior work by its view of per-stage and terminal reward functions as elements of a certain Hilbert space. In addition to a streamlined analysis establishing existence and uniqueness of a solution to Bellman's equation, this approach provides an elegant framework for the study of approximate solutions. In particular, the authors propose a stochastic approximation algorithm that tunes weights of a linear combination of basis functions in order to approximate a value function. They prove that this algorithm converges (almost surely) and that the limit of convergence has some desirable properties. The utility of the approximation method is illustrated via a computational case study involving the pricing of a path dependent financial derivative security that gives rise to an optimal stopping problem with a 100-dimensional state space     

Optimal control computation for nonlinear systems with state-dependent stopping criteria

In this paper, we consider a challenging optimal control problem in which the terminal time is determined by a stopping criterion. This stopping criterion is defined by a smooth surface in the state space; when the state trajectory hits this surface, the governing dynamic system stops. By restricting the controls to piecewise constant functions, we derive a finite-dimensional approximation of the optimal control problem. We then develop an efficient computational method, based on nonlinear programming, for solving the approximate problem. We conclude the paper with four numerical examples.     

Optimal almost-periodic control problem: a trigonometric approximation approach

The problem of finding an almost-periodic control that is optimal with respect to a certain time-averaged criterion for the dynamic system operated over a long period of time is considered. The existence of the optimal solution, spectral properties of which satisfy certain regularity conditions, is hypothesized. The problem is approximated by a sequence of finite-dimensional optimization problems containing trigonometric sums for the approximation of the state and control variables, and using a Fejér-Riesz type representation for a positive trigonometric sum to handle the instantaneous constraints for these variables. Sufficient conditions for the sequence of approximate optimal solutions of the discretized problems to be an approximately minimizing sequence for the basic problem are given. The constructive character of the proposed approach and its potential applications are pointed out both for dynamic systems affected by irregularly pulsating disturbances and for stationary systems, the non-linear dynamics of which can be exploited by a non-stationary control to improve the averaged system performance.     

Trigonometric approximation of optimal periodic control problems with variable delays

A trigonometric approximation scheme for optimal periodic control problems with state and control dependent delays is considered. The formulation of approximate problems is here adapted to a specific form of state equation with variable time delays. Sufficient conditions for the sequence of nearly optimal solutions of approximate problems to be a generalized minimizing sequence for the basic problem are given. The application of the method proposed to a periodic control of chemical reactors with recycles and controlled piping is pointed out.     

Turnpike solutions of optimal control problems

Minimizing sequences for degenerate optimal control problems are constructed from turnpike solutions. Two variational approximation schemes for the turnpike solution are described: the first is a direct improvement of the simple approximation of piecewise-continuous turnpikes by the solutions of the initial differential system and the second consists of constructing an approximate optimal control in the neighborhood of a turnpike by a parametric curve in the state space. Since a sequence of state-linear feedback controls with variable coefficients is generated in both variants, turnpikes can be easily realized in practice.     

On the computation of multi-dimensional¶single layer harmonic potentials¶via approximate approximations

Multidimensional surface potentials associated with elliptic differential operators are defined by surface integrals involving fundamental solutions of the differential operators which become singular when the observation point approaches the surface. Here we combine the choice of basis functions for the so-called approximate approximation of the surface layer density with the integration of the basis functions over the tangential space by the use of appropriate asymptotic expansions. Our approach leads to cubature formulae involving only nodes of a regular grid. These formulae turn out to be extremely efficient provided the saturation error of the approximate approximation is a priori chosen sufficiently small. Received: August 2002 / Accepted: November 2002     

Approximate greatest common divisor of many polynomials, generalised resultants, and strength of approximation

The computation of the greatest common divisor (GCD) of many polynomials is a nongeneric problem. Techniques defining “approximate GCD” solutions have been defined, but the proper definition of the “approximate” GCD, and the way we can measure the strength of the approximation has remained open. This paper uses recent results on the representation of the GCD of many polynomials, in terms of factorisation of generalised resultants, to define the notion of “approximate GCD” and define the strength of any given approximation by solving an optimisation problem. The newly established framework is used to evaluate the performance of alternative procedures which have been used for defining approximate GCDs.     

A distributed parallel genetic algorithm for solving optimal growth models

We use a distributed parallel genetic algorithm (DPGA) to fund numerical solutions to a single state deterministic optimal growth model for both the infinite and finite horizon cases. To evaluate the DPGA we consider a version of the Taylor-Uhlig problem for which the analytical solutions are known. The first-order conditions for the infinite horizon case lead to a nonlinear integral equation whose solution we approximate using a Chebyshev polynomial series expansion. The DPGA is used to search the parameter space for the optimal fit for this function. For the finite horizon case the DPGA searches the state space for a sequence of states which maximize the agent's discounted utility over the finite horizon. The DPGA runs on a cluster of up to fifty workstations linked via PVM. The topology of the function to be optimized is mapped onto each node on the cluster and the nodes essentially complete with one another for the optimal solution. We demonstrate that the DPGA has several useful features. For instance, the DPGA solves the exact Euler equation over the full range of the state variable and it does not require an accurate initial guess. The DPGA is easily generalized to multiple state problems.     

Sequential synthesis of the time-optimal control in real time

The paper considers the sequential synthesis method for time-optimal control of linear systems. The method is based on piecewise constant finite controls that ensure approximate solutions for time-optimal control problems. A sequence of finite controls is thereafter transformed into the optimal control. The appropriate computations are reduced to a sequence of linear algebraic equation problems and the integration of a matrix differential equation over the intervals of control switching points and final point change. It is proven that the sequence of finite controls converge to the optimal control. The sliding mode conditions are obtained, as well as the control structure modifications for the motions on switching manifolds. The initial approximations reducing considerably computational complexity are considered. The computational algorithm, together with the modelling and numerical results, are presented.     

Difference approximation of optimal periodic control problems

The constrained optimal periodic control problem is approximated by a sequence of discretized problems in which the system of differential equations of the basic continuous problem is replaced by a system of one–step difference equations. Two kinds of approximate optimal controls are derived from the optimal solutions of discretized problems: the first in the form of a step function and the second in the form of a special trigonometric polynomial generated by a positive kernel. Sufficient conditions for approximate solutions to be weakly convergent to the optimal solution of the basic problem are given. Certain improvements in the difference approximation considered are discussed and potential applications given.     

Discontinuous Petrov–Galerkin method with optimal test functions for thin-body problems in solid mechanics

We study the applicability of the discontinuous Petrov–Galerkin (DPG) variational framework for thin-body problems in structural mechanics. Our numerical approach is based on discontinuous piecewise polynomial finite element spaces for the trial functions and approximate, local computation of the corresponding ‘optimal’ test functions. In the Timoshenko beam problem, the proposed method is shown to provide the best approximation in an energy-type norm which is equivalent to the L₂-norm for all the unknowns, uniformly with respect to the thickness parameter. The same formulation remains valid also for the asymptotic Euler–Bernoulli solution. As another one-dimensional model problem we consider the modelling of the so called basic edge effect in shell deformations. In particular, we derive a special norm for the test space which leads to a robust method in terms of the shell thickness. Finally, we demonstrate how a posteriori error estimator arising directly from the discontinuous variational framework can be utilized to generate an optimal hp-mesh for resolving the boundary layer.     

Maximum error-bounded Piecewise Linear Representation for online stream approximation

Given a time series data stream, the generation of error-bounded Piecewise Linear Representation (error-bounded PLR) is to construct a number of consecutive line segments to approximate the stream, such that the approximation error does not exceed a prescribed error bound. In this work, we consider the error bound in \(L_\infty \) norm as approximation criterion, which constrains the approximation error on each corresponding data point, and aim on designing algorithms to generate the minimal number of segments. In the literature, the optimal approximation algorithms are effectively designed based on transformed space other than time-value space, while desirable optimal solutions based on original time domain (i.e., time-value space) are still lacked. In this article, we proposed two linear-time algorithms to construct error-bounded PLR for data stream based on time domain, which are named OptimalPLR and GreedyPLR, respectively. The OptimalPLR is an optimal algorithm that generates minimal number of line segments for the stream approximation, and the GreedyPLR is an alternative solution for the requirements of high efficiency and resource-constrained environment. In order to evaluate the superiority of OptimalPLR, we theoretically analyzed and compared OptimalPLR with the state-of-art optimal solution in transformed space, which also achieves linear complexity. We successfully proved the theoretical equivalence between time-value space and such transformed space, and also discovered the superiority of OptimalPLR on processing efficiency in practice. The extensive results of empirical evaluation support and demonstrate the effectiveness and efficiency of our proposed algorithms.     

HEURISTIC SEARCH UNDER CONTRACT

In this article, we present a heuristic search technique (Contract Search) that can be adapted automatically for a specific node contract. We analyze the node expansion characteristics of best‐first search techniques and identify a probabilistic model (rank profiles) that characterizes the search under restricted expansions. We use the model to formulate an optimal strategy to choose level dependent restriction bounds, maximizing the probability of obtaining the optimal cost goal node under the specified contract. We analyze the basic properties of the rank profiles and establish its relation with the search space configuration and heuristic error distributions. We suggest an approximation scheme for the profile function for unknown search spaces. We show how the basic framework can be adapted to achieve different objectives (like optimizing the expected quality) considering multiple goals and approximate solutions. Experimental comparison with anytime search techniques like ARA* and beam search on a number of search problems shows that Contract Search outperforms these techniques over a range of contract specifications.     

Consistent Sets of Secondary Structures in Proteins

Ab initio predictions of secondary structures in proteins have to combine local predictions, based on short fragments of the protein sequence, with consistency restrictions, as not all locally plausible predictions may be simultaneously true. We use the fact that secondary structures are patterns of hydrogen bonds and that a single residue can participate in hydrogen bonds of at most one secondary structure. Consistency of fixed-sized pieces of secondary structures is the easiest to approximate and we formalize it as 1-2 matching problem. Consistency of entire secondary structures is a version of set packing. We also investigate how to form a simple problem if we add the requirement that the secondary structure and the loops that connect them fit together in a metric space. Every problem that we investigated is MAX-SNP hard and it has a constant factor approximation. Computational experience suggests that in biological instances, we can find nearly optimal solutions using heuristics.     

On robotic optimal path planning in polygonal regions with pseudo-Euclidean metrics.

This paper presents several results on some cost-minimizing path problems in polygonal regions. For these types of problems, an approach often used to compute approximate optimal paths is to apply a discrete search algorithm to a graph G(epsilon) constructed from a discretization of the problem; this graph is guaranteed to contain an epsilon-good approximate optimal path, i.e., a path with a cost within (1 + epsilon) factor of that of an optimal path, between given source and destination points. Here, epsilon > 0 is the user-defined error tolerance ratio. We introduce a class of piecewise pseudo-Euclidean optimal path problems that includes several non-Euclidean optimal path problems previously studied and show that the BUSHWHACK algorithm, which was formerly designed for the weighted region optimal path problem, can be generalized to solve any optimal path problem of this class. We also introduce an empirical method called the adaptive discretization method that improves the performance of the approximation algorithms by placing discretization points densely only in areas that may contain optimal paths. It proceeds in multiple iterations, and in each iteration, it varies the approximation parameters and fine tunes the discretization.     

Optimal control problems with multiple characteristic time points in the objective and constraints

In this paper, we develop a computational method for a class of optimal control problems where the objective and constraint functionals depend on two or more discrete time points. These time points can be either fixed or variable. Using the control parametrization technique and a time scaling transformation, this type of optimal control problem is approximated by a sequence of approximate optimal parameter selection problems. Each of these approximate problems can be viewed as a finite dimensional optimization problem. New gradient formulae for the cost and constraint functions are derived. With these gradient formulae, standard gradient-based optimization methods can be applied to solve each approximate optimal parameter selection problem. For illustration, two numerical examples are solved.     

An efficient evolutionary algorithm for accurate polygonal approximation

An optimization problem for polygonal approximation of 2-D shapes is investigated in this paper. The optimization problem for a digital contour of N points with the approximating polygon of K vertices has a search space of C(N, K) instances, i.e., the number of ways of choosing K vertices out of N points. A genetic-algorithm-based method has been proposed for determining the optimal polygons of digital curves, and its performance is better than that of several existing methods for the polygonal approximation problems. This paper proposes an efficient evolutionary algorithm (EEA) with a novel orthogonal array crossover for obtaining the optimal solution to the polygonal approximation problem. It is shown empirically that the proposed EEA outperforms the existing genetic-algorithm-based method under the same cost conditions in terms of the quality of the best solution, average solution, variance of solutions, and the convergence speed, especially in solving large polygonal approximation problems.     

Solving a category of two-dimensional fractional optimal control problems using discrete Legendre polynomials

In this paper, we formulate a numerical method to approximate the solution of two-dimensional optimal control problem with a fractional parabolic partial differential equation (PDE) constraint in the Caputo type. First, the optimal conditions of the optimal control problems are derived. Then, we discretize the spatial derivatives and time derivatives terms in the optimal conditions by using shifted discrete Legendre polynomials and collocations method. The main idea is simplifying the optimal conditions to a system of algebraic equations. In fact, the main privilege of this new type of discretization is that the numerical solution is directly and globally obtained by solving one efficient algebraic system rather than step-by-step process which avoids accumulation and propagation of error. Several examples are tested and numerical results show a good agreement between exact and approximate solutions.     

Model Predictive Control for Stochastic Resource Allocation

In this paper, we consider a class of stochastic resource allocation problems where resources assigned to a task may fail probabilistically to complete assigned tasks. Failures to complete a task are observed before new resource allocations are selected. The resulting temporal resource allocation problem is a stochastic control problem, with a discrete state space and control space that grow in cardinality exponentially with the number of tasks. We modify this optimal control problem by expanding the admissible control space, and show that the resulting control problem can be solved exactly by efficient algorithms in time that grows nearly linear with the number of tasks. The approximate control problem also provides a bound on the achievable performance for the original control problem. The approximation is used as part of a model predictive control (MPC) algorithm to generate resource allocations over time in response to information on task completion status. We show in computational experiments that, for single resource class problems, the resulting MPC algorithm achieves nearly the same performance as the optimal dynamic programming algorithm while reducing computation time by over four orders of magnitude. In multiple resource class experiments involving 1000 tasks, the model predictive control performance is within 4% of the performance bound obtained by the solution of the expanded control space problem.