[PDF] [PDF] Convex optimization examples

[PDF] Convex optimization examples

Convex optimization examples • multi-period processor speed scheduling • minimum time optimal control • grasp force optimization • optimal broadcast 

[PDF] 4 Convex optimization problems

example: minimize f0(x) = −∑ k i=1 log(bi − aT i x) is an unconstrained problem with implicit constraints a T i x

[PDF] 4 Convex optimization problems

example: minimize f0(x) = −∑ k i=1 log(bi − aT i x) is an unconstrained problem with implicit constraints a T i x

[PDF] Introduction to Convex Optimization for Machine Learning - People

Example: Stock market “Minimize variance of return subject to getting at least $50 ” Duchi (UC Berkeley) Convex Optimization for Machine Learning Fall 2009

[PDF] A Tutorial on Convex Optimization - UBC ECE

The goal of this tutorial is to give an overview of the basic concepts of convex sets , functions and convex optimization problems, so that the reader can more readily  

[PDF] Convex optimization: applications, formulations, relaxations

Optimization of electricity production Examples of applications of convex optimization 1 Optimization of electricity production 2 Low-rank penalization for  

[PDF] Part I Formulation of convex optimization problems

Formulation of convex optimization problems Instituto Definition (Convex set) Let V be a vector space over R (usually, V = R More examples of convex sets:

[PDF] Convex Optimization - SIAM

(Indeed, they can be recast as minimization problems of convex functions by multiplying the objective function by minus one ) Example 8 4 The problem min −2x1 

[PDF] Convex Optimization

26 août 2008 · Solving Optimization Problems • Least-Squares • Linear Optimization • Convex Optimization • Practical Example • Ongoing Research in 

[PDF] convex optimization unique solution

[PDF] convocation centrale oral

[PDF] convocation centrale oraux

[PDF] convocation centrale supelec 2019

[PDF] convocation concours centrale

[PDF] convocation concours polytechnique 2020

[PDF] coo form a1

[PDF] coo form aanzfta

[PDF] coo form ai

[PDF] coo form ak

[PDF] cookies business plan pdf

[PDF] cool alt codes

[PDF] cooling period for schengen visa

[PDF] cop21

[PDF] cop21 highlights

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 speedst?[smin,smax]in each ofTtime periods •energy consumed in periodtisφ(st); total energy isE=?Tt=1φ(st)

•njobs

-jobiavailable att=Ai; must finish by deadlinet=Di -jobirequires total workWi≥0 •θti≥0is fraction of processor effort allocated to jobiin periodt 1

Tθt= 1,D

i? t=Aiθ tist≥Wi •choose speedsstand allocationsθtito minimize total energyE 2

Minimum energy processor speed scheduling

•work with variablesSti=θtist

s t=n? i=1S ti,D i? t=AiS ti≥Wi

•solve convex problem

minimizeE=?Tt=1φ(st) s t=?ni=1Sti, t= 1,...,T?Dit=AiSti≥Wi, i= 1,...,n

•a convex problem whenφis convex

•can recoverθ?tasθ?ti= (1/s?t)S?ti

3

Example

•T= 16periods,n= 12jobs

•smin= 1,smax= 6,φ(st) =s2t

•jobs shown as bars over[Ai,Di]with area?Wi

0 1 2 3 4 5 6 7

0510152025303540

st

φ(st)

0 2 4 6 8 10 12 14 16 18

024681012jobi

t 4

Optimal and uniform schedules

•uniform schedule:Sti=Wi/(Di-Ai+ 1); givesEunif= 204.3

•optimal schedule:S?ti; givesE?= 167.1

0 2 4 6 8 10 12 14 16 18

0123456st

t optimal 0 2 4 6 8 10 12 14 16 18

0123456st

tuniform 5

Minimum-time optimal control

•linear dynamical system:

x t+1=Axt+But, t= 0,1,...,K, x0=xinit

•inputs constraints:

u min?ut?umax, t= 0,1,...,K

•minimum time to reach statexdes:

6 state transfer timefis quasiconvex function of(u0,...,uK): if and only if for allt=T,...,K+ 1 x i.e., sublevel sets are affine minimum-time optimal control problem: minimizef(u0,u1,...,uK) subject toumin?ut?umax, t= 0,...,K with variablesu0,...,uK a quasiconvex problem; can be solved via bisection 7

Minimum-time control example

u1 u 2 •force(ut)1moves object modeled as 3 masses (2 vibration modes) •force(ut)2used for active vibration suppression •goal: move object to commanded position as quickly as possible, with 8

Ignoring vibration modes

•treat object as single mass; apply onlyu1

•analytical ('bang-bang") solution

-2 0 2 4 6 8 10 12 14 16 18 20

00.511.522.53(xt)3

t -2 0 2 4 6 8 10 12 14 16 18 20 -1-0.5

00.51-2

0 2 4 6 8 10 12 14 16 18 20 -0.1-0.05 0

0.050.1

tt (ut)1(ut)2 9

With vibration modes

•no analytical solution

•a quasiconvex problem; solved using bisection

-2 0 2 4 6 8 10 12 14 16 18 20

00.511.522.53(xt)3

t -2 0 2 4 6 8 10 12 14 16 18 20 -1-0.5

00.51-2

0 2 4 6 8 10 12 14 16 18 20 -0.1-0.05 0

0.050.1

tt (ut)1(ut)2 10

Grasp force optimization

•chooseKgrasping forces on object

-resist external wrench -respect friction cone constraints -minimize maximum grasp force

•convex problem (second-order cone program):

minimizemaxi?f(i)?2max contact force subject to? iQ(i)f(i)=fextforce equillibrium? ip(i)×(Q(i)f(i)) =τexttorque equillibrium if(i)

3≥?

f(i)2

1+f(i)2

2?

1/2friction cone constraints

variablesf(i)?R3,i= 1,...,K(contact forces) 11

Example

12

Optimal broadcast transmitter power allocation

•mtransmitters,mnreceivers all at same frequency •transmitteriwants to transmit tonreceivers labeled(i,j),j= 1,...,n •Aijkis path gain from transmitterkto receiver(i,j)

•Nijis (self) noise power of receiver(i,j)

•variables: transmitter powerspk,k= 1,...,m

transmitteritransmitterk receiver(i,j) 13 at receiver(i,j):

•signal power:

S ij=Aijipi

•noise plus interference power:

I ij=? k?=iA ijkpk+Nij •signal to interference/noise ratio (SINR):Sij/Iij problem:choosepito maximize smallest SINR: maximizemini,jA ijipi k?=iAijkpk+Nij . . . a (generalized) linear fractional program 14

Phased-array antenna beamforming

(xi,yi) •omnidirectional antenna elements at positions(x1,y1), . . . ,(xn,yn) •unit plane wave incident from angleθinduces inith element a signal e j(xicosθ+yisinθ-ωt) (j=⎷-1, frequencyω, wavelength2π) 15 •demodulate to get outputej(xicosθ+yisinθ)?C

•linearly combine with complex weightswi:

y(θ) =n? i=1w iej(xicosθ+yisinθ)

•y(θ)is (complex)antenna array gain pattern

• |y(θ)|gives sensitivity of array as function of incident angleθ

•depends on design variablesRew,Imw

(calledantenna array weightsorshading coefficients) design problem:choosewto 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 toy(θtar) = 1 (sum is over angles outside beam) least-squares problem with two (real) linear equality constraints 17

θtar= 30◦50

10 ???|y(θ)| ??sidelobe level 18 minimize sidelobe level(discretize angles) minimizemaxi|y(θi)| subject toy(θtar) = 1 (max over angles outside beam) can be cast as SOCP minimizet y(θtar) = 1 19

θtar= 30◦50

10 ???|y(θ)| ??sidelobe level 20

Extensions

convex (& quasiconvex) extensions:

•y(θ0) = 0(null in directionθ0)

•wis real (amplitude only shading)

•minimizeσ2?ni=1|wi|2(thermal noise power iny) •minimize beamwidth given a maximum sidelobe level nonconvex extension:

•maximize number of zero weights

21

Optimal receiver location

•Ntransmitter frequencies1,...,N

•transmitters at locationsai, bi?R2use frequencyi •transmitters ata1,a2, . . . ,aNare the wanted ones •transmitters atb1,b2, . . . ,bNare interfering

•receiver at positionx?R2

x b1? b2? b3 a1? a2? a3 22
•(signal) receiver power fromai:?x-ai?-α2(α≈2.1) •(interfering) receiver power frombi:?x-bi?-α2(α≈2.1) •worst signal to interference ratio, over all frequencies, is

S/I= mini?x-ai?-α2

?x-bi?-α2

•what receiver locationxmaximizes S/I?

23

S/I is quasiconcave on{x|S/I≥1},i.e., on

?b1? b2? b3 a1? a2? a3 can use bisection; every iteration is a convex quadratic feasibility problem 24
quotesdbs_dbs17.pdfusesText_23