The convex hull of a quadratic constraint over a polytope
Asteroide Santana Santanu S. Dey

Finger-GAN:
Generating
Realistic
Fingerprint Images
Using
Connectivity
Imposed
GAN
    Shervin Minaee^*, AmirAli Abdolrashidi^†  

^*New York University

 ^†University of California, Riverside
 


    

=================================================================================================================


A quadratically constrained quadratic program (QCQP) is an optimization problem in which the objective function is a quadratic function and the feasible region is defined by quadratic constraints. Solving non-convex QCQP to global optimality is a well-known NP-hard problem and a traditional approach is to use convex relaxations and branch-and-bound algorithms. This paper makes a contribution in this direction by showing that the exact convex hull of a general quadratic equation intersected with any bounded polyhedron is second-order cone representable. We present a simple constructive proof of this result.




§ INTRODUCTION



A quadratically constrained quadratic program (QCQP) is an optimization problem in which the objective function is a quadratic function and the feasible region is defined by quadratic constraints. A variety of complex systems can be cast as an instance of a QCQP.  Combinatorial problems like MAXCUT <cit.>, engineering problems such as signal processing <cit.>, chemical process <cit.> and power engineering problems such as the optimal power flow <cit.> are just a few examples.

Solving non-convex QCQP to global optimality is a well-know NP-hard problem and a traditional approach is to use spacial branch-and-bound tree based algorithm. The computational success of any branch-and-bound tree based algorithm depends on the convexification scheme used at each node of the tree. Not surprisingly, there has been a lot of research on deriving strong convex relaxations for general-purpose QCQPs.  The most common relaxations found in the literature are based on Linear
programming (LP), second order cone programing (SOCP) or semi-definite programming
(SDP). Reformulation-linearization technique (RLT) <cit.> is a LP-based hierarchy, Lasserre hierarchy or the sum-of-square hierarchy <cit.> is a SDP-based hierarchy which exactly solves QCQPs under some minor technical conditions and, recently, new  LP and SOCP-based alternatives to sum of squares optimization have also been proposed <cit.>. While SDP relaxations are know to be strong, they don't always scale very well computationally. SOCP relaxations tend to be more computationally attractive, although they are often derived by further relaxing SDP relaxations <cit.>.

Another direction of research focuses on convexification of functions, with the McCormick relaxation <cit.> being perhaps the most classic example. In this case, a constraint of the form f(x) = b is replaced with f̆(x) ≤ b and f̂(x) ≥ b, where f̆ is a convex lower approximation and f̂ is a concave upper approximation of f. While there have been a lot of work in function convexification (see for instance <cit.>) it is well-known that it does not necessarily yield the convex hull of the set {x  |  f(x) = b}. To the best of our knowledge, there have been much less work on explicit convexification of sets: <cit.>. 

A related question when studying convex relaxations is that of representability of the exact convex hull of the feasible set: Is it LP,  or SDP representable? In <cit.>, we prove that the convex hull of the so-called bipartite bilinear constraint (which is a special case of a quadratic constraint) intersected with a box constraint is  representable (). The proof yields a procedure to compute this convex hull exactly. Encouraging computational results are also reported in <cit.> in terms of obtaining dual bounds using this construction, which significantly outperform SDP and McCormick relaxations and also bounds produced by commercial solvers.



§ OUR RESULT
 
For an integer t ≥ 1, we use [t] to describe the set {1, …, t}. For a set G ⊆ℝ^n, we use (G), (G) to denote the convex hull of G and the set of extreme points of G respectively.

In this paper, we generalize one of the main result in <cit.>. Specifically, we show that the convex hull of a general quadratic equation intersected with any bounded polyhedron is . Moreover the proof is constructive, therefore adding to the literature on explicit convexification in the context of QCQPs. The formal result is as following:

Let

    S: ={ x ∈ℝ^n |  x^⊤Qx + α^⊤ x = g,  x ∈ P},

where Q∈ℝ^n× n is a symmetric matrix, α∈ℝ^n, g∈ℝ and P := {x  |  Ax ≤ b} is a polytope.  Then (S) is . 

Notice that we make no assumption regarding the structure or coefficients of the quadratic equation defining S. We require P to be a bounded polyhedron, which is not very restrictive given that in global optimization the variables are often assumed to be bounded to use branch-and-bound algorithms. 

The result presented in Theorem <ref> is somewhat unexpected since the sum-of-squares approach would build a sequence of SDP relaxations for (<ref>) in order to optimize (exactly) a linear function over S, while even the SDP cone of thre-by-three dimensional matrices is not   <cit.>. Note that optimizing a linear function over S is NP-hard, therefore, while the convex hull is , the construction involves the introduction of an exponential number of variables. 

Surprisingly, the proof of Theorem <ref> is fairly straightforward and it introduces a technique (new, to the best of our knowledge) to compute convex hull of certain surfaces over a compact set. In the case of Theorem <ref>, the key observation is that the surface defined by the quadratic equation either:


  * is defined as the union of two convex surfaces (see Figure <ref>); or

  * it has the property that, through every point of the surface, there exists a straight line that is entirely contained in the surface (see Figure <ref>).






In Case 1, we can easily obtain that the convex hull of S is  as we show in Section <ref>. In Case 2, no point in the interior of the polytope can be an extreme point of S. Observing that the convex hull of a compact set is also the convex hull of its extreme points, we intersect the surface with each facet of the polytope which will contain all the extreme points of S. Now, each such intersection leads to new sets with the same form as S but in one dimension lower. The argument then goes by recursion. The details of the proof are presented in Section <ref>.

After we had proved Theorem <ref>, we learned that the property described in Case 2 is known as “ruled surfaces” and it has been extensively studied from both algebraic and geometric perspectives <cit.>. To the best of our knowledge, however, no one from the global optimization community has ever exploited such results for convexification.



§ PROOF OF THEOREM <REF>



 §.§ Convex hulls via disjunctions


In this section, we describe a simple procedure to obtain the convex hull of a compact set S using a disjunctive argument. We use this procedure to prove Theorem <ref> in Section <ref>.
Let S be a compact set and let (S) be the set of extreme points of S. First, we partition the extreme points of S. Specifically, suppose there exist B^1, …, B^k ⊆ S such that:

    S ⊇⋃_i = 1^k B^i ⊇(S).

We observe that (<ref>) implies that 

    (S) ⊇(⋃_i = 1^k B^i ) ⊇((S)) = (S),

where the last equality holds due to S being compact. Finally, we obtain that 

    (S) = (⋃_i = 1^k B^i ) = (⋃_i = 1^k (B^i) ).



If (B^i) is  for all i ∈ [k], then the set 

    (⋃_i = 1^k (B^i) ),

is  <cit.>.  Thus, we obtain from (<ref>) that (S) is . In addition, we obtain a constructive procedure to compute (S).





 §.§ Reduction

In this section, we discuss how we can apply some transformations to the set S defined in (<ref>) so as to re-write it in a “canonical” form where all the quadratic terms are squared terms. This will allows us to easily classify S into Case 1 and 2 as discussed in Section <ref>. We start with the following observation.


Let S⊆ℝ^n and let F:ℝ^n →ℝ^n be an affine map. Then 

    (F(S)) = F((S)),

where F(S):= { Fx |  x ∈ S}. 
Furthermore if (S) is , then (F(S)) is also . 

Let S be the set defined in (<ref>). Suppose, without loss of generality, that Q is a symmetric matrix. By the spectral theorem Q= V^⊤Σ V, where Σ is a diagonal matrix and the columns of V are a set of orthogonal vectors. 

Letting 
w = Vx,
we have that 

    S:= V^-1({ w |  w^⊤Σ w + α^⊤V^-1w= d,  w ∈P̃}),

where P̃ := {w   |  AV^-1w ≤ b}. 

Therefore, by Observation <ref>, it is sufficient to study the convex hull of a set of the form:

    S: ={ (x,y, z) ∈ℝ^n |  ∑_i = 1^n_qa_ix^2_i + ∑_i =1^n_qα_i x_i +∑_j =1^n_lβ_jy_j = g,  (x, y, z) ∈ P },

where z ∈ℝ^n_o does not appear in the quadratic constraints, n_q + n_l + n_o  = n, a_i ≠ 0 for i ∈ [n_q] (i.e., the rank of Q is n_q) and β_j ≠ 0 for j ∈ [n_l].  By completing squares, we may further write S as:

    S: ={ (x,y, z) ∈ℝ^n |  ∑_i = 1^n_qσ(a_i) (√(|a_i|)x_i + σ(a_i) α_i/2√(|a_i|))^2+ ∑_i =1^n_lβ_iy_i = g + ∑_i = 1^n_qα_i^2/4a_i,  (x, y, z) ∈ P},

where σ(a) denotes the sign of a. Now, since u_i = (√(|a_i|)x_i + σ(a_i) α_i/2√(|a_i|))  for i ∈ [n_q] and v_i = β_i y_i for i ∈ [n_l] define linear bijections, it follows from Observation <ref> that it is sufficient to study the convex hull of the following set:

    S: ={ (w, x,y, z) ∈ℝ^n_q+×ℝ^n_q-×ℝ^n_l×ℝ^n_o |  ∑_i = 1^n_q+w^2_i - ∑_j =1^n_q-x^2_j + ∑_k = 1^n_ly_k = g,  (w, x, y, z) ∈ P},

where we may further assume that g ≥ 0, since otherwise we may multiply the equation by -1 and apply suitable affine transformations to bring it back to the form of (<ref>). 





 §.§ Recursive argument to prove Theorem <ref>


We begin by stating a variant of Observation <ref> that we will use twice along the proof.

Let G={(x,w)∈ℝ^n_1×ℝ^n_2 |   x∈ G_0,  w=C^⊤x+h}, where G_0⊆^n_1 is bounded, and C^⊤x + h is an affine function of x. Then,

    (G) = {(x,w)∈ℝ^n_1×ℝ^n_2 |  x∈(G_0),  w=C^⊤x+h}.



See Lemma 4 in <cit.>.




  §.§.§ Dealing with low dimensional polytope

Let S and P be defined as in (<ref>).
Next, we show that we may assume without loss of generality that P is full dimension. In fact, if P is not full dimensional, then P is contained in a non-trivial affine subspace defined by a system of linear equations M x = f. Without loss of generality, we may assume that M has full row-rank k, 1≤ k<n. Let 
M = 
[ M_B M_N ] where M_B is invertible. Then, we may write this system as x_B = -M^-1_BM_Nx_N+M^-1_Bf, where x_B ∈ℝ^k,  x_N ∈ℝ^n-k and, for simplicity, we assume that x_B (resp. x_N) correspond to the first k (resp. last n-k) components of x. By defining C=-M^-1_BM_N and h = M^-1_Bf to simplify notation, we obtain

    x_B = Cx_N+h.
 
By partitioning Q in sub-matrices of appropriate sizes, we  may explicitly write the quadratic equation defining S in terms of x_B and x_N as follows:

    [ x_B^⊤ x_N^⊤ ][ Q_BB Q_BN; Q_NB Q_NN ][ x_B; x_N ]
    + α^⊤[ x_B; x_N ] = g.

Using (<ref>), we replace x_B in (<ref>) to obtain

    x_N^⊤Q̃x_N + α̃^⊤ x_N = g̃,

where 

    Q̃   = C^⊤Q_BBC + C^⊤Q_BN + Q_NBC + Q_NN,
    α̃   = 2C^⊤Q_BBh + Q_BN^⊤h + Q_NBh + C^⊤α_B + α_N,
    g̃   = g - h^⊤Q_BBh - α_B^⊤h.

Therefore, we may write S as

    S: ={ (x_B,x_N) ∈ℝ^n |  x_N^⊤Q̃x_N + α̃^⊤ x_N = g̃,  x_N ∈P̃,  x_B = Cx_N+h},

where P̃ is now a full dimensional polytope. Therefore, by Lemma <ref>, we may assume from now on that P is full dimensional.



  §.§.§ Case 2: Sufficient conditions for points to not be extreme



Consider the set S as defined in (<ref>).

Suppose n_o≥ 1. If (a, b, c, d) ∈ S ∩ ( ℝ^n_q+×ℝ^n_q-×ℝ^n_l×ℝ^n_o) where (a, b, c, d) ∈(P), then (a, b, c, d) is not an extreme point of S.
 

Since (a, b, c, d) ∈(P), there exists a vector δ∈ℝ^n_o∖{0} such that (a,b,c,d + δ), (a,b,c,d - δ) ∈ P. Clearly these points are in S as well and, therefore, (a, b, c, d) is not an extreme point of S

	

Suppose n_o  = 0 and n_l ≥ 2. If (a, b, c) ∈ S ∩ ( ℝ^n_q+×ℝ^n_q-×ℝ^n_l) where (a, b, c) ∈(P), then (a, b, c) is not an extreme point of S.


Since n_l ≥ 2, (a,b,c_1 ±λ, c_2 ∓λ, …, c_n_3) are feasible for sufficiently small positive values of λ. Therefore, (a, b, c) is not an extreme point.



Suppose n_o = 0, n_q+, n_q-≥ 1 and n_l =1. If (a, b, c) ∈ S ∩ ( ℝ^n_q+×ℝ^n_q-×ℝ^n_l) where (a, b, c) ∈(P), then (a, b, c) is not an extreme point of S.


Since n_q+, n_q-≥ 1, and n_l =1, (a_1 + λ, a_2, …, a_n_q+, b_1 + λ, b_2, …, b_n_q-, c + 2λ(-a_1 + b_1) are feasible for sufficiently small positive and negative values of λ. Therefore, (a, b, c) is not an extreme point.


 
Suppose n_o = 0, n_q+≥ 2, n_q-≥ 1 and n_l=0. If (a, b) ∈ S ∩ ( ℝ^n_q+×ℝ^n_q- ) where (a, b) ∈(P), then (a, b) is not an extreme point of S.

 We show that there exists a straight line through (a,b) that is entirely contained in the surface defined by the quadratic equation. More specifically, we prove that there exists a vector (u,v) ∈ (ℝ^n_q+×ℝ^n_q-)∖{0} such that the line {(a,b) + λ (u,v) | λ∈ℝ} satisfies the quadratic equation and therefore, (a, b) being in the interior of P cannot be an extreme point of S.  
We consider two cases:


  * (a,b) ≠0: Then observe that a ≠0, since otherwise we would have a = 0 and b = 0, because g≥ 0. 

Observe that 

    ∑_i =1^n_q+a_i^2 = g + ∑_j = 1^n_q- b_j^2 ≥ b_1^2 ⇔|b_1|/a_2≤ 1.

Next, observe that:

    g    =   ∑_i = 1^n_q+( a_i + λ u_i)^2 -∑_i = 1^n_q-(b_i + λ v_i)^2  ∀λ∈ℝ
    ⇔  g     =    ( ∑_i = 1^n_q+a_i^2 -  ∑_i = 1^n_q-b_i^2 ) + λ^2 ( ∑_i = 1^n_q+u_i^2 -  ∑_i = 1^n_q-v_i^2 ) + 2λ(∑_i = 1^n_q+a_iu_i -  ∑_i = 1^n_q-b_iv_i )  ∀λ∈ℝ
    ⇔  0     =    λ(  ∑_i = 1^n_q+u_i^2 -  ∑_i = 1^n_q-v_i^2 ) + 2(∑_i = 1^n_q+a_iu_i -  ∑_i = 1^n_q-b_iv_i )  ∀λ∈ℝ
    ⇔      ∑_i = 1^n_q+u_i^2 -  ∑_i = 1^n_q-v_i^2 = 0,  ∑_i = 1^n_q+a_iu_i -  ∑_i = 1^n_q-b_iv_i =0.

Suppose we set v_1 = 1 and v_j =0 for all j ∈{2,…,n_q-}. Then satisfying (<ref>) is equivalent to finding real values of u satisfying:

    ∑_i = 1^n_q+u_i^2  =1,  ∑_i = 1^n_q+a_iu_i  = b_1.

This is the intersection of a circle of radius 1 in dimension two or higher (since n_q+≥ 2 in this case) and a hyperplane whose distance from the orgin is |b_1|/a_2. Since, by (<ref>), we have that this distance is at most 1, the hyperplane intersects the circle and therefore we know that a real solution exists. 

  * (a,b) = 0: In this case, observe that g = 0 and then 0 is a convex combination of

    ( ±λ, 0, …, 0_ n_q+, ±λ, 0, …, 0_ n_q-)
  for sufficiently small λ > 0.





  §.§.§ Case 1: Sufficient conditions for convex hull to be 


In this section, we repeatedly use the following result from <cit.>.

Let G ⊆ℝ^n be a convex set and let f: ℝ^n →ℝ be a continuous function.  Then 

    ({G ∩{x |  f(x) = 0}}) = ({G ∩{x |  f(x) ≤ 0}}) ∩({G ∩{x |  f(x) ≥ 0}}).



For the two lemmas that follows, consider the notation of S defined in (<ref>).
 
Suppose n_o = 0, n_l ≤ 1. If n_q+ = 0 or n_q- = 0, then (S) is .



We consider two cases.


  * n_q- = 0: Let (w, y)  ∈ S ∩ ( ℝ^n_q+×ℝ^n_l). Let y = y_1 if n_l=1 and y = 0 if n_l = 0. In this case, g - y is non-negative for all feasible values of y and we can use the identity t = (t+1)^2 - (t-1)^2/4 to write S = S' ∩ S”, where:

    S':= {(w,y) ∈ P | 2w_1, …, 2w_n_q+, (g - y - 1)≤ (g - y + 1)},
    
    S”:= {(w,y) ∈ P  | 2w_1, …, 2w_n_q+, (g - y - 1)≥ (g - y + 1)}.

Notice that S' is a  convex set. Also notice that S” is a reverse convex set intersected with a polytope and hence (S”∩ P) is polyhedral and contained in P (see <cit.>,Theorem 1). Therefore, by Theorem <ref>, we have that (S) = (S')∩(S”) is .


  * n_q+ = 0: Let (x, y)  ∈ S ∩ ( ℝ^n_q+×ℝ^n_l). Let y = y_1 if n_l=1 and y = 0 if n_l = 0. In this case, g - y is non-positive for all feasible values of y and may write S = S' ∩ S”, where:

    S':= {(x,y) ∈ P  | 2x_1, …, 2x_n_q-, (y - g - 1)≤ (y - g + 1)},
    
    S”:= {(x,y) ∈ P  | 2x_1, …, 2x_n_q-, (y - g - 1)≥ (y - g + 1).}

Therefore, as in the previous case,
(S) is .





Suppose n_q+≤ 1 and n_l = n_o =0. Then (S) is . 


If n_q+=0, then S is empty set or contains a single point, the origin. 

Therefore, consider the case where n_q+ = 1, thus w=w_1. 

Notice that S = S' ∩ S”, where

    S':= {(w,x) ∈ℝ^1×ℝ^n_q- |  w^2 ≥ g+∑_j=1^n_q-x_j^2,   (w,x) ∈ P},
    
    S”:= {(w,x) ∈ℝ^1×ℝ^n_q- |  w^2 ≤ g+∑_j=1^n_q-x_j^2,  (w,x) ∈ P}.

By Theorem <ref>, (S) = (S') ∩(S”). Next, we show that both (S') and (S”) are .
Notice that S' is the union of the following two  sets:

    S'_+   := { (w,x) ∈ℝ^1×ℝ^n_q- |  w ≥(g+∑_j=1^n_q-x_j^2)^1/2,  w ≥ 0,  (w,x) ∈ P},
       =Proj_w,x({(w,x,t) ∈ℝ^1×ℝ^n_q-×ℝ |  w ≥((√(g)t)^2+∑_j=1^n_q-x_j^2)^1/2,  x ≥ 0,  t = 1,  (w,x) ∈ P }),
    
    S'_-   := {(w,x) ∈ℝ^1×ℝ^n_q- |  -w ≥(g+∑_j=1^n_q-x_j^2)^1/2,  w ≤ 0,  (w,x) ∈ P}
       = Proj_w,x({(w,x,t) ∈ℝ^1×ℝ^n_q-×ℝ |  -w ≥(√(g)t)^2+∑_j=1^n_q-x_j^2)^1/2,  w ≤ 0,  t=1,  (w,x) ∈ P}).

Thus, (S') = (S'_+ ∪ S'_-) is . 

Notice that S” = {(w,x) ∈ℝ^1×ℝ^n_q- |  |w| ≤ (g+∑_j=1^n_q-x_j^2)^1/2,  (w,x) ∈ P} and is therefore the union of two sets:

    S”_+   := { (w,x) ∈ℝ^1×ℝ^n_q- |  w ≤(g+∑_j=1^n_q-x_j^2)^1/2,  w ≥ 0,  (w,x) ∈ P},
    
    S”_-   := {(w,x) ∈ℝ^1×ℝ^n_q- |  -w ≤(g+∑_j=1^n_q-x_j^2)^1/2,  w ≤ 0,  (w,x) ∈ P},

each of them being a reverse convex set intersected with a polyhedron. Therefore, (S”_+) and (S”_-) are polyhedral and therefore
(S”) =((S”_+) ∪(S”_-)) is a polyhedral set.



  §.§.§ Proof of Theorem <ref>


Finally, we bring the pieces together to prove Theorem <ref>. 
(of Theorem <ref>)
Let S(n) be defined as in (<ref>), where n=n_q+ + n_q- + n_l + n_o is the dimension of the space in which S is defined and without loss of generality P is full-dimensional (Section <ref>). The proof goes by induction on n.  Notice that S(1) is a polytope and hence (S(1)) is . Suppose S(n) is . We show that S(n+1) is  as well. If n_o = 0, n_l≤ 1, and n_q+ =0 or n_q-=0, then the result follows from Lemma <ref>. Similarly, if n_o = 0, n_q+≤ 1 and n_l=0, then the result follows from Lemma <ref>. Otherwise, it follows from Lemma <ref>, <ref>, <ref> and <ref> that no point in the interior of P can be an extreme point of S(n+1). Let N be the number of facets of P, each of which given by one equation of the linear system Fx = f. Let B^i = S(n+1) ∩{x∈ℝ^n+1 |  F_i.x = f_i} be the intersection of S(n+1) with the ith facet of P. By the discussion in Section <ref>, it is enough to show that the convex hull of each B^i is . Let i∈{1,…,N}. Choose j_0 such that F_ij_0≠ 0. For simplicity, suppose j_0 = 1. Then, we may write B^i = {x∈ℝ^n+1 |  (x_2,…,n_n+1)∈ B^i_0,  x_1 = b_i - ∑_j=2^n+1F_ijx_j}, where B_0^i is obtained from B^i by replacing x_1 = f_i - ∑_j=2^n+1F_ijx_j in all the constraints defining S(n+1). Now (B_0^i) ⊆ℝ^n is  by induction hyptothesis. Therefore, (B^i) is  by Lemma <ref>.




















§ ACKNOWLEDGMENTS


Funding: This work was supported by the NSF CMMI [grant number 1562578] and the CNPq-Brazil [grant number 248941/2013-5].


plain




