Lecture 2 Piecewise-linear optimization

L. Vandenberghe

EE236A (Fall 2013-14)

Lecture 2 Piecewise-linear optimization

? piecewise-linear minimization ? 1- and -norm approximation ? examples ? modeling software

2?1

Linear and affine functions

linear function: a function f : Rn R is linear if f (x + y) = f (x) + f (y) x, y Rn, , R

property: f is linear if and only if f (x) = aT x for some a

affine function: a function f : Rn R is affine if f (x + (1 - )y) = f (x) + (1 - )f (y) x, y Rn, R

property: f is affine if and only if f (x) = aT x + b for some a, b

Piecewise-linear optimization

2?2

Piecewise-linear function

f : Rn R is (convex) piecewise-linear if it can be expressed as f (x) = i=m1,a..x.,m(aTi x + bi)

f is parameterized by m n-vectors ai and m scalars bi

f (x)

aTi x + bi x

(the term piecewise-affine is more accurate but less common)

Piecewise-linear optimization

2?3

Piecewise-linear minimization

minimize f (x) = i=m1,a..x.,m(aTi x + bi)

? equivalent LP (with variables x and auxiliary scalar variable t) minimize t subject to aTi x + bi t, i = 1, . . . , m

to see equivalence, note that for fixed x the optimal t is t = f (x)

? LP in matrix notation: minimize c~T x~ subject to A~x~ ~b with

x~ =

x t

,

c~ =

0 1

,

A~ =

a..T1

-1 .. ,

aTm -1

~b =

-..b1

-bm

Piecewise-linear optimization

2?4

Minimizing a sum of piecewise-linear functions

minimize f (x) + g(x) = i=m1,a..x.,m(aTi x + bi) + i=m1,a..x.,p(ciT x + di) ? cost function is piecewise-linear: maximum of mp affine functions

f (x) + g(x) = max (ai + cj)T x + (bi + dj) i=1,...,m j=1,...,p

? equivalent LP with m + p inequalities

minimize t1 + t2 subject to aTi x + bi t1,

cTi x + di t2,

i = 1, . . . , m i = 1, . . . , p

note that for fixed x, optimal t1, t2 are t1 = f (x), t2 = g(x)

Piecewise-linear optimization

2?5

? equivalent LP in matrix notation

minimize c~T x~ subject to A~x~ ~b

with

x x~ = t1 ,

t2

0 c~ = 1 ,

1

a..T1

A~ =

aTm c..T1

cTp

-1 0 .. ..

-1 0

0 -1

,

..

..

0 -1

-..b1

~b

=

-bm -..d1

-dp

Piecewise-linear optimization

2?6

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download