Scaling, proximity, and optimization of integrally convex functions

In discrete convex analysis, the scaling and proximity properties for the class of L\(^{\natural }\)-convex functions were established more than a decade ago and have been used to design efficient minimization algorithms. For the larger class of integrally convex functions of n variables, we show here that the scaling property only holds when \(n \le 2\), while a proximity theorem can be established for any n, but only with a superexponential bound. This is, however, sufficient to extend the classical logarithmic complexity result for minimizing a discrete convex function of one variable to the case of integrally convex functions of any fixed number of variables.

1. \({{\mathbb {Z}}}\)-valued functions are treated in [4, Theorem 3], but the proof is valid for \({{\mathbb {R}}}\)-valued functions.

2. Recall that \(n=3\) in Example 4.4.

3. x is f-minimal if and only if \(\arg \min f_{[ \mathbf{0},x ]} = \{ x \}\) for the function \( f_{[\mathbf{0},x]}(y) = \left\{ \begin{array}{cl} f(y) &{}\quad (y \in [\mathbf{0},x]_{{{\mathbb {Z}}}}), \\ +\,\infty &{}\quad (y \in {{\mathbb {Z}}}^{n} {\setminus } [\mathbf{0},x]_{{{\mathbb {Z}}}}). \end{array}\right. \)

4. See H. Tuy: D.C. optimization: Theory, methods and algorithms, in: R. Horst and P. M. Pardalos, eds., Handbook of Global Optimization, Kluwer Academic Publishers, Dordrecht, 1995, 149–216; Lemma 2 to be specific.

The authors thank Yoshio Okamoto for communicating a relevant reference and two anonymous referees for detailed comments. This research was initiated at the Trimester Program “Combinatorial Optimization” at Hausdorff Institute of Mathematics, 2015. This work was supported by The Mitsubishi Foundation, CREST, JST, Grant Number JPMJCR14D2, Japan, and JSPS KAKENHI Grant Numbers JP26350430, JP26280004, JP16K00023, JP17K00037.

Authors and Affiliations

1. Tokyo Metropolitan University, Tokyo, Japan

   Satoko Moriguchi & Kazuo Murota

2. Keio University, Tokyo, Japan

   Akihisa Tamura

3. Sapienza University of Rome, Rome, Italy

   Fabio Tardella

Corresponding author

Correspondence to Satoko Moriguchi.

The extended abstract of this paper is included in the Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC), Sydney, December 12–14, 2016. Leibniz International Proceedings in Informatics (LIPIcs), 64 (2016), 57:1–57:12, Dagstuhl Publishing.

Appendix A: An alternative Proof of Theorem 2.4

Here is a proof of Theorem 2.4 (local characterization of integral convexity) that is shorter than the original proof in [2] and valid for functions defined on general integrally convex sets rather than discrete rectangles.

Obviously, (a) implies (b). The proof for the converse, (b) \(\Rightarrow \) (a), is given by the following two lemmas, where integral convexity of \(\mathrm{dom\,}f\) and condition (b) are assumed.

Lemma A.1

Let \(B \subseteq {{\mathbb {R}}}^{n}\) be a box of size two with integer vertices, i.e., \(B = [ {a}, {a} + 2 \varvec{1} ]_{{{\mathbb {R}}}}\) for some \({a} \in {{\mathbb {Z}}}^{n}\). Then \({\tilde{f}}\) is convex on \(B \cap \overline{\mathrm{dom\,}f}\).

Proof

First, the assumed integral convexity of \(\mathrm{dom\,}f\) implies that \(B \cap \overline{\mathrm{dom\,}f} = \overline{B \cap \mathrm{dom\,}f}\) and that every point in \(B \cap \overline{\mathrm{dom\,}f}\) can be represented as a convex combination of points in \(B \cap \mathrm{dom\,}f\). We may assume \(B = [ \varvec{0}, 2 \varvec{1} ]_{{{\mathbb {R}}}}\). To prove by contradiction, assume that there exist \(x \in B \cap \overline{\mathrm{dom\,}f}\) and \(y^{1},\ldots , y^{m} \in B \cap \mathrm{dom\,}f\) such that

where \(\sum _{i=1}^{m} \lambda _{i} = 1\) and \(\lambda _{i} > 0 \ (i=1,\ldots , m)\). We may also assume \(x \in [ \varvec{0}, \varvec{1} ]_{{{\mathbb {R}}}}\) without loss of generality. For each \(j=1,\ldots , n\), we look at the j-th component of the generating points \(y^{i}\) to define

Since \( x_{j} = \sum _{i=1}^{m} \lambda _{i} y^{i}_{j} \le 1\), if \(I_{j}^{2} \not = \emptyset \), then \(I_{j}^{0} \not = \emptyset \).

Let \(j=n\) and suppose that \(I_{n}^{2} \not = \emptyset \). Then \(I_{n}^{0} \not = \emptyset \). We may assume \(y^{1}_{n} = 0\), \(y^{2}_{n} = 2\); \(\lambda _{1} > 0\), \(\lambda _{2} > 0\). By (2.2) for \((y^{1}, y^{2})\) and the definition of \({\tilde{f}}\) we have

where

with \(\mu _{k} > 0\)\((k=1,\ldots , l)\) and \(\sum _{k=1}^{l} \mu _{k} = 1\). This implies, with notation \(\lambda = \min (\lambda _{1}, \lambda _{2})\), that

Hence

Since

we have obtained another representation of the form (A.1). With reference to this new representation define \({\hat{I}}_{n}^{0}\) (resp., \({\hat{I}}_{n}^{2}\)) to be the set of indices of the generators whose n-th component is equal to 0 (resp., 2). Since \(z^{k}_{n} = 1\) for all k as a consequence of (A.2) with \((y^{1}_{n}+ y^{2}_{n})/2 = (0 + 2)/2 = 1\), we have \({\hat{I}}_{n}^{0} \subseteq I_{n}^{0}\), \({\hat{I}}_{n}^{2} \subseteq I_{n}^{2}\) and \(|{\hat{I}}_{n}^{0}| + |{\hat{I}}_{n}^{2}| \le |I_{n}^{0}| + |I_{n}^{2}| - 1\).

By repeating the above process with \(j=n\), we eventually arrive at a representation of the form of (A.1) with \(I_{n}^{2} = \emptyset \), which means that \(y^{i}_{n} \in \{ 0,1 \}\) for all generators \(y^{i}\).

Then we repeat the above process for \(j=n-1,n-2, \ldots ,1\), to obtain a representation of the form of (A.1) with \(y^{i} \in [ \varvec{0}, \varvec{1} ]_{{{\mathbb {Z}}}}\) for all generators \(y^{i}\). This contradicts the definition of \({\tilde{f}}\). \(\square \)

Lemma A.2

For any \(x, y \in \overline{\mathrm{dom\,}f}\), \({\tilde{f}}\) is convex on the line segment connecting x and y.

Proof

Let L denote the (closed) line segment connecting x and y, and consider the boxes B, as in Lemma A.1, that intersect L. There exists a finite number of such boxes, say, \(B_{1}, \ldots , B_{m}\), and L is covered by the line segments \(L_{j} = L \cap B_{j}\)\((j=1,\ldots , m)\). That is, \( L = \bigcup _{j=1}^{m} L_{j}\). For each point \(z \in L {\setminus } \{ x, y \}\), there exists some \(L_{j}\) that contains z in its interior. Since \(L_{j} \subseteq L \subseteq \overline{\mathrm{dom\,}f}\), \({\tilde{f}}\) is convex on \(L_{j}\) by Lemma A.1. Hence^{Footnote 4}\({\tilde{f}}\) is convex on L. \(\square \)

Appendix B: Proof of Proposition 5.3

It is known (cf. [29, proof of Theorem 16.4]) that the set of integer vectors contained in

forms a Hilbert basis of \({\tilde{C}}_{A}\). Let z be an integer vector in \(F_{A}\). That is, \(z \in {{\mathbb {Z}}}^{n}\) and

for some \(\mu _{i}^{+}, \mu _{i}^{-} \in [0,1]_{{{\mathbb {R}}}}\;(i \in A)\); \(\mu _{i}^{\circ } \in [0,1]_{{{\mathbb {R}}}}\; (i \in N {\setminus } A)\); \(\lambda \in [0,1]_{{{\mathbb {R}}}}\). Our goal is to show that z can be represented as a nonnegative integer combination of vectors in \(B_{A}\).

First note that \(\mu _{i}^{\circ } \in \{ 0, 1 \}\) for each \(i \in N {\setminus } A\); define \(A^{\circ } = \{ i \in N {\setminus } A \mid \mu _{i}^{\circ }=1 \}\). We denote the coefficient of \(\varvec{1}_{A}\) in (B.2) as

and divide into cases according to whether \(\xi \) is an integer or not.

Case 1 (\(\xi \in {{\mathbb {Z}}}\)): Using \(\xi \) we rewrite (B.2) as

in which \(\xi \) is an integer. For each \(i \in A\), \(\mu _{i}^{+}-\mu _{i}^{-}\) must be an integer, which is equal to 0, 1 or \(-1\). Accordingly we define

to rewrite (B.1) as

Here the coefficient of \(\varvec{1}_{A}\) is integral, since

Hence (B.3) gives a representation of z as a nonnegative integer combination of vectors in \(B_{A}\).

Case 2 (\(\xi \not \in {{\mathbb {Z}}}\)): Let \(\eta \) denote the fractional part of \(\xi \), i.e., \(\eta = \xi - \lfloor \xi \rfloor \) with \(0< \eta < 1\). We rewrite (B.2) as

For each \(i \in A\), \(\mu _{i}^{+}-\mu _{i}^{-} + \eta \) must be an integer, which is equal to 1 or 0. Accordingly we define

Then

which follows from

In the case of \(|A^{+}| \le |A^{-}|\), we see from (B.4) that

which is a nonnegative integer combination of vectors in \(B_{A}\). In the other case with \(|A^{+}| > |A^{-}|\), we have an alternative expression

which is also a nonnegative integer combination of vectors in \(B_{A}\). This completes the proof of Proposition 5.3.

Reprints and permissions