X hits on this document

23 views

0 shares

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

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 views 23 Page views 23 Page last viewed Tue Jan 24 16:15:25 UTC 2017 Pages 6 Paragraphs 235 Words 1702