AdditionalExercisesfor ConvexOptimization

1 Additional Exercises for convex optimization Stephen Boyd Lieven Vandenberghe January 11, 2022. This is a collection of additional exercises, meant to supplement those found in the book convex optimization , by Stephen Boyd and Lieven Vandenberghe. These exercises were used in several courses on convex optimization , EE364a (Stanford), EE236b (UCLA), or (MIT), usually for homework, but sometimes as exam questions. Some of the exercises were originally written for the book, but were removed at some point. Many of them include a computational component using one of the software packages for convex optimization : CVXPY (Python), (Julia), CVX (Matlab), or CVXR (R). We refer to these collectively as CVX*. (Some problems have not yet been updated for all languages.)

2 The files required for these exercises can be found at the book web site ~boyd/cvxbook/. You are free to use these exercises any way you like (for example in a course you teach), provided you acknowledge the source. In turn, we gratefully acknowledge the teaching assistants (and in some cases, students) who have helped us develop and debug these exercises. Pablo Parrilo helped develop some of the exercises that were originally used in MIT , Sanjay Lall and John Duchi developed some other problems when they taught EE364a, and the instructors of EE364a during summer quarters developed others. We'll update this document as new exercises become available, so the exercise numbers and sections will occasionally change. We have categorized the exercises into sections that follow the book chapters, as well as various additional application areas.

3 Some exercises fit into more than one section, or don't fit well into any section, so we have just arbitrarily assigned these. Course instructors can obtain solutions to these exercises by email to us. Please specify the course you are teaching and give its URL. Stephen Boyd and Lieven Vandenberghe 1. Contents 1 introduction 3. 2 convex sets 4. 3 convex functions 8. 4 convex optimization problems 24. 5 Duality 45. 6 Approximation and fitting 66. 7 Statistical estimation 88. 8 Geometry 111. 9 Unconstrained minimization 129. 10 Equality constrained minimization 135. 11 Interior-point methods 138. 12 Mathematical background 148. 13 Numerical linear algebra 150. 14 Circuit design 151. 15 Signal processing and communications 159. 16 Control and trajectory optimization 171.

4 17 Finance 182. 18 Mechanical and aerospace engineering 206. 19 Graphs and networks 219. 20 Energy and power 227. 21 Miscellaneous applications 241. 2. 1 introduction convex optimization . Are the following statements true or false? (a) Least squares is a special case of convex optimization . (b) By and large, convex optimization problems can be solved efficiently. (c) Almost any problem you'd like to solve in practice is convex . (d) convex optimization problems are attractive because they always have a unique solution. Device sizing. In a device sizing problem the goal is to minimize power consumption subject to the total area not exceeding 50, as well as some timing and manufacturing constraints. Four candidate designs meet the timing and manufacturing constraints, and have power and area listed in the table below.

5 Design Power Area A 10 50. B 8 55. C 10 45. D 11 50. Are the statements below true or false? (a) Design B is better than design A. (b) Design C is better than design A. (c) Design D cannot be optimal. Computation time. Very roughly, how long would it take to solve a linear program with 100. variables and 1000 constraints on a computer capable of carrying out a 10 Gflops/sec ( , 1010. floating-point operations per second)? (a) Microseconds. (b) Milliseconds. (c) Seconds. (d) Minutes. Local optimization . Are the statements below true or false? (a) Local optimization can be quite useful in some contexts, and therefore is widely used. (b) Local optimization is currently illegal in 17 states. (c) Local optimization can't guarantee finding a (global) solution, and so is not widely used.

6 3. 2 convex sets Is the set {a Rk | p(0) = 1, |p(t)| 1 for t }, where p(t) = a1 + a2 t + + ak tk 1 , convex ? Set distributive characterization of convexity [Rockafellar]. Show that C Rn is convex if and only if ( + )C = C + C for all nonnegative , . Here we use standard notation for scalar-set multiplication and set addition, , C = {ac | c C} and A + B = {a + b | a A, b B}. Composition of linear-fractional functions. Suppose : Rn Rm and : Rm Rp are the linear-fractional functions Ax + b Ey + f (x) = , (y) = , cT x + d gT y + h with domains dom = {x | cT x + d > 0}, dom = {y | gT x + h > 0}. We associate with and the matrices . A b E f , , cT d gT h respectively. Now consider the composition of and , , (x) = ( (x)), with domain dom = {x dom | (x) dom }.

7 Show that is linear-fractional, and that the matrix associated with it is the product . E f A b . gT h cT d Dual of exponential cone. The exponential cone Kexp R3 is defined as Kexp = {(x, y, z) | y > 0, yex/y z}.. Find the dual cone Kexp We are not worried here about the fine details of what happens on the boundaries of these cones, so you really needn't worry about it. But we make some comments here for those who do care about such things. The cone Kexp as defined above is not closed. To obtain its closure, we need to add the points {(x, y, z) | x 0, y = 0, z 0}. (This makes no difference, since the dual of a cone is equal to the dual of its closure.). 4. Dual of intersection of cones. Let C and D be closed convex cones in Rn . In this problem we will show that (C D) = C + D.

8 When C + D is closed. Here, + denotes set addition: C + D is the set {u + v | u C , v D }. In other words, the dual of the intersection of two closed convex cones is the sum of the dual cones. (A sufficient condition for of C + D to be closed is that C int D 6= . The general statement is that (C D) = cl(C + D ), and that the closure is unnecessary if C int D 6= , but we won't ask you to show this.). (a) Show that C D and C + D are convex cones. (b) Show that (C D) C + D . (c) Now let's show (C D) C + D when C + D is closed. You can do this by first showing (C D) C + D C D (C + D ) . You can use the following result: If K is a closed convex cone, then K = K. Next, show that C D (C + D ) and conclude (C D) = C + D . (d) Show that the dual of the polyhedral cone V = {x | Ax 0} can be expressed as V = {AT v | v 0}.

9 Polar of a set. The polar of C Rn is defined as the set C = {y Rn | y T x 1 for all x C}. (a) Show that C is convex (even if C is not). (b) What is the polar of a cone? (c) What is the polar of the unit ball for a norm k k? (d) What is the polar of the set C = {x | 1T x = 1, x 0}? (e) Show that if C is closed and convex , with 0 C, then (C ) = C. Dual cones in R2 . Describe the dual cone for each of the following cones. (a) K = {0}. (b) K = R2 . (c) K = {(x1 , x2 ) | |x1 | x2 }. (d) K = {(x1 , x2 ) | x1 + x2 = 0}. Convexity of some sets. Determine if each set below is convex . (a) {(x, y) R2++ | x/y 1}. (b) {(x, y) R2++ | x/y 1}. 5. (c) {(x, y) R2+ | xy 1}. (d) {(x, y) R2+ | xy 1}. Correlation matrices. Determine if the following subsets of Sn are convex .

10 (a) the set of correlation matrices, C n = {C Sn+ | Cii = 1, i = 1, .. , n}. (b) the set of nonnegative correlation matrices, {C C n | Cij 0, i, j = 1, .. , n}. (c) the set of highly correlated correlation matrices, {C C n | Cij , i, j = 1, .. , n}. Helly's theorem. (a) (Radon's theorem) Let X = {x1 , .. , xm } be a set of m points in Rn , where m n + 2. Show that X can be partitioned in two sets S and T = X \ S such that conv S conv T 6= . Here conv S and conv T denote the convex hulls of S and T . Hint. Since m n + 2, the vectors (xi , 1), i = 1, .. , m, are linearly dependent. Therefore there exists a nonzero y such that . y1.. x1 x2 xm y 2 .. = 0. 1 1 1 .. ym Use y to define S and T , and to construct a point x conv S conv T . (b) Use the result in (a) to prove the following.