Sol3 PDF

Preview

Summary

sol...

Description

Analysis of Algorithms CS 6820, Fall 2017

Solution Set 3

(1) This exercise completes the description of a polynomial-time algorithm for linear programming, given a separation oracle. The problem is defined as follows: for a polyhedron P = {x 2 Rn | Ax  b}, determine whether P is empty and, if it is non-empty, output a point x 2 P . (This is called the LP feasibility problem; recall that in class we saw a reduction from linear programming with a maximization or minimization objective to LP feasibility.) In the LP feasibility problem it is assumed that the matrix A and the vector b have integer entries; let U denote the absolute value of the largest such entry. It is also assumed that the input to the LP feasibility problem specifies this value U (in binary) and that we are given (or can implement, based on the information given in the input) a separation oracle which can answer queries of the following form: given a vector x 2 Rn , determine whether Ax  b, and if not, output a row of the matrix A, denoted by a|j , such that aj| x > bj . Calls to the separation oracle are assumed to run in time poly(n log U ). The analysis of the ellipsoid method given in class demonstrated the following fact, which you may use in this exercise without proof: for the special case of LP feasibility in which we are given a promise that P is contained in the hypercube [0, R]n , and that it is either empty or has volume greater than , there is an algorithm that solves the problem in O(n2 log(R)  n log()) iterations, where each iteration runs in time poly(n log U ). (1a) Prove the following lemma, which will be useful in later parts of this exercise. If T is an invertible n⇥n matrix with integer entries belonging to [U, U ], then the absolute value of every entry of the matrix T 1 is bounded above by (nU )n , and the absolute value of every non-zero entry of T 1 is bounded below by (nU )n . Solution: Cramer’s Rule expresses each entry of T 1 as the ratio between two determinants: the numerator is (up to sign) the determinant of an (n  1) ⇥ (n  1) submatrix of T obtained by deleting one row and one column, whereas the denominator is the determinant of T . Both the numerator and the denominator determinant can be expressed as sums of n! or fewer terms, each of which is a product of at most n integers in the range [U, U]. Thus, both the numerator and the denominator are integers of absolute value (n!)U n or smaller. Since (n!)U n < (nU )n , the result follows. (1b) Give a polynomial-time reduction from the general case of LP feasibility to the special case in which P ✓ Rn+ . (Your reduction is allowed to change the problem dimension. For example you could 2 reduce LP feasibility in Rn to LP feasibility in Rn+ .) Solution: Every vector x 2 Rn can bee xpressed as the difference of two vectors in Rn+ . Hence, the feasibility problem {Ax  b} is equivalent to the feasibility problem {A(y  z)  b, y, z ⌫ 0}. The set of vector pairs (y, z) satisfying this latter system of inequalities is a subset of R2n + , as desired. (1c) Find a function R = R(n, U ) such that log(R)  poly(n log U ), and for every instance of LP feasibility with P ✓ Rn+ , the polyhedron P is non-empty if and only if P \ [0, R]n is non-empty. Solution: The function R(n, U ) = (nU )n+1 has this property. To see why, first note that if P is empty then P \ [0, R]n is clearly empty. So we really only need to worry about the case when P is non-empty. If so, then we claim that the polyhedron P must have a vertex, i.e. a point where the set of linear constraints which are “tight” has a unique solution. To reason more precisely about this situation, we need to introduce some notation. Denote the rows

of the constraint matrix A by a1| , a|2 , . . . , a|m . Among all the vectors that satisfy Ax  b, let x⇤ be one which maximizes the cardinality of the set of tight constraints, I(x) = {i 2 [m] | a|i x = bi }. Claim. The set of vectors {ai | i 2 I(x⇤ )} contains a basis of Rn . Proof. Assume by way of contradiction that {ai | i 2 I(x⇤ )} spans a proper linear subspace of Rn and let y denote any non-zero vector in the orthogonal complement of this subspace. If x is any vector in the line L = {x⇤ + ty | t 2 R} and i 2 I(x⇤ ) then a|i x = ai|x⇤ + t(a|i y) = bi hence I(x) ◆ I(x⇤ ). Consider the function (x) = max{aj| x  bj | 1  j  m, j 62 I(x⇤ )}. Note that (x)  0 if and only if x 2 P , and that (x⇤ ) < 0 by the definiton of I(x⇤ ). Since P ✓ Rn+ and n no line is a subset of R+ , we know that there exists a point of L where  attains a strictly positive value. By the intermediate value theorem and the continuity of , there must also be some x 2 L such that (x) = 0. This implies that for some j 62 I(x⇤ ) we have a|j x = bj , or equivalently j 2 I(x). Recalling that I(x) ◆ I(x⇤ ) for every x 2 L, we conclude that I(x) is a strict superset of I(x⇤ ), contradicting our choice of x⇤ . Now let J (x⇤ ) denote a subset of I(x⇤ ) that constitutes a basis for Rn . Let T denote the submatrix of A consisting of the rows indexed by J (x⇤ ) and let b0 denote the subvector of b consisting of the rows indexed by J (x⇤ ). The equation T x ⇤ = b0 implies that x⇤ = T 1 b0 . The entries of T 1 are bounded above by (nU )n in absolute value, and the entries of b0 are bounded above by U , so each entry of T 1 b0 is bounded by n · (nU )n · U = (nU )n+1 in absolute value. Thus, x⇤ 2 P \ [0, R]n when R = (nU )n+1 , as desired. (1d) Find a function ✏ = ✏(n, U ) such that log(1/✏)  poly(n log U ), and for every instance of LP feasibility, the polyhedron P = {x | Ax  b} is non-empty if and only if the polyhedron P✏ = {x | Ax  b + ✏1} is non-empty, where 1 denotes the vector whose components are all equal to 1. Prove that if P is non-empty, then the volume of P✏ is bounded below by  = (n, U ), where the function (n, U ) satisfies log(1/)  poly(n log U ). Solution: Let ✏ = 12 (nU )2(n+1) . The inclusion P ✓ P✏ implies that if P is non-empty, then so is P✏ . To prove the converse, assume P✏ is non-empty, and assume without loss of generality that P✏ \ Rn+ is non-empty. (If not, modify the coordinate system by applying a sign-flip in certain dimensions. This change of coordinates flips the signs of certain entries of the constraint matrix A but doesn’t affect the fact that the entries of A are integers in the range [U, U ].) The system of linear inequalities defining the polyhedron P✏ \ Rn+ can be written as ✓ ◆ ◆ ✓ A b + ✏1 x  0 I where the matrix on the left is obtained by stacking A on top of the negative identity matrix, and the vector on the right is obtained by stacking b + ✏1 on top of the n-dimensional zero vector. Let us refer to this stacked vector henceforth as b✏ , and let b0 denote the version of b✏ obtained by setting ✏ = 0, i.e. the vector consisting of b stacked on top of the n-dimensional zero vector. As in part (1c) above, the non-empty polyhedron P✏ \ Rn+ must have a vertex of the form x✏⇤ = T 1 b0✏ where T is an invertible matrix with integer entries in the range [U, U] and b0✏ is an n-dimensional

subvector of b✏ . Let b00 denote the corresponding subvector of b0 and let x⇤ = T 1 b00 . We claim that x⇤ 2 P . To see this, note first that x⇤  x⇤✏ = T 1 (b00  b✏0 ). Every entry of T 1 is bounded by (nU )n in absolute value, and every entry of b00 b0✏ is bounded by ✏ is absolutely value, so kx⇤ x⇤✏ k1  n·(nU )n ·✏. The row sums of A are bounded by nU in absolute value, so kA(x⇤  x✏⇤)k1  n · (nU )n+1 · ✏. Combined with the fact that Ax⇤✏  b + ✏1, this implies Ax⇤  b  (n · (nU )n+1 + 1)✏1  (nU )n 1

(1)

where the second inequality follows by our choice of ✏. Now, A is an integer matrix, b is an integer vector, and every entry of the vector x⇤ is an integer multiple of det(T )1 . Hence, every entry of the vector Ax⇤  b is an integer multiple of det(T )1 . If one of these entries exceeds 0, then it must do so by at least det(T )1 , which is stictly greater than (nU )n as was observed in part (1a). Therefore, from inequality (1) we may deduce the stronger inequality Ax⇤  b  0, which implies that x⇤ 2 P and P is non-empty. To complete this part of the exercise we need to compute a lower bound on the volume of P✏ , in the event that P is non-empty. If x⇤ 2 P and kx  x⇤ k1  ✏/U then kA(x  x⇤ )k1  ✏ because every entry of A is bounded in absolute value by U . Consequently, Ax  Ax⇤ + ✏1  b + ✏1 for every such x, which means that P✏ contains the L1 ball of radius ✏/U around x⇤ . The volume of this ball is (2✏/U )n /n!, so that is a lower bound on the volume of P✏ . Note that if (n, U ) = (2✏/U )n /n! then, by our choice of ✏ = ✏(n, U ) = 12 (nU )2(n+1) we have 1

log as desired.

 1 

 (nU )(2n+3)n · n! < (2n2 + 3n) log(nU ) + n log(n)

(1e) With ✏ and P✏ defined as in part (1d), give a polynomial-time algorithm that takes a separation oracle for P and a vector x✏ 2 P✏ , determines whether x✏ 2 P , and in the event that x✏ 62 P , outputs an equation of the form ai|x = bi such that P \ {x 2 Rn | a|i x = bi } is non-empty. Solution: Given x 2 P✏ , we call the separation oracle for P . If it reports that x 2 P then we are done. Otherwise, it reports a violated constraint of the form a|i x✏ > bi . In that case, our algorithm outputs the quation ai|x = bi . Below, we prove the correctness of this algorithm by showing that, in the event that ai|x✏ > b i , the set P \ {x | a|i x = bi } must be non-empty. | ˆ✏ be a vertex of this polyhedron. Consider the non-empty polyhedron P✏ \ {x | a|i x = ai x✏ } and let x Defining b✏ and b0 as in the solution to (1d), we may reason as in the solution to (1d) that there is a valid equation of the form x ˆ✏ = T 1ˆb0 where T is an invertible submatrix of A, ˆb is an (m + n)-dimensional vector satisfying b0  ˆb  b✏ , and bˆ0 is an n-dimensional subvector of ˆb. Let b00 denote the corresponding n-dimensional subvector of b0 and let x⇤ = T 1 b00 . Continuing to reason as in the solution to (1d), we derive the inequalities

kA(x⇤  x ˆ✏ )k1  n · (nU )n+1 · ✏   (Ax⇤  b)  (Aˆ x✏  ˆb)1  (n · (nU )n+1 + 1) · ✏  (nU )n .

(2) (3)

Reasoning as in part (1d), if any coordinate of the vector Ax⇤  b is a positive number, then it must be strictly greater than (nU )n , which would contradict (3). Hence Ax⇤  b  0 and x⇤ 2 P . In addition, ˆ✏  ˆbi = 0, equation (3) implies that |a|i x⇤  bi | cannot be greater than (nU )n . Since |ai|x⇤  bi | since a|i x is an integer multiple of det(T )1 , and det(T )1 > (nU )n , we may conclude that a|i x⇤  bi = 0. Hence, x⇤ belongs to the set P \ {x | a|i x = bi } which confirms that the set is non-empty.

(1f ) Using the ellipsoid algorithm in conjunction with the algorithm in part (1e), describe a polynomialtime algorithm for LP feasibility. Solution: The following was the intended solution for this part. It contains a subtle bug indicated by [⇤], and I will explain how to correct the bug later. Set R = R(n, U ), ✏ = ✏(n, U ),  = (n, U ) as defined in earlier parts of this solution. Using the transformations described in parts (1b), (1c), we can assume without loss of generality that P ✓ [0, R]n . The (1b) transformation is justified because if the linear program defining P has a solution x, then the linear program constructed in part (1b) will have a solution (y, z), and a solution x of the original LP can be found by simply forming the vector difference y  z. Conversely, if the linear program constructed in (1b) has no solution, then the original linear program also has no solution. The (1c) transformation is justified because if we find a vector x 2 P \ [0, R]n then x 2 P , and if we find no vector x 2 P \ [0, R]n then part (1c) shows that P is empty. Having reduced to the case P ✓ [0, R]n , the algorithm uses the ellipsoid method either to find a point x✏ 2 P✏ or to conclude that the volume of P✏ is less than (n, U ). In the latter case, we conclude that P✏ (and hence P ) is empty, and we terminate. In the former case, we call the separation oracle to test whether x✏ 2 P. If so, we output x✏ and terminate. Otherwise, using part (1e), we identify an equation a|i x = bi whose solution set is guaranteed to intersect P in the event that P is non-empty. This means that to solve the original LP feasibility problem, it suffices to solve the feasibility problem {Ax  b, ai|x = bi }. Any x satisfying the latter problem also satisfies the original one, and if there is no x satisfying the latter problem then the original one also has no solutions. | To solve {Ax  b, ai|x = bi } we use the equation a i x = bi to eliminate one of the variables, resulting in a linear program with n  1 variables. In more detail, we use the equation a|i x = bi to write one of the variables xj as a linear function of the other ones. (For example, in the equation a1 x1 + a2 x2 = b, if a2 6= 0 then we can rewrite the equation as x2 = (b/a2 )  (a1 /a2 )x1 .) We substitute this expression in place of the eliminated variable wherever it occurs, to obtain a new linear program in n  1 variables, which we solve by applying the same algorithm [⇤].

Thus, to solve a linear program with n variables we need to run the ellipsoid algorithm at most n times. Each of the runs takes O(n2 log(R)  n log()) iterations, where an iteration consists of calling the separation oracle and then performing a change of basis. Recalling that log(R) = (n + 1) log(nU ) and log(1/)  n(2n + 3) log(nU ) + n log(n) we find that every run of the ellipsoid algorithm takes O(n3 log(nU )) iterations, and the n runs of ellipsoid in total take O(n4 log(nU )) iterations. As noted at the start of this solution, the [⇤] above indicates the location of a subtle bug. When we eliminate one variable using the equation a|i x = bi , we express that variable as a linear function of the other variables with rational coefficients, not with integer coefficients. When we substitute that expression for every occurrence of the eliminated variable, we obtain a linear program with rational coefficients. To recursively apply the same algorithm, we would multiply all coefficients by a common denominator to make them integers again. This results in a linear program whose coefficients are bounded by U 2 in absolute value. After n iterations of this process, it would seem that the only upper n bound we can guarantee on the integer coefficients of the LP is U 2 , whose logarithm, 2n log(U ), is not polynomial in the original input size. To fix the bug, we need a more careful analysis of the process of eliminating variables, to ensure that the rational coefficients of the resulting LP continue to have small denominators even after a large number of variables have been eliminated. For this reason, we will keep a list (initially empty) of inequalities in the original LP that have been “made into equations” during the execution of our algorithm. In a stage of the algorithm that starts with k > 0 equations in the list, we will eliminate k variables to obtain a linear program LPk in n  k variables with integer coefficients, along with a function mapping each constraint of LPk to a constraint of the original linear program LP0 . In the following paragraph we will

∆

show that the coefficients of LPk are bounded by Uk = k!U k+1 in absolute value. Let LPk0 denote LPk with the right-hand side of each constraint relaxed by ✏k = ✏(n, Uk ). We will apply the ellipsoid method to LPk0 with one of the following three outcomes. ∆

• We conclude that the solution set of LP k0 has volume less than k = (n, Uk ), which implies using part (1d) that LPk0 is infeasible and, consequently, LP0 is infeasible as well. • We find a vector x(k) 2 Rnk which is feasible for LPk . This gives us n  k coordinates of a feasible vector x⇤ for LP0 . We fill in the remaining k coordinates of x⇤ using the linear functions that express these k coordinates in terms of the n  k remaining coordinates. Such a k-tuple of linear functions was discovered when eliminating the k variables. • We find that one of the defining inequalities of LPk can be made into an equation without affecting its feasibility. We look up the corresponding inequality of LP0 and add it to our list of equations. Running the ellipsoid method for LP 0k takes O(n2 log R(n, Uk )  n log(k )) = O(n3 k log(nU )) iterations. Summing over k = 1, . . . , n the total number of iterations is O(n5 log(nU )). Finally, we need to justify that Uk  k!U k+1 . If a stage of the algorithm starts with a list of k inequalities from the linear program Ax  b that have been made into equations, these correspond to a linear system Ak x = bk where the matrix Ak comprises k linearly independent rows of the original constraint matrix A. Rearranging columns of Ak if necessary so that the k rightmost columns are linearly independent, we may write Ak = (S T ) where S is k-by-(n  k) and T is k -by-k and invertible. Writing the vector x of formal variables as the concatenation of x0 (comprising the first n  k variables) and x00 (comparising the last k) the linear system Ak x = bk may be written as ✓ 0 ◆ x (S T ) = Sx0 + T x 00 = bk x00   x00 = T 1 bk  Sx0 This shows that each variable in the vector x00 can be expressed as a linear function of variables in the vector x0 where the coefficients of the linear function are rational numbers with numerator bounded by k!U k and denominator det(T ). We substitute these expressions wherever the variables of x00 occur in LP0 , to obtain a linear program in the n  k variables comprising the vector x0 . After doing this substitution, it is possible that cancellations of coefficients lead to the presence of “degenerate inequalities” in the linear program, such as 0  1 or 0  1, whose left and right sides are simply scalars, not linear functions of the variables in x0 . If any of the degenerate inequalities is false (e.g., 0  1) then we conclude that the linear program is infeasible. Otherwise, we discard the degenerate inqualities and let LPk denote the linear program specified by the remaining inequalities. (Discarding degenerate inequalities ensures that if we make add one of the remaining inequalities of LPk into our list of “tight constraints”, it is linaerly independent of the tight constraints we have already included in that list.) Each of the inequalities in LPk is obtained by taking an inequality in LP0 (which has integer coefficients bounded by U ) and replacing occurrences of variables in x00 with linear functions of the variables in x0 whose coefficients are rational numbers with numerator bounded by k!U k+1 and denominator det(T ). When we multiply all inequalities of the LP by det(T ) so that they have integer coefficients, those coefficients will be at most k!U k+1 , as desired.

(2) It turns out there is a very fast randomized algorithm to solve linear programs when the number of variables, n, is a small constant. Suppose the linear program is: max

cT x

s.t.

Ax  b

(4) The algorithm permutes the m constraints in random order, and it iteratively solves the linear program LPi defined by the first i constraints, for i = 1, . . . , m. If x(i1) is the optimum solution of LPi1 , then when the ith constraint aT i x  bi is introduced, the algorithm does one of two things: 1. If aTi x(i1)  bi then x(i1) is still optimal; set x(i) = x(i1) . 2. If aTi x(i1) > bi then the new optimum, x(i) , must satisfy the linear equation aTi x(i) = bi . Use this equation to eliminate one of the n variables, expressing it as a linear function of the remaining n  1 variables. Substitute this expression to rewrite LPi as a linear program in n  1 variables; recursively solve this LP to find the optimum point, x(i) . (a) Complete the description of the algorithm by describing how to deal with the case that LPi is unbounded. (In other words, the solution set of the first i constraints is an unbounded subset of Rn and the objective function attains unboundedly large values on this set, meaning that x(i) is undefined.) Solution: The most direct solution uses the ordered field F = R[✏] defined in Section 1.1 of the lecture notes on the simplex method. There are other ways to solve the problem that a...