An approach to constrained global optimization based on exact penalty functions

In the field of global optimization many efforts have been devoted to solve unconstrained global optimization problems. The aim of this paper is to show that unconstrained global optimization methods can be used also for solving constrained optimization problems, by resorting to an exact penalty approach. In particular, we make use of a non-differentiable exact penalty function ${P_q(x;\varepsilon)}$ . We show that, under weak assumptions, there exists a threshold value ${\bar \varepsilon >0 }$ of the penalty parameter ${\varepsilon}$ such that, for any ${\varepsilon \in (0, \bar \varepsilon]}$ , any global minimizer of P _q is a global solution of the related constrained problem and conversely. On these bases, we describe an algorithm that, by combining an unconstrained global minimization technique for minimizing P _q for given values of the penalty parameter ${\varepsilon}$ and an automatic updating of ${\varepsilon}$ that occurs only a finite number of times, produces a sequence {x ^k } such that any limit point of the sequence is a global solution of the related constrained problem. In the algorithm any efficient unconstrained global minimization technique can be used. In particular, we adopt an improved version of the DIRECT algorithm. Some numerical experimentation confirms the effectiveness of the approach.     

The universal Glivenko–Cantelli property

Let ${\mathcal{F}}$ be a separable uniformly bounded family of measurable functions on a standard measurable space ${(X, \mathcal{X})}$ , and let ${N_{[]}(\mathcal{F}, \varepsilon, \mu)}$ be the smallest number of ${\varepsilon}$ -brackets in L ¹(μ) needed to cover ${\mathcal{F}}$ . The following are equivalent:

1. ${\mathcal{F}}$ is a universal Glivenko–Cantelli class.
2. ${N_{[]}(\mathcal{F},\varepsilon,\mu) < \infty}$ for every ${\varepsilon > 0}$ and every probability measure μ.
3. ${\mathcal{F}}$ is totally bounded in L ¹(μ) for every probability measure μ.
4. ${\mathcal{F}}$ does not contain a Boolean σ-independent sequence.

It follows that universal Glivenko–Cantelli classes are uniformity classes for general sequences of almost surely convergent random measures.     

On the Neumann problem for PDE’s with a small parameter and the corresponding diffusion processes

The diffusion process in a region ${G \subset \mathbb R^2}$ governed by the operator ${\tilde L^\varepsilon = \frac{\,1}{\,2}\, u_{xx} + \frac1 {2\varepsilon}\, u_{zz}}$ inside the region and undergoing instantaneous co-normal reflection at the boundary is considered. We show that the slow component of this process converges to a diffusion process on a certain graph corresponding to the problem. This allows to find the main term of the asymptotics for the solution of the corresponding Neumann problem in G. The operator ${\tilde L^\varepsilon}$ is, up to the factor ε ^{? 1}, the result of small perturbation of the operator ${\frac{\,1}{\,2}\, u_{zz}}$ . Our approach works for other operators (diffusion processes) in any dimension if the process corresponding to the non-perturbed operator has a first integral, and the ε-process is non-degenerate on non-singular level sets of this first integral.     

Sharp geometric rigidity of isometries on Heisenberg groups

We prove sharp geometric rigidity estimates for isometries on Heisenberg groups. Our main result asserts that every $(1+\varepsilon )$ -quasi-isometry on a John domain of the Heisenberg group $\mathbb H ^n, n>1,$ is close to some isometry up to proximity order $\sqrt{\varepsilon }+\varepsilon $ in the uniform norm, and up to proximity order $\varepsilon $ in the $L_p^1$ -norm. We give examples showing the asymptotic sharpness of our results.     

Singular limits for Liouville-type equations on the flat two-torus

We consider the problem $$\begin{aligned} -\Delta u=\varepsilon ^{2}e^{u}- \frac{1}{|\Omega |}\int _\Omega \varepsilon ^{2} e^{u}+ {4\pi N\over |\Omega |} - 4 \pi N\delta _p, \quad \text{ in} {\Omega }, \quad \int _\Omega u=0 \end{aligned}$$ in a flat two-torus $\Omega $ with periodic boundary conditions, where $\varepsilon >0,\,|\Omega |$ is the area of the $\Omega $ , $N>0$ and $\delta _p$ is a Dirac mass at $p\in \Omega $ . We prove that if $1\le m<N+1$ then there exists a family of solutions $\{u_\varepsilon \}_{\varepsilon }$ such that $\varepsilon ^{2}e^{u_\varepsilon }\rightharpoonup 8\pi \sum _{i=1}^m\delta _{q_i}$ as $\varepsilon \rightarrow 0$ in measure sense for some different points $q_{1}, \ldots , q_{m}$ . Furthermore, points $q_i$ , $i=1,\dots ,m$ are different from $p$ .     

Dimension Reduction for Finite Trees in \varvec{\ell _1}

We show that every $n$ -point tree metric admits a $(1+\varepsilon )$ -embedding into $\ell _1^{C(\varepsilon ) \log n}$ , for every $\varepsilon > 0$ , where $C(\varepsilon ) \le O\big ((\frac{1}{\varepsilon })^4 \log \frac{1}{\varepsilon })\big )$ . This matches the natural volume lower bound up to a factor depending only on $\varepsilon $ . Previously, it was unknown whether even complete binary trees on $n$ nodes could be embedded in $\ell _1^{O(\log n)}$ with $O(1)$ distortion. For complete $d$ -ary trees, our construction achieves $C(\varepsilon ) \le O\big (\frac{1}{\varepsilon ^2}\big )$ .     

Tunneling for a Class of Difference Operators

We analyze a general class of difference operators ${H_\varepsilon = T_\varepsilon + V_\varepsilon}$ on ${\ell^2((\varepsilon \mathbb {Z})^d)}$ where ${V_\varepsilon}$ is a multi-well potential and ${\varepsilon}$ is a small parameter. We decouple the wells by introducing certain Dirichlet operators on regions containing only one potential well, and we shall treat the eigenvalue problem for ${H_\varepsilon}$ as a small perturbation of these comparison problems. We describe tunneling by a certain interaction matrix, similar to the analysis for the Schr?dinger operator [see Helffer and Sj?strand in Commun Partial Differ Equ 9:337–408, 1984], and estimate the remainder, which is exponentially small and roughly quadratic compared with the interaction matrix.     

Convergence rate of the Allen-Cahn equation to generalized motion by mean curvature

We investigate the singular limit, as ${\varepsilon \to 0}$ , of the Allen-Cahn equation ${u^\varepsilon_t=\Delta u^\varepsilon+\varepsilon^{-2}f(u^\varepsilon)}$ , with f a balanced bistable nonlinearity. We consider rather general initial data u ₀ that is independent of ${{\varepsilon}}$ . It is known that this equation converges to the generalized motion by mean curvature ?? in the sense of viscosity solutions??defined by Evans, Spruck and Chen, Giga, Goto. However, the convergence rate has not been known. We prove that the transition layers of the solutions ${u^{\varepsilon}}$ are sandwiched between two sharp ??interfaces?? moving by mean curvature, provided that these ??interfaces?? sandwich at t?=?0 an ${\mathcal O({\varepsilon}|\,{\rm ln}\,{\varepsilon}|)}$ neighborhood of the initial layer. In some special cases, which allow both extinction and pinches off phenomenon, this enables to obtain an ${\mathcal O({\varepsilon}|\,{\rm ln}\,{\varepsilon}|)}$ estimate of the location and the thickness measured in space-time of the transition layers. A result on the regularity of the generalized motion by mean curvature is also provided in the Appendix.     

Asymptotic analysis of a second-order singular perturbation model for phase transitions

We study the asymptotic behavior, as ${\varepsilon}$ tends to zero, of the functionals ${F^k_\varepsilon}$ introduced by Coleman and Mizel in the theory of nonlinear second-order materials; i.e., $$F^k_\varepsilon(u):=\int\limits_{I} \left(\frac{W(u)}{\varepsilon}-k\,\varepsilon\,(u')^2+\varepsilon^3(u'')^2\right)\,dx,\quad u\in W^{2,2}(I),$$ where k?>?0 and ${W:\mathbb{R}\to[0,+\infty)}$ is a double-well potential with two potential wells of level zero at ${a,b\in\mathbb{R}}$ . By proving a new nonlinear interpolation inequality, we show that there exists a positive constant k ₀ such that, for k?<?k ₀, and for a class of potentials W, ${(F^k_\varepsilon)}$ ??(L ¹)-converges to $$F^k(u):={\bf m}_k \, \#(S(u)),\quad u\in BV(I;\{a,b\}),$$ where m _k is a constant depending on W and k. Moreover, in the special case of the classical potential ${W(s)=\frac{(s^2-1)^2}{2}}$ , we provide an upper bound on the values of k such that the minimizers of ${F_\varepsilon^k}$ cannot develop oscillations on some fine scale and a lower bound on the values for which oscillations occur, the latter improving a previous estimate by Mizel, Peletier and Troy.     

Profile of the least energy solution of a singular perturbed Neumann problem with mixed powers

We consider the problem ${\varepsilon^{2}\Delta u - u^q + u^p = 0\,{\rm in}\,\Omega,\,u > 0\,{\rm in}\,\Omega,\,\frac{\partial u}{\partial \nu} = 0\,{\rm on}\,\partial\Omega }$ where Ω is a smooth bounded domain in ${\mathbb{R}^N}$ , ${1 < q < p < {N+2\over N-2}}$ if N ≥ 2 and ${\varepsilon}$ is a small positive parameter. We determine the location and shape of the least energy solution when ${\varepsilon \rightarrow 0.}$      

Gelfand numbers and metric entropy of convex hulls in Hilbert spaces

We establish optimal estimates of Gelfand numbers or Gelfand widths of absolutely convex hulls cov(K) of precompact subsets ${K\subset H}$ of a Hilbert space H by the metric entropy of the set K where the covering numbers ${N(K, \varepsilon)}$ of K by ${\varepsilon}$ -balls of H satisfy the Lorentz condition $$ \int\limits_{0}^{\infty} \left(\log N(K,\varepsilon) \right)^{r/s}\, d\varepsilon^{s} < \infty $$ for some fixed ${0 < r, s \le \infty}$ with the usual modifications in the cases r = ∞, 0 < s < ∞ and 0 < r < ∞, s = ∞. The integral here is an improper Stieltjes integral. Moreover, we obtain optimal estimates of Gelfand numbers of absolutely convex hulls if the metric entropy satisfies the entropy condition $$\sup_{\varepsilon >0 }\varepsilon \left(\log N(K,\varepsilon) \right)^{1/r}\left(\log(2+\log N(K,\varepsilon))\right)^\beta < \infty$$ for some fixed 0 < r < ∞, ?∞ < β < ∞. Using inequalities between Gelfand and entropy numbers we also get optimal estimates of the metric entropy of the absolutely convex hull cov(K). As an interesting feature of the estimates, a sudden jump of the asymptotic behavior of Gelfand numbers as well as of the metric entropy of absolutely convex hulls occurs for fixed s if the parameter r crosses the point r = 2 and, if r = 2 is fixed, if the parameter β crosses the point β = 1. The results established in Hilbert spaces extend and recover corresponding results of several authors.     

Homogenization of the Neumann problem in perforated domains: an alternative approach

The main result of this paper is a compactness theorem for families of functions in the space SBV (Special functions of Bounded Variation) defined on periodically perforated domains. Given an open and bounded set ${\Omega\subseteq\mathbb{R}^n}$ , and an open, connected, and (?1/2, 1/2) ⁿ -periodic set ${P\subseteq\mathbb{R}^n}$ , consider for any ???>?0 the perforated domain ?? _?? :=????????? P. Let ${(u_\varepsilon)\subset SBV^p(\Omega_{\varepsilon})}$ , p?>?1, be such that ${\int_{\Omega_{\varepsilon}}\left|{\nabla{u}_\varepsilon}\right|^pdx+\mathcal{H}^{n-1}(S_{u_\varepsilon}\,\cap\,\Omega_{\varepsilon}) +\left\Vert{u_\varepsilon}\right\Vert_{L^p(\Omega_{\varepsilon})}}$ is bounded. Then, we prove that, up to a subsequence, there exists ${u\in GSBV^p\,\cap\, L^p(\Omega)}$ satisfying ${\lim_\varepsilon\left\Vert{u-u_\varepsilon}\right\Vert_{L^1(\Omega_{\varepsilon})}=0}$ . Our analysis avoids the use of any extension procedure in SBV, weakens the hypotheses on P to the minimal ones and simplifies the proof of the results recently obtained in Focardi et?al. (Math Models Methods Appl Sci 19:2065?C2100, 2009) and Cagnetti and Scardia (J Math Pures Appl (9), to appear). Among the arguments we introduce, we provide a localized version of the Poincaré-Wirtinger inequality in SBV. As a possible application we study the asymptotic behavior of a brittle porous material represented by the perforated domain ?? _?? . Finally, we slightly extend the well-known homogenization theorem for Sobolev energies on perforated domains.     

Calderón–Zygmund Operators on Weighted Hardy Spaces

We study the boundedness of Calderón–Zygmund operators on weighted Hardy spaces $H^p_w$ using Littlewood-Paley theory. It is shown that if a Calderón–Zygmund operator T satisfies T ^*1?=?0, then T is bounded on $H^p_w$ for $w\in A_{p(1+\frac\varepsilon n)}$ and $\frac n{n+\varepsilon}<p\le1$ , where ε is the regular exponent of the kernel of T.     

Existence of semiclassical states for a quasilinear Schrödinger equation with critical exponent in {\mathbb{R}^N}

We consider the following perturbed version of quasilinear Schrödinger equation $$\begin{array}{lll}-\varepsilon^2\Delta u +V(x)u-\varepsilon^2\Delta (u^2)u=h(x,u)u+K(x)|u|^{22^*-2}u\end{array}$$ in ${\mathbb{R}^N}$ , where N ≥ 3, 22* = 4N/(N ? 2), V(x) is a nonnegative potential, and K(x) is a bounded positive function. Using minimax methods, we show that this equation has at least one positive solution provided that ${\varepsilon \leq \mathcal{E}}$ ; for any ${m\in\mathbb{N}}$ , it has m pairs of solutions if ${\varepsilon \leq \mathcal{E}_m}$ , where ${\mathcal{E}}$ and ${\mathcal{E}_m}$ are sufficiently small positive numbers. Moreover, these solutions ${u_\varepsilon \to 0}$ in ${H^1(\mathbb{R}^N)}$ as ${\varepsilon \to 0}$ .     

Dual fast projected gradient method for quadratic programming

The application of the fast gradient method to the dual quadratic programming (QP) problem leads to the dual fast projected gradient (DFPG) method. The DFPG converges with O(k ^?2) rate, where k > 0 is the number of steps. At each step, it requires O(nm) operations. Therefore for a given ${\varepsilon > 0}$ an ${\varepsilon}$ -approximation to the optimal dual function value one achieves in ${O(nm\varepsilon^{-\frac{1}{2}})}$ operations. We present numerical results which strongly corroborate the theory. In particular, we demonstrate high efficiency of the DFPG for large scale QP.     

Quantitative Stratification and the Regularity of Mean Curvature Flow

Let ${\mathcal{M}}$ be a Brakke flow of n-dimensional surfaces in ${\mathbb{R}^N}$ . The singular set ${\mathcal{S} \subset \mathcal{M}}$ has a stratification ${\mathcal{S}^0 \subset \mathcal{S}^1 \subset \cdots \mathcal{S}}$ , where ${X \in \mathcal{S}^j}$ if no tangent flow at X has more than j symmetries. Here, we define quantitative singular strata ${\mathcal{S}^j_{\eta, r}}$ satisfying ${\cup_{\eta>0} \cap_{0<r} \mathcal{S}^j_{\eta, r} = \mathcal{S}^j}$ . Sharpening the known parabolic Hausdorff dimension bound ${{\rm dim} \mathcal{S}^j \leq j}$ , we prove the effective Minkowski estimates that the volume of r-tubular neighborhoods of ${\mathcal{S}^j_{\eta, r}}$ satisfies ${{\rm Vol} (T_r(\mathcal{S}^j_{\eta, r}) \cap B_1) \leq Cr^{N + 2 - j-\varepsilon}}$ . Our primary application of this is to higher regularity of Brakke flows starting at k-convex smooth compact embedded hypersurfaces. To this end, we prove that for the flow of k-convex hypersurfaces, any backwards selfsimilar limit flow with at least k symmetries is in fact a static multiplicity one plane. Then, denoting by ${\mathcal{B}_r \subset \mathcal{M}}$ the set of points with regularity scale less than r, we prove that ${{\rm Vol}(T_r(\mathcal{B}_r)) \leq C r^{n+4-k-\varepsilon}}$ . This gives L ^p -estimates for the second fundamental form for any p < n + 1 ? k. In fact, the estimates are much stronger and give L ^p -estimates for the reciprocal of the regularity scale. These estimates are sharp. The key technique that we develop and apply is a parabolic version of the quantitative stratification method introduced in Cheeger and Naber (Invent. Math., (2)191 2013), 321–339) and Cheeger and Naber (Comm. Pure. Appl. Math, arXiv:1107.3097v1, 2013).     

Random subgraphs of the 2D Hamming graph: the supercritical phase

We study random subgraphs of the 2-dimensional Hamming graph H(2,n), which is the Cartesian product of two complete graphs on n vertices. Let p be the edge probability, and write ${p={(1+\varepsilon)}/{(2(n-1))}}$ for some ${\varepsilon \in \mathbb{R}}$ . In Borgs et al. (Random Struct Alg 27:137–184, 2005; Ann Probab 33:1886–1944, 2005), the size of the largest connected component was estimated precisely for a large class of graphs including H(2,n) for ${\varepsilon \leq \Lambda V^{-1/3}}$ , where Λ >  0 is a constant and V = n ² denotes the number of vertices in H(2,n). Until now, no matching lower bound on the size in the supercritical regime has been obtained. In this paper we prove that, when ${\varepsilon \gg (\log{V})^{1/3} V^{-1/3}}$ , then the largest connected component has size close to ${2 \varepsilon V}$ with high probability. We thus obtain a law of large numbers for the largest connected component size, and show that the corresponding values of p are supercritical. Barring the factor ${(\log{V})^{1/3}}$ , this identifies the size of the largest connected component all the way down to the critical p window.     

Perturbed asymptotically linear problems

The aim of this paper is to investigate the existence of solutions of the semilinear elliptic problem $$\left\{\begin{array}{ll} -\Delta u\ =\ p(x, u) + \varepsilon g(x, u)\quad {\rm in}\,\, \Omega, \\ u=0 \quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\,\,\,\,{\rm on}\,\, \partial\Omega, \end{array} \right. \quad\quad\quad(0.1) $$ where Ω is an open bounded domain of ${\mathbb{R}^N}$ , ${\varepsilon\in\mathbb{R}, p}$ is subcritical and asymptotically linear at infinity, and g is just a continuous function. Even when this problem has not a variational structure on ${H^1_0(\Omega)}$ , suitable procedures and estimates allow us to prove that the number of distinct critical levels of the functional associated to the unperturbed problem is “stable” under small perturbations, in particular obtaining multiplicity results if p is odd, both in the non-resonant and in the resonant case.