Chebyshev Polynomials

[dominik...@googlemail.com]

Hi

im trying to use Chebyshev Polynomials in an AMPL code. I use knitro as solver.

The vector of order id in 0..max(NE)-1 chebycheff polynomials evaluated at all values of the 3D variable x is

var Tx {id in NE,iE in NE, iEY in NEY, iw in NW}   =   if id = 1 then 1
                                                                              else if id = 2 then x[iE,iEY,iw]
                                                                              else           2*x[iE,iEY,iw]*Tx [id-1,iE,iEY,iw]-Tx [id-2,iE,iEY,iw];

where NE = 1..10;

Now AMPL seems happy with that when i set up the model.
But when i try to solve it with knitro i get something like:

Knitro: bad line at path1468.nl

If on the contrary i use the follwoing knitro works

var Tx {id in NE,iE in NE, iEY in NEY, iw in NW} = if id = 1 then 1
                                               else if id = 2 then x[iE,iEY,iw]
                                               else if id < 9 then     2*x[iE,iEY,iw]*Tx [id-1,iE,iEY,iw]-Tx [id-2,iE,iEY,iw]
                                                else 1;

I thought there might be some maximum level of recursiveness that Knitro allows for. So i spelled out the recursive formula for the Chebyshev Polynomials for the last two orders, but it didnt work either.

var Tx {id in NEY, iE in NE, iEY in NEY, iw in NW} = if id = 1 then 1
                                                  else if id = 2 then x[iE,iEY,iw]
                                                  else if id < 9 then 2*x[iE,iEY,iw]*Tx [id-1,iE,iEY,iw]-Tx [id-2,iE,iEY,iw]
                                                  else if id = 9 then 128*(x[iE,iEY,iw])^8-256*(x[iE,iEY,iw])^6+160*(x[iE,iEY,iw])^4-32*(x[iE,iEY,iw])^2+1
                                                  else         256*(x[iE,iEY,iw])^9-576*(x[iE,iEY,iw])^7+432*(x[iE,iEY,iw])^5-120*(x[iE,iEY,iw])^3+9*x[iE,iEY,iw];

Is there a maximum of if statements that knitro is willing to accept? Or what might be wrong?

Any thoughts?

Many thanks
Dominik

[Robert Fourer]

The file path1468.nl is written by AMPL and contains the complete problem instance that AMPL generated from your model and data.  The error message indicates a bug either in writing or reading the file.  Can you post or send us an example that would enable us to recreate this error?  Then it should get fixed pretty quickly.

 

The complexity of your model lies in the chain of variable definitions, which the AMPL translator and the AMPL-solver interface have to deal with.  However, internal to KNITRO these complexities are not visible, since KNITRO interacts with the optimization problem only by asking AMPL to compute function and gradient values at particular iterates.

 

Bob Fourer

am...@googlegroups.com

 

 

From: am...@googlegroups.com [mailto:am...@googlegroups.com]

On Behalf Of dominik...@googlemail.com
Sent: Monday, March 10, 2014 3:20 PM
To: am...@googlegroups.com
Subject: [AMPL 8177] Chebyshev Polynomials

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at http://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Dominik Thaler]

Dear Bob

im writing you in response to your answer on the AMPL googlegroup.
https://groups.google.com/forum/#!topic/ampl/T2shEotNQ4Q

First of all, thank you very much for taking the time to adress my problems.

Attached you find the code that i am trying to get running. Also the data file is needed.

When option presolve=0 the code runs. When presolve is > 0 the error appears. As i wrote in my post, the problem seems to be realted to the recursive definiton of TEYv and TEv.

What the code is trying to do is to solve an equation system. These are intertemporal equilibrium conditions (from an economic model) for each point on a grid (discretization of the continous state). SInce they are intertemporal both c,l2(state_today) and c,l2(state_tomorrow) appear. c,l2(state_today) on the grid points of the state defines a approximating Chebyshev Polynomial of c that is used for c(state_tomorrow) for the continous state space. Once i get this working, these conditions would become the constraints to a maximization problem over G. But so far, truning of presolve, it doesnt converge, im working on providing better starting points by backwards induction.

I kept this description short, if you need more information on the background please let me know.

Can you tell me what's wrong?

Furthermore, on a different issue, i had also been asking for multidimensional interpolation in a different post to which u answered:
https://groups.google.com/forum/#!topic/ampl/sshf5pqrJWI

The reason is that im not really happy about using a global approximation though Chebyshev Polynomials. This is because i have no experience with them and im not sure how stable they are in my context, where during the solver run the approximation function changes all the time. Furthermore there might be kinks in the function that is to be appoximated. Therefore i'd prefer a piecewise approximation by interpolation (linear, spline, finite elements...).

Answering to this question you wrote that you are working on a draft. When would you anticipate this would become available ? And in what manner (as an extension, with the next release,...)?

Thanks a lot for your suport, I greatly appreciate that.

Looking forward to hearing from you!

Best

Dominik

[Robert Fourer]

I have reported this as a probable bug in the AMPL-KNITRO interface, and I will post a notice when it is fixed or otherwise explained.  I expect to get a solution within the next week.

 

Bob Fourer

am...@googlegroups.com

 

 

From: am...@googlegroups.com [mailto:am...@googlegroups.com]

On Behalf Of Dominik Thaler
Sent: Saturday, March 15, 2014 3:34 PM
To: am...@googlegroups.com
Subject: [AMPL 8215] Chebyshev Polynomials

--

[dominik...@googlemail.com]

Thanks!!!!

[Robert Fourer]

This error turned out to be due to a bug in how AMPL processes
complementarity constraints in certain (uncommon) conditions. Here is the
official report:

20140320
Fix a bug with problems with general complementarity conditions
(expr1 >= 0 complements expr2 >= 0 where neither expression is
linear in just one variable) and some partially linear nonlinear
defined variables. The example that revealed the bug resulted in
an invalid .nl file.

(The bug only appeared when presolve was turned on, because presolved
simplified the problem to a form where conditions for the bug occurred.)
Versions of AMPL dated 20140320 or later will contain this fix.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of
Dominik Thaler
Sent: Saturday, March 15, 2014 3:34 PM
To: am...@googlegroups.com
Subject: [AMPL 8215] Chebyshev Polynomials