We show how to approximate the feasible region of structured convex optimization problems by a family of convex sets with explicitly given and efficient (if the accuracy of the approximation is moderate) self-concordant barriers. This approach extends the reach of the modern theory of interior-point methods, and lays the foundation for new ways to treat … Read more
We propose a moment relaxation for two problems, the separation and covering problem with semi-algebraic sets generated by a polynomial of degree d. We show that (a) the optimal value of the relaxation finitely converges to the optimal value of the original problem, when the moment order r increases and (b) there exist probability measures … Read more
We propose a method to approximate a class of exponential multivariate integrals using moment relaxations. Using this approach, both lower and upper bounds of the integrals are obtained and we show that these bound values asymptotically converge to the real value of the integrals when the moment degree r increases. We further demonstrate the method … Read more
We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets. Our main result is a randomized poly-time algorithm which approximates $V(K_1,…,K_n)$ with multiplicative error $e^n$ and with better rates if the affine dimensions of most of the sets $K_i$ are small.\\ Even such rate is impossible to achieve … Read more
It is known that the Karush-Kuhn-Tucker (KKT) conditions of semidefinite programming can be reformulated as a nonsmooth system via the metric projector over the cone of symmetric and positive semidefinite matrices. We show in this paper that the primal and dual constraint nondegeneracies, the strong regularity, the nonsingularity of the B-subdifferential of this nonsmooth system, … Read more
This paper is devoted to optimality conditions for nonsmooth quasiconcave programming. Arrow and Enthoven (1961) formulate several economic problems into quasiconcave programming, and give a sufficient condition for smooth quasiconcave programming in their epoch-making and comprehensive paper. In this paper, generalized necessary and sufficient conditions for nonsmooth quasiconcave programming have been derived in terms of … Read more
A convex variational framework is proposed for solving inverse problems in Hilbert spaces with a priori information on the representation of the target solution in a frame. The objective function to be minimized consists of a separable term penalizing each frame coefficient individually and of a smooth term modeling the data formation model as well … Read more
When is the linear image of a closed convex cone closed? We present very simple, and intuitive necessary conditions, which 1) unify, and generalize seemingly disparate, classical sufficient conditions: polyhedrality of the cone, and “Slater” type conditions; 2) are necessary and sufficient, when the dual cone belongs to a class, that we call nice cones. … Read more
In this paper we explore properties of a family of probability density functions, called norm-induced densities, defined as $$f_t(x) = \left\{ \begin{array}{ll} \displaystyle \frac{ e^{-t\|x\|^p}dx}{\int_K e^{-t\|y\|^p}dy}, & x \in K \\ 0, & x \notin K,\\ \end{array}\right. $$ where $K$ is a $n$-dimensional convex set that contains the origin, parameters $t > 0$ and $p … Read more
We provide a sufficient condition on a class of compact basic semialgebraic sets K for their convex hull to have a lifted semidefinite representation (SDr). This lifted SDr is explicitly expressed in terms of the polynomials that define K. Examples are provided. For convex and compact basic semi-algebraic sets K defined by concave polynomials, we … Read more