Hyperbolic Polynomials and Hyperbolic Programming
2019-04-30..2019-05-03
Berkeley, United States
[Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017), Solving Polynomial Equations (Simons Institute, 2014), Discrete Optimization via Continuous Relaxation, Semidefinite Optimization, Approximation and Applications 2014, Functional Inequalities in Discrete Spaces with Applications 2013, Optimization and Algorithm Design 2023]
who it's for
convex optimization researchers, computational algebraic geometers, optimization algorithm developers, semidefinite programming practitioners, combinatorial optimization researchers, theoretical computer scientists, numerical analysts
topics
hyperbolic polynomials and cones; lambda_min maximization for cones; primal-dual hyperbolic algorithms; interior-point methods for non-symmetric cones; moment-sums-of-squares hierarchy; sums of nonnegative circuit polynomials; log-concave and completely log-concave polynomials; spectrahedral representation lower bounds; volume computation of polynomial sublevel sets; Sherali-Adams relaxations for max-cut; Ehrhart and H*-polynomials real-rootedness; linear preservers and stability of polynomials
| title | author | length |
|---|---|---|
| Certificates of Polynomial Non-Negativity via Hyperbolic Optimization | James Saunderson | 59m |
Proposes certifying global non-negativity by encoding a hyperbolic polynomial and a direction into a family of polynomial Hankel/Bezoutian matrices whose… | ||
| Primal-Dual Algorithms for Hyperbolic Programming Problems | Levent Tuncel | 54m |
Presents a primal‑dual method that uses the barrier f(x) = -log P(x) for hyperbolic cones, exploits negative curvature (Hessian maps cone into its dual), and… | ||
| Tight Semidefinite Programming Relaxations for Polynomial Optimization | Jiawang Nie | 42m |
Shows that KKT multipliers admit a polynomial multiplier representation whenever the constraint Jacobian is nonsingular (over the complex variety), and uses… | ||
| First-Order Methods and Hyperbolic Programming | James Renegar | 51m |
Shows how a hyperbolic program becomes an affine lambda_min maximization problem once a strictly feasible e is known, and how the boundary solution is… | ||
| Volumes of Sublevel Sets of Homogeneous Polynomials | Jean-Bernard Lasserre | 43m |
Computes volumes of sublevel sets {x: p(x) ≤ t} for homogeneous polynomials p by relating them to integrals and moment sequences; uses moments and convex… | ||
| Discrete Optimization using Log-Concave Polynomials | Nima Anari | 49m |
Shows a concrete algorithmic pipeline: relax the 0/1 max-coefficient integer program to a continuous program over the polynomial G_mu, solve when G_mu is… | ||
| Completely Log-Concave Polynomials | Cynthia Vinzant | 57m |
Defines completely log-concave polynomials as those positive on a convex cone whose every directional derivative (along cone directions) is log‑concave, and… | ||
| Combinatorial Characterizations in Semidefinite Programming Duality: ... | Gabor Pataki | 44m |
Proves exact, checkable criteria for SDP pathologies: a system is badly behaved iff there exists a Z (max-rank slack) and V certificate with the stated… | ||
| Optimization over the Hypercube via Sums of Nonnegative Circuit Polynomials | Mareike Dressler | 39m |
Claims that nonnegativity can be certified by sums of nonnegative circuit polynomials (SONC), gives a converging Positivstellensatz-style hierarchy, and… | ||
| An Interior-Point Method for Convex Optimization over Non-symmetric Cones | Dávid Papp | 53m |
Describes an interior‑point predictor–corrector algorithm for convex optimization over non‑symmetric cones that uses only barrier gradient and Hessian (no need… | ||
| Ehrhart Polynomials of Dilated Polytopes | Katharina Victoria Jochemko | 43m |
Proves that dilating a lattice polytope by any integer R larger than the degree of its H-polynomial makes the H-polynomial real‑rooted (strengthening the… | ||
| Max Cut with Linear Programs: Sherali-Adams Strikes Back | Tselil Schramm | 52m |
Claim: linear programs from Sherali‑Adams level D can certify max‑cut ≲ 1/2+ε on graphs whose random‑walk eigenvalues are ≤ 1/√δ by using random‑walk spider… | ||
| Positively Hyperbolic Varieties | Josephine Yu | 49m |
Defines positively hyperbolic varieties via imaginary-part sign conditions and proves algebraic matroids of such varieties are positroids, using sign-variation… | ||
| Formulas for Riesz Kernels | Khazhgali Kozhasov | 51m |
Asks when P^{-α} (P a hyperbolic homogeneous polynomial positive on its hyperbolicity cone C) is completely monotone and constructs the Riesz kernel Q_α via… | ||
| Your Dreams May Come True with MTP2 | Caroline Uhler | 51m |
Defines MTP2 by the pointwise inequality p(x)p(y) ≤ p(x∧y)p(x∨y) and shows concrete consequences: Simpson's paradox cannot occur, MTP2 is closed under… | ||
| Constrained Subset Selection Problems under Diversity Measures | Mohit Singh | 52m |
Presents a concrete model: embed items as vectors and optimize spectral objectives (determinant for D-optimality, trace for average effective resistance… | ||
| Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones | Nick Ryder | 40m |
Proves that a family of hyperbolic polynomials requires spectrahedral representations of size exponential in the input parameters, and that even approximate… | ||
| Kippenhahn's Theorem in Higher Dimensions | Daniel Plaumann | 47m |
Kippenhahn's theorem identifies a matrix numerical range as the convex hull of the projective dual curve coming from the determinantal hyperbolic polynomial… | ||
| Linear Preservers of Stable and Lorentzian Polynomials and Deformations of Hyperbolicity Cones | Petter Brändén | 43m |
Linear operators on bounded-degree polynomials preserve complex stability exactly when their algebraic symbol criterion is stable, and that extends to… | ||
| nothing matches | ||