Convex hull property and maximum principle for finite element minimisers of general convex functionals

The convex hull property is the natural generalization of maximum principles from scalar to vector valued functions. Maximum principles for finite element approximations are often crucial for the preservation of qualitative properties of the respective physical model. In this work we develop a convex hull property for $\mathbb{P }_1$ conforming finite elements on simplicial non-obtuse meshes. The proof does not resort to linear structures of partial differential equations but directly addresses properties of the minimiser of a convex energy functional. Therefore, the result holds for very general nonlinear partial differential equations including e.g. the $p$ -Laplacian and the mean curvature problem. In the case of scalar equations the introduce techniques can be used to prove standard discrete maximum principles for nonlinear problems. We conclude by proving a strong discrete convex hull property on strictly acute triangulations.     

Numerical analysis of relaxed micromagnetics by penalised finite elements

Summary. Some micromagnetic phenomena in rigid (ferro-)magnetic materials can be modelled by a non-convex minimisation problem. Typically, minimising sequences develop finer and finer oscillations and their weak limits do not attain the infimal energy. Solutions exist in a generalised sense and the observed microstructure can be described in terms of Young measures. A relaxation by convexifying the energy density resolves the essential macroscopic information. The numerical analysis of the relaxed problem faces convex but degenerated energy functionals in a setting similar to mixed finite element formulations. The lowest order conforming finite element schemes appear instable and nonconforming finite element methods are proposed. An a priori and a posteriori error analysis is presented for a penalised version of the side-restriction that the modulus of the magnetic field is bounded pointwise. Residual-based adaptive algorithms are proposed and experimentally shown to be efficient. Received June 24, 1999 / Revised version received August 24, 2000 / Published online May 4, 2001     

Nonconforming P1 elements on distorted triangulations: Lower bounds for the discrete energy norm error

Compared to conforming P1 finite elements, nonconforming P1 finite element discretizations are thought to be less sensitive to the appearance of distorted triangulations. E.g., optimal-order discrete H¹ norm best approximation error estimates for H² functions hold for arbitrary triangulations. However, the constants in similar estimates for the error of the Galerkin projection for second-order elliptic problems show a dependence on the maximum angle of all triangles in the triangulation. We demonstrate on an example of a special family of distorted triangulations that this dependence is essential, and due to the deterioration of the consistency error. We also provide examples of sequences of triangulations such that the nonconforming P1 Galerkin projections for a Poisson problem with polynomial solution do not converge or converge at arbitrarily low speed. The results complement analogous findings for conforming P1 finite elements.     

Comparison principles applied to obstacle problems with penalties

Penalty methods form a well known technique to embed elliptic variational inequality problems into a family of variational equations (cf. [6], [13], [17]). Using the specific inverse monotonicity properties of these problems L _∞-bounds for the convergence can be derived by means of comparison solutions. Lagrange duality is applied to estimate parameters involved.

For piecewise linear finite elements applied on weakly acute triangulations in combination with mass lumping the inverse monotonicity of the obstacle problems can be transferred to its discretization. This forms the base of similar error estimations in the maximum norm for the penalty method applied to the discrete problem.

The technique of comparison solutions combined with the uniform boundedness of the Lagrange multipliers leads to decoupled convergence estimations with respect to the discretization and penalization parameters.     

The Number of Geometric Bistellar Neighbors of a Triangulation

The theory of secondary and fiber polytopes implies that regular (also called convex or coherent) triangulations of configurations with n points in R ^d have at least n-d-1 geometric bistellar neighbors. Here we prove that, in fact, all triangulations of n points in R ² have at least n-3 geometric bistellar neighbors. In a similar way, we show that for three-dimensional point configurations, in convex position and with no three points collinear, all triangulations have at least n-4 geometric bistellar flips. In contrast, we exhibit three-dimensional point configurations, with a single interior point, having deficiency on the number of geometric bistellar flips. A lifting technique allows us to obtain a triangulation of a simplicial convex 4-polytope with less than n-5 neighbors. We also construct a family of point configurations in R ³ with arbitrarily large flip deficiency. Received November 25, 1996, and in revised form March 10, 1997.     

An averaging scheme for macroscopic numerical simulation of nonconvex minimization problems

Averaging or gradient recovery techniques, which are a popular tool for improved convergence or superconvergence of finite element methods in elliptic partial differential equations, have not been recommended for nonconvex minimization problems as the energy minimization process enforces finer and finer oscillations and hence at the first glance, a smoothing step appears even counterproductive. For macroscopic quantities such as the stress field, however, this counterargument is no longer true. In fact, this paper advertises an averaging technique for a surprisingly improved convergence behavior for nonconvex minimization problems. Similar to a finite volume scheme, numerical experiments on a double-well benchmark example provide empirical evidence of superconvergence phenomena in macroscopic numerical simulations of oscillating microstructures. AMS subject classification (2000)  65K10,65N30     

Ferromagnets with biquadratic exchange coupling energy. Global existence of weak solutions

A global existence theorem is proved for the Landau–Lifshitz–Gilbert equations with biquadratic exchange coupling energy acting on the interfaces of a material composed by two ferromagnetic layers separated by a nonmagnetic one. This energy is not convex. The magnetization M satisfies on the interfaces a coupled non‐linear Neumann boundary condition with cubic growth. We use several regularizations, in particular for the traces of the magnetization at the interfaces, to obtain global weak solutions of the problem with finite energy. Copyright © 2005 John Wiley & Sons, Ltd.     

Study of a special nonlinear problem arising in convex semi-infinite programming

We consider convex problems of semi-infinite programming (SIP) using an approach based on the implicit optimality criterion. This criterion allows one to replace optimality conditions for a feasible solution x ⁰ of the convex SIP problem by such conditions for x ⁰ in some nonlinear programming (NLP) problem denoted by NLP(I(x ⁰)). This nonlinear problem, constructed on the base of special characteristics of the original SIP problem, so-called immobile indices and their immobility orders, has a special structure and a diversity of important properties. We study these properties and use them to obtain efficient explicit optimality conditions for the problem NLP(I(x ⁰)). Application of these conditions, together with the implicit optimality criterion, gives new efficient optimality conditions for convex SIP problems. Special attention is paid to SIP problems whose constraints do not satisfy the Slater condition and to problems with analytic constraint functions for which we obtain optimality conditions in the form of a criterion. Comparison with some known optimality conditions for convex SIP is provided.     

On the LASSO and its Dual

Abstract

Proposed by Tibshirani, the least absolute shrinkage and selection operator (LASSO) estimates a vector of regression coefficients by minimizing the residual sum of squares subject to a constraint on the l ¹-norm of the coefficient vector. The LASSO estimator typically has one or more zero elements and thus shares characteristics of both shrinkage estimation and variable selection. In this article we treat the LASSO as a convex programming problem and derive its dual. Consideration of the primal and dual problems together leads to important new insights into the characteristics of the LASSO estimator and to an improved method for estimating its covariance matrix. Using these results we also develop an efficient algorithm for computing LASSO estimates which is usable even in cases where the number of regressors exceeds the number of observations. An S-Plus library based on this algorithm is available from StatLib.     

Conform and mixed finite element schemes for the Dirichlet problem for the Bilaplacian in plane domains with corners

In plane domains with corners for the Bilaplacian a uniquely solvable conform variational principle is studied on weighted Sobolev spaces which is equivalent to the standard Dirichlet problem in the weak form. Clamped plates under point forces near corners are handled by this approach. With weighted Hsieh-Clough-Tocher elements on regular triangulations as conform C¹-finite elements a new error analysis is performed without higher regularity assumptions on the exact solution than given by the data and the boundary. The rate of convergence of the error depends on the eigenvalue with smallest imaginary part of a clamped infinite wedge since this eigenvalue describes the singularity of the exact solution in a sector with same angle. Using different spaces of trial and test functions in the standard Galerkin procedure it is shown that the error in the weighted energy norm does not pollute. For convex corners asymptotic error estimates, are proved yielding convergence for a mixed method in hydrodynamics where the solution of a system of 2^nd order and its Laplacian are approximated simultaneously by C⁰-finite elements being piecewise polynomials.     

Maxwell and Lamé eigenvalues on polyhedra

In a convex polyhedron, a part of the Lamé eigenvalues with hard simple support boundary conditions does not depend on the Lamé coefficients and coincides with the Maxwell eigenvalues. The other eigenvalues depend linearly on a parameter s linked to the Lamé coefficients and the associated eigenmodes are the gradients of the Laplace–Dirichlet eigenfunctions. In a non‐convex polyhedron, such a splitting of the spectrum disappears partly or completely, in relation with the non‐H² singularities of the Laplace–Dirichlet eigenfunctions. From the Maxwell equations point of view, this means that in a non‐convex polyhedron, the spectrum cannot be approximated by finite element methods using H¹ elements. Similar properties hold in polygons. We give numerical results for two L‐shaped domains. Copyright © 1999 John Wiley & Sons, Ltd.     

Numerical instabilities in structural optimization – analogy between topology & shape design problems

The formulation of structural optimization problems on the basis of the finite–element–method often leads to numerical instabilities resulting in non–optimal designs, which turn out to be difficult to realize from the engineering point of view. In the case of topology optimization problems the formation of designs characterized by oscillating density distributions such as the well–known “checkerboard–patterns” can be observed, whereas the solution of shape optimization problems often results in unfavourable designs with non–smooth boundary shapes caused by high–frequency oscillations of the boundary shape functions. Furthermore a strong dependence of the obtained designs on the finite–element–mesh can be observed in both cases. In this context we have already shown, that the topology design problem can be regularized by penalizing spatial oscillations of the density function by means of a penalty–approach based on the density gradient. In the present paper we apply the idea of problem regularization by penalizing oscillations of the design variable to overcome the numerical difficulties related to the shape design problem, where an analogous approach restricting the boundary surface can be introduced. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.     

Numerical homogenization of foam-like structures based on the FE2-approach

The computation of foam–like structures is still a topic of research. There are two basic approaches: the microscopic model where the foam–like structure is entirely resolved by a discretization (e.g. with Timoshenko beams) on a micro level, and the macroscopic approach which is based on a higher order continuum theory. A combination of both of them is the FE²-approach where the mechanical parameters of the macroscopic scale are obtained by solving a Dirichlet boundary value problem for a representative microstructure at each integration point. In this contribution, we present a two–dimensional geometrically nonlinear FE²-framework of first order (classical continuum theories on both scales) where the microstructures are discretized by continuum finite elements based on the p-version. The p-version elements have turned out to be highly efficient for many problems in structural mechanics. Further, a continuum–based approach affords two additional advantages: the formulation of geometrical and material nonlinearities is easier, and there is no problem when dealing with thicker beam–like structures. In our numerical example we will investigate a simple macroscopic shear test. Both the macroscopic load displacement behavior and the evolving anisotropy of the microstructures will be discussed. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Convex Minimization on a Grid and Applications

This article discusses a discrete version of the convex minimization problem with applications to the efficient computation of proximity measures for pairs of convex polyhedra. Given ad-variate convex function and an isothetic grid of sizeO(n^d) in ^d, which is supposed to be finite but not necessarily regular, we want to find the grid cell containing the minimum point. With this aim, we identify a class of elementary subproblems, each resulting in the determination of a half-space in ^d, and show that the minimization problem can be solved by computingO(log n) half-spaces in the worst case foralmost uniformgrids of fixed dimensiondandO(log n) half-planes in the average for arbitrary planar grids. A major point is the potential of the approach to uniformly solve distance related problems for different configurations of a pair of convex bodies. In this respect, the case of a bivariate function is of particular interest and leads to a fast algorithm for detecting collisions between two convex polyhedra in three dimensions. The collision algorithm runs inO(log² n) average time for polyhedra withO(n) vertices whose boundaries are suitably represented; more specifically, the 1-skeletons can be embedded into layered Directed Acyclic Graphs which require justO(n) storage. The article ends with a brief discussion of a few experimental results.     

Toric Ideals and an Infinite Family of Normal (0, 1)-Polytopes without Unimodular Regular Triangulations

Abstract. An infinite family of normal (0,1) -polytopes, none of whose unimodular triangulations is regular, is constructed. For the construction, we discuss triangulations of convex polytopes and flips of triangulations by studying markings on the set of circuits of toric ideals.     

Flipping Edges in Triangulations

In this paper we study the problem of flipping edges in triangulations of polygons and point sets. One of the main results is that any triangulation of a set of n points in general position contains at least edges that can be flipped. We also prove that O(n + k ² ) flips are sufficient to transform any triangulation of an n -gon with k reflex vertices into any other triangulation. We produce examples of n -gons with triangulations T and T' such that to transform T into T' requires Ω(n ² ) flips. Finally we show that if a set of n points has k convex layers, then any triangulation of the point set can be transformed into any other triangulation using at most O(kn) flips. Received May 13, 1997, and in revised form July 21, 1998, and February 1, 1999.     

On some relationships between biorthogonal systems,linear topologies and the weak‐AFPP

In this paper, we obtain new results for the weak‐AFPP in abstract spaces by exploiting biorthogonal systems techniques. Firstly, we investigate the strong‐AFPP on countably infinite dimensional Hausdorff locally convex spaces. Spaces of this class are shown to be sequentially complete iff they have the hereditary FPP for totally bounded, closed convex sets. This might open a research line for the analysis of weak‐AFPP in such frames. In connection, we provide a simple criterion for the containement of ?₁‐sequences in terms of strongly‐equicontinuous biorthogonal systems. We then establish a few results concerning the existence of Hausdorff finer vector topologies on abstract spaces having as prescribed condition the existence of such systems. The proofs are based on methods of Peck and Porta concerning building of finer vector topologies, and a classical construction of Singer which allows us to prove under rather natural conditions the existence of equicontinuous biorthogonal systems in metrizable locally convex spaces. These results are compatible with the failure of the weak‐AFPP. We also study the inverse problem by proving that every infinite dimensional vector space admits a (non‐locally convex) Hausdorff vector topology which is complete, non‐metrizable and is compatible with a bounded Hamel Schauder basis. It is shown further that such a topology has the ‐AFPP, where is the linear span of coefficient functionals associated to a Hamel basis. Finally, inspired by a result of Shapiro, we observe that if X is a non‐locally convex F‐space with an absolute basis, then the weak‐AFPP is equivalent to the fact that every bounded convex subset of X is compact.     

Analysis of a Prototypical Multiscale Method Coupling Atomistic and Continuum Mechanics： the Convex Case

In order to describe a solid which deforms smoothly in some region,but non smoothly in someother region,many multiscale methods have been recently proposed that aim at coupling an atomistic model(discrete mechanics) with a macroscopic model (continuum mechanics).We provide here a theoretical basis forsuch a coupling in a one-dimensional setting,in the case of convex energy.