Introduction to Semidefinite Programming (SDP)

Introduction to Semidefinite Programming (SDP) 1 Outline • 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 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 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 : maximize m
y i bi i=1 m
s.t. i=1 yi a i + s = c s ∈ n +. 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  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 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 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. 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  Define: Q := q 1 q 2 · · · q n  Then Q is an orthonormal matrix: QT Q = I, equivalently QT = Q−1 λ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 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. • 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. • If M is symmetric, then det(M ) = n  λj j=1 • 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 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 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 : 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  , 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. 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 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 ... ... .. . ... 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 : 0 c2 . . . 0 maximize m
i=1 m
s.t. i=1 y i bi yi A i + S = C S  0. Notice S=C− m  i=1 5 yi A i  0 0  0 . . . . cn 10 SDP Duality 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  , 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 0 2 8 2 6 0 8 0 4   +S = 1 2 3 2 9 0 3 0 7 1 2 3 2 9 0 3 0 7  S
0 SDD : maximize 11y1 + 19y2  s.t. y1 1 0 1 0 3 7 1 7 5   + y2   +S =  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 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 ∗ . zP∗ = zD 11 Some Important Weaknesses of SDP • 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 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 : s.t. M AXCU T : 1 4 maximizex i=1 j=1 wij (1 − xi xj ) xj ∈ {−1, 1}, j = 1, . . . , n. 1 4 maximizex s.t. n
n
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 wij − W • Y xj ∈ {−1, 1}, j = 1, . . . , n s.t. Y = xxT . 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 . 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 . 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 M AXCU T ≤ RELAX. 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. 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. 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. 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 ⇐⇒ 9 xT Qi x + qiT x + ci ≤ 0. 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 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 : 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 = SOCP : P vT v d 
0 ⇐⇒ d − vT P −1 v ≥ 0 . 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 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 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 Consider the design problem: EOP : minimize w, S s.t. λmax (S) − λmin (S) S=B− Gw ≤ d . 11 k
i=1 wi Ai 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). n = {X ∈ S n | λj (X) ≥ 0, j = 1, . . . , n, ∂S+ and λj (X) = 0 for some j ∈ {1, . . . , n}}. 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 17 The SDP Analytic Center Problem 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 λ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 (ACP:) − ln det(S) minimizey,S
m s.t. 0. 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 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 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 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 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. 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, −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. 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, −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 20 Interior-p oint Methods for SDP 20.1 Primal and Dual SDP SDP : minimize s.t. 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   λ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 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  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:  Ai • X = bi , i = 1, . . . , m, X  0  
m yi A i + S = C   i=1 XS = µI.  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  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 Website for SDP 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. • 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. • 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 Newton’s Second Law of Motion: F =m×a . k m u 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) 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 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 5 feet 6 feet 10 feet 22.2.2 Analog of k 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)) is the vector of displacements. The mass m extends to a mass matrix M 22.2.4 Laws of Motion −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. −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. −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 (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 ti ) Li  (ai )(ai )T yi = m  i=1 Ei (ai )(ai )T Li  22 , i = 1, . . . , m Ki yi 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
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
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 T SDP : s.t. minimizey m
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 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 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 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 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 tower 100 90 80 70 60 50 40 30 20 10 0 60 40 20 0 20 40 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 Lower bound on Threshold Frequency Ω versus Weight of Structure 26 60 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