Stability of the Minimizers of Least Squares with a Non-Convex Regularization. Part II: Global Behavior

We address estimation problems where the sought-after solution is defined as the minimizer of an objective function composed of a quadratic data-fidelity term and a regularization term. We especially focus on non-convex and possibly non-smooth regularization terms because of their ability to yield good estimates. This work is dedicated to the stability of the minimizers of such piecewise C^m, with m ≥ 2, non-convex objective functions. It is composed of two parts. In the previous part of this work we considered general local minimizers. In this part we derive results on global minimizers. We show that the data domain contains an open, dense subset such that for every data point therein, the objective function has a finite number of local minimizers, and a unique global minimizer. It gives rise to a global minimizer function which is C^m-1 everywhere on an open and dense subset of the data domain.     

Stability of the Minimizers of Least Squares with a Non-Convex Regularization. Part I: Local Behavior

Many estimation problems amount to minimizing a piecewise C^m objective function, with m ≥ 2, composed of a quadratic data-fidelity term and a general regularization term. It is widely accepted that the minimizers obtained using non-convex and possibly non-smooth regularization terms are frequently good estimates. However, few facts are known on the ways to control properties of these minimizers. This work is dedicated to the stability of the minimizers of such objective functions with respect to variations of the data. It consists of two parts: first we consider all local minimizers, whereas in a second part we derive results on global minimizers. In this part we focus on data points such that every local minimizer is isolated and results from a C^m-1 local minimizer function, defined on some neighborhood. We demonstrate that all data points for which this fails form a set whose closure is negligible.     

A new approximation of relaxed energies for harmonic maps and the Faddeev model

We propose a new approximation for the relaxed energy E of the Dirichlet energy and prove that the minimizers of the approximating functionals converge to a minimizer u of the relaxed energy, and that u is partially regular without using the concept of Cartesian currents. We also use the same approximation method to study the variational problem of the relaxed energy for the Faddeev model and prove the existence of minimizers for the relaxed energy ${\tilde{E}_F}$ in the class of maps with Hopf degree ±1.     

Characterization of energy minimizers in micromagnetics

We present a new characterization of minimizing sequences and possible minimizers (all called the minimizing magnetizations) for a nonlocal micromagnetic-like energy (without the exchange energy). Our method is to replace the nonlocal energy functional and its relaxation with certain local integral functionals on divergence-free fields obtained by a two-step minimization of some auxiliary augmented functionals. Through this procedure, the minimization problem becomes equivalent to the minimization of a new local variational functional, called the dual variational functional, which has a unique minimizer. We then precisely characterize the minimizing magnetizations of original nonlocal functionals in terms of the unique minimizer of the dual variational functional. Finally, we give some remarks and ideas on solving the dual minimization problem.     

On a variational problem with non-differentiable constraints

We study the regularity of minimizers and critical points of the Dirichlet energy under an integral constraint given by a non-differentiable function. We obtain existence of a Lipschitz continuous minimizer for a relaxed problem. In two dimensions, some regularity can also be proved for critical points.     

A Locally-Biased form of the DIRECT Algorithm

In this paper we propose a form of the DIRECT algorithm that is strongly biased toward local search. This form should do well for small problems with a single global minimizer and only a few local minimizers. We motivate our formulation with some results on how the original formulation of the DIRECT algorithm clusters its search near a global minimizer. We report on the performance of our algorithm on a suite of test problems and observe that the algorithm performs particularly well when termination is based on a budget of function evaluations.     

Solving nonlinearly constrained global optimization problem via an auxiliary function method

This paper considers the nonlinearly constrained continuous global minimization problem. Based on the idea of the penalty function method, an auxiliary function, which has approximately the same global minimizers as the original problem, is constructed. An algorithm is developed to minimize the auxiliary function to find an approximate constrained global minimizer of the constrained global minimization problem. The algorithm can escape from the previously converged local minimizers, and can converge to an approximate global minimizer of the problem asymptotically with probability one. Numerical experiments show that it is better than some other well known recent methods for constrained global minimization problems.     

Variational Problems with a p-Homogeneous Energy

We investigate existence, uniqueness and positivity of minimizers or critical points for an energy functional which contains only p-homogeneous and linear terms, 1p-homogeneous part of the energy functional is that it be given by the p-th power of an equivalent, uniformly convex norm on the underlying Sobolev space. Finally, continuous dependence of minimizers on the energy functional is established.     

Multiplicity results for interfaces of Ginzburg-Landau-Allen-Cahn equations in periodic media

The Ginzburg-Landau-Allen-Cahn equation is a variational model for phase coexistence and for other physical problems. It contains a term given by a kinetic part of elliptic type plus a double-well potential. We assume that the functional depends on the space variables in a periodic way.We show that given a plane with rational normal, there are minimal solutions, satisfying the following properties. These solutions are asymptotic to the pure phases and are separated by an interface. The convergence to the pure phases is exponentially fast. The interface lies at a finite distance M from the chosen plane, where M is a universal constant. Furthermore, these solutions satisfy some monotonicity properties with respect to integer translations (namely, integer translations are always comparable to the function).We then show that all the interfaces of the global periodic minimizers satisfy similar monotonicity and plane-like properties.We also consider the case of possibly irrationally oriented planes. We show that either there is a one parameter family of minimizers whose graphs provide a field of extremals or there are at least two solutions, one which is a minimizer and another one which is not. These solutions also have interfaces bounded by a universal constant, they enjoy monotonicity properties with respect to integer translations and the nonminimal solutions are trapped inside a gap of the lamination induced by the minimizers.     

A discrete dynamic convexized method for nonlinear integer programming

In this paper, we consider the box constrained nonlinear integer programming problem. We present an auxiliary function, which has the same discrete global minimizers as the problem. The minimization of the function using a discrete local search method can escape successfully from previously converged discrete local minimizers by taking increasing values of a parameter. We propose an algorithm to find a global minimizer of the box constrained nonlinear integer programming problem. The algorithm minimizes the auxiliary function from random initial points. We prove that the algorithm can converge asymptotically with probability one. Numerical experiments on a set of test problems show that the algorithm is efficient and robust.     

A Sequential Convexification Method (SCM) for Continuous Global Optimization

A new method for continuous global minimization problems, acronymed SCM, is introduced. This method gives a simple transformation to convert the objective function to an auxiliary function with gradually fewer local minimizers. All Local minimizers except a prefixed one of the auxiliary function are in the region where the function value of the objective function is lower than its current minimal value. Based on this method, an algorithm is designed which uses a local optimization method to minimize the auxiliary function to find a local minimizer at which the value of the objective function is lower than its current minimal value. The algorithm converges asymptotically with probability one to a global minimizer of the objective function. Numerical experiments on a set of standard test problems with several problems' dimensions up to 50 show that the algorithm is very efficient compared with other global optimization methods.     

Kuhn-Tucker sufficiency for global minimum of multi-extremal mathematical programming problems

The Kuhn-Tucker Sufficiency Theorem states that a feasible point that satisfies the Kuhn-Tucker conditions is a global minimizer for a convex programming problem for which a local minimizer is global. In this paper, we present new Kuhn-Tucker sufficiency conditions for possibly multi-extremal nonconvex mathematical programming problems which may have many local minimizers that are not global. We derive the sufficiency conditions by first constructing weighted sum of square underestimators of the objective function and then by characterizing the global optimality of the underestimators. As a consequence, we derive easily verifiable Kuhn-Tucker sufficient conditions for general quadratic programming problems with equality and inequality constraints. Numerical examples are given to illustrate the significance of our criteria for multi-extremal problems.     

Asymptotic analysis for the radial minimizer of a second-order energy functional

The convergence for the radial minimizers of a second-order energy functional, when the parameter tends to 0 is studied. And the location of the zeros of the radial minimizers of this functional is presented. Based on this result, the uniqueness of the radial minimizer is discussed.     

Geometric conditions for Kuhn–Tucker sufficiency of global optimality in mathematical programming

We present geometric criteria for a feasible point that satisfies the Kuhn–Tucker conditions to be a global minimizer of mathematical programming problems with or without bounds on the variables. The criteria apply to multi-extremal programming problems which may have several local minimizers that are not global. We establish such criteria in terms of underestimators of the Lagrangian of the problem. The underestimators are required to satisfy certain geometric property such as the convexity (or a generalized convexity) property. We show that the biconjugate of the Lagrangian can be chosen as a convex underestimator whenever the biconjugate coincides with the Lagrangian at a point. We also show how suitable underestimators can be constructed for the Lagrangian in the case where the problem has bounds on the variables. Examples are given to illustrate our results.     

A hybrid multiagent approach for global trajectory optimization

In this paper we consider a global optimization method for space trajectory design problems. The method, which actually aims at finding not only the global minimizer but a whole set of low-lying local minimizers (corresponding to a set of different design options), is based on a domain decomposition technique where each subdomain is evaluated through a procedure based on the evolution of a population of agents. The method is applied to two space trajectory design problems and compared with existing deterministic and stochastic global optimization methods.     

Global Optimization For Molecular Clusters Using A New Smoothing Approach

Strategies involving smoothing of the objective function have been used to help solve difficult global optimization problems arising in molecular chemistry. This paper proposes a new smoothing approach and examines some basic issues in smoothing for molecular configuration problems. We first propose a new, simple algebraic way of smoothing the Lennard-Jones energy function, which is an important component of the energy in many molecular models. This simple smoothing technique is shown to have close similarities to previously-proposed, spatial averaging smoothing techniques. We also present some experimental studies of the behavior of local and global minimizers under smoothing of the potential energy in Lennard-Jones problems. An examination of minimizer trajectories from these smoothed problems shows significant limitations in the use of smoothing to directly solve global optimization problems.     

Ginzburg-Landau equation with magnetic effect in a thin domain

We study the Ginzburg-Landau equation with magnetic effect in a thin domain in , where the thickness of the domain is controlled by a parameter . This equation is an Euler equation of a free energy functional and it has trivial solutions that are minimizers of the functional. In this article we look for a nontrivial stable solution to the equation, that is, a local minimizer of the energy functional. To prove the existence of such a stable solution in , we consider a reduced problem as and a nondegenerate stable solution to the reduced equation. Applying the standard variational argument, we show that there exists a stable solution in near the solution to the reduced equation if is sufficiently small. We also present a specific example of a domain which allows a stable vortex solution, that is, a stable solution with zeros. Received: 11 May 2001 / Accepted: 11 July 2001 /Published online: 19 October 2001     

Local minimizers and planar interfaces in a phase-transition model with interfacial energy

Interfacial energy is often incorporated into variational solid-solid phase transition models via a perturbation of the elastic energy functional involving second gradients of the deformation. We study consequences of such higher-gradient terms for local minimizers and for interfaces. First it is shown that at slightly sub-critical temperatures, a phase which globally minimizes the elastic energy density at super-critical temperatures is an L ¹-local minimizer of the functional including interfacial energy, whereas it is typically only a W ^1,??-local minimizer of the purely elastic functional. The second part deals with the existence and uniqueness of smooth interfaces between different wells of the multi-well elastic energy density. Attention is focussed on so-called planar interfaces, for which the deformation depends on a single direction x · N and the deformation gradient then satisfies a rank-one ansatz of the form ${Dy(x) = A + u(x \cdot N) \otimes N}$ , where A and ${B=A+a \otimes N}$ are the gradients connected by the interface.     

Newton's problem of the body of minimal resistance under a single-impact assumption

We consider the problem of the body of minimal resistance as formulated in [2], Sect. 5: minimize , where is the unit disc of , in the class of radial functions satisfying a geometrical property (1), corresponding to a single-impact assumption ( is a given parameter). We prove the existence of a critical value of M. For , there exist a unique local minimizer of the functional. For , the set of local minimizers is not compact in , though they all achieve the same value of the functional. Received February 15, 2000 / Accepted May 2, 2000 / Published online September 14, 2000     

An optimality criterion for global quadratic optimization

In this paper we prove a sufficient condition that a strong local minimizer of a bounded quadratic program is the unique global minimizer. This sufficient condition can be verified computationally by solving a linear and a convex quadratic program and can be used as a quality test for local minimizers found by standard indefinite quadratic programming routines.Part of this work was done while the author was at the University of Wisconsin-Madison.