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.     

Discrete global descent method for discrete global optimization and nonlinear integer programming

A novel method, entitled the discrete global descent method, is developed in this paper to solve discrete global optimization problems and nonlinear integer programming problems. This method moves from one discrete minimizer of the objective function f to another better one at each iteration with the help of an auxiliary function, entitled the discrete global descent function. The discrete global descent function guarantees that its discrete minimizers coincide with the better discrete minimizers of f under some standard assumptions. This property also ensures that a better discrete minimizer of f can be found by some classical local search methods. Numerical experiments on several test problems with up to 100 integer variables and up to 1.38 × 10¹⁰⁴ feasible points have demonstrated the applicability and efficiency of the proposed method.     

Heteroclinic solutions of a van der Waals model with indefinite nonlocal interactions

We construct heteroclinic the global minimizers of a nonlocal free energy functional that van der Waals derived in 1893. We study the case where the nonlocality satisfies only a weakened type of ellipticity, which precludes the use of comparison methods. In the interesting case when the local part of the energy is nonconvex, we construct a classical the global minimizer by studying a relaxed functional corresponding to the convexification of the local part and exclude the possibility of minimizers of the relaxed functional having rapid oscillations. We also construct examples where the global minimizer is not monotonic.     

Closed-form solutions, extremality and nonsmoothness criteria in a large deformation elasticity problem

The pure azimuthal shear problem for a circular cylindrical tube of nonlinearly elastic material, both isotropic and anisotropic, is examined on the basis of a complementary energy principle. For particular choices of strain-energy function, one convex and one non-convex, closed-form solutions are obtained for this mixed boundary-value problem, for which the governing differential equation can be converted into an algebraic equation. The results for the non-convex strain energy function provide an illustration of a situation in which smooth analytic solutions of a nonlinear boundary-value problem are not global minimizers of the energy in the variational statement of the problem. Both the global minimizer and the local extrema are identified and the results are illustrated for particular values of the material parameters.      

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.     

On the nonexistence of boundary branch points for minimal surfaces spanning smooth contours II

This is the second in a series of two papers discussing the elementary but beautiful and fundamental question (open for some eighty years) of whether or not a minimal surface spanning a sufficiently smooth curve, which is a local minimizer, is immersed up to and including the boundary. We show that C ^k minimizers of energy or area cannot have nonexceptional boundary branch points.     

A cut-peak function method for global optimization

A new method is proposed for solving box constrained global optimization problems. The basic idea of the method is described as follows: Constructing a so-called cut-peak function and a choice function for each present minimizer, the original problem of finding a global solution is converted into an auxiliary minimization problem of finding local minimizers of the choice function, whose objective function values are smaller than the previous ones. For a local minimum solution of auxiliary problems this procedure is repeated until no new minimizer with a smaller objective function value could be found for the last minimizer. Construction of auxiliary problems and choice of parameters are relatively simple, so the algorithm is relatively easy to implement, and the results of the numerical tests are satisfactory compared to other methods.     

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.     

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.     

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.     

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.     

Calculus of variations in Hilbert spaces

The objective of this paper is to discuss existence, uniqueness and regularity issues of minimizers of one dimensional variational problems in Hilbert spaces. We obtain existence of C ² local minimizers and prove that the value function of an optimal control problem solves corresponding Hamilton-Jacobi equation in a viscosity sense.     

New Sufficiency for Global Optimality and Duality of Mathematical Programming Problems via Underestimators

We present new conditions for a Karush-Kuhn-Tucker point to be a global minimizer of a mathematical programming problem which may have many local minimizers that are not global. The new conditions make use of underestimators of the Lagrangian at the Karush-Kuhn-Tucker point. We establish that a Karush-Kuhn-Tucker point is a global minimizer if the Lagrangian admits an underestimator, which is convex or, more generally, has the property that every stationary point is a global minimizer. In particular, we obtain sufficient conditions by using the fact that the biconjugate function of the Lagrangian is a convex underestimator at a point whenever it coincides with the Lagrangian at that point. We present also sufficient conditions for weak and strong duality results in terms of underestimators. The authors are grateful to Professor Gue Myung Lee, Pukyong National University, Korea, and the referees for their comments and suggestions which have contributed to the final preparation of the paper. The work was partially supported by the Australian Research Council Discovery Project Grant.     

Evolution by Non-Convex Functionals

We establish a semi-group solution concept for flows that are generated by generalized minimizers of non-convex energy functionals. We use relaxation and convexification to define these generalized minimizers. The main part of this work consists in exemplary validation of the solution concept for a non-convex energy functional. For rotationally invariant initial data it is compared with the solution of the mean curvature flow equation. The basic example relates the mean curvature flow equation with a sequence of iterative minimizers of a family of non-convex energy functionals. Together with the numerical evidence this corroborates the claim that the non-convex semi-group solution concept defines, in general, a solution of the mean curvature equation.     

The cluster problem in multivariate global optimization

We consider branch and bound methods for enclosing all unconstrained global minimizers of a nonconvex nonlinear twice-continuously differentiable objective function. In particular, we consider bounds obtained with interval arithmetic, with the midpoint test, but no acceleration procedures. Unless the lower bound is exact, the algorithm without acceleration procedures in general gives an undesirable cluster of boxes around each minimizer. In a previous paper, we analyzed this problem for univariate objective functions. In this paper, we generalize that analysis to multi-dimensional objective functions. As in the univariate case, the results show that the problem is highly related to the behavior of the objective function near the global minimizers and to the order of the corresponding interval extension.This work was partially funded by National Science Foundation grant # CCR-9203730.     

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.     

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.     

A perfect example for the BFGS method

Consider the BFGS quasi-Newton method applied to a general non-convex function that has continuous second derivatives. This paper aims to construct a four-dimensional example such that the BFGS method need not converge. The example is perfect in the following sense: (a) All the stepsizes are exactly equal to one; the unit stepsize can also be accepted by various line searches including the Wolfe line search and the Arjimo line search; (b) The objective function is strongly convex along each search direction although it is not in itself. The unit stepsize is the unique minimizer of each line search function. Hence the example also applies to the global line search and the line search that always picks the first local minimizer; (c) The objective function is polynomial and hence is infinitely continuously differentiable. If relaxing the convexity requirement of the line search function; namely, (b) we are able to construct a relatively simple polynomial example.     

Existence of minimizers of the Mumford-Shah functional with singular operators and unbounded data

We consider the regularization of linear inverse problems by means of the minimization of a functional formed by a term of discrepancy to data and a Mumford-Shah functional term. The discrepancy term penalizes the L ² distance between a datum and a version of the unknown function which is filtered by means of a non-invertible linear operator. Depending on the type of the involved operator, the resulting variational problem has had several applications: image deblurring, or inverse source problems in the case of compact operators, and image inpainting in the case of suitable local operators, as well as the modeling of propagation of fracture. We present counterexamples showing that, despite this regularization, the problem is actually in general ill-posed. We provide, however, existence results of minimizers in a reasonable class of smooth functions out of piecewise Lipschitz discontinuity sets in two dimensions. The compactness arguments we developed to derive the existence results stem from geometrical and regularity properties of domains, interpolation inequalities, and classical compactness arguments in Sobolev spaces.