The Computational Complexity of Duality

DOI10.1137/16M105887XzbMath1353.65144arXiv1601.07629OpenAlexW2963251533MaRDI QIDQ2832893

Lek-Heng Lim, Shmuel Friedland

Publication date: 15 November 2016

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1601.07629

zbMATH Keywords

approximationNP-hardproper conedual normdual coneMahler volumesymmetric convex bodyFenchel dualnorm ballpolynomial-time reducibleweak membership

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Optimality conditions and duality in mathematical programming (90C46) Convex functions and convex programs in convex geometry (52A41) Positive matrices and their generalizations; cones of matrices (15B48) Numerical computation of matrix norms, conditioning, scaling (65F35) Complexity and performance of numerical algorithms (65Y20)

Related Items (9)

Combinatorial methods for the spectral \(p\)-norm of hypermatrices ⋮ New estimations on the upper bounds for the nuclear norm of a tensor ⋮ Completely positive tensor recovery with minimal nuclear value ⋮ Highly entangled tensors ⋮ Nuclear norm of higher-order tensors ⋮ Symmetric Tensor Nuclear Norms ⋮ Approximation hierarchies for the cone of flow matrices ⋮ Operator norm inequalities between tensor unfoldings on the partition lattice ⋮ The global convergence of the nonlinear power method for mixed-subordinate matrix norms

Cites Work

• On the computational complexity of membership problems for the completely positive cone and its dual
• On cones of nonnegative quartic forms
• Semidefinite representation of convex sets
• Geometric algorithms and combinatorial optimization.
• New volume ratio properties for convex symmetric bodies in \({\mathbb{R}}^ n\)
• The concept of duality in convex analysis, and the characterization of the Legendre transform
• Classical deterministic complexity of Edmonds' Problem and quantum entanglement
• Some NP-complete problems in quadratic and nonlinear programming
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Most Tensor Problems Are NP-Hard
• Convex Analysis

This page was built for publication: The Computational Complexity of Duality