Searching for a simple polynomial curve fitting example

question

#1

Im new to mathematical optimisation, so I’m looking for a simple example I can learn from …

My (initial) problem looks like
1000 cartesian points in Float16
I want to find a polynomial p(x) (to be evaluated in Float16) to fit these points.

Conceptually
my constraints are |p(x) - y| <= \text{ulp}(y) and
the objective is \text{Min} of \text{norm(|p(x) - y|, Inf)}

But Im not seeing how to declare it within JuMP and I haven’t found a suitable example to learn from.

Any pointers ?

thanks in advance,
JT

Edit: I corrected the constraints refer to \text{ulp}(y) instead of x.


#2

You can use linear programming if you transform your model as follows:

Minimize t
s.t.
     -t <= p(x) - y <= t for each (x,y)

It’s an LP in the parameters of p(x).

using JuMP
using GLPKMathProgInterface
#using Clp

function fit_poly_inf_norm(x,y,n)
    m = Model(solver=GLPKSolverLP())
    #m = Model(solver=ClpSolver())
    @variable(m, alpha[1:n+1])
    @variable(m, t >= 0.)
    @constraint(m, [i=1:length(y)], sum(alpha[j]*x[i]^(j-1) for j in 1:n+1) - y[i] <= t);
    @constraint(m, [i=1:length(y)], -t <= sum(alpha[j]*x[i]^(j-1) for j in 1:n+1) - y[i]);
    @objective(m, Min, t)
    solve(m)
    return getvalue(alpha)
end

x = rand(100)
y = rand(100)
n = 4 #order
coeffs = fit_poly_inf_norm(x,y,n)

There are plenty of examples in https://github.com/JuliaOpt/JuMP.jl/tree/master/examples and http://www.juliaopt.org/JuMP.jl/0.18/.


#3

Thanks Mohamed.

I had found (many of) the examples, but failed to recognise my problem in the Julia implementation.
But I think I can easily extend this to solve my problem.

thanks again,
JT