# using discontinuous function as objective function in optimization

Discussion in 'Maple' started by Gino Linus, Sep 2, 2007.

1. ### Gino LinusGuest

HI all,

In my LSQ optimization problem, the objective function is defined by

f(x) = sum( (d_i - g_i(x))^2, i from 1 to n),

where d_i's are data points and g_i(x) are fitted values.

The goal above is to find the best x satisfying the linear and non-linear
constraints such that f(x) is minimized.

If, instead of hte LSQ problem above, I would like to define the objective
function to be:

f(x) = sum( abs(d_i - g_i(x)), i from 1 to n),

is this completely impossible? I heard this is a dangerous thing to do
because it will make gradient based methods fail.

I've also heard that there might be some tricks to get around this problem,
by transform the problem into another problem.

Here is my plan:

Define a new objective function by:

f(x) = sum( e_i , i from 1 to n)

s.t.

- e_i <= d_i - g_i(x) <= e_i

and other previous linear and non-linear constraints...

And in this new formulation, the variables are the e_i's and the original x.

So I will have a lot more variables to optimiz over. I am worried about the
performance of the above formulation.

Am I correct in this formulation?

Are there good solvers for this purpose? Will Matlab's "fmincon" do this job
well? Any cautions that I need to pay attention to?

Thanks a lot!

Gino Linus, Sep 2, 2007

2. ### Hans MittelmannGuest

Hans Mittelmann, Sep 3, 2007

3. ### Gino LinusGuest

Thanks Hans. Will my fomulation give me any advantage over choosing to
minimize the Sum of Squares as an objective function?

And thanks for the recommendation of IPOPT. What's the goodness about it? (I
probably won't be able to learn AMPL or GAMS so fast to submit the job to
NEOS...)

Gino Linus, Sep 3, 2007
4. ### Robert IsraelGuest

Minimizing the sum of absolute values rather than the sum of squares makes it
more sensitive to small differences and less sensitive to large differences.
In the simple one-dimensional case with data x_1,...,x_n
minimize sum_j |x - x_j| gives you the median, while
minimize sum_j (x - x_j)^2 gives you the mean.

Robert Israel, Sep 3, 2007
5. ### Gino LinusGuest

Thanks Hans.

But here is my design constraints: I don't knwo AMPL and probably it is hard
for me to switch to AMPL and to get it work.

And if I fail here and there, my boss will definitely discourage me to
explore further because of the project deadline doesn't allow us to deviate.

I did go through all the steps and successfully made IPOPT and its Matlab
interface work, only to find that it requires a gradent. But I won't be able
to supply gradient, because it is very hard to derive, and also very costly
to compute numerically.

Is there a way to bypass gradient in IPOPT?

Are there other "strong" optimizers?

Thanks!

Gino Linus, Sep 5, 2007
6. ### Hans MittelmannGuest

Hi,
IPOPT-Mex can be made with automatic differentiation. But you first
need to obtain this from the author. If you have other linear and
nonlinear constraints but your problem is not too large, try the free
solver SOLNP (computes
numerical derivative for you), check out SQPLab. If you want to avoid
derivatives entirely, use NOMADm. Your problem and the conditions you
have don't make it easy...

Hans Mittelmann, Sep 5, 2007
7. ### Gino LinusGuest

Very good! If AD works with IPOPT and IPOPT-Mex, then that's great! Does AD
work with any objective function? My objective function has an 6D integral
that I am using Monte Carlo in evaluating it.

SOLNP is inside SQPLab?

I guess I shouldn't avoid dierivative entirely, at least I should it solver
to compute the numerical differences... otherwise it becomes a weak,
simulated-annealing type solver, which doesn't rely on gradient at all...

Gino Linus, Sep 5, 2007
8. ### Gino LinusGuest

Looks there is no way to download SQPLab... As an initial trial, I used
Matlab's fmincon.

It seems there are lots of local minima for this formulation of problem.
Probably it is so by its very nature?

Gino Linus, Sep 6, 2007
9. ### Puppet_SockGuest

[re minimize sum of sq diffs, vs sum of absolute diffs, vs other
plans]

The sum-of-squares thing vs the sum-of-abs is fairly intuitive.
Because you are minimizing different things, you are weighting
different points more heavily, just as Robert Israel said.

What you need to do is, decide what your fit is supposed to
get for you. For example: Do you want your fit to be insensitive
to a few points that are very far off the main set of data? Or do
you want your fit to respond to these points? You may want
to use very different kinds of fits for different situations. There
is an entire "industry" of picking and designing such fitting.

There is a very brief intro to such things in _Numerical Recipes
in C_ by Press et al. That should only be treated as a first
step in understanding such things, as the text is not meant
to be the only text you read on such things.
Socks

Puppet_Sock, Sep 6, 2007
10. ### Gino LinusGuest

Yes, I want to use sum-of-abs as objective function and I found the
optimization w.r.t this objective function is quite hard, using the
formulation we've discussed above. Lots of local minima.

Gino Linus, Sep 7, 2007
11. ### medvallGuest

L1Solve will take care of the reformualtion for you automatically, and
also exploit the sparsity in full. Feel free to send me a test case.

Best wishes, Marcus
Tomlab Optimization Inc.
http://tomopt.com

medvall, Sep 12, 2007