Convex optimization examples • multi-period processor speed scheduling • minimum time optimal control • grasp force optimization • optimal broadcast transmitter power allocation • phased-array antenna beamforming • optimal receiver location 1� Multi-period processor speed scheduling processor adjusts its speed st ∈ [smin, smax] in each of T time periods • �T energy consumed in period t is φ(st); total energy is E = φ(st)• t=1 • n jobs – job i available at t = Ai; must finish by deadline t = Di – job i requires total work Wi ≥ 0 • θti ≥ 0 is fraction of processor effort allocated to job i in period t Di 1Tθt = 1, θtist ≥ Wi t=Ai • choose speeds st and allocations θti to minimize total energy E 2� � �Minimum energy processor speed scheduling • work with variables Sti = θtist n Di st = Sti,Sti ≥ Wi i=1 t=Ai • solve convex problem �Tminimize E = t=1 φ(st) subject to smin ≤ snt ≤ smax , t = 1, . . . , T st = i=1 Sti, t = 1, . . . , T �Di Sti ≥ Wi, i = 1, . . . , n t=Ai • a convex problem when φ is convex • can recover θt⋆ as θ⋆ = (1/s⋆t)S⋆ ti ti 3Example • T = 16 periods, n = 12 jobs smin = 1, smax = 6, φ(st) = s2 • t • jobs shown as bars over [Ai, Di] with area ∝ Wi 40 12 35 1030 25 0 2 4 6 8 10 12 14 16 18 φt (st ) 20 15 10 5 0 job i 8 6 4 2 0 0 1 2 3 4 5 6 7 st t 4Optimal and uniform schedules uniform schedule: Sti = Wi/(Di − Ai + 1); gives Eunif = 204.3• • ti; gives optimal schedule: S⋆ E⋆ = 167.1 optimal uniform 6 6 5 5 4 4 0 2 4 6 8 10 12 14 16 18 st 3 2 1 0 0 2 4 6 8 10 12 14 16 18 s t3 2 1 0 t t 5Minimum-time optimal control • linear dynamical system: xt+1 = Axt + But, t = 0, 1, . . . , K, x0 = x init • inputs constraints: umin � ut � umax, t = 0, 1, . . . , K • minimum time to reach state xdes: f(u0, . . . , uK) = min {T | xt = xdes for T ≤ t ≤ K + 1} 6state transfer time f is quasiconvex function of (u0, . . . , uK): f(u0, u1, . . . , uK) ≤ T if and only if for all t = T, . . . , K + 1 xt = At x init + At−1Bu0 + + But−1 = xdes ··· i.e., sublevel sets are affine minimum-time optimal control problem: minimize f(u0, u1, . . . , uK) subject to umin � ut � umax, t = 0, . . . , K with variables u0, . . . , uK a quasiconvex problem; can be solved via bisection 7Minimum-time control example u1 u2 • force (ut)1 moves object modeled as 3 masses (2 vibration modes) • force (ut)2 used for active vibration suppression • goal: move object to commanded position as quickly as possible, with |(ut)1| ≤ 1, |(ut)2| ≤ 0.1, t = 0, . . . , K 8(xt )3 Ignoring vibration modes • treat object as single mass; apply only u1 • analytical (‘bang-bang’) solution 1 −2 0 2 4 6 8 10 12 14 16 18 20 0 0.5 1 1.5 2 2.5 3 t (ut ) 1 (ut ) 2 0.5 0 −0.5 −1 −2 0 2 4 6 8 10 12 14 16 18 20 t 0.1 0.05 0 −0.05 −0.1 −2 0 2 4 6 8 10 12 14 16 18 20 t 90.5 2 2.5 3 With vibration modes • no analytical solution • a quasiconvex problem; solved using bisection 1 −2 0 2 4 6 8 10 12 14 16 18 20 t (ut ) 2 (ut ) 1 −1 −2 0 2 4 6 8 10 12 14 16 18 20 1.5 t 0.1 1 0.5 0 −0.5 0.05 0 −0.05 −0.1 0 −2 0 2 4 6 8 10 12 14 16 18 20 t 10 (xt )3� Grasp force optimization • choose K grasping forces on object – resist external wrench – respect friction cone constraints – minimize maximum grasp force • convex problem (second-order cone program): minimize maxi �f(i)�2 max contact force subject to � i Q(i)f(i) = fext force equillibrium i p(i) × (Q(i)f(i)) = τext torque equillibrium µif3(i) ≥ � f1(i)2 + f2(i)2 �1/2 friction cone contraints variables f(i) ∈ R3 , i = 1, . . . , K (contact forces) 11Example 12Optimal broadcast transmitter power allocation • m transmitters, mn receivers all at same frequency • transmitter i wants to transmit to n receivers labeled (i, j), j = 1, . . . , n • Aijk is path gain from transmitter k to receiver (i, j) • Nij is (self) noise power of receiver (i, j) • variables: transmitter powers pk, k = 1, . . . , m transmitter i transmitter k receiver (i, j) 13� at receiver (i, j): • signal power: Sij = Aijipi • noise plus interference power: Iij = Aijkpk + Nij k6=i • signal to interference/noise ratio (SINR): Sij/Iij problem: choose pi to maximize smallest SINR: Aijipimaximize min � i,j k6Aijkpk + Nij =i subject to 0 ≤ pi ≤ pmax . . . a (generalized) linear fractional program 14Phased-array antenna beamforming (xi, yi) θ • omnidirectional antenna elements at positions (x1, y1), . . . , (xn, yn) unit plane wave incident from angle θ induces in ith element a signal • j(xi cos θ+yi sin θ−ωt)e(j = √−1, frequency ω, wavelength 2π) 15� demodulate to get output ej(xi cos θ+yi sin θ) ∈ C• • linearly combine with complex weights wi: n y(θ) = wiej(xi cos θ+yi sin θ) i=1 • y(θ) is (complex) antenna array gain pattern • |y(θ)| gives sensitivity of array as function of incident angle θ • depends on design variables Re w, Im w (called antenna array weights or shading coefficients) design problem: choose w to achieve desired gain pattern 16� Sidelobe level minimization make |y(θ)| small for |θ − θtar| > α (θtar: target direction; 2α: beamwidth) via least-squares (discretize angles) minimize i y(θi)2| |subject to y(θtar) = 1 (sum is over angles outside beam) least-squares problem with two (real) linear equality constraints 17θtar = 30◦ 10◦ 50◦ � � ��|y(θ)| ���sidelobe level 18minimize sidelobe level (discretize angles) minimize maxi y(θi)| |subject to y(θtar) = 1 (max over angles outside beam) can be cast as SOCP minimize t subject to y(θi) t| | ≤y(θtar) = 1 19θtar = 30◦ 10◦ 50◦ � � ��|y(θ)| ���sidelobe level 20Extensions convex (& quasiconvex) extensions: • y(θ0) = 0 (null in direction θ0) • w is real (amplitude only shading) • |wi| ≤ 1 (attenuation only shading) • minimize σ2 �in =1 …