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 L_{1 }minimization Consider the following optimization problem which arises in signal processing

kxk_{1 }=

X

Ax = b

i

|x_{i}|

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

+

q

_{i }

(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 L_{∞ }minimization Consider a similar problem to the previous

min

kxk_{∞ }= max |x_{i}|

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 ≤ x_{i }≤ t

(1.11)

(1.12)

4