Two-level primal-dual decomposition technique for large-scale nonconvex optimization problems with constraints

A two-level decomposition method for nonconvex separable optimization problems with additional local constraints of general inequality type is presented and thoroughly analyzed in the paper. The method is of primal-dual type, based on an augmentation of the Lagrange function. Previous methods of this type were in fact three-level, with adjustment of the Lagrange multipliers at one of the levels. This level is eliminated in the present approach by replacing the multipliers by a formula depending only on primal variables and Kuhn-Tucker multipliers for the local constraints. The primal variables and the Kuhn-Tucker multipliers are together the higher-level variables, which are updated simultaneously. Algorithms for this updating are proposed in the paper, together with their convergence analysis, which gives also indications on how to choose penalty coefficients of the augmented Lagrangian. Finally, numerical examples are presented.     

参数识别问题混合有限元解的最大模误差估计

研究了参数识别问题混合有限元解的最大模误差估计.利用1阶Raviart-Thomas混合有限元离散状态和对偶状态变量,利用分片线性函数逼近控制变量,获得了状态变量和控制变量的最大模误差估计,这里控制变量的收敛阶是h~2,状态变量的收敛阶是h3/2|lnh|1/2.最后利用数值算例验证了理论结果.     

A hybridized weak Galerkin finite element scheme for the Stokes equations

In this paper a hybridized weak Galerkin(HWG) finite element method for solving the Stokes equations in the primary velocity-pressure formulation is introduced.The WG method uses weak functions and their weak derivatives which are defined as distributions.Weak functions and weak derivatives can be approximated by piecewise polynomials with various degrees.Different combination of polynomial spaces leads to different WG finite element methods,which makes WG methods highly flexible and efficient in practical computation.A Lagrange multiplier is introduced to provide a numerical approximation for certain derivatives of the exact solution.With this new feature,the HWG method can be used to deal with jumps of the functions and their flux easily.Optimal order error estimates are established for the corresponding HWG finite element approximations for both primal variables and the Lagrange multiplier.A Schur complement formulation of the HWG method is derived for implementation purpose.The validity of the theoretical results is demonstrated in numerical tests.     

On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions

Assuming that the primal part of the sequence generated by a Newton-type (e.g., SQP) method applied to an equality-constrained problem converges to a solution where the constraints are degenerate, we investigate whether the dual part of the sequence is attracted by those Lagrange multipliers which satisfy second-order sufficient condition (SOSC) for optimality, or by those multipliers which violate it. This question is relevant at least for two reasons: one is speed of convergence of standard methods; the other is applicability of some recently proposed approaches for handling degenerate constraints. We show that for the class of damped Newton methods, convergence of the dual sequence to multipliers satisfying SOSC is unlikely to occur. We support our findings by numerical experiments. We also suggest a simple auxiliary procedure for computing multiplier estimates, which does not have this undesirable property. Finally, some consequences for the case of mixed equality and inequality constraints are discussed.     

Error Estimates and Superconvergence of RT0 Mixed Methods for a Class of Semilinear Elliptic Optimal Control Problems

In this paper, we will investigate the error estimates and the superconvergence property of mixed finite element methods for a semilinear elliptic control problem with an integral constraint on control. The state and co-state are approximated by the lowest order Raviart-Thomas mixed finite element and the control variable is approximated by piecewise constant functions. We derive some superconvergence properties for the control variable and the state variables. Moreover, we derive $L^∞$- and $H^{-1}$-error estimates both for the control variable and the state variables. Finally, a numerical example is given to demonstrate the theoretical results.     

混合有限元法的误差分析

关于混合变分问题有限元方法的研究工作,见[1]—[4].其中已得出混合法的最优误差估计.本文讨论抽象混合有限元法的误差并证明一些超收敛估计,然后将其应用到具体问题上,即应用到一个四阶边值问题和一个二阶边值问题.     

Error estimates of mixed finite element methods for quadratic optimal control problems

In this paper, we investigate the error estimates for the solutions of optimal control problems by mixed finite element methods. The state and costate are approximated by Raviart-Thomas mixed finite element spaces of order k and the control is approximated by piecewise polynomials of order k. Under the special constraint set, we will show that the control variable can be smooth in the whole domain. We derive error estimates of optimal order both for the state variables and the control variable.     

An a priori error estimate for a monotone mixed finite-element discretization of a convection–diffusion problem

We present a local exponential fitting hybridized mixed finite-element method for convection–diffusion problem on a bounded domain with mixed Dirichlet Neuman boundary conditions. With a new technique that interpretes the algebraic system after static condensation as a bilinear form acting on certain lifting operators we prove an a priori error estimate on the Lagrange multipliers that requires minimal regularity. While an extension of more classical arguments provide an estimate for the other solution components.     

The multipliers‐free domain decomposition methods

This article concludes the development and summarizes a new approach to dual‐primal domain decomposition methods (DDM), generally referred to as “the multipliers‐free dual‐primal method.” Contrary to standard approaches, these new dual‐primal methods are formulated without recourse to Lagrange‐multipliers. In this manner, simple and unified matrix‐expressions, which include the most important dual‐primal methods that exist at present are obtained, which can be effectively applied to floating subdomains, as well. The derivation of such general matrix‐formulas is independent of the partial differential equations that originate them and of the number of dimensions of the problem. This yields robust and easy‐to‐construct computer codes. In particular, 2D codes can be easily transformed into 3D codes. The systematic use of the average and jump matrices, which are introduced in this approach as generalizations of the “average” and “jump” of a function, can be effectively applied not only at internal‐boundary‐nodes but also at edges and corners. Their use yields significant advantages because of their superior algebraic and computational properties. Furthermore, it is shown that some well‐known difficulties that occur when primal nodes are introduced are efficiently handled by the multipliers‐free dual‐primal method. The concept of the Steklov–Poincaré operator for matrices is revised by our theory and a new version of it, which has clear advantages over standard definitions, is given. Extensive numerical experiments that confirm the efficiency of the multipliers‐free dual‐primal methods are also reported here. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

UNIFORM STABILITY AND ERROR ANALYSIS FOR SOME DISCONTINUOUS GALERKIN METHODS

In this paper,we provide a number of new estimates on the stability and convergence of both hybrid discontinuous Galerkin(HDG)and weak Galerkin(WG)methods.By using the standard Brezzi theory on mixed methods,we carefully define appropriate norms for the various discretization variables and then establish that the stability and error estimates hold uniformly with respect to stabilization and discretization parameters.As a result,by taking appropriate limit of the stabilization parameters,we show that the HDG method converges to a primal conforming method and the WG method converges to a mixed conforming method.     

Application of functional error estimates with mixed approximations to plane problems of linear elasticity

S.I. Repin and his colleagues’ studies addressing functional a posteriori error estimates for solutions of linear elasticity problems are further developed. Although the numerical results obtained for planar problems by A.V. Muzalevsky and Repin point to advantages of the adaptive approach used, the degree of overestimation of the absolute error increases noticeably with mesh refinement. This shortcoming is eliminated by using approximations typical of mixed finite element methods. A comparative analysis is conducted for the classical finite element approximations, mixed Raviart-Thomas approximations, and relatively recently proposed Arnold-Boffi-Falk mixed approximations. It is shown that the last approximations are the most efficient.     

Adaptive Hybridized Interior Penalty Discontinuous Galerkin Methods for H(curl)-Elliptic Problems

We develop and analyze an adaptive hybridized Interior Penalty Discontinuous Galerkin (IPDG-H) method for H(curl)-elliptic boundary value problems in 2D or 3D arising from a semi-discretization of the eddy currents equations. The method can be derived from a mixed formulation of the given boundary value problem and involves a Lagrange multiplier that is an approximation of the tangential traces of the primal variable on the interfaces of the underlying triangulation of the computational domain. It is shown that the IPDG-H technique can be equivalently formulated and thus implemented as a mortar method. The mesh adaptation is based on a residual-type a posteriori error estimator consisting of element and face residuals. Within a unified framework for adaptive finite element methods, we prove the reliability of the estimator up to a consistency error. The performance of the adaptive symmetric IPDG-H method is documented by numerical results for representative test examples in 2D.     

Mixed Finite Element Methods for Fourth Order Elliptic Optimal Control Problems

In this paper, a priori error estimates are derived for the mixed finite element discretization of optimal control problems governed by fourth order elliptic partial differential equations. The state and co-state are discretized by Raviart-Thomas mixed finite element spaces and the control variable is approximated by piecewise constant functions. The error estimates derived for the state variable as well as those for the control variable seem to be new. We illustrate with a numerical example to confirm our theoretical results.     

Multilevel Preconditioners for Mixed Methods for Second Order Elliptic Problems

A new approach for constructing algebraic multilevel preconditioners for mixed finite element methods for second order elliptic problems with tensor coefficients on general geometry is proposed. The linear system arising from the mixed methods is first algebraically condensed to a symmetric, positive definite system for Lagrange multipliers, which corresponds to a linear system generated by standard nonconforming finite element methods. Algebraic multilevel preconditioners for this system are then constructed based on a triangulation of the domain into tetrahedral substructures. Explicit estimates of condition numbers and simple computational schemes are established for the constructed preconditioners. Finally, numerical results for the mixed finite element methods are presented to illustrate the present theory.     

EXPLICIT ERROR ESTIMATES FOR MIXED AND NONCONFORMING FINITE ELEMENTS

In this paper, we study the explicit expressions of the constants in the error estimates of the lowest order mixed and nonconforming finite element methods. We start with an explicit relation between the error constant of the lowest order Raviart-Thomas interpolation error and the geometric characters of the triangle. This gives an explicit error constant of the lowest order mixed finite element method. Furthermore, similar results can be ex- tended to the nonconforming P1 scheme based on its close connection with the lowest order Raviart-Thomas method. Meanwhile, such explicit a priori error estimates can be used as computable error bounds, which are also consistent with the maximal angle condition for the optimal error estimates of mixed and nonconforming finite element methods.     

Experiments with primal - dual decomposition and subgradient methods for the uncapacitatied facility location problem

For optimization problems that are structured both with respect to the constraints and with respect to the variables, it is possible to use primal–dual solution approaches, based on decomposition principles. One can construct a primal subproblem, by fixing some variables, and a dual subproblem, by relaxing some constraints and king their Lagrange multipliers, so that both these problems are much easier to solve than the original problem. We study methods based on these subproblems, that do not include the difficult Benders or Dantzig-Wolfe master problems, namely primal–dual subgradient optimization methods, mean value cross decomposition, and several comtbinations of the different techniques. In this paper, these solution approaches are applied to the well-known uncapacitated facility location problem. Computational tests show that some combination methods yield near-optimal solutions quicker than the classical dual ascent method of Erlenkotter     

EFK方程一个新的低阶非协调混合有限元方法的高精度分析

对Extended Fisher-Kolmogorov(EFK)方程,利用EQ_1~(rot)元和零阶RaviartThomas(R-T)元建立了一个新的非协调混合元逼近格式.首先,证明了半离散格式逼近解的一个先验估计并证明了逼近解的存在唯一性.在半离散格式下,利用上述两种元的高精度分析结果以及这个先验估计,在不需要有限元解u_h属于L~∞的条件下,得到了原始变量u和中间变量v=-?u的H~1-模以及流量p=u的(L~2)~2-模意义下O(h~2)阶的超逼近性质.同时,借助插值后处理技术,证明了上述变量的具有O(h~2)阶的整体超收敛结果.其次,建立了一个新的线性化向后Euler全离散格式并证明了其逼近解的存在唯一性.另一方面,通过对相容误差和非线性项采取与传统误差分析不同的新的分裂技巧,分别导出了以往文献中尚未涉及的关于u和v在H~1-模以及p在(L~2)~2-模意义下具有O(h~2+τ)阶的超逼近性质,进一步地,借助插值后处理技术,得到了上述变量的整体超收敛结果.这里h和τ分别表示空间剖分参数和时间步长.最后,给出了一个数值算例,计算结果验证了理论分析的正确性.     

Superconvergence and a posteriori error estimates of RT1 mixed methods for elliptic control problems with an integral constraint

In this paper, we investigate the superconvergence property and a posteriori error estimates of mixed finite element methods for a linear elliptic control problem with an integral constraint. The state and co-state are approximated by the order k = 1 Raviart-Thomas mixed finite element spaces and the control variable is approximated by piecewise constant functions. Approximations of the optimal control of the continuous optimal control problem will be constructed by a projection of the discrete adjoint state. It is proved that these approximations have convergence order h ². Moreover, we derive a posteriori error estimates both for the control variable and the state variables. Finally, a numerical example is given to demonstrate the theoretical results.     

Superconvergence and $L^∞$-Error Estimates of the Lowest Order Mixed Methods for Distributed Optimal Control Problems Governed by Semilinear Elliptic Equations

In this paper, we investigate the superconvergence property and the $L^∞$-error estimates of mixed finite element methods for a semilinear elliptic control problem. The state and co-state are approximated by the lowest order Raviart-Thomas mixed finite element spaces and the control variable is approximated by piecewise constant functions. We derive some superconvergence results for the control variable. Moreover, we derive $L^∞$-error estimates both for the control variable and the state variables. Finally, a numerical example is given to demonstrate the theoretical results.     

特征值问题混合有限元法的一个误差估计

设（λh,σh,uh）是一个混合有限元特征对.Babuska和Osborn建立了（λh,uh）的误差估计.本文导出了σh的抽象误差估计式.并把该估计式应用于二阶椭圆特征值问题Raviart-Thomas混合有限元格式和重调和算子特征值问题Ciarlet-Raviart混合有限元格式,得到了一些新的误差估计.