X hits on this document

13 views

0 shares

0 downloads

0 comments

4 / 6

1.2

Reformulation

For many optimization problems simple ”tricks” can transform a difficult problem into a much simpler one. Thus, before solving a particular problem it is worth while checking if there is a different equivalent problem which is easier to solve.

1.2.1

Adding

constraints

to

avoid

nondi

erentiability

May be the most common transformation is from problems with non-differentiable objective to one with differentiable objective and inequality constraints.

Example 5 L1 minimization Consider the following optimization problem which arises in signal processing

kxk1 =

X

Ax = b

i

|xi|

min

s.t

(1.7)

The objective function is not di erentiable at 0. To obtain a di erentiable objective we set

x=p

q;

p, q 0

It is then easy to check that the problem is equivalent to

min

X

p i

  • +

    qi

(1.8)

i

s.t

A(p

q) = b

p, q 0

(1.9)

The new objective function is obviously di erentiable but we have two inequality constraints.

Example 6 Lminimization Consider a similar problem to the previous

min

kxk= max |xi|

s.t

Ax = b

(1.10)

In this case the max function is non-di erentiable. Once again it is easy to convert the problem to a di erentiable one by introducing a new scalar variable t

min

t

s.t

Ax = b

t xi t

(1.11)

(1.12)

4

Document info
Document views13
Page views13
Page last viewedFri Dec 02 20:14:28 UTC 2016
Pages6
Paragraphs235
Words1702

Comments