Ee364a Homework 3 Solutions Designed

Unformatted text preview: f is not convex or quasiconvex. 4.1 Consider the optimization problem minimize f ( x 1 , x 2 ) subject to 2 x 1 + x 2 ≥ 1 x 1 + 3 x 2 ≥ 1 x 1 ≥ , x 2 ≥ . Make a sketch of the feasible set. For each of the following objective functions, give the optimal set and the optimal value. (a) f ( x 1 , x 2 ) = x 1 + x 2 . 4 (b) f ( x 1 , x 2 ) = − x 1 − x 2 . (c) f ( x 1 , x 2 ) = x 1 . (d) f ( x 1 , x 2 ) = max { x 1 , x 2 } . (e) f ( x 1 , x 2 ) = x 2 1 + 9 x 2 2 . Solution. The feasible set is shown in the figure. x 1 x 2 (1 , 0) (2 / 5 , 1 / 5) (0 , 1) (a) x ⋆ = (2 / 5 , 1 / 5). (b) Unbounded below. (c) X opt = { (0 , x 2 ) | x 2 ≥ 1 } . (d) x ⋆ = (1 / 3 , 1 / 3). (e) x ⋆ = (1 / 2 , 1 / 6). This is optimal because it satisfies 2 x 1 + x 2 = 7 / 6 > 1, x 1 +3 x 2 = 1, and ∇ f ( x ⋆ ) = (1 , 3) is perpendicular to the line x 1 + 3 x 2 = 1. A1.7 Dual cones in R 2 . Describe the dual cone for each of the following cones. (a) K = { } . (b) K = R 2 . (c) K = { ( x 1 , x 2 ) | | x 1 | ≤ x 2 } . (d) K = { ( x 1 , x 2 ) | x 1 + x 2 = 0 } . Solution. (a) K ∗ = R 2 . To see this: K ∗ = { y | y T x ≥ 0 for all x ∈ K } = { y | y T ≥ } = R 2 . 5 (b) K ∗ = { } . To see this, we need to identify the values of y ∈ R 2 for which y T x ≥ for all x ∈ R 2 . But given any y negationslash = 0, consider the choice x = − y , for which we have y T x = −bardbl y bardbl 2 2 < 0. So the only possible choice is y = 0 (which indeed satisfies y T x ≥ 0 for all x ∈ R 2 ). (c) K ∗ = K . (This cone is self-dual.) (d) K ∗ = { ( x 1 , x 2 ) | x 1 − x 2 = 0 } . Here K is a line, and K ∗ is the line orthogonal to it. A2.2 A general vector composition rule. Suppose f ( x ) = h ( g 1 ( x ) , g 2 ( x ) , . . . , g k ( x )) where h : R k → R is convex, and g i : R n → R . Suppose that for each i , one of the following holds: • h is nondecreasing in the i th argument, and g i is convex • h is nonincreasing in the i th argument, and g i is concave • g i is affine. Show that f is convex. (This composition rule subsumes all the ones given in the book, and is the one used in software systems such as CVX.) You can assume that dom h = R k ; the result also holds in the general case when the monotonicity conditions listed above are imposed on ˜ h , the extended-valued extension of h . Solution. Fix x , y , and θ ∈ [0 , 1], and let z = θx + (1 − θ ) y . Let’s re-arrange the indexes so that g i is affine for i = 1 , . . . , p , g i is convex for i = p + 1 , . . . , q , and g i is concave for i = q + 1 , . . . , k . Therefore we have g i ( z ) = θg i ( x ) + (1 − θ ) g i ( y ) , i = 1 , . . . , p, g i ( z ) ≤ θg i ( x ) + (1 − θ ) g i...
View Full Document

Unformatted text preview: EE364a, Winter 2014-15 Prof. S. Boyd EE364a Homework 6 solutions 8.16 Maximum volume rectangle inside a polyhedron. Formulate the following problem as a convex optimization problem. Find the rectangle R = { x ∈ R n | l ± x ± u } of maximum volume, enclosed in a polyhedron P = { x | Ax ± b } . The variables are l,u ∈ R n . Your formulation should not involve an exponential number of constraints. Solution. A straightforward, but very inefficient, way to express the constraint R ⊆ P is to use the set of m 2 n inequalities Av i ± b , where v i are the (2 n ) corners of R . (If the corners of a box lie inside a polyhedron, then the box does.) Fortunately it is possible to express the constraint in a far more efficient way. Define a + ij = max { a ij , } , a-ij = max {-a ij , } . Then we have R ⊆ P if and only if n X j =1 ( a + ij u j-a-ij l j ) ≤ b i , i = 1 ,...,m, The maximum volume rectangle is the solution of maximize ( Q n i =1 ( u i-l i )) 1 /n subject to ∑ n j =1 ( a + ij u j-a-ij l j ) ≤ b i , i = 1 ,...,m, with implicit constraint u ² l . Another formulation can be found by taking the log of the objective, which yields maximize ∑ n i =1 log( u i-l i ) subject to ∑ n j =1 ( a + ij u j-a-ij l j ) ≤ b i , i = 1 ,...,m. A3.28 Probability bounds. Consider random variables X 1 ,X 2 ,X 3 ,X 4 that take values in { , 1 } . We are given the following marginal and conditional probabilities: prob ( X 1 = 1) = 0 . 9 , prob ( X 2 = 1) = 0 . 9 , prob ( X 3 = 1) = 0 . 1 , prob ( X 1 = 1 ,X 4 = 0 | X 3 = 1) = 0 . 7 , prob ( X 4 = 1 | X 2 = 1 ,X 3 = 0) = 0 . 6 . 1 Explain how to find the minimum and maximum possible values of prob ( X 4 = 1), over all (joint) probability distributions consistent with the given data. Find these values and report them. Hints. (You should feel free to ignore these hints.) • Matlab: – CVX supports multidimensional arrays; for example, variable p(2,2,2,2) declares a 4-dimensional array of variables, with each of the four indices taking the values 1 or 2. – The function sum(p,i) sums a multidimensional array p along the i th index. – The expression sum(a(:)) gives the sum of all entries of a multidimensional array a . You might want to use the function definition sum_all = @(A) sum( A(:)); , so sum_all(a) gives the sum of all entries in the multidimensional array a . • Python: – Create a 1-d Variable and manually index the entries. You should come up with a reasonable scheme to avoid confusion. • Julia: – You can create a multidimensional array of variables in Convex.jl. For exam-ple, the following creates a 4-dimensional array of variables, with each of the four indices taking the values 1 or 2....
View Full Document

One thought on “Ee364a Homework 3 Solutions Designed

Leave a Reply

Your email address will not be published. Required fields are marked *