Introduction to Semidefinite Programming

Introduction to Semidefinite Programming (SDP) 1 Outline Slide 1 • Alternate View of Linear Programming • Facts about Symmetric and Semidefinite Matrices • SDP • SDP Duality • Examples of SDP – Combinatorial Optimization: MAXCUT – Convex Optimization: Quadratic Constraints, Eigenvalue Problems, log det(X) problems • Interior-Point Methods for SDP • Application: Truss Vibration Dynamics via SDP 2 2.1 Linear Programming Alternative Perspective Slide 2 LP : minimize c·x ai · x = bi , i = 1, . . . , m s.t.
n x ∈ n +. “c · x” means the linear function “ j=1 cj xj ” n n + := {x ∈  | x ≥ 0} is the nonnegative orthant. is a convex cone. n + K is convex cone if x, w ∈ K and α, β ≥ 0 ⇒ αx + βw ∈ K. LP : minimize Slide 3 c·x ai · x = bi , i = 1, . . . , m s.t. x ∈ n +. “Minimize the linear function c · x, subject to the condition that x must solve m given equations ai · x = bi , i = 1, . . . , m, and that x must lie in the convex cone K = n + .” 2.1.1 LP Dual Problem LD : Slide 4 maximize m
y i bi i=1 m
s.t. i=1 yi a i + s = c n . s ∈ + 1 For feasible solutions x of LP and (y, s) of LD, the duality gap is simply c·x− m   y i bi = c− i=1 m   yi a i ·x=s·x≥0 i=1 If LP and LD are feasible, then there exists x∗ and (y ∗ , s∗ ) feasible for the primal and dual, respectively, for which c · x∗ − m  Slide 5 yi∗ bi = s∗ · x∗ = 0 i=1 3 Facts about the Semidefinite Cone If X is an n × n matrix, then X is a symmetric positive semidefinite (SPSD) matrix if X = X T and v T Xv ≥ 0 for any v ∈ n Slide 6 If X is an n × n matrix, then X is a symmetric positive definite (SPD) matrix if X = X T and v T Xv > 0 for any v ∈ n , v =  0 4 Facts about the Semidefinite Cone S n denotes the set of symmetric n × n matrices n denotes the set of (SPSD) n × n matrices. S+ n denotes the set of (SPD) n × n matrices. Let X, Y ∈ S n . S++ “X  0” denotes that X is SPSD “X  Y ” denotes that X − Y  0 “X  0” to denote that X is SPD, etc. n = {X ∈ S n | X  0} is a convex cone. Remark: S+ 5 Slide 7 Slide 8 Facts about Eigenvalues and Eigenvectors If M is a square n × n matrix, then λ is an eigenvalue of M with corresponding eigenvector q if M q = λq and q =  0. Slide 9 Let λ1 , λ2 , . . . , λn enumerate the eigenvalues of M . 6 Facts about Eigenvalues and Eigenvectors The corresponding eigenvectors q 1 , q 2 , . . . , q n of M can be chosen so that they are orthonormal, namely  i T  j  q q = 0 for i = j, and 2  i T  i  q q =1 Slide 10  Define: Q := q 1 q 2 · · · q n  Then Q is an orthonormal matrix: QT Q = I, equivalently QT = Q−1 Slide 11 λ1 , λ2 , . . . , λn are the eigenvalues of M q 1 , q 2 , . . . , q n are the corresponding orthonormal eigenvectors of M  Q := q 1 q 2 · · · q n  QT Q = I, equivalently QT = Q−1 λ Define D: 1 0 D :=  0 λ2  0 ..   . . 0 λn Property: M = QDQT . The decomposition of M into M = QDQT is called its eigendecomposition. 7 Slide 12 Facts about Symmetric Matrices • If X ∈ S n , then X = QDQT for some orthonormal matrix Q and some diagonal matrix D. The columns of Q form a set of n orthogonal eigenvectors of X, whose eigenvalues are the corresponding entries of the diagonal matrix D. Slide 13 • X  0 if and only if X = QDQT where the eigenvalues (i.e., the diagonal entries of D) are all nonnegative. • X  0 if and only if X = QDQT where the eigenvalues (i.e., the diagonal entries of D) are all positive. Slide 14 • If M is symmetric, then det(M ) = n  λj j=1 Slide 15 • Consider the matrix M defined as follows:  M= P vT v d  , where P  0, v is a vector, and d is a scalar. Then M  0 if and only if d − v T P −1 v ≥ 0. • For a given column vector a, the matrix X := aaT is SPSD, i.e., X = aaT  0. • If M  0, then there is a matrix N for which M = N T N . To see this, simply 1 take N = D 2 QT . 3 8 SDP 8.1 8.1.1 Semidefinite Programming Think about X Slide 16 Let X ∈ S n . Think of X as: • a matrix • an array of n2 components of the form (x11 , . . . , xnn ) • an object (a vector) in the space S n . All three different equivalent ways of looking at X will be useful. 8.1.2 Linear Function of X Slide 17 Let X ∈ S n . What will a linear function of X look like? If C(X) is a linear function of X, then C(X) can be written as C • X, where C • X := n n   Cij Xij . i=1 j=1 There is no loss of generality in assuming that the matrix C is also symmetric. 8.1.3 Definition of SDP SDP : Slide 18 C•X minimize Ai • X = bi , i = 1, . . . , m, s.t. X  0, n ” “X  0” is the same as “X ∈ S+ The data for SDP consists of the symmetric matrix C (which is the data for the objective function) and the m symmetric matrices A1 , . . . , Am , and the m−vector b, which form the m linear equations. 8.1.4 Example  A1 = 1 0 1 0 3 7 1 7 5   , A2 = 0 2 8 2 6 0 8 0 4   , b= 11 19 The variable X will be the 3 × 3 symmetric matrix:  X= x11 x21 x31 x12 x22 x32 4 x13 x23 x33   , and C =  , 1 2 3 2 9 0 3 0 7 Slide 19  , SDP : x11 + 4x12 + 6x13 + 9x22 + 0x23 + 7x33 x11 + 0x12 + 2x13 + 3x22 + 14x23 + 5x33 0x11 + 4x12 + 16x13 + 6x22 + 0x23 + 4x33 minimize s.t.  X = SDP : minimize s.t. x11 x21 x31 x12 x22 x32 x13 x23 x33  = =
0. Slide 20 x11 + 4x12 + 6x13 + 9x22 + 0x23 + 7x33 x11 + 0x12 + 2x13 + 3x22 + 14x23 + 5x33 0x11 + 4x12 + 16x13 + 6x22 + 0x23 + 4x33  X= x11 x21 x31 x12 x22 x32 x13 x23 x33 11 19 = = 11 19 
0. It may be helpful to think of “X
0” as stating that each of the n eigenvalues of X must be nonnegative. 8.1.5 LP ⊂ SDP Slide 21 LP : Define:  ai1 Ai =  0 . . . 0 0 ai2 . . . 0 SDP : 9 ... ... .. . ... minimize s.t. c·x ai · x = bi , i = 1, . . . , m x ∈ n +. 0  0 .  , i = 1, . . . , m, and C = . . ain minimize s.t.  c1  0 . . . 0 0 c2 . . . 0 ... ... .. . ... 0  0 . . . . cn C•X Ai • X = bi , i = 1, . . . , m, Xij = 0, i = 1, . . . , n, j = i + 1, . . . , n,  x1 0 . . . 0  0 0 x2 . . . X = . . . 
0, .. . . . . . . . 0 0 . . . xn SDP Duality SDD : maximize m
i=1 m
s.t. i=1 Slide 22 y i bi yi A i + S = C S  0. Notice S=C− m  i=1 5 yi A i  0 10 SDP Duality Slide 23 and so equivalently: SDD : maximize m
i=1 C− s.t. 10.1 y i bi m
i=1 yi A i  0 Example  A1 = 1 0 1 SDD : 0 3 7 1 7 5   , maximize A2 = 2 6 0 8 0 4  , b= 11 19   , and C = 1 2 3 2 9 0 3 0 7 Slide 24  , 11y1 + 19y2  s.t. 0 2 8  y1 1 0 1 0 3 7 1 7 5   + y2 0 2 8 2 6 0 8 0 4   +S = 1 2 3 2 9 0 3 0 7  S
0 SDD : maximize  s.t. Slide 25 11y1 + 19y2 y1 1 0 1 0 3 7 1 7 5   + y2 0 2 8 2 6 0 8 0 4   +S = 1 2 3 2 9 0 3 0 7  S
0 is the same as: SDD : maximize s.t. 10.2 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 
0. Weak Duality Weak Duality Theorem: Given a feasible solution X of SDP and a feasible solution (y, S) of SDD, the duality gap is C •X − m  y i bi = S • X ≥ 0 . i=1 If C•X− m  y i bi = 0 , i=1 then X and (y, S) are each optimal solutions to SDP and SDD, respectively, and furthermore, SX = 0. 6 Slide 26 10.3 Strong Duality ∗ Strong Duality Theorem: Let zP∗ and zD denote the optimal objective function values of SDP and SDD, respectively. Suppose that there exists a feasible solution ˆ of SDP such that X ˆ  0, and that there exists a feasible solution (ˆ X y, Ŝ) of SDD such that Ŝ  0. Then both SDP and SDD attain their optimal values, and Slide 27 ∗ . zP∗ = zD 11 Some Important Weaknesses of SDP Slide 28 • There may be a finite or infinite duality gap. • The primal and/or dual may or may not attain their optima. • Both programs will attain their common optimal value if both programs have feasible solutions that are SPD. • There is no finite algorithm for solving SDP . • There is a simplex algorithm, but it is not a finite algorithm. There is no direct analog of a “basic feasible solution” for SDP . 12 12.0.1 SDP in Combinatorial Optimization The MAX CUT Problem G is an undirected graph with nodes N = {1, . . . , n} and edge set E. Let wij = wji be the weight on edge (i, j), for (i, j) ∈ E. We assume that wij ≥ 0 for all (i, j) ∈ E. The MAX CUT problem is to determine a subset S of the nodes N for which the sum of the weights of the edges that cross from S to its complement S¯ is maximized (S̄ := N \ S). 12.0.2 Formulations Slide 29 Slide 30 The MAX CUT problem is to determine a subset S of the nodes N for which the sum of the weights wij of the edges that cross from S to its complement S¯ is maximized (S̄ := N \ S). Let xj = 1 for j ∈ S and xj = −1 for j ∈ S̄. M AXCU T : 1 4 maximizex s.t. n
n
i=1 j=1 wij (1 − xi xj ) xj ∈ {−1, 1}, j = 1, . . . , n. Slide 31 M AXCU T : 1 4 maximizex s.t.

n n i=1 j=1 wij (1 − xi xj ) xj ∈ {−1, 1}, j = 1, . . . , n. 7 Let Y = xxT . Then Yij = xi xj i = 1, . . . , n, j = 1, . . . , n. Also let W be the matrix whose (i, j)th element is wij for i = 1, . . . , n and j = 1, . . . , n. Then M AXCU T : 1 4 maximizeY,x n n

i=1 j=1 Slide 32 wij − W • Y xj ∈ {−1, 1}, j = 1, . . . , n s.t. Y = xxT . Slide 33 M AXCU T : 1 4 maximizeY,x n
n
i=1 j=1 wij − W • Y xj ∈ {−1, 1}, j = 1, . . . , n s.t. Y = xxT . Slide 34 The first set of constraints are equivalent to Yjj = 1, j = 1, . . . , n. M AXCU T : 1 4 maximizeY,x n
n
i=1 j=1 wij − W • Y Yjj = 1, j = 1, . . . , n s.t. Y = xxT . Slide 35 M AXCU T : 1 4 maximizeY,x n
n
i=1 j=1 wij − W • Y Yjj = 1, j = 1, . . . , n s.t. Y = xxT . Notice that the matrix Y = xxT is a rank-1 SPSD matrix. We relax this condition by removing the rank-1 restriction: RELAX : 1 4 maximizeY s.t. n
n
i=1 j=1 wij − W • Y Yjj = 1, j = 1, . . . , n Y
0. It is therefore easy to see that RELAX provides an upper bound on MAXCUT, i.e., 8 Slide 36 M AXCU T ≤ RELAX. Slide 37 RELAX : 1 4 maximizeY n n

i=1 j=1 wij − W • Y Yjj = 1, j = 1, . . . , n s.t. Y  0. As it turns out, one can also prove without too much effort that: 0.87856 RELAX ≤ M AXCU T ≤ RELAX. Slide 38 This is an impressive result, in that it states that the value of the semidefinite relaxation is guaranteed to be no more than 12.2% higher than the value of N P -hard problem MAX CUT. 13 SDP for Convex QCQP A convex quadratically constrained quadratic program (QCQP) is a problem of the form: QCQP : minimize x s.t. Slide 39 xT Q0 x + q0T x + c0 xT Qi x + qiT x + ci ≤ 0 , i = 1, . . . , m, where the Q0  0 and Qi  0, i = 1, . . . , m. This is the same as: QCQP : minimize x, θ s.t. θ xT Q0 x + q0T x + c0 − θ ≤ 0 xT Qi x + qiT x + ci ≤ 0 , i = 1, . . . , m. Slide 40 QCQP : minimize x, θ s.t. θ xT Q0 x + q0T x + c0 − θ ≤ 0 xT Qi x + qiT x + ci ≤ 0 , i = 1, . . . , m. Factor each Qi into Qi = MiT Mi and note the equivalence:  I xT MiT Mi x −ci − qiT x  0 ⇐⇒ xT Qi x + qiT x + ci ≤ 0. Slide 41 9 QCQP : minimize x, θ s.t. θ xT Q0 x + q0T x + c0 − θ ≤ 0 xT Qi x + qiT x + ci ≤ 0 , i = 1, . . . , m. Re-write QCQP as: QCQP : minimize x, θ θ  s.t. I M0 x −c0 − q0T x + θ I Mi x −ci − qiT x xT M0T  xT MiT 14 14.1  
0
0 , i = 1, . . . , m. SDP for SOCP Second-Order Cone Optimization Slide 42 Second-order cone optimization: SOCP : minx cT x s.t. Ax = b  Recall v := √ Qi x + di ≤ giT x + hi  , i = 1, . . . , k . vT v SOCP : Slide 43 minx cT x s.t. Ax = b  Qi x + di  ≤ giT x + hi Property:  Qx + d ≤ g T x + h  ⇐⇒   (g T x + h)I (Qx + d)T , i = 1, . . . , k . (Qx + d) gT x + h 
0. This property is a direct consequence of the fact that  M = P vT v d 
0 ⇐⇒ d − vT P −1 v ≥ 0 . Slide 44 SOCP : minx cT x s.t. Ax = b  Qi x + di  ≤ giT x + hi Re-write as: 10  , i = 1, . . . , k . SDPSOCP : minx cT x s.t. Ax = b  15 (giT x + hi )I (Qi x + di )T (Qi x + di ) giT x + hi 
0, i = 1, . . . , k . Eigenvalue Optimization Slide 45 We are given symmetric matrices B and Ai , i = 1, . . . , k Choose weights w1 , . . . , wk to create a new matrix S: S := B − k  wi Ai . i=1 There might be restrictions on the weights Gw ≤ d. The typical goal is for S is to have some nice property such as: • λmin (S) is maximized • λmax (S) is minimized • λmax (S) − λmin (S) is minimized 15.1 Some Useful Relationships Slide 46 Property: M  tI if and only if λmin (M ) ≥ t. Proof: M = QDQT . Define R = M − tI = QDQT − tI = Q(D − tI)QT . M  tI ⇐⇒ R  0 ⇐⇒ D − tI  0 ⇐⇒ λmin (M ) ≥ t . q.e.d. Property: M 15.2 tI if and only if λmax (M ) ≤ t. Design Problem Slide 47 Consider the design problem: EOP : minimize w, S s.t. λmax (S) − λmin (S) S=B− k
wi Ai i=1 Gw ≤ d . Slide 48 11 EOP : λmax (S) − λmin (S) minimize w, S S=B− s.t. k
i=1 w i Ai Gw ≤ d . This is equivalent to: EOP : µ−λ minimize w, S, µ, λ S=B− s.t. Gw ≤ d λI 16 S k
w i Ai i=1 µI. The Logarithmic Barrier Function for SPD Matrices n Let X  0, equivalently X ∈ S+ . X will have n nonnegative eigenvalues, say λ1 (X), . . . , λn (X) ≥ 0 (possibly counting multiplicities). Slide 49 n = {X ∈ S n | λj (X) ≥ 0, j = 1, . . . , n, ∂S+ and λj (X) = 0 for some j ∈ {1, . . . , n}}. Slide 50 n ∂S+ = {X ∈ S n | λj (X) ≥ 0, j = 1, . . . , n, and λj (X) = 0 for some j ∈ {1, . . . , n}}. A natural barrier function is: B(X) := − n   ln(λi (X)) = − ln j=1 n   = − ln(det(X)). λi (X) j=1 This function is called the log-determinant function or the logarithmic barrier function for the semidefinite cone. B(X) := − n   ln(λi (X)) = − ln j=1 λi (X) = − ln(det(X)). j=1 ¯ Quadratic Taylor expansion at X = X: ¯ + αD) ≈ B(X) ¯ + αX ¯ −1 • D + B(X n    1 1 2 ¯− 1 α X 2 D X̄ − 2 2   1 1 • X̄ − 2 D X̄ − 2  . B(X) has the same remarkable
properties in the context of interior-point methods for n SDP as the barrier function − j=1 ln(xj ) does in the context of linear optimization. 12 Slide 51 17 The SDP Analytic Center Problem Slide 52 Given a system: m  yi Ai C , i=1 ˆ of: the analytic center is the solution (ˆ y, S) (ACP:) n  maximizey,S
m s.t. λi (S) i=1 i=1 yi Ai + S = C S
0. (ACP:) n  maximizey,S i=1
m s.t. i=1 Slide 53 λi (S) yi Ai + S = C S
0. This is the same as: (ACP:) − ln det(S) minimizey,S
m s.t. i=1 yi Ai + S = C S 0. Slide 54 (ACP:) − ln det(S) minimizey,S
m s.t. i=1 yi Ai + S = C S 0. Let (ŷ, Ŝ) be the analytic center. There are easy-to-construct ellipsoids EIN and EOUT , both centered at ŷ and where EOUT is a scaled version of EIN with scale factor n, with the property that: EIN ⊂ P ⊂ EOUT Slide 55 13 ^ x P Ein Eout 18 Minimum Volume Circumscription R  0 and z ∈ n define an ellipsoid in n : ER,z := {y | (y − z)T R(y − z) ≤ 1}.  The volume of ER,z is proportional to det(R−1 ). Given k points c1 , . . . , ck , we would like to find an ellipsoid circumscribing c1 , . . . , ck that has minimum volume: 14 Slide 56 Slide 57 Slide 58 M CP : minimize R, z s.t. vol (ER,z ) ci ∈ ER,z , i = 1, . . . , k which is equivalent to: M CP : minimize R, z s.t. − ln(det(R)) (ci − z)T R(ci − z) ≤ 1, i = 1, . . . , k R0 Slide 59 M CP : minimize R, z s.t. − ln(det(R)) (ci − z)T R(ci − z) ≤ 1, i = 1, . . . , k R0 Factor R = M 2 where M  0 (that is, M is a square root of R): M CP : minimize M, z s.t. − ln(det(M 2 )) (ci − z)T M T M (ci − z) ≤ 1, i = 1, . . . , k, M 0 Slide 60 15 M CP : minimize M, z s.t. − ln(det(M 2 )) (ci − z)T M T M (ci − z) ≤ 1, i = 1, . . . , k, M 0. Notice the equivalence:  I (M ci − M z)T M ci − M z 1 
0 ⇐⇒ (ci − z)T M T M (ci − z) ≤ 1 Re-write M CP : M CP : minimize M, z s.t. −2 ln(det(M ))  I (M ci − M z)T M 0. M ci − M z 1 
0, i = 1, . . . , k, Slide 61 M CP : minimize M, z s.t. −2 ln(det(M ))  I (M ci − M z)T M 0. M ci − M z 1 
0, i = 1, . . . , k, Substitute y = M z: M CP : minimize M, y s.t. −2 ln(det(M ))  I (M ci − y)T M 0. M ci − y 1 
0, i = 1, . . . , k, Slide 62 M CP : minimize M, y s.t. −2 ln(det(M ))  I (M ci − y)T M  0. M ci − y 1   0, i = 1, . . . , k, This problem is very easy to solve. Recover the original solution R, z by computing: R = M 2 and z = M −1 y. 19 SDP in Control Theory A variety of control and system problems can be cast and solved as instances of SDP . This topic is beyond the scope of this lecturer’s expertise. 16 Slide 63 20 Interior-p oint Methods for SDP 20.1 Primal and Dual SDP SDP : minimize s.t. Slide 64 C •X Ai • X = bi , i = 1, . . . , m, X
0 and SDD : m
maximize yi bi i=1 m
s.t. yi Ai + S = C i=1 S
0. If X and (y, S) are feasible for the primal and the dual, the duality gap is: C •X − m  yi bi = S • X ≥ 0 . i=1 Also, S • X = 0 ⇐⇒ SX = 0 . B(X) = − n   ln(λi (X)) = − ln j=1 n  Slide 65  λi (X) = − ln(det(X)) . j=1 Consider: BSDP (µ) : minimize s.t. C • X − µ ln(det(X)) Ai • X = bi , i = 1, . . . , m, X 0. Let fµ (X) denote the objective function of BSDP (µ). Then: −∇fµ (X) = C − µX −1 Slide 66 BSDP (µ) : minimize s.t. C • X − µ ln(det(X)) Ai • X = bi , i = 1, . . . , m, X 0. ∇fµ (X) = C − µX −1 Karush-Kuhn-Tucker conditions for BSDP (µ) are:  Ai • X = bi , i = 1, . . . , m,      X 0,  m 
  yi Ai .  C − µX −1 = i=1 17 Slide 67  A • X = bi , i = 1, . . . , m,   i X  0, m
  C − µX −1 = yi A i . i=1 Define S = µX −1 , which implies XS = µI , and rewrite KKT conditions as: Slide 68  Ai • X = bi , i = 1, . . . , m, X  0  
m yi A i + S = C   i=1 XS = µI. Slide 69  Ai • X = bi , i = 1, . . . , m, X  0  
m yi A i + S = C   i=1 XS = µI. If (X, y, S) is a solution of this system, then X is feasible for SDP , (y, S) is feasible for SDD, and the resulting duality gap is S •X = n n   Sij Xij = i=1 j=1 n  (SX)jj = j=1 n  (µI)jj = nµ. j=1 Slide 70  Ai • X = bi , i = 1, . . . , m, X  0  
m yi A i + S = C   i=1 XS = µI. If (X, y, S) is a solution of this system, then X is feasible for SDP , (y, S) is feasible for SDD, the duality gap is S • X = nµ. This suggests that we try solving BSDP (µ) for a variety of values of µ as µ → 0. Interior-point methods for SDP are very similar to those for linear optimization, in that they use Newton’s method to solve the KKT system as µ → 0. 21 Slide 71 Website for SDP Slide 72 A good website for semidefinite programming is: http://www-user.tu-chemnitz.de/ helmberg/semidef.html. 18 22 22.1 Optimization of Truss Vibration Motivation • The design and analysis of trusses are found in a wide variety of scientific applications including engineering mechanics, structural engineering, MEMS, and biomedical engineering. Slide 73 • As finite approximations to solid structures, a truss is the fundamental concept of Finite Element Analysis. • The truss problem also arises quite obviously and naturally in the design of scaffolding-based structures such as bridges, the Eiffel tower, and the skeletons for tall buildings. Slide 74 • Using semidefinite programming (SDP) and the interior-point software SDPT3, we will explore an elegant and powerful technique for optimizing truss vibration dynamics. • The problem we consider here is designing a truss such that the lowest frequency ¯ Ω at which it vibrates is above a given lower bound Ω. • November 7, 1940, Tacoma Narrows Bridge in Tacoma, Washington 22.2 The Dynamics Model Slide 75 Newton’s Second Law of Motion: F =m×a . k m u Slide 76 19 k m u If the mass is pulled down, the displacement u produces a force in the spring tending to move the mass back to its equilibrium point (where u = 0). The displacement u causes an upward force k × u, where k is the spring constant. We obtain from F = m × a that: −ku(t) = mü(t) Slide 77 Law of Motion: −ku(t) = mü(t)  Solution: u(t) = sin Frequency of vibration:  ω= 22.2.1  k t m k . m Apply to Truss Structure Slide 78 Law of Motion: −ku(t) = mü(t)  Solution: u(t) = sin  k t m  ω= k m For truss structure, we need multidimensional analogs for k, u(t), and m. A simple truss. Each bar has both stiffness and mass that depend on material properties and the bar’s cross-sectional area. 20 Slide 79 5 feet 6 feet 10 feet 22.2.2 Analog of k Slide 80 The spring constant k extends to the stiffness matrix of a truss. We used G to denote the stiffness matrix. Here we will use K. K = G = AB −1 AT Each column of A, denoted as ai , is the projection of bar i onto the degrees of freedom of the nodes that bar i meets.   B= L2 1 E1 t 1 0 .. 0 22.2.3 .     E1 t 1  B −1 =  , L2 m Em t m 0 2 L1 .. 0    . . Em t m L2 m Analog of m Instead of a single displacement scalar u(t), we have N degrees of freedom, and the vector u(t) = (u1 (t), . . . , uN (t)) Slide 81 is the vector of displacements. The mass m extends to a mass matrix M 22.2.4 Laws of Motion Slide 82 −ku(t) = mu(t) ¨ 21 becomes: −Ku(t) = M ü(t) Both K and M are SPD matrices, and are easily computed once the truss geometry and the nodal constraints are specified. Slide 83 −Ku(t) = M ü(t) The truss structure vibration involves sine functions with frequencies √ ωi = λi where λ1 , . . . , λ N are the eigenvalues of M −1 K The threshold frequency Ω of the truss is the lowest frequency ωi , i = 1, . . . , N , or equivalently, the square root of the smallest eigenvalue of M −1 K. Slide 84 −Ku(t) = M ü(t) The threshold frequency Ω of the truss is the square root of the smallest eigenvalue of M −1 K. Lower bound constraint on the threshold frequency ¯ Ω≥Ω Property: 22.3 ¯ ⇐⇒ K − Ω ¯ 2M  0 . Ω≥Ω Truss Vibration Design We wrote the stiffness matrix as a linear function of the volumes ti of the bars i: K= m  Ei ti i=1 L2i Slide 85 (ai )(ai )T , Li is the length of bar i Ei is the Young’s modulus of bar i ti is the volume of bar i. 22.4 Truss Vibration Design Here we use yi to represent the area of bar i (yi = K = K(y) = m   Ei i=1  where Ki = Li Slide 86 ti ) Li  (ai )(ai )T yi = m  Ki yi i=1 Ei (ai )(ai )T Li  22 , i = 1, . . . , m Slide 87 There are matrices M1 , . . . , Mm for which we can write the mass matrix as a linear function of the areas y1 , . . . , ym : M = M (y) = m  Mi yi i=1 In truss vibration design, we seek to design a truss of minimum weight whose threshold ¯ frequency Ω is at least a pre-specified value Ω. T SDP : minimize m
Slide 88 bi y i i=1 m
s.t. ¯ 2 Mi )yi  0 (Ki − Ω i=1 li ≤ yi ≤ ui , i = 1, . . . , m . The decision variables are y1 , . . . , ym li , ui are bounds on the area yi of bar i (perhaps from the output of the static truss design model) bi is the length of bar i times the material density of bar i T SDP : minimizey m
Slide 89 Slide 90 bi y i i=1 m
s.t. i=1 ¯ 2 Mi )yi  0 (Ki − Ω li ≤ yi ≤ ui , i = 1, . . . , m . 22.5 Computational Example Slide 91
m T SDP : s.t. minimizey bi y i i=1 m
i=1 ¯ 2 Mi )yi  0 (Ki − Ω li ≤ yi ≤ ui , i = 1, . . . , m . 23 5 feet 6 feet 10 feet T SDP : minimizey Slide 92 m
i=1 m
s.t. bi yi ¯ 2 Mi )yi
0 (Ki − Ω i=1 li ≤ yi ≤ ui , i = 1, . . . , m . • li = 5.0 square inches for all bars i • ui = 8.0 square inches for all bars i • mass density for steel, which is ρ =0.736e−03 • Young’s modulus for steel, which is 3.0e+07 pounds per square inch ¯ = 220Hz • Ω 22.5.1 SDPT3 Slide 93 SDPT3 is the semidefinite programming software developed by “T3”: • Kim Chuan Toh of National University of Singapore • Reha T¨ ut¨ unçu of Carnegie Mellon University • Michael Todd of Cornell University Slide 94 Statistics for TSDP problem run using SDPT3 Linear Inequalities Semidefinite block size CPU time (seconds): IPM Iterations: Optimal Solution Bar 1 area (square inches) Bar 2 area (square inches) Bar 3 area (square inches) Bar 4 area (square inches) Bar 5 area (square inches) Bar 6 area (square inches) Bar 7 area (square inches) 24 14 6×6 0.8 15 8.0000 8.0000 7.1797 6.9411 5.0000 6.9411 7.1797 Slide 95 5 feet 6 feet 10 feet 22.6 More Computation A truss tower used for computational experiments. This version of the tower has 40 bars and 32 degrees of freedom. 25 Slide 96 tower 100 90 80 70 60 50 40 30 20 10 0 60 40 20 0 20 40 60 Slide 97 Computational results using SDPT3 for truss frequency optimization. Semidefinite Linear Scalar IPM CPU time Block Inequalities Variables Iterations (sec) 12 × 12 30 15 17 1.17 20 × 20 50 25 20 1.49 32 × 32 80 40 21 1.88 48 × 48 120 60 20 2.73 60 × 60 150 75 20 3.76 80 × 80 200 100 23 5.34 120 × 120 300 150 23 9.46 22.6.1 Frontier Solutions Slide 98 Lower bound on Threshold Frequency Ω versus Weight of Structure 26 5 4.5 4 Weight 3.5 3 2.5 2 1.5 200 205 210 215 220 Ω, lower bound on frequency (Hz) 27 225 230 235