using discontinuous function as objective function in optimization

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

  1. Gino Linus

    Gino Linus Guest

    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
    #1
    1. Advertisements

  2. Hans Mittelmann, Sep 3, 2007
    #2
    1. Advertisements

  3. Gino Linus

    Gino Linus Guest

    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
    #3
  4. 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
    #4
  5. Gino Linus

    Gino Linus Guest

    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
    #5
  6. 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
    #6
  7. Gino Linus

    Gino Linus Guest

    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
    #7
  8. Gino Linus

    Gino Linus Guest

    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
    #8
  9. Gino Linus

    Puppet_Sock Guest

    [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
    #9
  10. Gino Linus

    Gino Linus Guest

    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
    #10
  11. Gino Linus

    medvall Guest

    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
    #11
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.