1 Some Convex Analysis (20 p oints) (a) Given positive scalars L and E , consider the following set in three-dimensional space: ( ) L2 S = (f; t; s) j f 2 s t ; s 0 ; t 0 : E This set arises in the optimization of load bearing truss structures that you have seen in the lectures on truss design. Show that S is a convex set. (b) Let S kk denote the set of k k square symmetric matrices. A matrix X symmetric positive semide nite (SPSD) if 2 S kk is vT Xv 0 for all v 2 0 for all v 2 0, then the AMPL model will have a slightly smaller feasible region than the true model of the problem. The purpose of introducing > 0 is to speed up solution time by \smoothing" the second-order cone constraint a bit. Change the value of the tolerance parameter in the range from = 0:00000001 up to = 1:0 and solve the resulting model. Record the optimal compliance and the number of iterations it takes to solve the model as functions of the value of . What do you observe? Can you suggest any reasons for this? 4 High-Percentage Covering Disk Problem (20 p oints) Consider the problem of determining the smallest disk that contains the m given points c1 ; : : : ; cm . The decision variables in the problem are the center x and the radius R of the enclosing disk, and the problem yields the simple formulation: 3 CDP : minimizex;R R s.t. kx ci k R i = 1; : : : ; m n x 2 < ;R 2 < ; where in this case n = 2 is the dimension in which the problem arises. The Ampl le CDPql.mod contains a reformulation of this problem with quadratic objective and linear constraints. CDPql2.mod is the same formulation but demonstrates the problem command in Ampl. The Ampl le CDPlq.mod contains the version of the problem with a linear objective and quadratic constraints. All of these formulations of the problem solve very rapidly, with zero duality gap. (a) The data les cover18.dat and cover19.dat each contain the locations of 100 points in n = 2 dimensions. The rst column in the le is the index of the point, and the second and third columns contain the rst and second coordinates of the point. Solve the problem using these data sets, and create gures illustrating your solution. Solve CDPql2.mod with the LOQO convex option turned on and o . Is there a di erence in how LOQO solves the problem? If so, why? Solve CDPlq.mod with the LOQO convex option turned on and o . Is there a di erence in how LOQO solves the problem? If so, why? (b) Consider the following variation of the problem, where we would like to nd the smallest disk that contains 90% of the points. This problem arises in data mining, for example. We will use the sigmoid function: 1 f (s) := 1+e s to account for points that might lie outside the disk. The sigmoid function with parameter > 0 has the following attractive properties: f f f f (s) ! 0 as s ! 1 (s) ! 1 as s ! +1 (s) = f ( s) (0) = 21 A graph of this function is shown in Figure 2. Using the sigmoid function, our problem can be approximated as the following smooth nonlinear problem: HPCDP : minimizex;R;s1;:::;sm R s.t. kx ci k R + si i = 1; : : : ; m x 2