The Computational Complexity of Duality

Introduction

In convex optimization, we often encounter problems that involve one of the following notions of duality. For convex sets: (i) norm balls and their polar duals, (ii) proper cones and their dual cones; for convex functions: (iii) norms and their dual norms; (iv) functions and their Fenchel duals. The main goal of this article is to establish the equivalence between the polynomial-time computability or NP-hardness of these objects and their duals.

We will first show in Section 3 that the weak membership problem for a norm ball is NP-hard (resp. is polynomial-time) if and only if the weak membership problem for its dual norm ball is NP-hard (resp. is polynomial-time). For readers unfamiliar with the notion, NP-hardness of weak membership is a stronger statement than NP-hardness of membership, i.e., the latter is implied by the former. Since every symmetric convex compact set with nonempty interior is a norm ball, the result applies to such objects and their polar duals as well.

In Section 4 we show that the approximation of a norm to arbitrary precision is NP-hard (resp. is polynomial-time) if and only if weak membership in the unit ball of the norm is NP-hard (resp. is polynomial-time). A consequence is that if the weak membership problem for a norm ball is polynomial-time decidable, then its Mahler volume is polynomial-time approximable. In fact, computation of Mahler volume is polynomial-time reducible to the weak membership problem for a norm ball.

In Section 5, we establish an analogue of our norm ball result for proper cones, showing that the weak membership problem for such a cone is NP-hard (resp. is polynomial-time) if and only if the weak membership problem for its dual cone can be decided is NP-hard (resp. is polynomial-time).

We conclude by showing in Section 6 that for convex functions that satisfy a polynomial-growth condition, its Fenchel dual must also satisfy the same condition with possibly different constants. A consequence of this is that such a function is polynomial-time approximable to arbitrary precision if and only if its Fenchel dual is also polynomial-time approximable to arbitrary precision. On the other hand, such a function is NP-hard to approximate if and only if its Fenchel dual is NP-hard to approximate.

Weak membership, weak validity, and polynomial-time reducibility

Note that if $K$ has no interior point, then $S(K,-\delta)=\varnothing$.

For the benefit of readers unfamiliar with these notions, we highlight that in our weak membership problem, there are $x$’s that satisfy both $x\in S(K,\delta)$ and $x\notin S(K,-\delta)$ simultaneously. So if we can ascertain mem, we can ascertain wmem, but not conversely. A consequence is that if wmem problem for $K$ is NP-hard, then mem for $K$ is also NP-hard.

Recall that a problem $\mathscr{P}$ is said to be polynomial-time reducible [6, p. 28] to a problem $\mathscr{Q}$ if there is a polynomial-time algorithm $A_{\mathscr{P}}$ for solving $\mathscr{P}$ by making a polynomial number of oracle calls to an algorithm $A_{\mathscr{Q}}$ for solving $\mathscr{Q}$. This notion of polynomial-time reducibility is also called Cook or Turing reducibility and will be the one used throughout our article. There is also a more restrictive notion of polynomial-time reducibility that allows only a single oracle call to $A_{\mathscr{Q}}$ called Karp or many-one reducibility.

Note that if $A_{\mathscr{Q}}$ is a polynomial-time algorithm for $\mathscr{Q}$, then $A_{\mathscr{P}}$ is a polynomial-time algorithm for $\mathscr{P}$. Consequently, if $\mathscr{Q}$ is computable in polynomial-time, then so is $\mathscr{P}$. On the other hand, if $\mathscr{P}$ is NP-hard, then so is $\mathscr{Q}$.

We say that $\mathscr{P}$ and $\mathscr{Q}$ are polynomial-time inter-reducible if $\mathscr{P}$ is polynomial-time reducible to $\mathscr{Q}$ and $\mathscr{Q}$ is polynomial-time reducible to $\mathscr{P}$. The polynomial-time inter-reducibility of two problems $\mathscr{P}$ and $\mathscr{Q}$ implies that they are in the same time-complexity classAssuming that the complexity class is defined by polynomial-time inter-reducibility. whatever it may be. Nevertheless, in this article we will restrict ourselves to just polynomial-time computability and NP-hardness, the two most often used cases in optimization.

Weak membership in dual norm balls

There is no loss of generality in assuming that $k_{\nu}$ and $K_{\nu}$ are rationalIf not just pick a smaller $k_{\nu}$ or a larger $K_{\nu}$ that is rational. and we may denote the number of bits required to specify them by $\langle k_{\nu}\rangle$ and $\langle K_{\nu}\rangle$ respectively.

Recall that the dual norm of $\nu$, denoted $\nu^{*}$, is given by

Observe first that $B(0,1/K_{\nu})\subseteq B_{\nu}\subseteq B(0,1/k_{\nu})$ and $B(0,k_{\nu})\subseteq B_{\nu^{*}}\subseteq B(0,K_{\nu})$. So $B_{\nu}$ and $B_{\nu^{*}}$ satisfy the centering assumption after Definition 2.2 with $a=0$. Hence

The main result of this section is the polynomial-time inter-reducibility between a norm and its dual.

Let $\nu$ be a norm and $\nu^{*}$ be its dual norm. The wmem problem for the unit ball of $\nu^{*}$ is polynomial-time reducible to the wmem problem for the unit ball of $\nu$.

We will prove this result via two intermediate lemmas. A key step in our proof depends on the Yudin–Nemirovski Theorem , which may be stated as follows [6, Theorem 4.3.2].

The original Yudin–Nemirovski Theorem is in fact stronger than the version stated here, allowing the weak violation problem wviol to be reduced to wmem. Nevertheless in this article we will only require the weaker result with wval in place of wviol.

whenever $K_{\nu}\delta<1$, and the inequalities

Also, $\bigcup_{x\in B_{\nu}}B_{\nu}(x,r)=B_{\nu}(0,1+r)$ by the defining properties of a norm. Hence

To prove (5), let $T=\bigcup_{x\,:\,\nu(x)=1}B^{\circ}(x,\delta)$ and so $S(B_{\nu},-\delta)=B_{\nu}\setminus T$. Let

Since $T_{1}\supseteq T$ and $T_{2}\subseteq T$, we obtain

The last two inequalities follow from the first two inclusions and (3). ∎

Let $k_{\nu}\geq 2$. Then the solution to wval problem for $B_{\nu^{*}}$ gives the solution to wmem problem for $B_{\nu}$.

It follows from (4) that $x\in S(B_{\nu},\delta)$.

Suppose that $x^{\mathsf{T}}y>1-\delta$ for some $y\in S(B_{\nu^{*}},\delta)$. Then \max\bigl{(}S(B_{\nu^{*}},\delta),x\bigr{)}>1-\delta and we deduce from (7) that

As straightforward calculation shows that

It follows from (5) that $x\notin S(B_{\nu},-\delta)$. ∎

We observe that the assumption $k_{\nu}\geq 2$ in Lemma 3.4 is not restrictive. Let $r\geq 2/k_{\nu}$. Then a new norm defined by $\nu_{r}(x)=r\nu(x)$ would satisfy the assumption. Now note that $x\in B_{\nu}$ if and only if $\frac{1}{r}x\in B_{\nu_{r}}$. With this observation, Theorem 3.1 follows from

Here $\mathscr{P}\Rightarrow\mathscr{Q}$ means that $\mathscr{Q}$ is polynomial-time reducible to $\mathscr{P}$. Yudin–Nemirovski Theorem gives the first and third reductions whereas Lemma 3.4 gives the second and last reductions. ∎

Since taking the dual of a dual norm gives us back the original norm, we have the following corollary.

The wmem problem for the unit ball of a norm $\nu$ is polynomial-time decidable (resp. NP-hard) if and only if the wmem problem for the unit ball of the dual norm $\nu^{*}$ is polynomial-time decidable (resp. NP-hard).

Since every centrally symmetric compact convex set with nonempty interior is a norm ball for some norm and its polar dual is exactly the norm ball for the corresponding dual norm, we immediately have the following.

be its polar dual. Then wmem in $C$ is polynomial-time inter-reducible to the wmem in $C^{*}$. In particular, if one is polynomial-time decidable (resp. NP-hard), then so is the other.

Approximation of dual norms

We call $\omega$ a $\delta$-approximation of $\nu$.

The weak membership problem for $B_{\nu}$.

and (4) yields that $x\in S(B_{\nu},\delta)$. Assume now that

and so $x\notin S(B_{\nu},-\delta)$. This shows that we may decide weak membership in $B_{\nu}$ with a $\delta$-approximation to $\nu$. In fact we just need one oracle call to approx.

and consider $y=x/r$. Assume first that $y\in S(B_{\nu},\varepsilon)$. Then the right inclusion in (4) yields $\nu(y)\leq 1+K_{\nu}\varepsilon$ and thus

In this case we set $a_{i+1}=a_{i}$ and $b_{i+1}=3b_{i}/4+a_{i}/4$. Assume now that $y\notin S(B_{\nu},-\varepsilon)$. Then the left inclusion in (5) yields

In this case we set $a_{i+1}=b_{i}/4+3a_{i}/4$ and $b_{i+1}=b_{i}$.

Clearly $m$ is polynomial, in fact linear, in $\langle K_{\nu}\rangle+\langle k_{\nu}\rangle+\langle\delta\rangle$. Setting $\omega(x)\coloneqq(a_{m}+b_{m})/2$, we obtain a $\delta$-approximation of $\nu(x)$. This shows that we may determine a $\delta$-approximation to $\nu$ with $m$ oracle calls to wmem in $B_{\nu}$. ∎

A norm is polynomial-time approximable (resp. NP-hard to approximate) if and only if its dual norm is polynomial-time approximable (resp. NP-hard to approximate).

A particularly nice property of the Mahler volume is that it is invariant under any invertible linear transformation, regardless of whether it is volume-preserving or not.

If the weak membership problem in $B_{\nu}$ is polynomial-time decidable, then $M(\nu)$ is polynomial-time approximable.

If the wmem in $B_{\nu}$ is polynomial-time decidable, then it follows from that there exist polynomial-time algorithms to approximate $\operatorname{Vol}_{n}(B_{\nu})$ to any given error $\varepsilon>0$. By Corollary 4.3, the wmem in $B_{\nu^{*}}$ is also polynomial-time decidable and thus the same holds for $\operatorname{Vol}_{n}(B_{\nu^{*}})$. ∎

Mahler volume is more commonly defined for a centrally symmetric compact convex set but as we mentioned before Corollary 3.6, this is equal to a unit norm ball for an appropriate choice of norm.

Weak membership in dual cones

is also a proper cone . The main result of this section is an analogue of Theorem 3.1 for such cones: The weak membership problem for $K^{*}$ is polynomial-time reducible to the weak membership problem for $K$.

It is well-known that deciding mem for the cone of copositive matrices is NP-hard . This result has recently been extended : wmem in the cone of copositive matrices and wmem in its dual cone, the cone of completely positive matrices, are both NP-hard problems. Our result in this section generalizes this to arbitrary proper cones.

We first recall a well-known result regarding the interior points of $K^{*}$.

Let $x\in K\setminus\{0\}$. Then $c\coloneqq b-\varepsilon_{b}x/\|x\|\in K^{*}$. Hence $c^{\mathsf{T}}x\geq 0$, which implies (10). ∎

are compact convex sets of dimension $n-1$. Hence the sets $P_{b}-(b^{\mathsf{T}}a)^{-1}a$ and $P_{a}^{*}-(a^{\mathsf{T}}b)^{-1}b$ are full-dimensional compact convex sets in the orthogonal complements of $\operatorname{span}(b)$ and $\operatorname{span}(a)$ respectively. In fact $P_{b}$ and $P_{a}^{*}$ are compact convex sets of maximal dimension in the affine hyperplanes

respectively. We may also view $H_{b}$ and $H_{a}$ as the affine hulls of $P_{b}$ and $P_{a}^{*}$ respectively.

As the cones $K$ and $K^{*}$ are noncompact, these hyperplane sections $P_{b}$ and $P_{a}^{*}$ serve as their compact proxies, allowing us to encode $K$ and $K^{*}$ (for a Turing machine). We will assume knowledge of four positive rational numbers $\rho_{a}^{\prime}<\rho_{a}$ and $\rho_{b}^{\prime}<\rho_{b}$ such that

While the numbers $\rho_{a},\rho_{a}^{\prime},\rho_{b},\rho_{b}^{\prime}$ do not appear explicitly in our proofs, they are needed implicitly when we invoke the Yudin–Nemirovski Theorem.

Given any $x\neq 0$, observe that $x\in K$ if and only if $x/(b^{\mathsf{T}}x)\in P_{b}$. Thus the membership problem for $K$ is equivalent to the membership problem for $P_{b}$. We show in the following that this extends, in an appropriate sense, to weak membership as well.

Decide weak membership of $y\coloneqq x/(b^{\mathsf{T}}x)$ in $P_{b}$ relative to $H_{b}$.

In the following, we let $y\coloneqq x/(b^{\mathsf{T}}x)$ and u\coloneqq(x+z)/\bigl{(}b^{\mathsf{T}}(x+z)\bigr{)}\in H_{b}.

Hence $y\notin S_{H_{b}}(P_{b},-\varepsilon)$.

Consider first the case $y\notin S_{H_{b}}(P_{b},-\varepsilon)$. There exists $v\in H_{b}\setminus{P_{b}}$ such that $\|v-y\|\leq\varepsilon$. Let $z=(b^{\mathsf{T}}x)(v-y)$. So

Hence $(b^{\mathsf{T}}x)v=x+z\notin K$ and so $x\notin S(K,-\delta)$.

Consider now the case $y\in S_{H_{b}}(P_{b},\varepsilon)$. The same line of argument as above yields that $x\in S(K,\delta)$. Together the two cases show that if we can decide wmem in $P_{b}$ relative to $H_{b}$ with inputs $y$, $\varepsilon$, then we can decide wmem in $K$ with inputs $x$, $\delta$. ∎

Lemma 5.2 may be viewed as a compactification result: We transform a problem involving a noncompact object $K$ to a problem involving a compact object $P_{b}$. The motivation is so that we may apply the Yudin–Nemirovski Theorem later.

where $\delta/0\coloneqq\infty$ if $b=c$. It follows from (12) that

Consider first the case $c^{\mathsf{T}}x\geq-c^{\mathsf{T}}a-\varepsilon$ for all $x\in S_{H_{b}}(K_{b},-\varepsilon)$, or, equivalently, $c^{\mathsf{T}}y\geq-\varepsilon$ for all $y=x+a\in S_{H_{b}}(P_{b},-\varepsilon)$. We claim that $c^{\mathsf{T}}y\geq-(1+\|c\|)\varepsilon$ for all $y\in P_{b}$. This holds for $y\in S_{H_{b}}(P_{b},-\varepsilon)$ since $c^{\mathsf{T}}y\geq-\varepsilon\geq-(1+\|c\|)\varepsilon$. For $y\in P_{b}\setminus S_{H_{b}}(P_{b},-\varepsilon)$, there exists $x\in S_{H_{b}}(P_{b},-\varepsilon)$ such that $\|y-x\|\leq\varepsilon$. Thus $c^{\mathsf{T}}y=c^{\mathsf{T}}x+c^{\mathsf{T}}(y-x)\geq-\varepsilon-\|c\|\|y-x\|=-(1+\|c\|)\varepsilon$. Then for any $y\in P_{b}$,

By the middle inequality in (13), we obtain $c\in S_{H_{a}}(P_{a}^{*},\delta)$.

Consider now the case $c^{\mathsf{T}}x\leq-c^{\mathsf{T}}a+\varepsilon$ for some $x\in S_{H_{b}}(K_{b},\varepsilon)$, or, equivalently, $c^{\mathsf{T}}y\leq\varepsilon$ for some $y=x+a\in S_{H_{b}}(P_{b},\varepsilon)$. Hence there exists $z\in P_{b}$ such that $\|z-y\|\leq\varepsilon$ and so $c^{\mathsf{T}}z=c^{\mathsf{T}}y+c^{\mathsf{T}}(z-y)\leq(1+\|c\|)\varepsilon=\tau<1/4$ by the left inequality in (13). Then

By the right inequality in (13), we obtain $c\not\in S_{H_{a}}(P_{a}^{*},-\delta)$. ∎

Approximation of Fenchel duals

(i) is of course a generalization of Definition 4.1 from norms to a more general function. We will show that (i) and (ii) are polynomial-time inter-reducible. For this purpose, we will need a useful corollary [6, Corollary 4.3.12] of the Yudin–Nemirovski Theorem (cf. Theorem 3.2) with the wopt problem in place of the wval problem.

Then the approximation problem for $\mu$ is polynomial-time reducible to the approximation problem for $f$.

Note that we require knowledge of the values of both $\alpha$ and $\delta$, not just of their existence. We need the condition (14) to ensure that no minimizer of $f$ lies on the boundary of $C$ and that any minimizer is at least distance $\delta$ away from the boundary.

We will show that wopt in $\operatorname{epi}_{2\alpha}(f)$ yields a solution to approx for $\mu$. The result then follows from two polynomial-time reductions: wopt in $\operatorname{epi}_{2\alpha}(f)$ can be reduced to wmem in $\operatorname{epi}_{2\alpha}(f)$, wmem in $\operatorname{epi}_{2\alpha}(f)$ can be reduced to approx for $f$.

for all $(x,t)\in S(C^{\prime},-\varepsilon)$. We claim that $s=\mu(\varepsilon)$, the required approximation to $\mu$. Since $\varepsilon<\delta$, it follows that $S(C^{\prime},-\varepsilon)\supseteq S(C^{\prime},-\delta)$. The assumption (14) ensures that $(x^{\star},\mu)\in S(C,-\delta)$ where $f(x^{\star})=\mu$. Hence we deduce that $s\leq\mu+\varepsilon$, i.e., $\mu\geq s-\varepsilon$. As $(y,s)\in S(C^{\prime},\varepsilon)$, it follow that there exists $(x^{\prime},t^{\prime})\in C^{\prime}$ such that $t^{\prime}\geq f(x^{\prime})$ and $\lvert t^{\prime}-s\rvert\leq\varepsilon$. So $s\geq t^{\prime}-\varepsilon\geq\mu-\varepsilon$. Thus $\mu-\varepsilon\leq s\leq\mu+\varepsilon$, but starting with $2\varepsilon$ in place of $\varepsilon$ allows us to replace ‘$\leq$’ by ‘$<$’ as required by Definition 6.1(ii). ∎

The Fenchel dual is also known as the Fenchel conjugate and the map $f\mapsto f^{*}$ is sometimes called the Legendre transform. It is well-known that $f^{*}$ is always a convex function, being the pointwise supremum of a family of affine functions $y\mapsto y^{\mathsf{T}}x-f(x)$. It is also well-known that $f$ is a lower semicontinuous proper convex function if and only if $f^{**}=f$.

for some constants $0<k_{f}\leq K_{f}$, $1<s\leq t$, and $r>0$ depending on $f$. We now show that $f^{*}$ must satisfy similar growth conditions

For $\|x\|\geq r$, the lower bound in (15) and $y^{\mathsf{T}}x\leq\|y\|\|x\|$ give

Observe that for $z\in[0,\infty)$, the maximum of $h(z)\coloneqq\|y\|z-k_{f}z^{s}$ is attained at

Let $\mu\coloneqq\min_{\lVert x\rVert\leq r}f(x)$. Then

This last inequality yields the upper bound in (16) with

for a corresponding $r_{1}$ that depends on $k_{f},s,r,\mu$. More precisely, either $r_{1}=0$ or $r_{1}$ is the unique positive solution of

To deduce the lower bound in (16), let $y$ be such that

It follows that $\|x\|\geq r$ and so the upper bound in (15) yields $f^{*}(y)\geq\|y\|\|x\|-K_{f}\|x\|^{t}$. Hence we have the lower bound in (16) with

We will compute an approximation of $f^{*}(y)$ with oracle calls to approximations of $f(x)$.

Let $C=B(0,\rho_{0}+1)$. Since mem in a Euclidean ball $B(0,\rho)$ is clearly polynomial-time decidable, the conditions of Lemma 6.3 are satisfied. Hence approx for $f^{*}(0)$ is polynomial-time reducible to approx for $f$.

Suppose now that $y\neq 0$. Clearly $f^{*}(y)\geq-f(0)$. Let $\rho>r$, where $r$ is as in (15). Let f^{*}_{\rho}(y)\coloneqq\max_{\|x\|=\rho}\bigl{(}y^{\mathsf{T}}x-f(x)\bigr{)}. As $y^{\mathsf{T}}x\leq\|y\|\|x\|$, the lower bound in (15) gives

Since $f^{**}=f$ for a convex function and by Lemma 15, $f$ and $f^{*}$ both satisfy the polynomial growth condition if either one does, we obtain the following.

Conclusion

In this article, we have focused on establishing equivalence in the computational complexity of dual objects for several common convex objects and common notions of duality. These results are expected to have immediate applications in many areas. We conclude our article with two such examples.

Drawing from our own work, we rely on the results in Sections 3 and 4 to deduce that the nuclear norm for higher-order tensors is NP-hard to compute [5, Corollary 8.8] and likewise for the dual norm of an operator $(p,q)$-norm when $1\leq q<p\leq\infty$ or when $p=q\notin\{1,2,\infty\}$ [5, Section 7].

Acknowledgment

We are very grateful to the two anonymous referees for their exceptionally helpful suggestions and comments. We would like to thank Lev Reyzin for telling us about the various variants of the membership problem, and to Shuzhong Zhang for informing us that the problem of complexity of dual cones is still open and pointing us to .

References