Truss Design and Convex Optimization

Truss Design and Convex Optimization April 13, 2004 1 1 Outline • Physical Laws of a Truss System • The Truss Design Problem • Second-Order Cone Optimization • Truss Design and Second-Order Cone Optimization • Some Computational Results • Semi-Definite Optimization • Truss Design and Semi-Definite Optimization • Truss Design and Linear Optimization • Extensions of the Truss Design Problem 2 Physical Laws of a Truss System A truss is a structure in d = 2 or d = 3 dimensions, formed by n nodes and m bars joining these nodes. Figure 1 shows an example of a truss. 2 4 6 1 3 5 Figure 1: Example of a truss in d = 2 dimensions, with n = 6 nodes and m = 13 bars. Examples of trusses include bridges, cranes, and the Eiffel Tower. 2 The data used to describe a truss is: • a set of nodes (given in physical space) • a set of bars joining pairs of nodes with associated data for each bar: – the length Lk of bar k – the Young’s modulus Ek of bar k – the volume tk of bar k • an external force vector F on the nodes Nodes can be static (fixed in place) or free (movable when the truss is stressed). The allowable movements of the nodes defines the degrees of freedom (dof) of the truss. We say that the truss has N degrees of freedom. Of course, N ≤ nd. Movements of nodes in the truss will be represented by a vector u of displacements, where u ∈ N . The external force on the truss is given by a vector F ∈ N . Displacements of the nodes in the truss cause internal forces of compression and/or expansion to appear in the bars in the truss. Let fk denote the internal force of bar k. The vector f ∈ m is the vector of forces of the bars. Figure 2 shows an example of a truss problem. In the figure, there is a single external force applied to node 3 in the direction indicated. This will result in internal forces along the bars in the truss and will simultaneously cause small displacements in all of the nodes. In Figure 2, nodes 1 and 5 are fixed, and the other nodes are free. To simplify notation we will label the 13 different bars by the nodes that hey link to: in general the bar k will join nodes i and j. The bars will be: 12, 13, . . ., 56. The internal force fk of bar k can be positive or negative: • If fk ≥ 0, bar k has been expanded and its internal force counteracts the expansion with compression, see Figure 3. 3 2 4 6 3 5 f12 1 f13 F3 Figure 2: A truss problem. ∆> 0 Lk Figure 3: A bar under expansion. ∆<0 Lk Figure 4: A bar under compression. 4 • If fk ≤ 0, bar k has been compressed and its internal force counteracts the compression with expansion, see Figure 4. 2.1 2.1.1 Physical Laws Force Balance Equations In a static truss the internal forces will balance the external forces in every degree of freedom. That is, the forces around each free node must balance. This is a law of conservation of forces. (This is akin to material balance equations in networks, for example.) For example, consider the balance of forces on node 3: x coordinate: y coordinate: +f35 +f36 cos(π/4) = −F3x −f13 −f23 cos(π/4) +f23 sin(π/4) +f34 +f36 sin(π/4) = −F3y For the entire truss we write N linear equations that represent the balance of forces in each degree of freedom. In matrix notation this can be written as Af = −F where A is an N × m matrix, and where each column of A, denoted as ak , is the projection of the bar onto the degrees of freedom of the nodes that bar k meets. In our example, we have: 5         A=              2.1.2 12 13 14 16 0 0 0 0 −1 0 0 0 0 −1 0 0 0 0 0 0 0 0 − √12 0 0 0 − √12 0 0 0 0 0 0 23 24 √1 2 − √12 − √12 √1 2 1 0 25 √2 5 − √15 34 35 36 45 46 56 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 −1 0 0 0 −1 √1 2 1 √ 2 0 0 0 1 0 0 1 0 0 −1 0 0 0 0 0 0 0 0 −1 0 0 − √25 0 0 0 0 0 0 0 0 − √15 0 − √12 0 − √12 √1 2 − √12 Constitutive Relationship between Forces and Distortion of a Bar If bar k has length Lk and cross-sectional area Ack , Young’s modulus Ek , and its length is changed by ∆k , then the internal force fk is given by: fk = Ek Ack ∆k . Lk However, for our purposes it will be easier to work instead with the volume tk of bar k, which is: tk = Ack Lk . We therefore can write the constitutive relationship as: fk = Ek t k ∆k . L2k 6                      2x 2y 3x 3y 4x 4y 6x 6y 2.1.3 Distortion and Displacements Displacements in the nodes will cause the lengths of the bars to change. Suppose that L12 = L13 = L35 = 1.0, with all other bars measured proportionally. In Figure 5, we show a displacement of: u = (−, −, 0, 0, 0, 0, 0, 0) . 2 4 6 1 3 5 2 F3 Figure 5: Example of a small displacement in a node. Table 1 shows the new lengths of the bars under the displacement u = (−, −, 0, 0, 0, 0, 0, 0). The third column of the table shows the linearization (first-order Taylor approximation) of the lengths of the bars, and the last column shows the computation of the inner product: (ak )T u . Note that if  is small, then the distortion of bar k is nicely approximated by the linear expression: ∆k = −(ak )T u . 7 Bar k 12 13 14 16 23 24 25 34 35 36 45 46 56 Old Length 1 1 √1 √5 2 1 √ 5 1 √1 √2 2 1 1 New Length 1 + 2( − 1) 1 √1 √ 5 2  2 + 2 1 + 2( + 1)  5 + 2( + 1) 1 √1 √2 2 1 1  Linearized Length 1− 1 √1 √5 2 1 +  √ √ 5 + 15  1 √1 √2 2 1 1 Linearized Change ∆k − 0 0 0 0  √1  5 0 0 0 0 0 0 Table 1: Changes in the lengths of the bars under nodal displacement We therefore write the internal force on bar k due to a feasible displacement u as: Ek fk = − 2 tk (ak )T u Lk Let the matrix B be the following diagonal matrix:  L2 1  E1 t1 B=  0  0 .. . L2m Em tm     E1 t1 L2  1 −1 B =  , 0 Then we can write the above relationship as: f = −B −1 AT u , which is: Bf + AT u = 0 . 8 0 .. . Em tm L2m    .  (ak )T u  0 0 0 0 − − √15  0 0 0 0 0 0 2.1.4 Equilibrium Conditions and Compliance Now we can write the physical laws of the truss system as: Af Bf = −F +AT u = 0 (conservation of forces) (forces, distortions, and displacements) The compliance of the truss is the work (or energy) performed by the truss, which is the sum of the forces times displacements: 1 T F u. 2 We really do not need the fraction “ 12 ”, but we will keep it for convenience. Notice that the larger the compliance, the more work or displacement that the truss undergoes under the load F . Ideally, we would like the compliance to be a small number. Combining the equilibrium conditions, we write: F = −Af = AB −1 AT u = Ku where the matrix K is defined to be: K = AB −1 AT . The matrix K is called the stiffness matrix of the truss. Note that K is an SPSD matrix. 9 Using this, we can write the compliance as: 1 T 1 F u = uT Ku . 2 2 Note from this that the compliance will always be a nonnegative quantity, as intuition suggests. More generally, of course, we would expect the stiffness matrix K to be SPD, and so the compliance will generally be a positive quantity. 2.1.5 Solving the Equations and Computing the Compliance We solve the equation system: Ku = F to obtain the nodal displacements u, and then obtain the forces on the bars by computing: f = −B −1 AT u . For each bar k, this last expression is simply: fk = − Ek tk (ak )T u . L2k The compliance is then computed as: 1 T 1 F u = uT Ku . 2 2 2.2 Viewing the Equilibrium Conditions as the Solution to an Optimization Problem We can also view the truss equilibrium conditions as the solution to an optimization problem. Consider the following optimization problem: 10 OP : minimizef˜ m  1 1 L2k ˜2 f k=1 m  s.t. 2 tk Ek k ak f˜k = −F . k=1 Problem OP seeks a force vector f˜ that satisfies the force balance equations: m  −F = ak f˜k = Af˜ , k=1 and that minimizes the weighted sum of squares of the forces: m  1 1 L2k ˜2 fk . k=1 2 tk Ek Problem OP is a convex quadratic problem. The KKT optimality conditions for this problem are: m  ak fk = −F k=1 L2k fk + aTk u = 0 for k = 1, . . . , m. tk Ek Notice that we can rewrite these optimality conditions as: Af = −F Bf + AT u = 0 , which are precisely the equilibrium conditions for the truss system. This shows that the truss system is nature’s solution to an optimization problem. 11 The optimal objective function value of the optimization problem OP is: m  1 1 L2k k=1 2 tk 1 1 1 1 fk2 = f T Bf = − f T AT u = − uT Af = F T u , Ek 2 2 2 2 which is the compliance of the truss. Therefore we see that the optimal objective value of OP is the compliance of the truss system. 3 The Truss Design Problem Let us now consider the volumes tk of the bars k to be design parameters that we wish to determine. We can write the system of equations: F = Ku as: F = Ku = AB −1 AT u = m  (ak ) B −1 AT u k=1 = m  k −(ak )fk k=1 = m  tk k=1 Ek (ak )(ak )T u Lk2 = K(t)u where the stiffness matrix is now written as: K(t) = m  k=1 tk Ek (ak )(ak )T . Lk2 12 Note in this expression that K = K(t) is a weighted sum of rank-one matrices (weighted by the volumes tk ). Put another way, K = K(t) is a weighted sum of outer-product matrices. In designing the truss, we must choose the volumes tk of the bars subject to linear constraints on the volumes of the bars: Mt ≤ d t ≥ 0, where typically these constraints include upper and lower bounds on the volumes of certain bars, as well as an overall cost or volume constraint: m  tk ≤ V . k=1 The criterion in truss design is to choose the volumes tk of the bars so as to minimize the compliance of the truss, namely: minimizet,u 1 T F u. 2 Such a truss will be the most resistant to the external force F . The single-load truss design problem can be stated as: (TDP1 ) : minimizet,u s.t. 1 T F u 2 K(t)u = F Mt ≤ d t≥0 u ∈ N , t ∈ m . 13 which is the same as: (TDP1 ) : minimizet,u 1 T F u 2 m s.t. k=1 k tk E (ak )(ak )T u = F L2 k Mt ≤ d t≥0 u ∈ N , t ∈ m . The decision variables here are u and t. However, one should really think of the decision variables as t only, since once t is chosen, u will be determined by the solution to the system of equations: m   Ek tk 2 (ak )(ak )T u = F . Lk k=1 Note that as written, the truss design problem TDP is not a convex problem. 4 A Convex Version of the Truss Design Problem Recall that for given volumes tk on the bars of the truss, that the compliance of the truss is the optimal objective value of the quadratic problem: OP : minimizef˜ m  1 1 L2k ˜2 f k=1 m  s.t. k=1 14 2 tk Ek k ak f˜k = −F . The truss design problem is then to choose the values of the volumes t = (t1 , . . . , tm ) on the bars so that the optimal solution of OP (which we have shown is the compliance of the truss) is minimized, subject to the constraints on t: Mt ≤ d t ≥ 0. We write this all as: (TDP2 ) : minimizef,t  1 1 L2 k tk 2 tk Ek >0  s.t. tk >0 fk2 ak fk = −F Mt ≤ d t≥0 f ∈ m , t ∈ m . Notice here that we have made two modifications to the optimization problem. First, we have modified the summation in the objective function, so that bars with zero volume (tk = 0) are no longer counted, since they will not exist. Second, we changed the notation, using f instead of f˜. Because the summations with the tk > 0 is rather awkward mathematically, we further re-write TDP2 as follows: 15 (TDP2 ) : minimizef,t,s s.t. m 1 sk 2 k=1 m  ak fk = −F k=1 Mt ≤ d L2k Ek fk2 ≤ tk sk for k = 1, . . . m t ≥ 0, s ≥ 0 f, t, s ∈ m . In this problem, we have replaced the quantity 1 L2k 2 f tk Ek k with the new variable sk subject to the condition: L2k 2 f ≤ tk sk . Ek k We can further re-write this now as: 16 (TDP2 ) : minimizef,t,s s.t. m 1 sk 2 k=1 Af = −F Mt ≤ d L2k Ek fk2 ≤ tk sk for k = 1, . . . m t ≥ 0, s ≥ 0 f, t, s ∈ m . This last problem has a linear objective function, and linear constraints except for the constraints: L2k 2 f ≤ tk sk . Ek k However, it is pretty easy to show that the constraints: L2k 2 f ≤ tk sk , tk ≥ 0, sk ≥ 0 Ek k describe a convex region, and so this formulation is actually a convex optimization problem. 5 Second-Order Cone Optimization A second-order cone optimization problem (SOCP) is an optimization problem of the form: SOCP : minx cT x s.t. Ax = b Qi x + di  ≤ giT x + hi 17 , i = 1, . . . , k . In this problem, the norm v is the standard Euclidean norm: v := √ vT v . The norm constraints in SOCP are called “second-order cone” constraints. Notice first that SOCP is a convex problem, since the function: Qi x + di  − giT x + hi is a convex function. Notice also that linear optimization is a special case of SOCP, if we set Qi = 0, di = 0, hi = 0, and gi to be the ith unit vector for i = 1, . . . , n. Also notice that any convex quadratic constraint can be converted into a second-order constraint. To see this, suppose we have a constraint: 1 T x Qx + q T x + r ≤ 0 , 2 where Q is SPSD. We can factor Q = MT M for some matrix M , and then write our constraint as:   1   √ Mx ,  2 qtx + r + 1 2      ≤ −q t x − r + 1 . 2 If you square both sides and collect terms, you will see that this is indeed equivalent to the original convex quadratic constraint. 18 Finally, note that we can always formulate a convex quadratic problem as an SOCP, since we can create a new variable xn+1 and write our quadratic problem as: minx,xn+1 xn+1 s.t. .. . 1 T 2 x Qx + q T x ≤ xn+1 , which can be further re-written as an SOCP. 6 Truss Design and Second-Order Cone Optimiza­ tion We now present a second-order cone optimization problem that is equivalent to the truss design problem TDP2 . Recall this version of the truss design problem: (TDP2 ) : minimizef,t,s s.t. m 1 sk 2 k=1 Af = −F Mt ≤ d L2k Ek fk2 ≤ tk sk for k = 1, . . . m t ≥ 0, s ≥ 0 f, t, s ∈ m . Let us now make the simple change of variables: 19 1 2 tk wk = + 12 sk yk = − 12 tk + 12 sk Then sk = wk + yk and tk = wk − yk , and so: tk sk = (wk − yk )(wk + yk ) = wk2 − yk2 , and so the constraint L2k 2 f ≤ tk sk Ek k becomes: L2k 2 f ≤ wk2 − yk2 . Ek k We can rearrange this and take square roots to obtain:  L2k 2 f + yk2 ≤ wk , Ek k which we can in turn write as:      yk , √Lk fk  ≤ wk .   E k Therefore we can re-write TDP2 as: (CTDP): minimizef,w,y s.t. 1 T e (w + y) 2 Af = −F     L  yk , √Ek fk  ≤ wk , k M (w − y) ≤ d w, y, f ∈ m . 20 k = 1, . . . , m Notice that CTDP is a second-order cone problem. The objective function and the first and third set of constraints are linear equations and inequalities. The second set of constraints are second-order-cone constraints, since the LHS is the norm of a 2-dimensional vector:       Lk  √ (v1 , v2 ) :=  yk , fk   , E k and the RHS is the linear expression: wk . Proposition 6.1 Suppose that (f, w, y) is a feasible or optimal solution of CTDP. Let: t = w − y and s = w + y. Then (f, t, s) is the corresponding feasible or optimal solution of TDP2 . 6.1 Other Formulations and Formats for the Truss Design Problem We have just seen how to formulate the truss design problem as the convex optimization problem TDP2 and more specially as the second-order cone optimization problem CTDP. In addition to these two formulations of the problem, there is a way to formulate the truss design problem as an instance of a more general type of convex problem called a “semi-definite optimization problem” (SDO for short). The topic of SDO and its application to truss design is discussed herein in Sections 8 and 9. Finally, when the only constraints on the volume variables t1 , . . . , tm are nonnegativity conditions and a total-volume constraint of the form: m  tk ≤ V , k=1 then the truss design problem can actually be converted to a linear optimization problem. This is shown herein in Section 10. 21 7 Some Computational Results In this section we report some computational results on solving truss design problems. We solved three different types of truss design problems. The first type is a basic bridge design, and is illustrated in Figure 6. In the figure, the arrows collectively comprise the force vector F applied to the structure, and the circles (in the left lower and right lower corners) are the fixed nodes of the structure. The stars in the figures are the other nodes in the truss structure. Figure 7 shows the set of bars that can be used to construct the bridge. These bars were generated by considering bars between any two nodes whose “distance” from one another was three nodes or less. 7 6 5 4 3 2 1 0 0 2 4 6 8 10 12 14 16 Figure 6: The forces and nodes for the basic bridge design model. The second type of problem that we solved is the problem of designing a hanging support for a load such as a traffic sign, and is illustrated in Figure 22 7 6 5 4 3 2 1 0 0 2 4 6 8 10 12 14 16 Figure 7: The set of possible bars for the basic bridge design problem. 23 8. The circles on the left part of the figure correspond to the fixed nodes, and the arrow on the right side is a force that will be applied (the gravitational force of the traffic sign). 20 18 16 14 12 10 8 6 4 2 0 0 5 10 15 20 25 30 Figure 8: The forces and nodes for the hanging sign design model. The third type of problem that we solved is the problem of designing a crane to handle a gravitational load, and is illustrated in Figure 9. The circles on the bottom of the figure correspond to the fixed nodes, and the arrow on the right side is a force that will be applied (the gravitational force of the traffic sign). For the problems shown in Figures 6, 8, and 9, the truss design model solutions are shown in Figures 10, 11, and 12. In these figures, the thickness of the image of the bars is drawn proportional to the volumes of the bars in the optimal solutions. 24 40 35 30 25 20 15 10 5 0 0 2 4 6 8 10 12 14 16 18 20 Figure 9: The forces and nodes for the crane design model. 25 7 6 5 4 3 2 1 0 0 2 4 6 8 10 12 14 16 Figure 10: Optimal solution to the basic bridge design problem. 26 20 18 16 14 12 10 8 6 4 2 0 0 5 10 15 20 25 30 Figure 11: Optimal solution to the hanging sign design problem. 27 40 35 30 25 20 15 10 5 0 0 2 4 6 8 10 12 14 16 18 20 Figure 12: Optimal solution to the crane design problem. 28 Notice in Figure 10 that the basic bridge design does not automatically include horizontal bars for a “road surface” on the base of the structure. In order to force there to be such a road surface, we must add lower bounds on the volumes of those bars on the base of structure. If we add such lower bounds, the optimal bridge design is as shown in Figure 13. 7 6 5 4 3 2 1 0 0 2 4 6 8 10 12 14 16 Figure 13: Optimal solution of the bridge design problem, with lower bounds on the “road surface” bar volumes. 7.1 Details of Problems Solved For the bridge design problem, we included lower-bound constraints on the volumes of the road-surface bars as well as a constraint on the total volume of the structure. With the lower-bound constraints in the model, the model must be solved either as a second-order cone problem (SOCP) or as a semidefinite optimization problem (SDO). For the hanging sign design problem 29 Name Size of grid Bridge-16×7 Bridge-20×10 Bridge-30×10 Sign-10×20 Sign-20×30 Sign-30×40 Crane-10×20 Crane-20×40 Crane-30×40 16×7 20×10 30×10 10×20 20×30 30×40 10×20 20×40 30×40 Nodes n 136 231 341 231 651 1,271 96 291 401 Arcs m 1,547 2,878 4,368 2,878 9,058 18,438 818 3,188 4,678 Degrees of freedom N 268 458 678 444 1,280 2,512 188 578 798 Maximum Volume Table 2: Dimensions of the truss design problems. as well as for the crane design problem, the only constraint on the volumes was a constraint on the total volume of the truss structure. This made it possible to solve these problems using linear optimization. We solved three different instances of each of the bridge, hanging sign, and crane design problems, with different numbers of nodes corresponding to different meshes. Table 2 shows details of the models that we solved. The right-most column in the table shows the value of the volume constraint on the volume of the truss structure. Table 3 shows the number of variables and the number of inequalities in these problems, and Table 4 shows the number of variables and the number of equations/constraints/matrix dimension of these problems. Table 5 shows the compliance of the optimal truss design for the nine problems that were solved. Table 6 shows the iterations of the interior-point algorithms that were used to solve the truss design problems. For the linear problems and the second-order cone problems, we used LOQO to solve the model. For the semi-definite optimization models, we used an SDO algorithm called SDPa. The running times of these methods is shown in Table 7. 30 1,600 2,000 4,000 1,000 2,000 3,000 2,000 5,000 10,000 Problem Bridge-16×7 Bridge-20×10 Bridge-30×10 Sign-10×20 Sign-20×30 Sign-30×40 Crane-10×20 Crane-20×40 Crane-30×40 LP Model Variables Inequalities 2m 2m † † † † † † 5,756 5,756 18,116 18,116 36,876 36,876 1,636 1,636 6,376 6,376 9,356 9,356 SOCP Model Variables Inequalities 3m m + 1 + LBs 4,641 1,564 8,634 2,899 13,104 4,399 8,634 2,879 27,174 9,059 55,314 18,439 2,454 819 9,564 3,189 14,034 4,679 Table 3: Number of variables and inequalities in the truss design problems. †The linear optimization model cannot be used for the modified bridge design model. Problem Bridge-16×7 Bridge-20×10 Bridge-30×10 Sign-10×20 Sign-20×30 Sign-30×40 Crane-10×20 Crane-20×40 Crane-30×40 LP Model Variables Equations 2m N † † † † † † 5,756 444 18,116 1,280 36,876 2,512 1,636 188 6,376 578 9,356 798 SOCP Model Variables Constraints 3m N + m + 1 + LBs 4,641 1,832 8,634 3,357 13,104 5,077 8,634 3,323 27,174 10,339 55,314 20,951 2,454 1,007 9,564 3,767 14,034 5,477 SDO Model Matrix Dimension N +m+2 1,685 3,111 4,711 3,111 9,711 19,711 916 3,481 5,081 Table 4: Number of variables and equations in the truss design problems. †The linear optimization model cannot be used for the modified bridge design model. 31 Problem Bridge-16×7 Bridge-20×10 Bridge-30×10 Sign-10×20 Sign-20×30 Sign-30×40 Crane-10×20 Crane-20×40 Crane-30×40 LP † † † 0.77279 2.52003 4.08573 28.67827 286.24854 596.73177 SOCP 27.43365 52.58314 132.46038 0.77293 2.52056 4.08681 28.67840 286.24954 596.73324 SDP 27.15510 52.10850 ‡ 0.77279 ‡ ‡ 28.67753 286.19340 596.63740 Table 5: Compliance of the optimized truss design for the truss design problems. †The linear optimization model cannot be used for the modified bridge design model. ‡The data to run the SDO model could not be prepared for this instance due to memory restrictions. Problem Bridge-16×7 Bridge-20×10 Bridge-30×10 Sign-10×20 Sign-20×30 Sign-30×40 Crane-10×20 Crane-20×40 Crane-30×40 LP † † † 18 21 24 17 31 31 SOCP 38 55 47 61 47 53 52 158 144 SDO 36 43 ‡ 37 ‡ ‡ 34 58 60 Table 6: Number of iterations of the interior-point algorithm to solve the truss design problems. †The linear optimization model cannot be used for the modified bridge design model. ‡The data to run the SDO model could not be prepared for this instance due to memory restrictions. 32 Problem Bridge-16×7 Bridge-20×10 Bridge-30×10 Sign-10×20 Sign-20×30 Sign-30×40 Crane-10×20 Crane-20×40 Crane-30×40 LP † † † 3.33 32.08 111.03 0.52 6.46 10.67 SOCP 93.90 460.96 904.86 513.37 4,254.08 26,552.74 41.12 1,299.12 1,599.85 SDO 257.01 1,088.09 ‡ 1,081.54 ‡ ‡ 446.98 33,926.20 95,131.49 Table 7: Running time (in seconds) of the interior-point algorithm to solve the truss design problems. †The linear optimization model cannot be used for the modified bridge design model. ‡The data to run the SDO model could not be prepared for this instance due to memory restrictions. 8 Semi-Definite Optimization If S is a k × k matrix, then S is a symmetric positive semi-definite (SPSD) matrix if S is symmetric (Sij = Sji for any i, j = 1, . . . , k) and v T Sv ≥ 0 for any v ∈ k . If S is a k × k matrix, then S is a symmetric positive definite (SPD) matrix if S is symmetric and v T Sv > 0 for any v ∈ k , v = 0. k denote the Let S k denote the set of symmetric k × k matrices, and let S+ set of symmetric positive semi-definite (SPSD) k × k matrices. Similarly let k denote the set of symmetric positive definite (SPD) k × k matrices. S++ 33 Let S and X be any symmetric matrices. We write “S 0” to denote that S is symmetric and positive semi-definite, and we write “S X” to denote that S − X 0. We write “S 0” to denote that S is symmetric and positive definite, etc. k = {S ∈ S k | S Remark 1 S+ 2 0} is a convex set in k . k . Pick any scalars α, β ≥ 0 for which Proof: Suppose that S, X ∈ S+ k α + β = 1. For any v ∈  , we have: v T (αS + βX)v = αv T Sv + βv T Xv ≥ 0, k . This shows that S k is a convex set. whereby αS + βX ∈ S+ + q.e.d. A semi-definite optimization problem is an optimization problem of the following type: SDO : minimizey bT y s.t. C+ m i=1 yi Ai 0 My ≥ g . where the matrices C, A1 , . . . , Am are symmetric matrices. One convenient way of thinking about this problem is as follows. Given values of the m scalar variables y1 , . . . , ym , the objective is to minimize the linear function: m  bi yi . i=1 The constraints of SDO state that the variables y = (y1 , . . . , ym ) must satisfy the linear inequalities: My ≥ g 34 as well as the condition that the matrix S, defined by: S := C + m  yi Ai , i=1 must be positive semi-definite. That is, S := C + m  yi Ai 0. i=1 We illustrate this construction with the following example: SDO : minimizey1 ,y2 11y1 + 19y2       1 2 3 1 0 1 0 2 8  2 9 0  + y1  0 3 7  + y2  2 6 0  = S 3 0 7 1 7 5 8 0 4 s.t. 3y1 + 7y2 ≤ 12 2y1 + y2 ≤ 6 . which we can rewrite in the following form: SDO : minimize s.t. 11y1 + 19y2   1 + 1y1 + 0y2 2 + 0y1 + 2y2 3 + 1y1 + 8y2    2 + 0y1 + 2y2 9 + 3y1 + 6y2 0 + 7y1 + 0y2  3 + 1y1 + 8y2 0 + 7y1 + 0y2 7 + 5y1 + 4y2 3y1 + 7y2 ≤ 12 2y1 + y2 ≤ 6 . 35 0 0 Remark 2 SDO is a convex minimization problem. Proof: The objective function of SDO is a linear function, which is convex. Suppose that y¯ and y˜ are two feasible solutions of SDO, and let y = αȳ + βỹ, where α, β ≥ 0 and α + β = 1. Then: S := C + m  ȳi Ai 0 ỹi Ai 0. i=1 and X := C + m  i=1 Therefore, C+ m i=1 yi Ai = C + m i=1  = α C+ (αȳ + β ỹ) Ai m i=1 = αS + βX   ȳi Ai + β C + m i=1  ỹi Ai 0. This shows that the feasible region of SDO is a convex set. q.e.d. Semi-definite optimization is a unifying model in optimization. Linear optimization, quadratic optimization, second-order cone optimization, as well as certain other convex optimization problems, can all be shown to be special cases of semi-definite optimization. Furthermore, semi-definite optimization has applications that span convex optimization, discrete optimization, and control theory. In fact, semi-definite optimization may very well become the canonical way that optimizers will think about optimization in the next decade. 36 9 Truss Design and Semi-Definite Optimization We now present an SDO problem that is equivalent to the truss design problem TDP. This problem is: (STDP): minimizet,θ θ s.t.  θ F m k=1 FT k tk E (ak )(ak )T L2  0 k Mt ≤ d t≥0 θ ∈ , t ∈ m . Notice that STDP is a semi-definite optimization problem. The equivalence of TDP and STDP is a consequence of the following two propositions: Proposition 9.1 Suppose that (t, u) is a feasible solution of TDP. Let: θ = FTu . Then (t, θ) is a feasible solution of STDP, and θ = F T u. Proposition 9.2 Suppose that (t, θ) is a feasible solution of STDP. Then there exists a vector u for which (t, u) is feasible for TDP, and in fact: FTu ≤ θ . Together, Propositions 9.1 and 9.2 demonstrate that any solution of STDP translates into a solution to TDP. Therefore, in order to solve TDP, 37 we can solve STDP for (t∗ , θ∗ ) and then solve the following linear equation system for u∗ : m  t∗ Ek k Lk2 k=1  ak aTk u∗ = F . As a means to prove Propositions 9.1 and 9.2, we first show the following: Remark 3 Given a vector v, a square matrix M , and a scalar θ, then:  Q := θ vT v M  0 if and only if: 0 , there exists u satisfying M u = v , and θ ≥ v T u . M Proof of Remark 3: To see why this is true, let us first suppose that Q 0. Then clearly M 0, since M is formed by a subset of the components that form Q. Now, let us suppose that there is no u such that M u = v. This implies that there exists λ such that λT M = 0 and λT v > 0. Then:  (−, λT ) θ vT v M  − λ  = θ2 − 2v T λ + λT M λ = θ2 − 2v T λ < 0 for  small enough, which is a contradiction. Therefore there exists u such that M u = v. Furthermore, for such a u, we have:  T 0 ≤ (−1, u ) θ vT v M  −1 u  = θ − 2v T u + uT M u = θ − v T u which shows that θ ≥ v T u. Now let us prove the reverse of these implications. Suppose that M 0, there exists u satisfying M u = v, and θ ≥ v T u. Since M 0 we only have to prove that: 38  T δ(x) := (−1, x ) θ vT v M  −1 x  = θ − 2v T x + xT M x ≥ 0 ∀x . But notice that δ(x) is a convex quadratic function of x (since in particular M 0), and therefore ∇δ(x) = −2v + 2M x = 0 is a necessary and sufficient condition for the unconstrained minimization of δ(x). Since u satisfies this condition, it is true that δ(x) ≥ δ(u) = θ − 2v T u + uT M u = θ − v T u ≥ 0 ∀x . q.e.d. Now let us prove the propositions. Proof of Proposition 9.1: Suppose that (t, u) is a feasible solution of TDP. Let: θ = FTu , m  and let Ek tk 2 (ak )(ak )T M= Lk k=1  , and let v = F . Then m   Ek Mu = tk 2 (ak )(ak )T u = F , Lk k=1 and notice as well that 39 M 0 because M is the nonnegative sum of rank-one SPSD matrices. From Remark 3,   θ F m k=1  FT k tk E (ak )(ak )T L2  = k θ vT v M  0. Therefore (t, θ) is feasible for STDP with objective function value θ = F T u. q.e.d. Proof of Proposition 9.2: Suppose that (t, θ) is a feasible solution of STDP. Then from Remark 3, there exists a vector u for which: m   Ek tk 2 (ak )(ak )T u = F , Lk k=1 and θ ≥ F T u. Therefore (t, u) is feasible for TDP and θ ≥ F T u. q.e.d. 10 Truss Design and Linear Optimization Consider the following special, but not unusual, instance of the truss design problem: 40 (TDP): minimizet,u F T u m s.t. k=1 m k=1 k tk E (ak )(ak )T u = F L2 k tk ≤ V t≥0 u ∈ N , t ∈ m . In this problem, the only constraint on the volumes of the bars tk is a volume constraint limiting the total volume of the bars to not exceed the given value V . Substituting the notation: m  Ek tk 2 (ak )(ak )T K(t) := Lk k=1  , we can also conveniently write our problem as: (TDP): minimizet,u F T u s.t. K(t)u = F m k=1 tk ≤ V t≥0 u ∈ N , t ∈ m . In this section, we show that when TDP has this particularly simple form, then it can be solved via linear optimization. Before doing so, we first write down a dual problem associated with TDP in this form: 41 (DTDP): maximizev,z −2F T v − V z s.t. aTk v 2 ≤ L2k Ek z , k = 1, . . . , m y ∈ N . In order for DTDP to be an honest dual of TDP, we now present a weak duality result: Proposition 10.1 Suppose that (t, u) is feasible for TDP and that (v, z) is feasible for DTDP. Then: F T u ≥ −2F T v − V z . Proof: For k = 1, . . . , m, we have tk ≥ 0 and Ek T 2 (a v) ≤ z. L2k k Multiplying and summing terms, we obtain: v T K(t)v = m  tk Ek k=1 L2k (v T ak ) (akT v) ≤ m   tk z ≤ V z. k=1 Also, 0 ≤ (u + v)T K(t)(u + v) = uT K(t)u + 2uT K(t)v + v T K(t)v = F T u + 2v T F + v T K(t)v ≤ F T u + 2v T F + V z. Therefore F T u ≥ −2F T v − V z. q.e.d. Consider the following pair of primal and dual linear optimization models: 42 (LP): minimizef + ,f − m k=1 √Lk Ek fk+ + fk− A(f + − f − ) = −F s.t. f+ ≥ 0 , f− ≥ 0 f + , f − ∈ m . (LD): maximizey −F T y s.t. − √LEk ≤ aTk y ≤ k √Lk Ek , k = 1, . . . , m y ∈ N . We will prove the following important result that shows how to use solutions of LP and LD to construct solutions to TDP: Proposition 10.2 Suppose that (f¯+ , f¯− ) is an optimal solution of LP and that ȳ is an optimal solution of LD, and consider the following assignment of variables: R = m  Lk √ k=1 Ek f¯k+ + f¯k− V Lk √ f¯+ + f¯k− R Ek k R ū = − ȳ V R ȳ v̄ = V R2 z̄ = V2 t̄k = 43 k = 1, . . . , m, ¯ u) Then (t, ¯ solves TDP and (¯ v, z) ¯ solves DTDP. Proof: Note that by the complementary slackness property of linear optimization, we have: + aTk yf k − aTk yf k = = L + √ k fk , Ek −Lk − √ f , Ek k k = 1, . . . , m, k = 1, . . . , m. We first show that (t, u) is feasible for TDP. Note that t ≥ 0 and V R = V . Also R m k=1 tk = R K(t)y V m R tk Ek = − ak aTk y V k=1 L2k K(t)u = − m L Ek + R V  − √k (f k + f k )ak akT y = − 2 V R k=1 Ek Lk √ m  Ek + T − = − (f k ak y + f k aTk y) ak L k k=1 = − m  k=1 + − + − ak (f k − f k ) = −A(f − f ) = F. We next show that (v, z) is feasible for DTDP. To see this, observe that for k = 1, . . . , m, we have: (aTk v)2 = R2 T 2 R2 (a y) ≤ V2 k V2  L √k Ek 2 =z L2k , Ek and so (v, z) is feasible. Finally, we show that these solutions exhibit strong duality: −2F T v−V z = R2 R R −2R T V R2 2R2 R2 F y− 2 = − = = R = (−F T y) = F T u. V V V V V V V q.e.d. 44 11 Extensions of the Truss Design Problem • Multiple Loads. We consider a finite set of external loads on the truss: F = {F1 , F2 , . . . , FJ } ⊂ IRN . In this case we might consider solving two types of design problems. The first is to design the truss structure conservatively, so as to minimize the maximum compliance:   minimizet maxj=1,...,J FjT uj M t ≤ d, t≥0 s.t. K(t)uj = Fj . Alternatively, we might consider the “average-case” design problem: let λj denote the relative frequency or importance associated with the truss structure undergoing the external force Fj , where J j=1 λj = 1.0. The following optimization model minimizes the average compliance of the truss structure: J minimizet M t ≤ d, t≥0 j=1 λj FjT uj s.t. K(t)uj = Fj . • Self-weights. The truss design problem that we have formulated presumes that the truss structure itself is not affected by its own weight. To correct for this, we can simply add an external force corresponding to the gravitational force associated with bar k, and linearly proportional to tk for k = 1, . . . , m. Let us denote by gk ∈ IRN the vector that projects the gravitational force of bar k onto the appropriate nodes. 45 Then we can write the TDP of a truss under a single external load vector F as:  (TDP): minimizet,u F+ T m k=1 tk gk  s.t. K(t)u = F + u m k=1  tk gk Mt ≤ d t≥0 u ∈ N , t ∈ m . It is straightforward to convert this problem into a convex problem, just as for the base case considered earlier. • Reinforcement. In this problem, we are given an existing truss structure, and we must determine how to strengthen it. To solve this problem, we simply add lower bounds on the volumes of the existing bars equal to the current volumes of the bars: (TDP): minimizet,u F T u s.t. K(t)u = F Mt ≤ d t≥0 tk ≥ tk , k = 1, . . . , m u ∈ N , t ∈ m . 46 • Robustness of Solutions. The optimal solution of the TDP might yield a truss design that is not rigid for a different external force than the one used, and could change considerably even under a small change in the external force. To obtain a robust solution, we must consider multiple external loads that will contain the possible loads that the truss will be subject to. This can be modeled by convex optimization as well. • Buckling Constraints. The truss design problem that we have presented ignores the fact that if a bar is under great compression it might actually collapse instead of counteracting that external force with its internal force. For this we have to add lower bounds on the allowable internal forces in terms of the design variables tk and the geometry of the bars. These constraints cause the resulting problem to lose its convex structure. • Other Considerations . . . . 47