On convex relaxations for quadratically constrained quadratic programming

We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let $\mathcal{F }$ denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on $\mathcal{F }$ is dominated by an alternative methodology based on convexifying the range of the quadratic form $\genfrac(){0.0pt}{}{1}{x}\genfrac(){0.0pt}{}{1}{x}^T$ for $x\in \mathcal{F }$ . We next show that the use of ?? $\alpha $ BB?? underestimators as computable estimates of convex lower envelopes is dominated by a relaxation of the convex hull of the quadratic form that imposes semidefiniteness and linear constraints on diagonal terms. Finally, we show that the use of a large class of D.C. (??difference of convex??) underestimators is dominated by a relaxation that combines semidefiniteness with RLT constraints.     

Computable representations for convex hulls of low-dimensional quadratic forms

Let ${\mathcal{C}}$ be the convex hull of points ${{\{{1 \choose x}{1 \choose x}^T \,|\, x\in \mathcal{F}\subset \Re^n\}}}$ . Representing or approximating ${\mathcal{C}}$ is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. We show that if n ≤ 4 and ${\mathcal{F}}$ is a simplex, then ${\mathcal{C}}$ has a computable representation in terms of matrices X that are doubly nonnegative (positive semidefinite and componentwise nonnegative). We also prove that if n = 2 and ${\mathcal{F}}$ is a box, then ${\mathcal{C}}$ has a representation that combines semidefiniteness with constraints on product terms obtained from the reformulation-linearization technique (RLT). The simplex result generalizes known representations for the convex hull of ${{\{(x_1, x_2, x_1x_2)\,|\, x\in\mathcal{F}\}}}$ when ${\mathcal{F}\subset\Re^2}$ is a triangle, while the result for box constraints generalizes the well-known fact that in this case the RLT constraints generate the convex hull of ${{\{(x_1, x_2, x_1x_2)\,|\, x\in\mathcal{F}\}}}$ . When n = 3 and ${\mathcal{F}}$ is a box, we show that a representation for ${\mathcal{C}}$ can be obtained by utilizing the simplex result for n = 4 in conjunction with a triangulation of the 3-cube.     

Complexity and nonlinear semidefinite programming reformulation of \ell _1-constrained nonconvex quadratic optimization

In this article, we show that the $\ell _1$ -constrained nonconvex quadratic optimization problem (QPL1) is NP-hard, even when the off-diagonal elements are all nonnegative. Then we give an answer to Pinar and Teboulle’s open problem on the nonlinear semidefinite programming relaxation of (QPL1). The analytical approach is extended to $\ell _p$ -constrained quadratic programs with $1<p<2$ .     

Separation and relaxation for cones of quadratic forms

Let ${P \subseteq \mathfrak{R}_{n}}$ be a pointed, polyhedral cone. In this paper, we study the cone ${\mathcal{C} = {\rm cone}\{xx^T : x \in P\}}$ of quadratic forms. Understanding the structure of ${\mathcal{C}}$ is important for globally solving NP-hard quadratic programs over P. We establish key characteristics of ${\mathcal{C}}$ and construct a separation algorithm for ${\mathcal{C}}$ provided one can optimize with respect to a related cone over the boundary of P. This algorithm leads to a nonlinear representation of ${\mathcal{C}}$ and a class of tractable relaxations for ${\mathcal{C}}$ , each of which improves a standard polyhedral-semidefinite relaxation of ${\mathcal{C}}$ . The relaxation technique can further be applied recursively to obtain a hierarchy of relaxations, and for constant recursive depth, the hierarchy is tractable. We apply this theory to two important cases: P is the nonnegative orthant, in which case ${\mathcal{C}}$ is the cone of completely positive matrices; and P is the homogenized cone of the “box” [0, 1] ⁿ . Through various results and examples, we demonstrate the strength of the theory for these cases. For example, we achieve for the first time a separation algorithm for 5 × 5 completely positive matrices.     

Weak quadratic overgroups for a class of Lie groups

Let $G$ be a connected and simply connected Lie group with Lie algebra $\mathfrak g $ . We say that a subset $X$ in the set $\mathfrak g ^\star / G$ of coadjoint orbits is convex hull separable when the convex hulls differ for any pair of distinct coadjoint orbits in $X$ . In this paper, we define a class of solvable Lie groups, and we give an explicit construction of an overgroup $G^+$ and a quadratic map $\varphi $ sending each generic orbit in $\mathfrak g ^\star $ to a $G^+$ -orbit in $\mathfrak{g ^+}^\star $ , in such a manner that the set $\varphi (\mathfrak g ^\star _{gen}){/ G^+}$ is convex hull separable. We then call $G^+$ a weak quadratic overgroup for $G$ . Thanks to this construction, we prove that any nilpotent Lie group, with dimension at most 7 admits such a weak quadratic overgroup. Finally, we produce different examples of solvable Lie groups, having weak quadratic overgroups, but which are not in our class of Lie groups and for which usual constructions fail to hold.     

The pure virtual braid group is quadratic

If an augmented algebra $K$ over $\mathbb Q $ is filtered by powers of its augmentation ideal $I$ , the associated graded algebra $gr_I K$ need not in general be quadratic: although it is generated in degree 1, its relations may not be generated by homogeneous relations of degree 2. In this paper, we give a sufficient criterion (called the PVH Criterion) for $gr_I K$ to be quadratic. When $K$ is the group algebra of a group $G$ , quadraticity is known to be equivalent to the existence of a (not necessarily homomorphic) universal finite type invariant for $G$ . Thus, the PVH Criterion also implies the existence of such a universal finite type invariant for the group $G$ . We apply the PVH Criterion to the group algebra of the pure virtual braid group (also known as the quasi-triangular group), and show that the corresponding associated graded algebra is quadratic, and hence that these groups have a universal finite type invariant.     

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

We consider $N$ -fold $4$ -block decomposable integer programs, which simultaneously generalize $N$ -fold integer programs and two-stage stochastic integer programs with $N$ scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable  $N$ , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result (Hochbaum and Shanthikumar in J. ACM 37:843–862,1990), which allows us to use convex continuous optimization as a subroutine.     

Iterative hard thresholding methods for l_0 regularized convex cone programming

In this paper we consider \(l_0\) regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving \(l_0\) regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer. Also, we establish the iteration complexity of the IHT method for finding an \({{\epsilon }}\) -local-optimal solution. We then propose a method for solving \(l_0\) regularized convex cone programming by applying the IHT method to its quadratic penalty relaxation and establish its iteration complexity for finding an \({{\epsilon }}\) -approximate local minimizer. Finally, we propose a variant of this method in which the associated penalty parameter is dynamically updated, and show that every accumulation point is a local izer of the problem.     

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.     

The average size of Ramanujan sums over quadratic number fields

This article is concerned with Ramanujan sums ${c_{\mathcal{I}_1}(\mathcal{I}),}$ where ${\mathcal{I},\mathcal{I}_1}$ are integral ideals in an arbitrary quadratic number field ${\mathbb{Q}(\sqrt{d}).}$ In particular, the asymptotic behavior of sums of ${c_{\mathcal{I}_1}(\mathcal{I}),}$ over both ${\mathcal{I}}$ and ${c_{\mathcal{I}_1}(\mathcal{I}),}$ is investigated.     

Variance asymptotics for random polytopes in smooth convex bodies

Let $K \subset \mathbb R ^d$ be a smooth convex set and let $\mathcal{P }_{\lambda }$ be a Poisson point process on $\mathbb R ^d$ of intensity ${\lambda }$ . The convex hull of $\mathcal{P }_{\lambda }\cap K$ is a random convex polytope $K_{\lambda }$ . As ${\lambda }\rightarrow \infty $ , we show that the variance of the number of $k$ -dimensional faces of $K_{\lambda }$ , when properly scaled, converges to a scalar multiple of the affine surface area of $K$ . Similar asymptotics hold for the variance of the number of $k$ -dimensional faces for the convex hull of a binomial process in $K$ .     

Nonnegative Polynomials and Their Carathéodory Number

In 1888 Hilbert showed that every nonnegative homogeneous polynomial with real coefficients of degree $2d$ in $n$ variables is a sum of squares if and only if $d=1$ (quadratic forms), $n=2$ (binary forms) or $(n,d)=(3,2)$ (ternary quartics). In these cases, it is interesting to compute canonical expressions for these decompositions. Starting from Carathéodory’s Theorem, we compute the Carathéodory number of Hilbert cones of quadratic forms and binary forms.     

Characterization of ellipses as uniformly dense sets with respect to a family of convex bodies

Let \(K\subset \mathbb R ^N\) be a convex body containing the origin. A measurable set \(G\subset \mathbb R ^N\) with positive Lebesgue measure is said to be uniformly \(K\) -dense if, for any fixed \(r>0\) , the measure of \(G\cap (x+r K)\) is constant when \(x\) varies on the boundary of \(G\) (here, \(x+r K\) denotes a translation of a dilation of \(K\) ). We first prove that \(G\) must always be strictly convex and at least \(C^{1,1}\) -regular; also, if \(K\) is centrally symmetric, \(K\) must be strictly convex, \(C^{1,1}\) -regular and such that \(K=G-G\) up to homotheties; this implies in turn that \(G\) must be \(C^{2,1}\) -regular. Then for \(N=2\) , we prove that \(G\) is uniformly \(K\) -dense if and only if \(K\) and \(G\) are homothetic to the same ellipse. This result was already proven by Amar et al. in 2008 . However, our proof removes their regularity assumptions on \(K\) and \(G\) , and more importantly, it is susceptible to be generalized to higher dimension since, by the use of Minkowski’s inequality and an affine inequality, avoids the delicate computations of the higher-order terms in the Taylor expansion near \(r=0\) for the measure of \(G\cap (x+r\,K)\) (needed in 2008).     

The convex hull of the lattice points inside a curve

Let $C$ be a smooth convex closed plane curve. The $C$ -ovals $C(R,u,v)$ are formed by expanding by a factor  $R$ , then translating by  $(u,v)$ . The number of vertices $V(R,u,v)$ of the convex hull of the integer points within or on  $C(R,u,v)$ has order  $R^{2/3}$ (Balog and Bárány) and has average size $BR^{2/3}$ as $R$ varies (Balog and Deshouillers). We find the space average of  $V(R,u,v)$ over vectors  $(u,v)$ to be  $BR^{2/3}$ with an explicit coefficient  $B$ , and show that the average over  $R$ has the same  $B$ . The proof involves counting edges and finding the domain $D(q,a)$ of an integer vector, the set of  $(u,v)$ for which the convex hull has a directed edge parallel to  $(q,a)$ . The resulting sum over bases of the integer lattice is approximated by a triple integral.     

The third moment of quadratic Dirichlet L-functions

We study the third moment of quadratic Dirichlet $L$ -functions, obtaining an error term of size $O(X^{3/4 + \varepsilon })$ .     

Multiple P-invariant closed characteristics on partially symmetric compact convex hypersurfaces in {\varvec{R}}^{2n}

In this paper, let $n$ be a positive integer and $P=diag(-I_{n-\kappa },I_\kappa ,-I_{n-\kappa },I_\kappa )$ for some integer $\kappa \in [0, n]$ , we prove that for any compact convex hypersurface $\Sigma $ in $\mathbf{R}^{2n}$ with $n\ge 2$ there exist at least two geometrically distinct P-invariant closed characteristics on $\Sigma $ , provided that $\Sigma $ is P-symmetric, i.e., $x\in \Sigma $ implies $Px\in \Sigma $ . This work is shown to extend and unify several earlier works on this subject.     

Non-Archimedean stability of a quadratic functional equation

Recently the Hyers–Ulam stability of the quadratic functional equation $ f(kx+y)+f(kx+\sigma (y))- 2k^2 f(x)-2f(y)=0 $ where $\sigma $ is an involution of the normed space $E$ and $k$ is a fixed positive integer greater that 1, has been proved in the earlier work. In this paper, using fixed point and direct methods, we prove the Hyers–Ulam stability of the above functional equation in non-Archimedean normed spaces.     

Minimal simplices inscribed in a convex body

Measuring how far a convex body $\mathcal{K }$ (of dimension $n$ ) with a base point ${O}\in \,\text{ int }\,\mathcal{K }$ is from an inscribed simplex $\Delta \ni {O}$ in “minimal” position, the interior point ${O}$ can display regular or singular behavior. If ${O}$ is a regular point then the $n+1$ chords emanating from the vertices of $\Delta $ and meeting at ${O}$ are affine diameters, chords ending in pairs of parallel hyperplanes supporting $\mathcal{K }$ . At a singular point ${O}$ the minimal simplex $\Delta $ degenerates. In general, singular points tend to cluster near the boundary of $\mathcal{K }$ . As connection to a number of difficult and unsolved problems about affine diameters shows, regular points are elusive, often non-existent. The first result of this paper uses Klee’s fundamental inequality for the critical ratio and the dimension of the critical set to obtain a general existence for regular points in a convex body with large distortion (Theorem A). This, in various specific settings, gives information about the structure of the set of regular and singular points (Theorem B). At the other extreme when regular points are in abundance, a detailed study of examples leads to the conjecture that the simplices are the only convex bodies with no singular points. The second and main result of this paper is to prove this conjecture in two different settings, when (1) $\mathcal{K }$ has a flat point on its boundary, or (2) $\mathcal{K }$ has $n$ isolated extremal points (Theorem C).     

On the quadratic Lagrange spectrum

We study the quadratic Lagrange spectrum defined by Parkkonen and Paulin by considering the approximation by elements of the orbit of a given real quadratic irrational number for the action by homographies and anti-homographies of $PSL_2(\mathbf{Z})$ on $\mathbf{R}\cup \{\infty \}$ . Our approach is based on the theory of continued fractions.     

A canonical structure on the tangent bundle of a pseudo- or para-Kähler manifold

It is a classical fact that the cotangent bundle \(T^* {\mathcal {M}}\) of a differentiable manifold \({\mathcal {M}}\) enjoys a canonical symplectic form \(\Omega ^*\) . If \(({\mathcal {M}},\mathrm{J} ,g,\omega )\) is a pseudo-Kähler or para-Kähler \(2n\) -dimensional manifold, we prove that the tangent bundle \(T{\mathcal {M}}\) also enjoys a natural pseudo-Kähler or para-Kähler structure \(({\tilde{\hbox {J}}},\tilde{g},\Omega )\) , where \(\Omega \) is the pull-back by \(g\) of \(\Omega ^*\) and \(\tilde{g}\) is a pseudo-Riemannian metric with neutral signature \((2n,2n)\) . We investigate the curvature properties of the pair \(({\tilde{\hbox {J}}},\tilde{g})\) and prove that: \(\tilde{g}\) is scalar-flat, is not Einstein unless \(g\) is flat, has nonpositive (resp. nonnegative) Ricci curvature if and only if \(g\) has nonpositive (resp. nonnegative) Ricci curvature as well, and is locally conformally flat if and only if \(n=1\) and \(g\) has constant curvature, or \(n>2\) and \(g\) is flat. We also check that (i) the holomorphic sectional curvature of \(({\tilde{\hbox {J}}},\tilde{g})\) is not constant unless \(g\) is flat, and (ii) in \(n=1\) case, that \(\tilde{g}\) is never anti-self-dual, unless conformally flat.