We give explicit polynomial-sized (in @math n and @math k) semidefinite representations of the hyperbolicity cones associated with the elementary symmetric polynomials of degree @math k in @math n variables. These convex cones form a family of non-polyhedral outer approximations of the non-negative orthant that preserve low-dimensional faces while successively discarding high-dimensional faces. More generally we construct explicit semidefinite representations (polynomial-sized in @math k,m, and @math n) of the hyperbolicity cones associated with @math kth directional derivatives of polynomials of the form @math p(x)=det(?i=1nAixi) where the @math Ai are @math m×m symmetric matrices. These convex cones form an analogous family of outer approximations to any spectrahedral cone. Our representations allow us to use semidefinite programming to solve the linear cone programs associated with these convex cones as well as their (less well understood) dual cones.
From a computational perspective, G " u ler @cite_11 showed that if @math has degree @math and is hyperbolic with respect to @math then @math is a self-concordant barrier function (with barrier parameter @math ) for the hyperbolicity cone @math . As such, as long as @math and its gradient and Hessian can be computed efficiently, one can use interior point methods to minimize a linear functional over an affine slice of @math efficiently. Renegar [Section 9] renegar2006hyperbolic gave an efficient interpolation-based method for computing @math (and its gradient and Hessian) whenever @math (and its gradient and Hessian) can be evaluated efficiently. G " u ler and Renegar's observations together yield efficient computational methods to optimize a linear functional over an affine slice of a derivative relaxation of a spectrahedral cone. Our results complement these, giving a method to solve optimization problems of this type using existing numerical procedures for semidefinite programming.
@cite_11
2655474054
We focus on nonconvex and nonsmooth minimization problems with a composite objective, where the differentiable part of the objective is freed from the usual and restrictive global Lipschitz gradient continuity assumption. This longstanding smoothness restriction is pervasive in first order methods (FOM), and was recently circumvent for convex composite optimization by Bauschke, Bolte and Teboulle, through a simple and elegant framework which captures, all at once, the geometry of the function and of the feasible set. Building on this work, we tackle genuine nonconvex problems. We first complement and extend their approach to derive a full extended descent lemma by introducing the notion of smooth adaptable functions. We then consider a Bregman-based proximal gradient methods for the nonconvex composite model with smooth adaptable functions, which is proven to globally converge to a critical point under natural assumptions on the problem's data. To illustrate the power and potential of our general framework and results, we consider a broad class of quadratic inverse problems with sparsity constraints which arises in many fundamental applications, and we apply our approach to derive new globally convergent schemes for this class.