POD a-posteriori error analysis for optimal control problems with mixed control-state constraints

In this work linear-quadratic optimal control problems for parabolic equations with mixed control-state constraints are considered. These problems arise when a Lavrentiev regularization is utilized for state constrained linear-quadratic optimal control problems. For the numerical solution a Galerkin discretization is applied utilizing proper orthogonal decomposition (POD). Based on a perturbation method it is determined how far the suboptimal control, computed on the basis of the POD method, is from the (unknown) exact one. Numerical examples illustrate the theoretical results. In particular, the POD Galerkin scheme is applied to a problem with state constraints.     

Variational discretization of Lavrentiev-regularized state constrained elliptic optimal control problems

In the present work, we apply a variational discretization proposed by the first author in (Comput. Optim. Appl. 30:45–61, 2005) to Lavrentiev-regularized state constrained elliptic control problems. We extend the results of (Comput. Optim. Appl. 33:187–208, 2006) and prove weak convergence of the adjoint states and multipliers of the regularized problems to their counterparts of the original problem. Further, we prove error estimates for finite element discretizations of the regularized problem and investigate the overall error imposed by the finite element discretization of the regularized problem compared to the continuous solution of the original problem. Finally we present numerical results which confirm our analytical findings.     

Error estimates for abstract linear–quadratic optimal control problems using proper orthogonal decomposition

In this paper we investigate POD discretizations of abstract linear–quadratic optimal control problems with control constraints. We apply the discrete technique developed by Hinze (Comput. Optim. Appl. 30:45–61, 2005) and prove error estimates for the corresponding discrete controls, where we combine error estimates for the state and the adjoint system from Kunisch and Volkwein (Numer. Math. 90:117–148, 2001; SIAM J. Numer. Anal. 40:492–515, 2002). Finally, we present numerical examples that illustrate the theoretical results.     

Optimal Control of PDEs with Regularized Pointwise State Constraints

This paper addresses the regularization of pointwise state constraints in optimal control problems. By analyzing the associated dual problem, it is shown that the regularized problems admit Lagrange multipliers in L²-spaces. Under a certain boundedness assumption, the solution of the regularized problem converges to the one of the original state constrained problem. The results of our analysis are confirmed by numerical tests. Supported by the DFG Research Center “Mathematics for key technologies” (FZT 86) in Berlin.     

Sensitivity analysis for parametric control problems with control-state constraints

Parametric nonlinear control problems subject to vector-valued mixed control-state constraints are investigated. The model perturbations are implemented by a parameter p of a Banach-space P. We prove solution differentiability in the sense that the optimal solution and the associated adjoint multiplier function are differentiable functions of the parameter. The main assumptions for solution differentiability are composed by regularity conditions and recently developed second-order sufficient conditions (SSC). The analysis generalizes the approach in [16, 20] and establishes a link between (1) shooting techniques for solving the associated boundary value problem (BVP) and (2) SSC. We shall make use of sensitivity results from finite-dimensional parametric programming and exploit the relationships between the variational system associated to BVP and its corresponding Riccati equation.Solution differentiability is the theoretical backbone for any numerical sensitivity analysis. A numerical example with a vector-valued control is presented that illustrates sensitivity analysis in detail.     

Adaptive finite element methods for mixed control-state constrained optimal control problems for elliptic boundary value problems

Mixed control-state constraints are used as a relaxation of originally state constrained optimal control problems for partial differential equations to avoid the intrinsic difficulties arising from measure-valued multipliers in the case of pure state constraints. In particular, numerical solution techniques known from the pure control constrained case such as active set strategies and interior-point methods can be used in an appropriately modified way. However, the residual-type a posteriori error estimators developed for the pure control constrained case can not be applied directly. It is the essence of this paper to show that instead one has to resort to that type of estimators known from the pure state constrained case. Up to data oscillations and consistency error terms, they provide efficient and reliable estimates for the discretization errors in the state, a regularized adjoint state, and the control. A documentation of numerical results is given to illustrate the performance of the estimators.     

Optimal buffer size for a stochastic processing network in heavy traffic

We consider a one-dimensional stochastic control problem that arises from queueing network applications. The state process corresponding to the queue-length process is given by a stochastic differential equation which reflects at the origin. The controller can choose the drift coefficient which represents the service rate and the buffer size b>0. When the queue length reaches b, the new customers are rejected and this incurs a penalty. There are three types of costs involved: A “control cost” related to the dynamically controlled service rate, a “congestion cost” which depends on the queue length and a “rejection penalty” for the rejection of the customers. We consider the problem of minimizing long-term average cost, which is also known as the ergodic cost criterion. We obtain an optimal drift rate (i.e. an optimal service rate) as well as the optimal buffer size b ^*>0. When the buffer size b>0 is fixed and where there is no congestion cost, this problem is similar to the work in Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005). Our method is quite different from that of (Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005)). To obtain a solution to the corresponding Hamilton–Jacobi–Bellman (HJB) equation, we analyze a family of ordinary differential equations. We make use of some specific characteristics of this family of solutions to obtain the optimal buffer size b ^*>0. A.P. Weerasinghe’s research supported by US Army Research Office grant W911NF0510032.     

A priori error estimates for space–time finite element discretization of semilinear parabolic optimal control problems

In this paper, a priori error estimates for space–time finite element discretizations of optimal control problems governed by semilinear parabolic PDEs and subject to pointwise control constraints are derived. We extend the approach from Meidner and Vexler (SIAM Control Optim 47(3):1150–1177, 2008; SIAM Control Optim 47(3):1301–1329, 2008) where linear-quadratic problems have been considered, discretizing the state equation by usual conforming finite elements in space and a discontinuous Galerkin method in time. Error estimates for controls discretized by piecewise constant functions in time and cellwise constant functions in space are derived in detail and we explain how error estimate for further discretization approaches, e.g., cellwise linear discretization in space, the postprocessing approach from Meyer and R?sch (SIAM J Control Optim 43:970–985, 2004), and the variationally discrete approach from Hinze (J Comput Optim Appl 30:45–63, 2005) can be obtained. In addition, we derive an estimate for a setting with finitely many time-dependent controls.     

Semilinear Mixed Problems on Hilbert Complexes and Their Numerical Approximation

Arnold, Falk, and Winther recently showed (Bull. Am. Math. Soc. 47:281–354, 2010) that linear, mixed variational problems, and their numerical approximation by mixed finite element methods, can be studied using the powerful, abstract language of Hilbert complexes. In another recent article (arXiv:), we extended the Arnold–Falk–Winther framework by analyzing variational crimes (à la Strang) on Hilbert complexes. In particular, this gave a treatment of finite element exterior calculus on manifolds, generalizing techniques from surface finite element methods and recovering earlier a priori estimates for the Laplace–Beltrami operator on 2- and 3-surfaces, due to Dziuk (Lecture Notes in Math., vol. 1357:142–155, 1988) and later Demlow (SIAM J. Numer. Anal. 47:805–827, 2009), as special cases. In the present article, we extend the Hilbert complex framework in a second distinct direction: to the study of semilinear mixed problems. We do this, first, by introducing an operator-theoretic reformulation of the linear mixed problem, so that the semilinear problem can be expressed as an abstract Hammerstein equation. This allows us to obtain, for semilinear problems, a priori solution estimates and error estimates that reduce to the Arnold–Falk–Winther results in the linear case. We also consider the impact of variational crimes, extending the results of our previous article to these semilinear problems. As an immediate application, this new framework allows for mixed finite element methods to be applied to semilinear problems on surfaces.     

Sensitivity analysis and the adjoint update strategy for an optimal control problem with mixed control-state constraints

In this article, an optimal control problem subject to a semilinear elliptic equation and mixed control-state constraints is investigated. The problem data depends on certain parameters. Under an assumption of separation of the active sets and a second-order sufficient optimality condition, Bouligand-differentiability (B-differentiability) of the solutions with respect to the parameter is established. Furthermore, an adjoint update strategy is proposed which yields a better approximation of the optimal controls and multipliers than the classical Taylor expansion, with remainder terms vanishing in L ^∞.     

Error estimates for the numerical approximation of Neumann control problems

We continue the discussion of error estimates for the numerical analysis of Neumann boundary control problems we started in Casas et al. (Comput. Optim. Appl. 31:193–219, 2005). In that paper piecewise constant functions were used to approximate the control and a convergence of order O(h) was obtained. Here, we use continuous piecewise linear functions to discretize the control and obtain the rates of convergence in L ²(Γ). Error estimates in the uniform norm are also obtained. We also discuss the approach suggested by Hinze (Comput. Optim. Appl. 30:45–61, 2005) as well as the improvement of the error estimates by making an extra assumption over the set of points corresponding to the active control constraints. Finally, numerical evidence of our estimates is provided. The authors were supported by Ministerio de Ciencia y Tecnología (Spain).     

Error estimates for the discretization of elliptic control problems with pointwise control and state constraints

A family of elliptic optimal control problems with pointwise constraints on control and state is considered. We are interested in approximation of the optimal solution by a finite element discretization of the involved partial differential equations. The discretization error for a problem with mixed state constraints is estimated in the semidiscrete case and in the fully discrete scheme with the convergence of order h|ln h| and h ^1/2, respectively. However, considering the unregularized continuous problem and the discrete regularized version, and choosing suitable relation between the regularization parameter and the mesh size, i.e., ε∼h ², a convergence order arbitrary close to 1, i.e., h ^1−β is obtained. Therefore, we benefit from tuning the involved parameters.     

Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs

In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and simplifying the factor 100 and 27 algorithms of Bǎdoiu et al. (Proceedings of the eighteenth annual ACM–SIAM symposium on discrete algorithms (SODA 2007), pp. 512–521, 2007) and Bǎdoiu et al. (Proceedings of the 11th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2008), Springer, Berlin, pp. 21–34, 2008)). We also present a constant factor algorithm for approximating the optimal distortion of embedding a graph metric into an outerplanar metric. For this, we introduce a general notion of a metric relaxed minor and show that if G contains an α-metric relaxed H-minor, then the distortion of any embedding of G into any metric induced by a H-minor free graph is ≥α. Then, for H=K _2,3, we present an algorithm which either finds an α-relaxed minor, or produces an O(α)-embedding into an outerplanar metric.     

Mesh-independence of semismooth Newton methods for Lavrentiev-regularized state constrained nonlinear optimal control problems

A class of nonlinear elliptic optimal control problems with mixed control-state constraints arising, e.g., in Lavrentiev-type regularized state constrained optimal control is considered. Based on its first order necessary optimality conditions, a semismooth Newton method is proposed and its fast local convergence in function space as well as a mesh-independence principle for appropriate discretizations are proved. The paper ends by a numerical verification of the theoretical results including a study of the algorithm in the case of vanishing Lavrentiev-parameter. The latter process is realized numerically by a combination of a nested iteration concept and an extrapolation technique for the state with respect to the Lavrentiev-parameter.     

A numerical algorithm for singular optimal LQ control systems

A numerical algorithm to obtain the consistent conditions satisfied by singular arcs for singular linear–quadratic optimal control problems is presented. The algorithm is based on the Presymplectic Constraint Algorithm (PCA) by Gotay-Nester (Gotay et al., J Math Phys 19:2388–2399, 1978; Volckaert and Aeyels 1999) that allows to solve presymplectic Hamiltonian systems and that provides a geometrical framework to the Dirac-Bergmann theory of constraints for singular Lagrangian systems (Dirac, Can J Math 2:129–148, 1950). The numerical implementation of the algorithm is based on the singular value decomposition that, on each step, allows to construct a semi-explicit system. Several examples and experiments are discussed, among them a family of arbitrary large singular LQ systems with index 2 and a family of examples of arbitrary large index, all of them exhibiting stable behaviour. Research partially supported by MEC grant MTM2004-07090-C03-03. SIMUMAT-CM, UC3M-MTM-05-028 and CCG06-UC3M/ESP-0850.     

Jacobi spectral Galerkin method for elliptic Neumann problems

This paper is concerned with fast spectral-Galerkin Jacobi algorithms for solving one- and two-dimensional elliptic equations with homogeneous and nonhomogeneous Neumann boundary conditions. The paper extends the algorithms proposed by Shen (SIAM J Sci Comput 15:1489–1505, 1994) and Auteri et al. (J Comput Phys 185:427–444, 2003), based on Legendre polynomials, to Jacobi polynomials with arbitrary α and β. The key to the efficiency of our algorithms is to construct appropriate basis functions with zero slope at the endpoints, which lead to systems with sparse matrices for the discrete variational formulations. The direct solution algorithm developed for the homogeneous Neumann problem in two-dimensions relies upon a tensor product process. Nonhomogeneous Neumann data are accounted for by means of a lifting. Numerical results indicating the high accuracy and effectiveness of these algorithms are presented.     

Parametric continuation method with correction and its applications

The article discusses the parametric continuation method for nonlinear equations. A continuation algorithm with correction is proposed, an approximation accuracy theorem is proved, and issues of efficient numerical implementation are considered. An approach is described to the application of the continuation method for seeking the Pontryagin extremal solution in the optimal control problem. Algorithms developed by the author are applied to optimal control problems nonlinear in control, to problems with a nonsmooth control region, and to affine problems with mixed constraints. Translated from Prikladnaya Matematika i Informatika, No. 30, 2008, pp. 55–94.     

A block coordinate gradient descent method for regularized convex separable optimization and covariance selection

We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ ₁-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated as BCGD) for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n³/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807–1827, 2009; SIAM J Matrix Anal Appl 31:2000–2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for large-scale covariance selection problems with constraints.     

On saturation effects in the Neumann boundary control of elliptic optimal control problems

A Neumann boundary control problem for a linear-quadratic elliptic optimal control problem in a polygonal domain is investigated. The main goal is to show an optimal approximation order for discretized problems after a postprocessing process. It turns out that two saturation processes occur: The regularity of the boundary data of the adjoint is limited if the largest angle of the polygon is at least 2π/3. Moreover, piecewise linear finite elements cannot guarantee the optimal order, if the largest angle of the polygon is greater than π/2. We will derive error estimates of order h ^α with α∈[1,2] depending on the largest angle and properties of the finite elements. Finally, numerical test illustrates the theoretical results.     

Elliptic control problems with gradient constraints—variational discrete versus piecewise constant controls

We consider an elliptic optimal control problem with pointwise bounds on the gradient of the state. To guarantee the required regularity of the state we include the L ^r -norm of the control in our cost functional with r>d (d=2,3). We investigate variational discretization of the control problem (Hinze in Comput. Optim. Appl. 30:45–63, 2005) as well as piecewise constant approximations of the control. In both cases we use standard piecewise linear and continuous finite elements for the discretization of the state. Pointwise bounds on the gradient of the discrete state are enforced element-wise. Error bounds for control and state are obtained in two and three space dimensions depending on the value of r.