The computational complexity of duality

DOI10.1137/16M105887XMaRDI QIDQ2832893zbMATH OpenOpenAlexFDO

Authors Lek-Heng Lim, S. 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

approximationdual conedual normFenchel dualMahler volumenorm ballNP-hardpolynomial-time reducibleproper conesymmetric convex bodyweak membership

Mathematics Subject Classification ID

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

Abstract: We show that for any given norm ball or proper cone, weak membership in its dual ball or dual cone is polynomial-time reducible to weak membership in the given ball or cone. A consequence is that the weak membership or membership problem for a ball or cone is NP-hard if and only if the corresponding problem for the dual ball or cone is NP-hard. In a similar vein, we show that computation of the dual norm of a given norm is polynomial-time reducible to computation of the given norm. This extends to convex functions satisfying a polynomial growth condition: for such a given function, computation of its Fenchel dual/conjugate is polynomial-time reducible to computation of the given function. Hence the computation of a norm or a convex function of polynomial-growth is NP-hard if and only if the computation of its dual norm or Fenchel dual is NP-hard. We discuss implications of these results on the weak membership problem for a symmetric convex body and its polar dual, the polynomial approximability of Mahler volume, and the weak membership problem for the epigraph of a convex function with polynomial growth and that of its Fenchel dual.

Recommendations

• Computational complexity of norm-maximization
• On the computational complexity of membership problems for the completely positive cone and its dual
• Fixed-parameter complexity and approximability of norm maximization
• An exact duality theory for semidefinite programming and its complexity implications
• scientific article; zbMATH DE number 1182920

Cites work

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

Cited in

(13)

• Completely positive tensor recovery with minimal nuclear value
• Approximation hierarchies for the cone of flow matrices
• The global convergence of the nonlinear power method for mixed-subordinate matrix norms
• Combinatorial methods for the spectral \(p\)-norm of hypermatrices
• Nuclear norm of higher-order tensors
• The Big Mother of all Dualities: Möller Algorithm
• Highly entangled tensors
• Operator norm inequalities between tensor unfoldings on the partition lattice
• Symmetric tensor nuclear norms
• On semidefinite programming characterizations of the numerical radius and its dual norm
• Rank of a tensor and quantum entanglement
• On spectral and nuclear norms of order three tensors with one fixed dimension
• New estimations on the upper bounds for the nuclear norm of a tensor

This page was built for publication: The computational complexity of duality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2832893)