Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization

The continuous hitting set problem stated above corresponds to the decision version of the optimization Problem (3) when there is no first-stage decision ($\mathrm{\ell }=0$); See Lemma 5. This correspondence is also the motivation for our convention that an affine family of polyhedra with one empty member has no hitting set, as such a family corresponds to an unfeasible problem. Like in the discrete setting, the hitting and covering problems for affine families of polyhedra enjoy some form of duality (see Section 2.1). We prove (Lemma 6) that the decision version of the general finite adaptability problem is a special case of the following covering problem:

Given two affine families of polyhedra in ${ℝ}^d$ and $k\in \mathbb{N}$, does there exist $k$ polyhedra in the second family whose union covers a polyhedron from the first family?

Notice that this problem is purely linear, whereas the finite adaptability Problem (3) exhibits some non-linearity.

We then turn our attention to the computational complexity of these problems. We first observe that quantifier elimination methods yield strongly polynomial solutions ¹¹1The standard model of computation in computational geometry is the Real-RAM model, a variant of the classical random access machine (RAM) that operates on arbitrary real numbers instead of finite binary words, see [20, $\mathrm{\S }7.4$] and [21, $\mathrm{\S }6.1$]. Algorithms that run in polynomial time on a Real-RAM and that translate to polynomial-time algorithms in the usual sense are called strongly polynomial. Whether linear programming can be solved in strongly polynomial time remains a major open problem, known as Smale’s 9th problem [34]. for these problems in fixed dimension.

Similarly, the hitting and covering problems stated above can be solved in time $m^{O(1)}$ when we fix $k$, the ambient dimensions of the polyhedra and the dimension of the parameter space(s) (see Section 3). The bound in the exponent grows with the values of the fixed parameters, and the fixed-parameter tractability of these problems is a natural question. In the special case where the parameter domain is one-dimensional, we can give an algorithm for the hitting set problem where the order of the complexity does not depend on $k$ or the ambient dimension of the polyhedra.

If $k$ is part of the input, then our algorithm has complexity $O(k{m}^2)$ in the Real-RAM model (Proposition 13) but is no longer strongly polynomial. We can extend the method behind Theorem 2 to the optimization problem:

Let us fix a basis $(e_1,e_2,\mathrm{\dots },e_p)$ of ${ℝ}^p$, so as to write $\omega =({\omega }_1,{\omega }_2,\mathrm{\dots },{\omega }_p)$, $A(\omega )=A_0+{\sum }_{i=1}^p{\omega }_i{A}_i$ and $b(\omega )=b_0+{\sum }_{i=1}^p{\omega }_i{b}_i$, where $A_0,A_1,\mathrm{\dots },A_p\in {ℝ}^{m\times d}$, $b_0,b_1,\mathrm{\dots },b_p\in {ℝ}^m$. For $x\in {ℝ}^d$, we have

Let $\widehat{A}(x)={\sum }_{i=1}^p\left(A_{i}x-b_i\right)e_i^{}{}_{}{}^T\in {ℝ}^{m\times p}$, so that $\widehat{A}(x)\omega ={\sum }_{i=1}^p\left(A_{i}x-b_i\right){\omega }_i$. Let $\widehat{b}(x)=b_0-A_{0}x$. Note that $\widehat{P}(x)=\{\omega \in {ℝ}^p:\widehat{A}(x)\omega \le \widehat{b}(x)\}$ with $\widehat{A}$ and $\widehat{b}$ affine maps. It follows that $\widehat{P}({ℝ}^d)$ is an affine family of polyhedra, with ambient space of dimension $p$, parameter space of dimension $d$ and each polyhedron defined by $m$ constraints. $◀$ When $\mathrm{\Omega }$ is a polyhedron in ${ℝ}^p$, a natural candidate for the dual of an affine family $P(\mathrm{\Omega })$ of polyhedra is $\{\omega \in \mathrm{\Omega }:x\in P(\omega )\}$. This is again an affine family of polyhedra, which we denote by ${\widehat{P}}_{|\mathrm{\Omega }}({ℝ}^d)=\{\widehat{P}(x)\cap \mathrm{\Omega }:x\in {ℝ}^d\}$. In other words, restricting $P({ℝ}^p)$ into $P(\mathrm{\Omega })$ translates, under duality, into intersecting each dual polyhedron with $\mathrm{\Omega }$.

Let $t\in ℝ$. The value of Problem (4) is at most $t$ if and only if there exists $x_s=(x_s^1,x_s^2,\mathrm{\dots },x_s^k)\in {({ℝ}^d)}^k$ such that

Hence, the value of Problem (4) is at most $t$ if and only if $P_t(\mathrm{\Omega })$ admits a hitting set of size $k$. Observe that in particular, Problem (4) is infeasible if and only if there is no feasible solution $(x_s^1,x_s^2,\mathrm{\dots },x_s^k)$, that is no hitting set of size $k$ for $P(\mathrm{\Omega })$. $◀$

When there is a first decision ($\mathrm{\ell }>0$), one may proceed as in Lemma 5, mutatis mutandis, and obtain the following characterizations of the fact that the value of (3) is at most $t$:

1. (a)

   The affine family of polyhedra $P_t(\mathrm{\Omega })=\{P_t(\omega ):\omega \in \mathrm{\Omega }\}$ defined by

   admits a hitting set of size $k$ in which all points have the same first $\mathrm{\ell }$ coordinates.

2. (b)

   There exists $x_f\in {ℝ}^{\mathrm{\ell }}$ such that the affine family of polyhedra $P_{x_f,t}(\mathrm{\Omega })=\{P_{x_f,t}(\omega ):\omega \in \mathrm{\Omega }\}$ defined by

   $$P_{x_f,t}(\omega )=\{x_s\in {ℝ}^{\delta }:\left(\begin{array}{c}{A}_s(\omega )\\ c_s{(\omega )}^T\end{array}\right)x_s\le \left(\begin{array}{c}b(\omega )-A_f(\omega )x_f\\ t-c_f^{}{}_{}{}^T{x}_f\end{array}\right)\}$$

   admits a hitting set of size $k$.

In other words, we have to either require the hitting set to lie on some coordinate subspace (a), or work with an affinely parameterized family of affine families of polyhedra (b). Each affine family of polyhedra in (b) corresponds to the slice of the affine family of polyhedra of (a) by a coordinate subspace of codimension $\mathrm{\ell }$.

Let us fix $t\in ℝ$ and start from the characterization (b) from Section 2.2 – from which we recover the notation $P_{x_f,t}(\omega )$. The value of the $k$-adaptability problem (3) is at most $t$ if and only if there exists $(x_f,x_s^1,x_s^2,\mathrm{\dots },x_s^k)\in {ℝ}^{\mathrm{\ell }}\times {({ℝ}^{\delta })}^k$ such that for every $\omega \in \mathrm{\Omega }$, there exists $i\in [k]$ such that $x_s^i\in P_{x_f,t}(\omega )$. Letting $S_t(x_s)=\{(x_f,\omega )\in {ℝ}^{\mathrm{\ell }}\times \mathrm{\Omega }:x_s\in P_{x_f,t}(\omega )\}$, the characterization becomes: there exists $(x_f,x_s^1,x_s^2,\mathrm{\dots },x_s^k)\in {ℝ}^{\mathrm{\ell }}\times {({ℝ}^{\delta })}^k$ such that $\{x_f\}\times \mathrm{\Omega }$ is covered by $S_t(x_s^1)\cup S_t(x_s^2)\cup \mathrm{\dots }\cup S_t(x_s^k)$.

Let us now consider how the lift $L$ acts on this characterization. First, $L$ is a bijection from ${ℝ}^{\mathrm{\ell }+p}$ to $\mathrm{\Sigma }$, so $\{x_f\}\times \mathrm{\Omega }$ is covered by $S_t(x_s^1)\cup S_t(x_s^2)\cup \mathrm{\dots }\cup S_t(x_s^k)$ if and only if $L(\{x_f\}\times \mathrm{\Omega })$ is covered by $L(S_t(x_s^1))\cup L(S_t(x_s^2))\cup \mathrm{\dots }\cup L(S_t(x_s^k))$. Now, $L(\{x_f\}\times \mathrm{\Omega })=\stackrel{⌣}{𝑃}(x_f)$ by definition of $\stackrel{⌣}{𝑃}$ . On the other hand, the definition of $\stackrel{⌣}{𝑄}$  ensures that $L(S_t(x_s))=\stackrel{⌣\phantom{t}}{Q_t}(x_s)\cap \mathrm{\Sigma }$. The characterization therefore reformulates as: there exists $(x_f,x_s^1,x_s^2,\mathrm{\dots },x_s^k)\in {ℝ}^{\mathrm{\ell }}\times {({ℝ}^{\delta })}^k$ such that $\stackrel{⌣}{𝑃}(x_f)$ is covered by $(\stackrel{⌣\phantom{t}}{Q_t}(x_s^1)\cap \mathrm{\Sigma })\cup (\stackrel{⌣\phantom{t}}{Q_t}(x_s^2)\cap \mathrm{\Sigma })\cup \mathrm{\dots }\cup (\stackrel{⌣\phantom{t}}{Q_t}(x_s^k)\cap \mathrm{\Sigma })$. Since for every $x_f\in {ℝ}^{\mathrm{\ell }}$, the set $\stackrel{⌣}{𝑃}(x_f)$ is contained in $\mathrm{\Sigma }$, we can drop the intersections with $\mathrm{\Sigma }$ in that characterization, and the statement follows. $◀$

The decision version of Problem 3 can be cast as deciding, given $t$, the validity of the formula

where

and $P_t(\mathrm{\Omega })$ is the affine family of polyhedra defined by

Note that the polyhedron $P_t(\omega )$ encodes both the constraints enforced by $A_f,A_s$, and $b$ on $(x_f,x_s^i)$, and the bound $t$ on the optimal value (like in the proof of Lemma 4). The universal quantifier on $\omega$ takes care of the ${sup}_{\omega \in \mathrm{\Omega }}$ in the formulation (3), while the disjunction on the terms of the form $(x_f,x_s^i)\in P_t(\omega )$ takes care of the ${inf}_{i\in [k]}$.

We can apply Theorem 7 to eliminate the universal quantifier in ${\mathrm{\Phi }}_t(x_f,x_s)$. Referring to the parameters in Theorem 7, we have $n=1$ and $b=p$, and there are $s\le v+k(m+1)$ polynomials involved, defining the polyhedra $\mathrm{\Omega }$ and $P_t(\omega )$. Each polynomial is of degree at most $r=2$, and the total number of free variables is $k\delta +\mathrm{\ell }$. Hence, the elimination of the quantifier takes time $O\left({\left(v+m\right)}^{(k\delta +\mathrm{\ell }+1)(p+1)}\right)$.

We now have a formula with a single existential quantifier on $(x_f,x_s)$, to which we can apply Theorem 8. Following Theorem 7, the degree is at most $r^{O{(b)}^n}=2^{O(p)}$, and we can therefore decide the validity of the formula in time

as claimed. $◀$

Similarly, we can express the hitting and covering problems for affine families of polyhedra as the decision of the validity of a formula, which can then be handled by Theorems 7 and 8. This gives the following results:

• $\mathrm{■}$

  For every constant $k$, $p$, and $d$ there is an algorithm that decides in time strongly polynomial in $m$, given a polyhedron $\mathrm{\Omega }$ in ${ℝ}^p$ defined by $m$ constraints and an affine family of polyhedra $P(\mathrm{\Omega })$ in ${ℝ}^d$, each defined by at most $m$ constraints, whether $P(\mathrm{\Omega })$ admits a hitting set of size $k$. The complexity is $m^{O(1)}$, where the exponent depends on $k$, $p$, and $d$.

• $\mathrm{■}$

  For every constant $k$, $\gamma$, $\lambda$ and $d$ there is an algorithm that decides in time strongly polynomial in $m$, given an affine family of polyhedra $P(\mathrm{\Gamma })$ in ${ℝ}^d$ defined by at most $m$ constraints, and an affine family of polyhedra $Q(\mathrm{\Lambda })$ in ${ℝ}^d$, defined by at most $m$ constraints, with $\mathrm{\Gamma }\subseteq {ℝ}^{\gamma }$ and $\mathrm{\Lambda }\subseteq {ℝ}^{\lambda }$ polyhedra defined by at most $m$ constraints each, whether there exist ${\gamma }_0\in \mathrm{\Gamma }$ and ${\lambda }_1,{\lambda }_2,\mathrm{\dots },{\lambda }_k\in \mathrm{\Lambda }$ such that $P({\gamma }_0)\subseteq Q({\lambda }_1)\cup Q({\lambda }_2)\cup \mathrm{\dots }\cup Q({\lambda }_k)$. The complexity is $m^{O(1)}$, where the exponent depends on $k$, $\gamma$, $\lambda$ and $d$.

This approach can also be applied to the decision version of the two-stage robust optimization problem (2), yielding an algorithm with higher complexity than for the decision version of finite adaptability (3), see [12, Appendix C]. We also note that similar tools [4, $\mathrm{\S }14$, Algorithm 14.9] can solve the optimization version of the $k$-adaptability Problem (3), with $\mathrm{\Omega }$ a polyhedron in ${ℝ}^p$, in polynomial time for every constant $k$, $\mathrm{\ell }$, $\delta$ and $p$.

Observe first that for every subsets $A,B\subseteq \mathrm{\Omega }$, if $A\subseteq B$, then ${\bigcap }_{\omega \in B}P(\omega )\subseteq {\bigcap }_{\omega \in A}P(\omega )$. It follows that ${\mathscr{H}}_P\left(\mathrm{\Lambda }\right)\supseteq {\mathscr{H}}_P\left(\mathrm{conv}\mathrm{\Lambda }\right)$ and ${\mathscr{H}}_P\left(\mathrm{\Lambda }\right)\supseteq {\mathscr{H}}_P\left(\overline{\mathrm{\Lambda }}\right)$.

Let us prove that ${\mathscr{H}}_P\left(\mathrm{\Lambda }\right)\subseteq {\mathscr{H}}_P\left(\mathrm{conv}\mathrm{\Lambda }\right)$. Let $x\in {\bigcap }_{\omega \in \mathrm{\Lambda }}P(\omega )$. Consider a finite convex combination $\omega ={\sum }_{i=1}^v{\alpha }_i{\lambda }_i$ where $v\in \mathbb{N}$ and ${\lambda }_1,\mathrm{\dots },{\lambda }_v\in \mathrm{\Lambda }$. By assumption, for all $i\in [v]$, $x$ hits the polyhedron $P({\lambda }_i)$, that is for all $i\in [v]$, $A({\lambda }_i)x\le b({\lambda }_i)$. It follows that

and $x\in P(\omega )$. This completes the proof of (i).

Let us now prove that ${\mathscr{H}}_P\left(\mathrm{\Lambda }\right)\subseteq {\mathscr{H}}_P\left(\overline{\mathrm{\Lambda }}\right)$. Let $x\in {\bigcap }_{\omega \in \mathrm{\Lambda }}P(\omega )$. Let $\omega \in \overline{\mathrm{\Lambda }}$. Then there exists a sequence ${({\lambda }_n)}_{n\in \mathbb{N}}$ of elements of $\mathrm{\Lambda }$ that converges to $\omega$. By assumption, for all $n\in \mathbb{N}$, $x$ hits the polyhedron $P({\lambda }_n)$, that is for all $n\in \mathbb{N}$, $A({\lambda }_n)x\le b({\lambda }_n)$. Since $A$ and $b$ are continuous, it comes that $A(\omega )x\le b(\omega )$, that is $x\in P(\omega )$. This completes the proof of (ii).

Let us prove ${\mathscr{H}}_P\left(\mathrm{\Lambda }\right)={\mathscr{H}}_P\left(\mathrm{ext}\left(\overline{\mathrm{conv}\mathrm{\Lambda }}\right)\right)$. A theorem of Minkowski (see [26, Chapter A, $\mathrm{\S }2.3$, Theorem 2.3.4]) asserts that if $C$ is compact, convex in a finite dimensional euclidean space, then $C$ is the convex hull of its extreme points. Hence, if $\mathrm{\Lambda }$ is bounded, $\overline{\mathrm{conv}\mathrm{\Lambda }}$ is a compact convex set in ${ℝ}^p$, and is therefore the convex hull of its extreme points. So we have:

$◀$ This has an interesting computational consequence, which is already known as a tractable instance of static robust optimization [6, Chapter 1, Corollary 1.3.5 (i)], and which we include here for completeness.

We apply Lemma 9 (i) to the set $\mathrm{\Lambda }=\mathrm{ext}(\mathrm{\Omega })$. Since $\mathrm{conv}(\mathrm{ext}(\mathrm{\Omega }))=\mathrm{\Omega }$, it comes that ${\bigcap }_{\omega \in \mathrm{ext}(\mathrm{\Omega })}P(\omega )={\bigcap }_{\omega \in \mathrm{conv}(\mathrm{ext}(\mathrm{\Omega }))}P(\omega )={\bigcap }_{\omega \in \mathrm{\Omega }}P(\omega )$. That is to say, $P(\mathrm{\Omega })$ admits a one-point hitting set if and only if the set $P(\mathrm{ext}(\mathrm{\Omega }))=\{P(\omega ):\omega \in \mathrm{ext}(\mathrm{\Omega })\}$ admits a one-point hitting set. The latter condition is equivalent to the existence of $x\in {ℝ}^d$ such that for all $\omega \in \mathrm{ext}(\mathrm{\Omega })$, $A(\omega )x\le b(\omega )$. This is equivalent to finding a feasible solution of a linear program with $d$ variables and $v\cdot m$ constraints. $◀$

Let $\lambda \in [\alpha ,\beta ]$. We can assume that $P(\lambda )$ is nonempty, as otherwise the statement is trivial. We can also assume that ${\sigma }_P(\lambda )>\lambda$, as otherwise any point $x_{\lambda }\in P(\lambda )$ satisfies the condition. Now, suppose, by contradiction, that ${\bigcap }_{t\in [\lambda ,{\sigma }_P(\lambda )]}P(t)={\mathscr{H}}_P\left([\lambda ,{\sigma }_P(\lambda )]\right)$ is empty. Since ${\sigma }_P(\lambda )>\lambda$, we have ${\mathscr{H}}_P\left([\lambda ,{\sigma }_P(\lambda ))\right)={\mathscr{H}}_P\left([\lambda ,{\sigma }_P(\lambda )]\right)$ by Lemma 9 (ii), so ${\bigcap }_{t\in [\lambda ,{\sigma }_P(\lambda ))}P(t)$ is already empty. Helly’s theorem asserts that if a (possibly infinite) family of compact convex sets in ${ℝ}^d$ has empty intersection, then some $d+1$ of them already have empty intersection. Therefore, there exist $t_1\le t_2\le \mathrm{\dots }\le t_{d+1}$ in $[\lambda ,{\sigma }_P(\lambda ))$ such that ${\bigcap }_{i=1}^{d+1}P(t_i)$ is empty. Yet, ensures that there exists $x\in {ℝ}^d$ such that $[\lambda ,t_{d+1}]\subseteq \widehat{P}(x)$. In particular, $x\in {\bigcap }_{i=1}^{d+1}P(t_i)$, a contradiction. $◀$ Let us write ${\sigma }_P^{(i)}=\underset{i\text{ times}}{\underbrace{{\sigma }_P\circ {\sigma }_P\circ \mathrm{\dots }\circ {\sigma }_P}}$. Lemma 11 yields a simple characterization of the size of hitting sets of one-parameter families of polytopes.

Suppose that ${\sigma }_P^{(k)}(\alpha )=\beta$. Let $t_0=\alpha$ and for $i=1,2,\mathrm{\dots }k$ let $t_i={\sigma }_P(t_{i-1})$. By Lemma 11, for $i=1,2,\mathrm{\dots },k$ there exists $x_i\in {ℝ}^d$ such that $\widehat{P}(x_i)\supseteq [t_{i-1},t_i]$. Since $t_k={\sigma }_P^{(k)}(\alpha )=\beta$, we have ${\bigcup }_{i=1}^k[t_{i-1},t_i]=[\alpha ,\beta ]$, and $\{x_1,x_2,\mathrm{\dots },x_k\}$ is a hitting set for $P([\alpha ,\beta ])$.