On optimality conditions of relaxed non-convex variational problems

Non-convex variational problems in many situations lack a classical solution. Still they can be solved in a generalized sense, e.g., they can be relaxed by means of Young measures. Various sets of optimality conditions of the relaxed non-convex variational problems can be introduced. For example, the so-called “variations” of Young measures lead to a set of optimality conditions, or the Weierstrass maximum principle can be the base of another set of optimality conditions. Moreover the second order necessary and sufficient optimality conditions can be derived from the geometry of the relaxed problem. In this article the sets of optimality conditions are compared. Illustrative examples are included.     

On the numerical analysis of non-convex variational problems

Summary. We discuss a numerical method for finding Young-measure-valued minimizers of non-convex variational problems. To have any hope of a convergence theorem, one must work in a setting where the minimizer is unique and minimizing sequences converge strongly. This paper has two main goals: (i) we specify a method for producing strongly-convergent minimizing sequences, despite the failure of strict convexity; and (ii) we show how uniqueness of the Young measure can be parlayed into a numerical convergence theorem. The treatment of (ii) is done in the setting of two model problems, one involving scalar valued functions and a multiwell energy, the other from micromagnetics. Received July 29, 1995     

Projection Method Approach for General Regularized Non-convex Variational Inequalities

In this paper, we investigate or analyze non-convex variational inequalities and general non-convex variational inequalities. Two new classes of non-convex variational inequalities, named regularized non-convex variational inequalities and general regularized non-convex variational inequalities, are introduced, and the equivalence between these two classes of non-convex variational inequalities and the fixed point problems are established. A projection iterative method to approximate the solutions of general regularized non-convex variational inequalities is suggested. Meanwhile, the existence and uniqueness of solution for general regularized non-convex variational inequalities is proved, and the convergence analysis of the proposed iterative algorithm under certain conditions is studied.     

Numerical approximation of non-homogeneous, non-convex vector variational problems

Summary. In this paper we study a numerical scheme for non-convex vector variational problems allowing for microstructure, based on the approximation of gradient Young measures. We present a convergence result and some numerical experiments. Received March 26, 2000 / Revised version received November 13, 2000 / Published online March 20, 2001     

Variational principles with integrands defined through a minimum

We revisit a systematic approach for the computation and analysis of the convex hull of non-convex integrands defined through the minimum of convex densities. It consists in reformulating the non-convex variational problem as a double minimization and exploiting appropriately the nature of optimality of the inner minimization. This requires gradient Young measures in the vector case, even if the initial problem was scalar, as the full problem is recast through the computation of a certain quasiconvexification. We illustrate this strategy by looking at two typical non-convex scalar problems. We hope to address vector problems in the near future.     

An alternating iterative method and its application in statistical inference

This paper studies non-convex programming problems. It is known that, in statistical inference, many constrained estimation problems may be expressed as convex programming problems. However, in many practical problems, the objective functions are not convex. In this paper, we give a definition of a semi-convex objective function and discuss the corresponding non-convex programming problems. A two-step iterative algorithm called the alternating iterative method is proposed for finding solutions for such problems. The method is illustrated by three examples in constrained estimation problems given in Sasabuchi et al. （Biometrika, 72, 465472 （1983））, Shi N. Z. （J. Multivariate Anal., 50, 282-293 （1994）） and El Barmi H. and Dykstra R. （Ann. Statist., 26, 1878 1893 （1998））.     

Structure of entropy solutions to the eikonal equation

In this paper, we establish rectifiability of the jump set of an S ¹–valued conservation law in two space–dimensions. This conservation law is a reformulation of the eikonal equation and is motivated by the singular limit of a class of variational problems. The only assumption on the weak solutions is that the entropy productions are (signed) Radon measures, an assumption which is justified by the variational origin. The methods are a combination of Geometric Measure Theory and elementary geometric arguments used to classify blow–ups.?The merit of our approach is that we obtain the structure as if the solutions were in BV, without using the BV–control, which is not available in these variationally motivated problems. Received June 24, 2002 / final version received November 12, 2002?Published online February 7, 2003     

Auxiliary space preconditioning in H 0(curl; Ω)

We adapt the principle of auxiliary space preconditioning as presented in [J. Xu, The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids, Computing, 56 (1996), pp. 215–235.] to H (curl; ω)-elliptic variational problems discretized by means of edge elements. The focus is on theoretical analysis within the abstract framework of subspace correction. Employing a Helmholtz-type splitting of edge element vector fields we can establish asymptotic h-uniform optimality of the preconditioner defined by our auxiliary space method. This author was fully supported by Hong Kong RGC grant (Project No. 403403) This author acknowledges the support from a Direct Grant of CUHK during his visit at The Chinese University of Hong Kong.     

η-Approximation Method for Non-convex Multiobjective Variational Problems

In this paper, we use the η-approximation method for a class of non-convex multiobjective variational problems with invex functionals. In this approach, for the considered multiobjective variational problem, the associated η-approximated multiobjective variational problem is constructed at the given feasible solution. The equivalence between (weakly) e?cient solutions in the original multiobjective variational problem and its associated η-approximated multiobjective variational problem is established under invexity hypotheses.     

Multigrid in H (div) and H (curl)

Summary. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces and in three dimensions. We show that if appropriate finite element spaces and appropriate additive or multiplicative Schwarz smoothers are used, then the multigrid V-cycle is an efficient solver and preconditioner for the discrete operator. All results are uniform with respect to the mesh size, the number of mesh levels, and weights on the two terms in the inner products. Received June 12, 1998 / Revised version received March 12, 1999 / Published online January 27, 2000     

Minimizing Sum of Truncated Convex Functions and Its Applications

In this article, we study a class of problems where the sum of truncated convex functions is minimized. In statistical applications, they are commonly encountered when ?₀-penalized models are fitted and usually lead to NP-Hard non-convex optimization problems. In this article, we propose a general algorithm for the global minimizer in low-dimensional settings. We also extend the algorithm to high-dimensional settings, where an approximate solution can be found efficiently. We introduce several applications where the sum of truncated convex functions is used, compare our proposed algorithm with other existing algorithms in simulation studies, and show its utility in edge-preserving image restoration on real data.     

Adaptive frame methods for nonlinear variational problems

In this paper we develop adaptive numerical solvers for certain nonlinear variational problems. The discretization of the variational problems is done by a suitable frame decomposition of the solution, i.e., a complete, stable, and redundant expansion. The discretization yields an equivalent nonlinear problem on the space of frame coefficients. The discrete problem is then adaptively solved using approximated nested fixed point and Richardson type iterations. We investigate the convergence, stability, and optimal complexity of the scheme. A theoretical advantage, for example, with respect to adaptive finite element schemes is that convergence and complexity results for the latter are usually hard to prove. The use of frames is further motivated by their redundancy, which, at least numerically, has been shown to improve the conditioning of the discretization matrices. Also frames are usually easier to construct than Riesz bases. We present a construction of divergence-free wavelet frames suitable for applications in fluid dynamics and magnetohydrodynamics. M. Fornasier acknowledges the financial support provided through the Intra-European Individual Marie Curie Fellowship Programme, under contract MOIF-CT-2006-039438. All of the authors acknowledge the hospitality of Dipartimento di Metodi e Modelli Matematici per le Scienze Applicate, Università di Roma “La Sapienza”, Italy, during the early preparation of this work. The authors want to thank Daniele Boffi, Dorina Mitrea, and Karsten Urban for the helpful and fruitful discussions on divergence-free function spaces.     

A globally convergent interior point algorithm for non-convex nonlinear programming

In this paper, a new algorithm for tracing the combined homotopy path of the non-convex nonlinear programming problem is proposed. The algorithm is based on the techniques of β$\beta$-cone neighborhood and a combined homotopy interior point method. The residual control criteria, which ensures that the obtained iterative points are interior points, is given by the condition that ensures the β$\beta$-cone neighborhood to be included in the interior part of the feasible region. The global convergence and polynomial complexity are established under some hypotheses.     

On Fictitious Domain Formulations for Maxwell''s Equations

We consider fictitious domain-Lagrange multiplier formulations for variational problems in the space H(curl: Ω{\bf)} derived from Maxwell's equations. Boundary conditions and the divergence constraint are imposed weakly by using Lagrange multipliers. Both the time dependent and time harmonic formulations of the Maxwell's equations are considered, and we derive well-posed formulations for both cases. The variational problem that arises can be discretized by functions that do not satisfy an a-priori divergence constraint.     

From discrete to continuum: A Young measure approach

The passage from atomistic to continuum models is usually done via G\Gamma-convergence with respect to the weak topology of some Sobolev space; the obtained continuum energy, in a one dimensional model, is then convex. These kind of results are not optimal for problems related to materials which may undergo to phase transitions. We present here a new simple way for dealing with these problems. Our method consists in rewriting the discrete energy in terms of particular measures and taking the G\Gamma-limit with respect to the weak * convergence of measures. The continuum energy arising from a linear chain of discrete mass points interacting with only the nearest neighbours turns out to be written in terms of Young measures. While, if the discrete mass points interact not only with the nearest neighbours but also with the second nearest neighbours we obtain a continuum problem in which appears a ``multiple Young measure" representing multiple levels of interaction. In this way we obtain a novel continuum problem which is able to capture the ``microstructure" at two different levels.     

Optimal design of the damping set for the stabilization of the wave equation

We consider the problem of optimizing the shape and position of the damping set for the internal stabilization of the linear wave equation in RN, N=1,2. In a first theoretical part, we reformulate the problem into an equivalent non-convex vector variational one using a characterization of divergence-free vector fields. Then, by means of gradient Young measures, we obtain a relaxed formulation of the problem in which the original cost density is replaced by its constrained quasi-convexification. This implies that the new relaxed problem is well-posed in the sense that there exists a minimizer and, in addition, the infimum of the original problem coincides with the minimum of the relaxed one. In a second numerical part, we address the resolution of the relaxed problem using a first-order gradient descent method. We present some numerical experiments which highlight the influence of the over-damping phenomena and show that for large values of the damping potential the original problem has no minimizer. We then propose a penalization technique to recover the minimizing sequences of the original problem from the optimal solution of the relaxed one.     

Non-convex and non-smooth variational decomposition for image restoration

The variational image decomposition model decomposes an image into a structural and an oscillatory component by regularization technique and functional minimization. It is an important task in various image processing methods, such as image restoration, image segmentation, and object recognition. In this paper, we propose a non-convex and non-smooth variational decomposition model for image restoration that uses non-convex and non-smooth total variation (TV) to measure the structure component and the negative Sobolev space $H^{-1}$ to model the oscillatory component. The new model combines the advantages of non-convex regularization and weaker-norm texture modeling, and it can well remove the noises while preserving the valuable edges and contours of the image. The iteratively reweighted l¹ (IRL1) algorithm is employed to solve the proposed non-convex minimization problem. For each subproblem, we use the alternating direction method of multipliers (ADMM) algorithm to solve it. Numerical results validate the effectiveness of the proposed model for both synthetic and real images in terms of peak signal-to-noise ratio (PSNR) and mean structural similarity index (MSSIM).     

Orlicz–Young Structures of Young Measures

The paper examines the integration of Young functions applied to Young measures and identifies Orlicz-like structures in the space of Young measures. In particular, a convergence intermediate between the weak convergence of measures and the variational norm is determined; it serves in the completion of the Orlicz space of functions when interpreted as degenerate Young measures. Partial linear operations are defined on Young measures with respect to which the linear operations in the Orlicz space of functions are continuously embedded in the space of Young measures. This leads to a definition of convexity-type structures in the space of Young measures via a limiting procedure. These structures enable applications of Young functions arguments to Young measures. Applications to optimal control and to well posedness of minimization in function spaces with respect to convex functions are provided.     

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     

The sdfem on Shishkin meshes for linear convection-diffusion problems

Summary. We consider singularly perturbed linear elliptic problems in two dimensions. The solutions of such problems typically exhibit layers and are difficult to solve numerically. The streamline diffusion finite element method (SDFEM) has been proved to produce accurate solutions away from any layers on uniform meshes, but fails to compute the boundary layers precisely. Our modified SDFEM is implemented with piecewise linear functions on a Shishkin mesh that resolves boundary layers, and we prove that it yields an accurate approximation of the solution both inside and outside these layers. The analysis is complicated by the severe nonuniformity of the mesh. We give local error estimates that hold true uniformly in the perturbation parameter , provided only that , where mesh points are used. Numerical experiments support these theoretical results. Received February 19, 1999 / Revised version received January 27, 2000 / Published online August 2, 2000