4 ECE 5759 Problem 1. Due: October 25 Closed Convex set in the space of Matrices (10 marks) nn A matrix A R is called a positive semidefinite matrix if xT Ax 0 for every x Rn . Prove that the set of positive semidefinite matrices is a closed convex set in Rnn . [Hint: You can use the fact that if bn is a convergent sequence such that bn 0 and bn b , then b 0. Also, a sequence of matrices {An } is said to converge to A if every element of An A converges to 0.] Problem 2. Barrier functions (20 marks) Assume that gj : Rn R, j = 1, . . . , r are convex functions (gj may not be differentiable). Assume that the set D := {x Rn : gj (x) < 0, j = 1, . . . , r} is nonempty (the set D is convex). Part (a) Prove that if p1 : R R is a non-decreasing convex function and p2 : Rn R is a convex function, then p1 p2 : Rn R is a convex function. DO NOT assume that p1 and p2 are differentiable. Part (b) Use the above result to show that the log and inverse barrier functions are convex in D, where Blog (x) = r X ln(gj (x)), Binv (x) = j=1 j=1 Problem 3. r X 1 . gj (x) External Vendor in a Juice Company (20 marks) A juice company Juiceville makes juices 1 and 2 by mixing two fruit concentrates A and B. The cost of concentrates A and B are $0.5 and $1.2 per gallon, respectively. The revenue from selling juices 1 and 2 are $1.4 and $3 per gallon, respectively. Juice 1 must contain at least 55% concentrate A and 35% concentrate B. Juice 2 must contain at least 25% concentrate A and 65% concentrate B. The Juiceville can definitely sell up to 1000 gallons of juice 1 and 1600 gallons of juice 2. The Juiceville wants to maximize its profit by choosing appropriate quantities xA and xB of fruit concentrates A and B and quantities y1 and y2 of juices 1 and 2. Part (a) Formulate this problem as a linear programming minimization problem. Hint: You may have to introduce some new variables intelligently. I introduced 4 new variables, but one may be able to solve this problem with less. Part (b) Solve the formulated problem using MATLAB linprog command. Write the optimal solution and Lagrange multipliers associated with each equality/inequality constraints. No need to submit the MATLAB code. Part (c) Assume that external vendors 1, 2, and 3 can sell Juiceville up to 30 gallons of juice 2 at a price of $0.8, $0.95, and $1.1 per gallon. Should the Juiceville reduce its production and buy a certain amount of juice 2 from these external vendors? Why? (10 marks) Hint: You must use sensitivity theorem. Problem 4. A Variation of Method of Multiplier Methods (40 marks) n nn Theorem: Consider the sequence {xk } and b Rn . If the k=1 defined by xk+1 = Axk + b, where xk R , A R spectral radius (A) < 1, then the sequence xk converges to x that satisfies x = A x + b. Consider the following optimization problem min x21 + 2x22 + 5x23 subject to h(x) = x1 + x2 + x3 2 = 0. xR3 Page 1 of 2 Assignment 4 ECE 5759 Due: October 25 Part (a) Use Lagrange multiplier theory to find x? and ? . Note that you must justify why the solution you found is indeed the optimal solution. Part (b) What is the augmented Lagrangian Lc (x, ) for this problem? For fixed c > 0 and R, find arg minxR3 Lc (x, ). Part (c) Now assume that c = ck = 2 for all k N. Pick your favorite 1 R. Prove that if xk+1 = arg minxR3 Lc (x, k ) and k+1 = k + ck h(xk ), then k ? as k . [Hint: You need to expand the \"state space\": Analyze the convergence of the sequence {zk }kN , where zk = [k , k+1 ]T ]. Part (d) Write a MATLAB code using c = ck = 105 for all k N and 1 = 1. Plot k vs k for 50 iterations. Why k does not converge even though c is chosen large enough? DO NOT SUBMIT THE CODE, but submit the plot. NOTE: If you run the code for 106 iterations, then it may converge. Problem 5. Min-max and max-min (10 marks) n Let X R and Y Rm . Let f : X Y R be any function. Prove that min max f (x, y) max min f (x, y). xX yY yY xX Assume that the minimum and the maximum exist in the above expression. Remark: When the above inequality holds with equality, then we say that f has a saddle-point. Page 2 of 2