On quasi $$\epsilon $$-solution for robust convex optimization problems

This paper devotes to the quasi \(\epsilon \)-solution (one sort of approximate solutions) for a robust convex optimization problem in the face of data uncertainty. Using robust optimization approach (worst-case approach), we establish approximate optimality theorem and approximate duality theorems in term of Wolfe type on quasi \(\epsilon \)-solution for the robust convex optimization problem. Moreover, some examples are given to illustrate the obtained results.     

Iterative reweighted methods for $$\ell _1-\ell _p$$ minimization

In this paper, we focus on the \(\ell _1-\ell _p\) minimization problem with \(0<p<1\), which is challenging due to the \(\ell _p\) norm being non-Lipschizian. In theory, we derive computable lower bounds for nonzero entries of the generalized first-order stationary points of \(\ell _1-\ell _p\) minimization, and hence of its local minimizers. In algorithms, based on three locally Lipschitz continuous \(\epsilon \)-approximation to \(\ell _p\) norm, we design several iterative reweighted \(\ell _1\) and \(\ell _2\) methods to solve those approximation problems. Furthermore, we show that any accumulation point of the sequence generated by these methods is a generalized first-order stationary point of \(\ell _1-\ell _p\) minimization. This result, in particular, applies to the iterative reweighted \(\ell _1\) methods based on the new Lipschitz continuous \(\epsilon \)-approximation introduced by Lu (Math Program 147(1–2):277–307, 2014), provided that the approximation parameter \(\epsilon \) is below a threshold value. Numerical results are also reported to demonstrate the efficiency of the proposed methods.     

On approximation algorithms for concave mixed-integer quadratic programming

Concave mixed-integer quadratic programming is the problem of minimizing a concave quadratic polynomial over the mixed-integer points in a polyhedral region. In this work we describe an algorithm that finds an \(\epsilon \)-approximate solution to a concave mixed-integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in \(1/\epsilon \), provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. The running time of the proposed algorithm is expected unless \(\mathcal {P}=\mathcal {NP}\).     

How to convexify the intersection of a second order cone and a nonconvex quadratic

A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown—by several authors using different techniques—that the convex hull of the intersection of an ellipsoid, \(\mathcal {E}\), and a split disjunction, \((l - x_j)(x_j - u) \le 0\) with \(l < u\), equals the intersection of \(\mathcal {E}\) with an additional second-order-cone representable (SOCr) set. In this paper, we study more general intersections of the form \(\mathcal {K}\cap \mathcal {Q}\) and \(\mathcal {K}\cap \mathcal {Q}\cap H\), where \(\mathcal {K}\) is a SOCr cone, \(\mathcal {Q}\) is a nonconvex cone defined by a single homogeneous quadratic, and H is an affine hyperplane. Under several easy-to-verify conditions, we derive simple, computable convex relaxations \(\mathcal {K}\cap \mathcal {S}\) and \(\mathcal {K}\cap \mathcal {S}\cap H\), where \(\mathcal {S}\) is a SOCr cone. Under further conditions, we prove that these two sets capture precisely the corresponding conic/convex hulls. Our approach unifies and extends previous results, and we illustrate its applicability and generality with many examples.     

Rigidity of Free Boundary Surfaces in Compact 3-Manifolds with Strictly Convex Boundary

In this paper, we obtain an analogue of Toponogov theorem in dimension 3 for compact manifolds \(M^3\) with nonnegative Ricci curvature and strictly convex boundary \(\partial M\). Here we obtain a sharp upper bound for the length \(L(\partial \Sigma )\) of the boundary \(\partial \Sigma \) of a free boundary minimal surface \(\Sigma ^2\) in \(M^3\) in terms of the genus of \(\Sigma \) and the number of connected components of \(\partial \Sigma \), assuming \(\Sigma \) has index one. After, under a natural hypothesis on the geometry of M along \(\partial M\), we prove that if \(L(\partial \Sigma )\) saturates the respective upper bound, then \(M^3\) is isometric to the Euclidean 3-ball and \(\Sigma ^2\) is isometric to the Euclidean disk. In particular, we get a sharp upper bound for the area of \(\Sigma \), when \(M^3\) is a strictly convex body in \(\mathbb {R}^3\), which is saturated only on the Euclidean 3-balls (by the Euclidean disks). We also consider similar results for free boundary stable CMC surfaces.     

Positive semidefinite indicator property for norm-numerical range

In this paper, using an elementary method, we prove that if norm-numerical range related to an absolute norm \(\Vert .\Vert \) on \(\mathbb {C}^n\) satisfies the positive semidefinite indicator property, then \(\Vert .\Vert \) will be a multiple of Euclidian norm.     

On Ambrosetti–Malchiodi–Ni conjecture on two-dimensional smooth bounded domains

We consider the problem

$$\begin{aligned} \epsilon ^2 \Delta u-V(y)u+u^p\,=\,0,\quad u>0\quad \text{ in }\quad \Omega , \quad \frac{\partial u}{\partial \nu }\,=\,0\quad \text{ on }\quad \partial \Omega , \end{aligned}$$

where \(\Omega \) is a bounded domain in \({\mathbb {R}}^2\) with smooth boundary, the exponent p is greater than 1, \(\epsilon >0\) is a small parameter, V is a uniformly positive, smooth potential on \(\bar{\Omega }\), and \(\nu \) denotes the outward unit normal of \(\partial \Omega \). Let \(\Gamma \) be a curve intersecting orthogonally \(\partial \Omega \) at exactly two points and dividing \(\Omega \) into two parts. Moreover, \(\Gamma \) satisfies stationary and non-degeneracy conditions with respect to the functional \(\int _{\Gamma }V^{\sigma }\), where \(\sigma =\frac{p+1}{p-1}-\frac{1}{2}\). We prove the existence of a solution \(u_\epsilon \) concentrating along the whole of \(\Gamma \), exponentially small in \(\epsilon \) at any fixed distance from it, provided that \(\epsilon \) is small and away from certain critical numbers. In particular, this establishes the validity of the two dimensional case of a conjecture by Ambrosetti et al. (Indiana Univ Math J 53(2), 297–329, 2004).

     

Exploiting algebraic structure in global optimization and the Belgian chocolate problem

The Belgian chocolate problem involves maximizing a parameter \(\delta \) over a non-convex region of polynomials. In this paper we detail a global optimization method for this problem that outperforms previous such methods by exploiting underlying algebraic structure. Previous work has focused on iterative methods that, due to the complicated non-convex feasible region, may require many iterations or result in non-optimal \(\delta \). By contrast, our method locates the largest known value of \(\delta \) in a non-iterative manner. We do this by using the algebraic structure to go directly to large limiting values, reducing the problem to a simpler combinatorial optimization problem. While these limiting values are not necessarily feasible, we give an explicit algorithm for arbitrarily approximating them by feasible \(\delta \). Using this approach, we find the largest known value of \(\delta \) to date, \(\delta = 0.9808348\). We also demonstrate that in low degree settings, our method recovers previously known upper bounds on \(\delta \) and that prior methods converge towards the \(\delta \) we find.     

Exact formulas for the proximal/regular/limiting normal cone of the second-order cone complementarity set

In this paper we address the problem of locating a new facility on a d-dimensional space when the distance measure (\(\ell _p\)- or polyhedral-norms) is different at each one of the sides of a given hyperplane \(\mathcal {H}\). We relate this problem with the physical phenomenon of refraction, and extend it to any finite dimensional space and different distances at each one of the sides of any hyperplane. An application to this problem is the location of a facility within or outside an urban area where different distance measures must be used. We provide a new second order cone programming formulation, based on the \(\ell _p\)-norm representation given in Blanco et al. (Comput Optim Appl 58(3):563–595, 2014) that allows to solve the problem in any finite dimensional space with second order cone or semidefinite programming tools. We also extend the problem to the case where the hyperplane is considered as a rapid transit media (a different third norm is also considered over \(\mathcal {H}\)) that allows the demand to travel, whenever it is convenient, through \(\mathcal {H}\) to reach the new facility. Extensive computational experiments run in Gurobi are reported in order to show the effectiveness of the approach. Some extensions of these models are also presented.     

Dirichlet and Neumann eigenvalue problems on CR manifolds

We study the properties of Carnot–Carathéodory spaces attached to a strictly pseudoconvex CR manifold M, in a neighborhood of each point \(x \in M\), versus the pseudohermitian geometry of M arising from a fixed positively oriented contact form \(\theta \) on M. The weak Dirichlet problem for the sublaplacian \(\Delta _b\) on \((M, \theta )\) is solved on domains \(\Omega \subset M\) supporting the Poincaré inequality. The solution to Neumann problem for the sublaplacian \(\Delta _b\) on a \(C^{1,1}\) connected \((\epsilon , \delta )\)-domain \(\Omega \subset {{\mathbb {G}}}\) in a Carnot group (due to Danielli et al. in: Memoirs of American Mathematical Society 2006) is revisited for domains in a CR manifold. As an application we prove discreetness of the Dirichlet and Neumann spectra of \(\Delta _b\) on \(\Omega \subset M\) in a Carnot–Carthéodory complete pseudohermitian manifold \((M, \theta )\).     

Computing the Permanent of (Some) Complex Matrices

We present a deterministic algorithm, which, for any given \(0< \epsilon < 1\) and an \(n \times n\) real or complex matrix \(A=\left( a_{ij}\right) \) such that \(\left| a_{ij}-1 \right| \le 0.19\) for all \(i, j\) computes the permanent of \(A\) within relative error \(\epsilon \) in \(n^{O\left( \ln n -\ln \epsilon \right) }\) time. The method can be extended to computing hafnians and multidimensional permanents.     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).     

Compact $$\lambda $$-translating Solitons with Boundary

A \(\lambda \)-translating soliton with density vector \(\mathbf {v}\) is a surface \(\varSigma \) in Euclidean space \(\mathbb {R}^3\) whose mean curvature H satisfies \(2H=2\lambda +\langle N,\mathbf {v}\rangle \), where N is the Gauss map of \(\varSigma \). In this article, we study the shape of a compact \(\lambda \)-translating soliton in terms of its boundary. If \(\varGamma \) is a given closed curve, we deduce under what conditions on \(\lambda \) there exists a compact \(\lambda \)-translating soliton \(\varSigma \) with boundary \(\varGamma \) and we provide estimates of the surface area depending on the height of \(\varSigma \). Finally, we study the shape of \(\varSigma \) related with the geometry of \(\varGamma \), in particular, we give conditions that assert that \(\varSigma \) inherits the symmetries of its boundary \(\varGamma \).     

From a Microscopic to a Macroscopic Model for Alzheimer Disease: Two-Scale Homogenization of the Smoluchowski Equation in Perforated Domains

In this paper, we study the homogenization of a set of Smoluchowski’s discrete diffusion–coagulation equations modeling the aggregation and diffusion of \(\beta \)-amyloid peptide (A\(\beta \)), a process associated with the development of Alzheimer’s disease. In particular, we define a periodically perforated domain \(\Omega _{\epsilon }\), obtained by removing from the fixed domain \(\Omega \) (the cerebral tissue) infinitely many small holes of size \(\epsilon \) (the neurons), which support a non-homogeneous Neumann boundary condition describing the production of A\(\beta \) by the neuron membranes. Then, we prove that, when \(\epsilon \rightarrow 0\), the solution of this micromodel two-scale converges to the solution of a macromodel asymptotically consistent with the original one. Indeed, the information given on the microscale by the non-homogeneous Neumann boundary condition is transferred into a source term appearing in the limiting (homogenized) equations. Furthermore, on the macroscale, the geometric structure of the perforated domain induces a correction in that the scalar diffusion coefficients defined at the microscale are replaced by tensorial quantities.     

A Theory of Super-Resolution from Short-Time Fourier Transform Measurements

While spike trains are obviously not band-limited, the theory of super-resolution tells us that perfect recovery of unknown spike locations and weights from low-pass Fourier transform measurements is possible provided that the minimum spacing, \(\Delta \), between spikes is not too small. Specifically, for a measurement cutoff frequency of \(f_c\), Donoho (SIAM J Math Anal 23(5):1303–1331, 1992) showed that exact recovery is possible if the spikes (on \(\mathbb {R}\)) lie on a lattice and \(\Delta > 1/f_c\), but does not specify a corresponding recovery method. Candès and Fernandez-Granda (Commun Pure Appl Math 67(6):906–956, 2014; Inform Inference 5(3):251–303, 2016) provide a convex programming method for the recovery of periodic spike trains (i.e., spike trains on the torus \(\mathbb {T}\)), which succeeds provably if \(\Delta > 2/f_c\) and \(f_c \ge 128\) or if \(\Delta > 1.26/f_c\) and \(f_c \ge 10^3\), and does not need the spikes within the fundamental period to lie on a lattice. In this paper, we develop a theory of super-resolution from short-time Fourier transform (STFT) measurements. Specifically, we present a recovery method similar in spirit to the one in Candès and Fernandez-Granda (2014) for pure Fourier measurements. For a STFT Gaussian window function of width \(\sigma = 1/(4f_c)\) this method succeeds provably if \(\Delta > 1/f_c\), without restrictions on \(f_c\). Our theory is based on a measure-theoretic formulation of the recovery problem, which leads to considerable generality in the sense of the results being grid-free and applying to spike trains on both \(\mathbb {R}\) and \(\mathbb {T}\). The case of spike trains on \(\mathbb {R}\) comes with significant technical challenges. For recovery of spike trains on \(\mathbb {T}\) we prove that the correct solution can be approximated—in weak-* topology—by solving a sequence of finite-dimensional convex programming problems.     

Spectral density estimates with partial symmetries and an application to Bahri–Lions-type results

We are concerned with the existence of infinitely many solutions for the problem \(-\Delta u=|u|^{p-2}u+f\) in \(\Omega \), \(u=u_0\) on \(\partial \Omega \), where \(\Omega \) is a bounded domain in \(\mathbb {R}^N\), \(N\ge 3\). This can be seen as a perturbation of the problem with \(f=0\) and \(u_0=0\), which is odd in u. If \(\Omega \) is invariant with respect to a closed strict subgroup of O(N), then we prove infinite existence for all functions f and \(u_0\) in certain spaces of invariant functions for a larger range of exponents p than known before. In order to achieve this, we prove Lieb–Cwikel–Rosenbljum-type bounds for invariant potentials on \(\Omega \), employing improved Sobolev embeddings for spaces of invariant functions.     

Sharp MSE Bounds for Proximal Denoising

Denoising has to do with estimating a signal \(\mathbf {x}_0\) from its noisy observations \(\mathbf {y}=\mathbf {x}_0+\mathbf {z}\). In this paper, we focus on the “structured denoising problem,” where the signal \(\mathbf {x}_0\) possesses a certain structure and \(\mathbf {z}\) has independent normally distributed entries with mean zero and variance \(\sigma ^2\). We employ a structure-inducing convex function \(f(\cdot )\) and solve \(\min _\mathbf {x}\{\frac{1}{2}\Vert \mathbf {y}-\mathbf {x}\Vert _2^2+\sigma {\lambda }f(\mathbf {x})\}\) to estimate \(\mathbf {x}_0\), for some \(\lambda >0\). Common choices for \(f(\cdot )\) include the \(\ell _1\) norm for sparse vectors, the \(\ell _1-\ell _2\) norm for block-sparse signals and the nuclear norm for low-rank matrices. The metric we use to evaluate the performance of an estimate \(\mathbf {x}^*\) is the normalized mean-squared error \(\text {NMSE}(\sigma )=\frac{{\mathbb {E}}\Vert \mathbf {x}^*-\mathbf {x}_0\Vert _2^2}{\sigma ^2}\). We show that NMSE is maximized as \(\sigma \rightarrow 0\) and we find the exact worst-case NMSE, which has a simple geometric interpretation: the mean-squared distance of a standard normal vector to the \({\lambda }\)-scaled subdifferential \({\lambda }\partial f(\mathbf {x}_0)\). When \({\lambda }\) is optimally tuned to minimize the worst-case NMSE, our results can be related to the constrained denoising problem \(\min _{f(\mathbf {x})\le f(\mathbf {x}_0)}\{\Vert \mathbf {y}-\mathbf {x}\Vert _2\}\). The paper also connects these results to the generalized LASSO problem, in which one solves \(\min _{f(\mathbf {x})\le f(\mathbf {x}_0)}\{\Vert \mathbf {y}-{\mathbf {A}}\mathbf {x}\Vert _2\}\) to estimate \(\mathbf {x}_0\) from noisy linear observations \(\mathbf {y}={\mathbf {A}}\mathbf {x}_0+\mathbf {z}\). We show that certain properties of the LASSO problem are closely related to the denoising problem. In particular, we characterize the normalized LASSO cost and show that it exhibits a “phase transition” as a function of number of observations. We also provide an order-optimal bound for the LASSO error in terms of the mean-squared distance. Our results are significant in two ways. First, we find a simple formula for the performance of a general convex estimator. Secondly, we establish a connection between the denoising and linear inverse problems.     

Stability of Dirac concentrations in an integro-PDE model for evolution of dispersal

We consider an integro-PDE model from evolutionary biology. The solution \(u_\epsilon (x,\alpha )\) is structured by two variables \(x\in D \subset {\mathbb {R}}^k\) and \(\alpha \in (\underline{\alpha },{\overline{\alpha }})\subset \subset {\mathbb {R}}_+\). The diffusion coefficient in the x direction depends on \(\alpha \) and the diffusion coefficient in the \(\alpha \) direction is a constant \(\epsilon ^2\). A special feature of this model is the appearance of the integral \({\hat{u}}_\epsilon (x)\) of the solution in the \(\alpha \) variable, which can be viewed as an infinite dimensional parameter of the problem. In a previous work, the existence of a steady state that exhibits Dirac-concentration in one of the variables yet remains regular in the other variables was proved independently by Lam and Lou (J Funct Anal 272:1755–1790, 2017) and by Perthame and Souganidis (Math Model Nat Phenom 11:154–166, 2016). In this paper, we tackle the long-time dynamics of solutions. When the environment function is non-constant, we show that the steady state is linearly stable by considering the corresponding nonlocal eigenvalue problem. Uniqueness of steady state is obtained from the stability result via a degree argument. When the environment function is a constant, the global asymptotic stability result is obtained. This problem can be regarded as a competition of infinitely many species parameterized by \(\alpha \). As with the competition model for three or more species, the integro-PDE model does not generate a monotone dynamical system so that it is necessary to consider all (real or complex) eigenvalues in determining its linear stability.     

A Compactness Theorem of the Space of Free Boundary <Emphasis Type="Italic">f</Emphasis>-Minimal Surfaces in Three-Dimensional Smooth Metric Measure Space with Boundary

Let \((M^3,g,e^{-f}d\mu _M)\) be a compact three-dimensional smooth metric measure space with nonempty boundary. Suppose that M has nonnegative Bakry–Émery Ricci curvature and the boundary \(\partial M\) is strictly f-mean convex. We prove that there exists a properly embedded smooth f-minimal surface \(\Sigma \) in M with free boundary \(\partial \Sigma \) on \(\partial M\). If we further assume that the boundary \(\partial M\) is strictly convex, then we prove that \(M^3\) is diffeomorphic to the 3-ball \(B^3\), and a compactness theorem for the space of properly embedded f-minimal surfaces with free boundary in such \((M^3,g,e^{-f}d\mu _M)\), when the topology of these f-minimal surfaces is fixed.     

On the Multiplication Tuples Related to Certain Reproducing Kernel Hilbert Spaces

We consider a class of subnormal operator tuples \(M_z\) consisting of multiplications by coordinate functions on a class of reproducing kernel Hilbert spaces associated with certain bounded domains \(\Omega \) in \({\mathbb {C}}^m\), with the closure \({{\bar{\Omega }}}\) of \(\Omega \) being the Taylor spectrum of \(M_z\) and the topological boundary \(\partial \Omega \) of \(\Omega \) being the Taylor essential spectrum of \(M_z\). If T is a subnormal operator tuple quasisimilar to \(M_z\), then we show that the Taylor spectrum of T is \({{\bar{\Omega }}}\) provided \({{\bar{\Omega }}}\) is polynomially convex and provided \(\Omega \) is either strictly pseudoconvex with \(C^2\) boundary or is starlike, and that the Taylor essential spectrum of T is \(\partial \Omega \) provided \(\Omega \) satisfies the Gleason property as well. This generalizes some previous work of the first-named author in the context of the unit ball and the unit polydisk. The relevant theory is then applied to the multiplication tuples on the Hardy and Bergman spaces of complex ellipsoids.