Certified Reduced Basis Methods for Parametrized Elliptic Optimal Control Problems with Distributed Controls

In this paper, we consider the efficient and reliable solution of distributed optimal control problems governed by parametrized elliptic partial differential equations. The reduced basis method is used as a low-dimensional surrogate model to solve the optimal control problem. To this end, we introduce reduced basis spaces not only for the state and adjoint variable but also for the distributed control variable. We also propose two different error estimation procedures that provide rigorous bounds for the error in the optimal control and the associated cost functional. The reduced basis optimal control problem and associated a posteriori error bounds can be efficiently evaluated in an offline–online computational procedure, thus making our approach relevant in the many-query or real-time context. We compare our bounds with a previously proposed bound based on the Banach–Ne?as–Babu?ka theory and present numerical results for two model problems: a Graetz flow problem and a heat transfer problem. Finally, we also apply and test the performance of our newly proposed bound on a hyperthermia treatment planning problem.     

New Results on Web Caching with Request Reordering

We study web caching with request reordering. The goal is to maintain a cache of web documents so that a sequence of requests can be served at low cost. To improve cache hit rates, a limited reordering of requests is allowed. Feder et al. (Proceedings of the 13th ACM–SIAM Symposium on Discrete Algorithms, pp. 104–105, 2002), who recently introduced this problem, considered caches of size 1, i.e. a cache can store one document. They presented an offline algorithm based on dynamic programming as well as online algorithms that achieve constant factor competitive ratios. For arbitrary cache sizes, Feder et al. (Theor. Comput. Sci. 324:201–218, 2004) gave online strategies that have nearly optimal competitive ratios in several cost models.     

离线椭圆集的非线性模型预测控制算法研究

针对一类带有约束的非线性系统,提出一种非线性时间最优模型预测控制算法。这种方法首先基于Jacobian线性化将非线性进行线性化,能够推导一系列凸优化问题,而且产生的线性化误差在Lipschitz条件下确定上边界范围。然后采用双重模式策略,在离线情况下构造一系列椭圆集来描述[t]步可行区域,每个椭圆集的平衡点根据上一个椭圆来选取,最后再根据在线计算合适的输入使系统稳定。采用逐步倒退计算的方法能够确保迭代的可行性和稳定性,大大减少了计算负担。数值例子证明了算法的有效性。     

基于RBF神经网络的电动加载控制策略分析

针对电动加载系统特有的多余力矩问题,设计并分析了基于RBF神经网络的直接逆模型控制策略,仿真结果表明,该控制策略能够有效地抑制多余力矩,提高了系统的加载精度及动态特性.同时,本文提出一种改进的RAN算法,离线构建,在线调整,充分利用已有先验知识的同时,实现了网络局部在线优化,有效的控制了运算量及网络规模,为控制算法的硬件实现提供了保证.     

Reduced Basis’ Acquisition by a Learning Process for Rapid On-line Approximation of Solution to PDE’s: Laminar Flow Past a Backstep

Reduced basis methods for the approximation to parameter-dependent partial differential equations are now well-developed and start to be used for industrial applications. The classical implementation of the reduced basis method goes through two stages: in the first one, offline and time consuming, from standard approximation methods a reduced basis is constructed; then in a second stage, online and very cheap, a small problem, of the size of the reduced basis, is solved. The offline stage is a learning one from which the online stage can proceed efficiently. In this paper we propose to exploit machine learning procedures in both offline and online stages to either tackle different classes of problems or increase the speed-up during the online stage. The method is presented through a simple flow problem—a flow past a backward step governed by the Navier Stokes equations—which shows, however, interesting features.     

Improved multi-processor scheduling for?flow time and?energy

Energy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between flow time and energy (Albers and Fujiwara in ACM Trans. Algorithms 3(4), 2007; Bansal et al. in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 805–813, 2007b, Bansal et al. in Proceedings of International Colloquium on Automata, Languages and Programming, pp. 409–420, 2008; Lam et al. in Proceedings of European Symposium on Algorithms, pp. 647–659, 2008b) in the multi-processor setting. Our main result is an enhanced analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m≥2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis that CRR is O(log P)-competitive where P is the ratio of the maximum job size to the minimum job size.     

Moving Mesh Finite Element Methods for an Optimal Control Problem for the Advection-Diffusion Equation

An optimal control problem for the advection-diffusion equation is studied using a Lagrangian-moving mesh finite element method. The weak formulation of the model advection–diffusion equation is based on Lagrangian coordinates, and semi–discrete (in space) error estimates are derived under minimal regularity assumptions. In addition, using these estimates and Brezzi-Rappaz-Raviart theory, symmetric error estimates for the optimality system are derived. The results also apply for advection dominated problems     

A robust error estimator and a residual-free error indicator for reduced basis methods

The Reduced Basis Method (RBM) is a rigorous model reduction approach for solving parameterizedpartial differential equations. It identifies a low-dimensional subspace for approximation of the parametric solution manifold that is embedded in high-dimensional space. A reduced order model is subsequently constructed in this subspace. RBM relies on residual-based error indicators or a posteriori error bounds to guide construction of the reduced solution subspace, to serve as a stopping criteria, and to certify the resulting surrogate solutions. Unfortunately, it is well-known that the standard algorithm for residual norm computation suffers from premature stagnation at the level of the square root of machine precision.In this paper, we develop two alternatives to the standard offline phase of reduced basis algorithms. First, we design a robust strategy for computation of residual error indicators that allows RBM algorithms to enrich the solution subspace with accuracy beyond root machine precision. Secondly, we propose a new error indicator based on the Lebesgue function in interpolation theory. This error indicator does not require computation of residual norms, and instead only requires the ability to compute the RBM solution. This residual-free indicator is rigorous in that it bounds the error committed by the RBM approximation, but up to an uncomputable multiplicative constant. Because of this, the residual-free indicator is effective in choosing snapshots during the offline RBM phase, but cannot currently be used to certify error that the approximation commits. However, it circumvents the need for a posteriori analysis of numerical methods, and therefore can be effective on problems where such a rigorous estimate is hard to derive.     

Optimal control as a graphical model inference problem

We reformulate a class of non-linear stochastic optimal control problems introduced by Todorov (in Advances in Neural Information Processing Systems, vol. 19, pp. 1369–1376, 2007) as a Kullback-Leibler (KL) minimization problem. As a result, the optimal control computation reduces to an inference computation and approximate inference methods can be applied to efficiently compute approximate optimal controls. We show how this KL control theory contains the path integral control method as a special case. We provide an example of a block stacking task and a multi-agent cooperative game where we demonstrate how approximate inference can be successfully applied to instances that are too complex for exact computation. We discuss the relation of the KL control approach to other inference approaches to control.     

Numerical Solution of Optimal Control Problems with Constant Control Delays

We investigate a class of optimal control problems that exhibit constant exogenously given delays in the control in the equation of motion of the differential states. Therefore, we formulate an exemplary optimal control problem with one stock and one control variable and review some analytic properties of an optimal solution. However, analytical considerations are quite limited in case of delayed optimal control problems. In order to overcome these limits, we reformulate the problem and apply direct numerical methods to calculate approximate solutions that give a better understanding of this class of optimization problems. In particular, we present two possibilities to reformulate the delayed optimal control problem into an instantaneous optimal control problem and show how these can be solved numerically with a state-of-the-art direct method by applying Bock’s direct multiple shooting algorithm. We further demonstrate the strength of our approach by two economic examples.      

A Computational Method for Stochastic Optimal Control Problems in Financial Mathematics

Principle of optimality or dynamic programming leads to derivation of a partial differential equation (PDE) for solving optimal control problems, namely the Hamilton‐Jacobi‐Bellman (HJB) equation. In general, this equation cannot be solved analytically; thus many computing strategies have been developed for optimal control problems. Many problems in financial mathematics involve the solution of stochastic optimal control (SOC) problems. In this work, the variational iteration method (VIM) is applied for solving SOC problems. In fact, solutions for the value function and the corresponding optimal strategies are obtained numerically. We solve a stochastic linear regulator problem to investigate the applicability and simplicity of the presented method and prove its convergence. In particular, for Merton's portfolio selection model as a problem of portfolio optimization, the proposed numerical method is applied for the first time and its usefulness is demonstrated. For the nonlinear case, we investigate its convergence using Banach's fixed point theorem. The numerical results confirm the simplicity and efficiency of our method.     

Efficient MFS Algorithms for Inhomogeneous Polyharmonic Problems

In this work we develop an efficient algorithm for the application of the method of fundamental solutions to inhomogeneous polyharmonic problems, that is problems governed by equations of the form Δ ^ℓ u=f, ℓ∈ℕ, in circular geometries. Following the ideas of Alves and Chen (Adv. Comput. Math. 23:125–142, 2005), the right hand side of the equation in question is approximated by a linear combination of fundamental solutions of the Helmholtz equation. A particular solution of the inhomogeneous equation is then easily obtained from this approximation and the resulting homogeneous problem in the method of particular solutions is subsequently solved using the method of fundamental solutions. The fact that both the problem of approximating the right hand side and the homogeneous boundary value problem are performed in a circular geometry, makes it possible to develop efficient matrix decomposition algorithms with fast Fourier transforms for their solution. The efficacy of the method is demonstrated on several test problems.     

Construction of optimal feedback control for nonlinear systems via Chebyshev polynomials

A method is proposed to determine the optimal feedback control law of a class of nonlinear optimal control problems. The method is based on two steps. The first step is to determine the open-hop optimal control and trajectories, by using the quasilinearization and the state variables parametrization via Chebyshev polynomials of the first type. Therefore the nonlinear optimal control problem is replaced by a sequence of small quadratic programming problems which can easily be solved. The second step is to use the results of the last quasilinearization iteration, when an acceptable convergence error is achieved, to obtain the optimal feedback control law. To this end, the matrix Riccati equation and another n linear differential equations are solved using the Chebyshev polynomials of the first type. Moreover, the differentiation operational matrix of Chebyshev polynomials is introduced. To show the effectiveness of the proposed method, the simulation results of a nonlinear optimal control problem are shown.     

Optimal and online preemptive scheduling on uniformly related machines

We consider the problem of preemptive scheduling on uniformly related machines. We present a semi-online algorithm which, if the optimal makespan is given in advance, produces an optimal schedule. Using the standard doubling technique, this yields a 4-competitive deterministic and an e≈2.71-competitive randomized online algorithm. In addition, it matches the performance of the previously known algorithms for the offline case, with a considerably simpler proof. Finally, we study the performance of greedy heuristics for the same problem.     

Solution of Strongly Coupled Multiphysics Problems Using Space-Time Separated Representations—Application to Thermoviscoelasticity

The space-time separated representation method (Ladevèze, C. R. Acad. Sci. Paris 309(II):1095–1099, 1989; Ammar et al., J. Non-Newton. Fluid Mech. 144:98–121, 2007) is here extended to solve strongly coupled multiphysics problems. The feasibility of the method for dealing with strongly coupled multiphysics problems with different characteristic times is here discussed and a new strategy to solve the nonlinear system for the basis enrichment is proposed. The method is validated in the case of a strongly coupled thermoviscoelastic model.     

Optimal tracking control of nonlinear partially-unknown constrained-input systems using integral reinforcement learning

In this paper, a new formulation for the optimal tracking control problem (OTCP) of continuous-time nonlinear systems is presented. This formulation extends the integral reinforcement learning (IRL) technique, a method for solving optimal regulation problems, to learn the solution to the OTCP. Unlike existing solutions to the OTCP, the proposed method does not need to have or to identify knowledge of the system drift dynamics, and it also takes into account the input constraints a priori. An augmented system composed of the error system dynamics and the command generator dynamics is used to introduce a new nonquadratic discounted performance function for the OTCP. This encodes the input constrains into the optimization problem. A tracking Hamilton–Jacobi–Bellman (HJB) equation associated with this nonquadratic performance function is derived which gives the optimal control solution. An online IRL algorithm is presented to learn the solution to the tracking HJB equation without knowing the system drift dynamics. Convergence to a near-optimal control solution and stability of the whole system are shown under a persistence of excitation condition. Simulation examples are provided to show the effectiveness of the proposed method.     

The Canny Edge Detector Revisited

Canny (IEEE Trans. Pattern Anal. Image Proc. 8(6):679-698, 1986) suggested that an optimal edge detector should maximize both signal-to-noise ratio and localization, and he derived mathematical expressions for these criteria. Based on these criteria, he claimed that the optimal step edge detector was similar to a derivative of a gaussian. However, Canny’s work suffers from two problems. First, his derivation of localization criterion is incorrect. Here we provide a more accurate localization criterion and derive the optimal detector from it. Second, and more seriously, the Canny criteria yield an infinitely wide optimal edge detector. The width of the optimal detector can however be limited by considering the effect of the neighbouring edges in the image. If we do so, we find that the optimal step edge detector, according to the Canny criteria, is the derivative of an ISEF filter, proposed by Shen and Castan (Graph. Models Image Proc. 54:112–133, 1992).     

On the use of reduced models obtained through identification for feedback optimal control problems in a heat convection–diffusion problem

This paper deals with the use of reduced models for solving some optimal control problems. More precisely, the reduced model is obtained through the modal identification method. The test case which the algorithms is tested on is based on the flow over a backward-facing step. Though the reduction for the velocity fields for different Reynolds numbers is treated elsewhere [1], only the convection–diffusion equation for the energy problem is treated here. The model reduction is obtained through the solution of a gradient-type optimization problem where the objective function gradient is computed through the adjoint-state method. The obtained reduced models are validated before being coupled to optimal control algorithms. In this paper the feedback optimal control problem is considered. A Riccati equation is solved along with the Kalman gain equation. Additionally, a Kalman filter is performed to reconstruct the reduced state through previous and actual measurements. The numerical test case shows the ability of the proposed approach to control systems through the use of reduced models obtained by the modal identification method.     

A New Mapped Weighted Essentially Non-oscillatory Scheme

The weighted essentially non-oscillatory (WENO) methods are a popular high-order spatial discretization for hyperbolic partial differential equations. Recently Henrick et al. (J. Comput. Phys. 207:542–567, 2005) noted that the fifth-order WENO method by Jiang and Shu (J. Comput. Phys. 126:202–228, 1996) is only third-order accurate near critical points of the smooth regions in general. Using a simple mapping function to the original weights in Jiang and Shu (J. Comput. Phys. 126:202–228, 1996), Henrick et al. developed a mapped WENO method to achieve the optimal order of accuracy near critical points. In this paper we study the mapped WENO scheme and find that, when it is used for solving the problems with discontinuities, the mapping function in Henrick et al. (J. Comput. Phys. 207:542–567, 2005) may amplify the effect from the non-smooth stencils and thus cause a potential loss of accuracy near discontinuities. This effect may be difficult to be observed for the fifth-order WENO method unless a long time simulation is desired. However, if the mapping function is applied to seventh-order WENO methods (Balsara and Shu in J. Comput. Phys. 160:405–452, 2000), the error can increase much faster so that it can be observed with a moderate output time. In this paper a new mapping function is proposed to overcome this potential loss of accuracy.     

Convex multi-task feature learning

We present a method for learning sparse representations shared across multiple tasks. This method is a generalization of the well-known single-task 1-norm regularization. It is based on a novel non-convex regularizer which controls the number of learned features common across the tasks. We prove that the method is equivalent to solving a convex optimization problem for which there is an iterative algorithm which converges to an optimal solution. The algorithm has a simple interpretation: it alternately performs a supervised and an unsupervised step, where in the former step it learns task-specific functions and in the latter step it learns common-across-tasks sparse representations for these functions. We also provide an extension of the algorithm which learns sparse nonlinear representations using kernels. We report experiments on simulated and real data sets which demonstrate that the proposed method can both improve the performance relative to learning each task independently and lead to a few learned features common across related tasks. Our algorithm can also be used, as a special case, to simply select—not learn—a few common variables across the tasks. Editors: Daniel Silver, Kristin Bennett, Richard Caruana. This is a longer version of the conference paper (Argyriou et al. in Advances in neural information processing systems, vol. 19, 2007a). It includes new theoretical and experimental results.