orange Optimizationorange Least Action Principleorange Equation of Motionorange Periodic Solutionsorange The ampl Modelorange Choreographies and the DucatiHome PageTitle PageContentsJJ IIJ IPage 1 of 9Go BackFull ScreenCloseQuitNew Orbits for theEquimass n-Body ProblemRobert J. Vanderbei—The LOQO GuyMay 14, 2004Workshop onLarge Scale Nonlinear and Semidefinite ProgrammingWaterloo, OntarioOperations Research and Financial Engineering, Princeton Universityhttp://www.princeton.edu/∼rvdbHome PageTitle PageContentsJJ IIJ IPage 2 of 9Go BackFull ScreenCloseQuit1. Optimizationminimize f(x)subject to b ≤ h(x) ≤ b + r,l ≤ x ≤ u• Linear Programming (LP): f and h are linear.• Convex Optimization: f is convex, each hiis concave, and r = ∞.• Nonlinear Optimization: f and each hiis assumed to be twicedifferentiable• Generally, we seek a local solution in the vicinity of a given startingpoint.• If problem is convex (which includes LP), any local solution is au-tomatically a global solution.Home PageTitle PageContentsJJ IIJ IPage 3 of 9Go BackFull ScreenCloseQuit2. Least Action PrincipleGiven: n bodies.Let:mjdenote the mass andzj(t) denote the position in R2= C of body j at time t.Action Functional:A =Z2π0Xjmj2k ˙zjk2+Xj,k:k<jmjmkkzj− zkkdt.Home PageTitle PageContentsJJ IIJ IPage 4 of 9Go BackFull ScreenCloseQuit3. Equation of MotionFirst Variation:δA =Z2π0XαXjmj˙zαj˙δzαj−Xj,k:k<jmjmk(zαj− zαk)(δzαj− δzαk)kzj− zkk3dt= −Z2π0XjXαmj¨zαj+Xk:k6=jmjmkzαj− zαkkzj− zkk3δzαjdtSetting firs t variation to zer o, we get:mj¨zαj= −Xk:k6=jmjmkzαj− zαkkzj− zkk3, j = 1, 2, . . . , n, α = 1, 2Note: If mj= 0 for some j, then the first order optimality conditionreduces to 0 = 0, which is not the equation of motion for a m assles sbody.Home PageTitle PageContentsJJ IIJ IPage 5 of 9Go BackFull ScreenCloseQuit4. Periodic SolutionsWe assume solutions can be expressed in the formzj(t) =∞Xk=−∞γkeikt, γk∈ C.Writing with components zj(t) = (xj(t), yj(t)) and γk= (αk, βk), wegetx(t) = a0+∞Xk=1ackcos(kt) + asksin(kt)y(t) = b0+∞Xk=1bckcos(kt) + bsksin(kt)wherea0= α0, ack= αk+ α−k, ask= β−k− βk,b0= β0, bck= βk+ β−k, bsk= αk− α−k.The variables a0, ack, ask, b0, bck, and bskare the decision variables in theoptimization model.Home PageTitle PageContentsJJ IIJ IPage 6 of 9Go BackFull ScreenCloseQuit5. The ampl Modelparam N := 3; # number of massesparam n := 15; # number of terms in Fourier series representationparam m := 100; # number of terms in numerical approx to integralparam theta {j in 0..m-1} := j*2*pi/m;param a0 {i in 0..N-1} default 0; param b0 {i in 0..N-1} default 0;var as {i in 0..N-1, k in 1..n} := 0; var bs {i in 0..N-1, k in 1..n} := 0;var ac {i in 0..N-1, k in 1..n} := 0; var bc {i in 0..N-1, k in 1..n} := 0;var x {i in 0..N-1, j in 0..m-1}= a0[i]+sum {k in 1..n} ( as[i,k]*sin(k*theta[j]) + ac[i,k]*cos(k*theta[j]) );var y {i in 0..N-1, j in 0..m-1}= b0[i]+sum {k in 1..n} ( bs[i,k]*sin(k*theta[j]) + bc[i,k]*cos(k*theta[j]) );var xdot {i in 0..N-1, j in 0..m-1}= if (j<m-1) then (x[i,j+1]-x[i,j])*m/(2*pi) else (x[i,0]-x[i,m-1])*m/(2*pi);var ydot {i in 0..N-1, j in 0..m-1}= if (j<m-1) then (y[i,j+1]-y[i,j])*m/(2*pi) else (y[i,0]-y[i,m-1])*m/(2*pi);var K {j in 0..m-1} = 0.5*sum {i in 0..N-1} (xdot[i,j]^2 + ydot[i,j]^2);var P {j in 0..m-1}= - sum {i in 0..N-1, ii in 0..N-1: ii>i}1/sqrt((x[i,j]-x[ii,j])^2 + (y[i,j]-y[ii,j])^2);minimize A: (2*pi/m)*sum {j in 0..m-1} (K[j] - P[j]);Home PageTitle PageContentsJJ IIJ IPage 7 of 9Go BackFull ScreenCloseQuitContinued...let {i in 0..N-1, k in 1..n} as[i,k] := 1*(Uniform01()-0.5);let {i in 0..N-1, k in 1..n} ac[i,k] := 1*(Uniform01()-0.5);let {i in 0..N-1, k in n..n} bs[i,k] := 0.01*(Uniform01()-0.5);let {i in 0..N-1, k in n..n} bc[i,k] := 0.01*(Uniform01()-0.5);solve;Home PageTitle PageContentsJJ IIJ IPage 8 of 9Go BackFull ScreenCloseQuit6. Choreographies and the DucatiThe previous ampl model was used to find many choreographies (a laMoore and Montgomery/Chencinier) in the equimass n-body problemand the stable Ducati solution to the 3-body problem.-1.5-1-0.500.511.5-1.5 -1 -0.5 0 0.5 1 1.5"after.out"Home PageTitle PageContentsJJ IIJ IPage 9 of 9Go BackFull ScreenCloseQuitContents1 Optimization 22 Least Action Principle 33 Equation of Motion 44 Periodic Solutions 55 The ampl Model 66 Choreographies and the Ducati