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.     

Totally geodesic discs in strongly convex domains

We prove that every isometry from the unit disk Δ in ${\mathbb{C}}$ , endowed with the Poincaré distance, to a strongly convex bounded domain Ω of class ${\mathcal{C}^3}$ in ${\mathbb{C}^n}$ , endowed with the Kobayashi distance, is the composition of a complex geodesic of Ω with either a conformal or an anti-conformal automorphism of Δ. As a corollary we obtain that every isometry for the Kobayashi distance, from a strongly convex bounded domain of class ${\mathcal{C}^3}$ in ${\mathbb{C}^n}$ to a strongly convex bounded domain of class ${\mathcal{C}^3}$ in ${\mathbb{C}^m}$ , is either holomorphic or anti-holomorphic.     

The \mathcal{VU} -decomposition to the proper convex function

Based on the $\mathcal{VU}$ -theory of the finite-value convex function, this paper gives the $\mathcal{VU}$ -theory of the proper convex function. We give three equivalent definitions of the space decomposition. Also, we get the $\mathcal{U}$ -Lagrangian function and its corresponding properties. Furthermore, we apply this method to the nonlinear programming. And we obtain its algorithm and convergence theorem.     

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$ .     

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).     

An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general solution method based on quadratic convex reformulation, that we called MIQCR. This reformulation consists in designing an equivalent quadratic program with a convex objective function. The problem reformulated by MIQCR has a relatively important size that penalizes its solution time. In this paper, we propose a convex reformulation less general than MIQCR because it is limited to the general integer case, but that has a significantly smaller size. We call this approach Compact Quadratic Convex Reformulation (CQCR). We evaluate CQCR from the computational point of view. We perform our experiments on instances of general integer quadratic programs with one equality constraint. We show that CQCR is much faster than MIQCR and than the general non-linear solver BARON (Sahinidis and Tawarmalani, User??s manual, 2010) to solve these instances. Then, we consider the particular class of binary quadratic programs. We compare MIQCR and CQCR on instances of the Constrained Task Assignment Problem. These experiments show that CQCR can solve instances that MIQCR and other existing methods fail to solve.     

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.     

On an extension of the H^{k} mean curvature flow of closed convex hypersurfaces

In this paper we prove that the \(H^{k}\) ( \(k\) is odd and larger than \(2\) ) mean curvature flow of a closed convex hypersurface can be extended over the maximal time provided that the total \(L^{p}\) integral of the mean curvature is finite for some \(p\) .     

Optimization of expected shortfall on convex sets

In this article, we prove that the minimization problem of the expected shortfall over a convex but not necessarily closed set of financial positions $ \mathcal{X}\subseteq {L^1} $ has a solution. We provide both minimax and variational approaches on this problem. In the case where the optimization conclusions arise from the application of subgradient arguments, we need the assumption that the set of financial positions $ \mathcal{X} $ is closed.     

Using quadratic convex reformulation to tighten the convex relaxation of a quadratic program with complementarity constraints

Quadratic Convex Reformulation (QCR) is a technique that has been proposed for binary and mixed integer quadratic programs. In this paper, we extend the QCR method to convex quadratic programs with linear complementarity constraints (QPCCs). Due to the complementarity relationship between the nonnegative variables $y$ and $w$ , a term $y^{T}Dw$ can be added to the QPCC objective function, where $D$ is a nonnegative diagonal matrix chosen to maintain the convexity of the objective function and the global resolution of the QPCC. Following the QCR method, the products of linear equality constraints can also be used to perturb the QPCC objective function, with the goal that the new QP relaxation provides a tighter lower bound. By solving a semidefinite program, an equivalent QPCC can be obtained whose QP relaxation is as tight as possible. In addition, we extend the QCR to a general quadratically constrained quadratic program (QCQP), of which the QPCC is a special example. Computational tests on QPCCs are presented.     

An isoperimetric deficit upper bound of the convex domain in a surface of constant curvature

In this paper, we give a reverse analog of the Bonnesen-style inequality of a convex domain in the surface $ \mathbb{X} $ _∈ of constant curvature ∈, that is, an isoperimetric deficit upper bound of the convex domain in $ \mathbb{X} $ _∈ . The result is an analogue of the known Bottema’s result of 1933 in the Euclidean plane $ \mathbb{E} $ ².     

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.     

Conic volume ratio of the packing cone associate to a convex body

Given a convex body ${K\subset\mathbb{R}^n}$ (n??? 1) which contains o in its interior and ${{\bf u} \in S^{n-1}}$ , we introduce conic volume ratio r(K, u) of K in the direction of u by $$r(K, {\bf u})=\frac{vol(cone(K,{\bf u})\cap B_2^n)}{vol(B_2^n)},$$ where cone(K, u) is the packing cone of K in the direction of u. We prove that if K is an o-symmetric convex body in ${\mathbb{R}^n}$ and r(K, u) is a constant function of u, then K must be a Euclidean ball.     

Strongly convex set-valued maps

We introduce the notion of strongly $t$ -convex set-valued maps and present some properties of it. In particular, a Bernstein–Doetsch and Sierpiński-type theorems for strongly midconvex set-valued maps, as well as a Kuhn-type result are obtained. A representation of strongly $t$ -convex set-valued maps in inner product spaces and a characterization of inner product spaces involving this representation is given. Finally, a connection between strongly convex set-valued maps and strongly convex sets is presented.     

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.     

Fast alternating linearization methods for minimizing the sum of two convex functions

We present in this paper alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most ${O(1/\epsilon)}$ iterations to obtain an ${\epsilon}$ -optimal solution, while our accelerated (i.e., fast) versions of them require at most ${O(1/\sqrt{\epsilon})}$ iterations, with little change in the computational effort required at each iteration. For both types of methods, we present one algorithm that requires both functions to be smooth with Lipschitz continuous gradients and one algorithm that needs only one of the functions to be so. Algorithms in this paper are Gauss-Seidel type methods, in contrast to the ones proposed by Goldfarb and Ma in (Fast multiple splitting algorithms for convex optimization, Columbia University, 2009) where the algorithms are Jacobi type methods. Numerical results are reported to support our theoretical conclusions and demonstrate the practical potential of our algorithms.     

A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square

We propose an algorithm to sample the area of the smallest convex hull containing \(n\) sample points uniformly distributed over unit square. To do it, we introduce a new coordinate system for the position of vertexes and re-write joint distribution of the number of vertexes and their locations in the new coordinate system. The proposed algorithm is much faster than existing procedure and has a computational complexity on the order of \(O(T)\) , where \(T\) is the number of vertexes. Using the proposed algorithm, we numerically investigate the asymptotic behavior of functionals of the random convex hull. In addition, we apply it to finding pairs of stocks where the returns are dependent on each other on the New York Stock Exchange.     

Disjoint empty convex pentagons in planar point sets

In this paper we obtain the first non-trivial lower bound on the number of disjoint empty convex pentagons in planar points sets. We show that the number of disjoint empty convex pentagons in any set of n points in the plane, no three on a line, is at least $\left\lfloor {\tfrac{{5n}} {{47}}} \right\rfloor $ . This bound can be further improved to $\tfrac{{3n - 1}} {{28}} $ for infinitely many n.