6.079/6.975, Fall 2009–10 S. Boyd & P. Parrilo Homework 3 additional problems 1. Reverse Jensen inequality. Suppose f is convex, λ1 > 0, λi ≤ 0, i = 2, . . . , k, and λ1 + · · · + λn = 1, and let x1, . . . , xn ∈ dom f. Show that the inequality f(λ1x1 + · · · + λnxn) ≥ λ1f(x1) + · · · + λnf(xn) always holds. Hints. Draw a picture for t he n = 2 case first. For the general case, express x1 as a convex combination of λ1x1 +· · · +λnxn and x2, . . . , xn, and use Jensen’s inequality. 2. Reformulating constraints in cvx. Each of the following cvx code fragments describes a convex constraint on the scalar variables x, y, a nd z, but violates the cvx rule set, and so is invalid. Briefly explain why each fragment is invalid. Then, rewrite each one in an equivalent form that conforms to the cvx rule set. In your reformulations, you can use linear equality and inequality constraints, and inequalities constructed using cvx f unctions. You can also introduce additional varia bles, or use LMIs. Be sure to explain (briefly) why your reformulation is equivalent to the original constraint, if it is not obvious. Check your reformulations by creating a small problem that includes these constraints, and solving it using cvx. Your test pro blem doesn’t have to be feasible; it’s enough to verify that cvx processes your constraints without error. Remark. This looks like a problem about ‘how to use cvx software’, or ‘tricks for using cvx’. But it really checks whether you understand the various composition rules, convex analysis, and constraint reformulation rules. (a) norm([x + 2*y, x - y]) == 0 (b) square(square(x + y)) <= x - y (c) 1/x + 1/y <= 1; x >= 0; y >= 0 (d) norm([max(x,1), max(y,2)]) <= 3*x + y (e) x*y >= 1; x >= 0; y >= 0 (f) (x + y)^2/sqrt(y) <= x - y + 5 (g) x^3 + y^3 <= 1; x >= 0; y >= 0 (h) x + z <= 1 + sqrt(x*y - z^2); x >= 0; y >= 0 13. Optimal activity levels. Solve the optimal activity level problem described in exercise 4.17 in Convex Optimization, for the instance with problem data ⎡ ⎤ ⎡ ⎤ 1 2 0 1 100 ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ 3 2 4⎢ ⎥ ⎢ ⎥0 0 3 1 100 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ max ⎢ ⎥ ⎢ ⎢ 2 ⎥ ⎥ disc ⎢ ⎢ 1 ⎥ ⎥ ⎢ ⎢ 10 ⎥ ⎥A = ⎢ 0 3 1 1 ⎥ , c = ⎢ 100 ⎥ , p = ⎢ ⎥ , p = ⎢ ⎥ , q = ⎢ ⎥ . ⎢ ⎥ ⎢ ⎥ 7 4 5⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎢ 2 1 2 5 ⎥ ⎢ 100 ⎥ ⎣ ⎦ ⎣ ⎦ 6 2 10 1 0 3 2 100 You can do this by forming the LP you f ound in your solution of exercise 4.17, or more directly, using cvx. Give the optimal activity levels, the revenue generated by each one, and the total revenue generated by the optimal solution. Also, give the average price per unit for each activity level, i.e., the ratio o f the revenue asso ciated with an activity, to the activity level. (These numbers should be between the basic and discounted prices f or each activity.) Give a very brief story explaining, or at least commenting on, the solution you find. 2MIT OpenCourseWare http://ocw.mit.edu 6.079 / 6.975 Introduction to Convex Optimization Fall 2009 For information about citing these materials or our Terms of Use, visit: