API

Quadratic{D, T<:Real, L}
Quadratic(a,b,c)

A struct that represents quadratic polynomial on $\mathbb{R}^D$.

\[\begin{aligned} q(p) &= \frac{1}{2}p^{\intercal} A p + b^{\intercal} p + c \\ A &= \begin{pmatrix} a_1 & a_2 & \cdots & a_D \\ a_2 & a_{D+1} & \cdots & a_{2D-1} \\ \vdots & \vdots & \ddots & \vdots \\ a_D & a_{2D-1} & \cdots & a_{L} \end{pmatrix} \end{aligned}\]

Examples

julia> q = Quadratic{2}([2.0, 1.0, 3.0], [-1.2, -2.3], 4.5)
Quadratic{2, Float64, 3}([2.0, 1.0, 3.0], [-1.2, -2.3], 4.5)

julia> q([1,2])
7.7

M(D::Integer) = (D+2)*(D+1)÷2

Calculate the number of required points for QIM/QFM that is equal to the number of terms in D-dimensional quadratic polynomial.

\[\begin{aligned} M(1) &= 3 \quad (\text{Number of terms in} \ \frac{a_1}{2} x^2 + b_1 x + c) \\ M(2) &= 6 \quad (\text{Number of terms in} \ \frac{a_1}{2} x^2 + a_2 xy + \frac{a_3}{2} y^2 + b_1 x + b_2 y + c) \\ M(0) &= 1 \quad (\text{Number of terms in} \ c) \end{aligned}\]

Examples

julia> using QuadraticOptimizer: M

julia> M(1)  # 3 points to interpolate a parabola
3

julia> M(2)  # 6 points to interpolate a 2-dimensional quadratic
6

julia> M(0)  # 1 point for constant, terms
1

distance(q1::Quadratic, q2::Quadratic; S=I, h=1)

Calculate the distance between two Quadratic instances based on the following expression.

\[\begin{aligned} \operatorname{distance}(q_1, q_2) &= \sqrt{\operatorname{tr}(\Delta A \Delta A) + (\Delta s)^{\intercal}S(\Delta s) + h\Delta h^2} \\ \Delta A &= A_1 - A_2 \\ \Delta s &= s_1 - s_2 \\ \Delta h &= h_1 - h_2 \\ q_1(p) &= (p-s_1)^{\intercal}A_1(p-s_1) + h_1 \\ q_2(p) &= (p-s_2)^{\intercal}A_2(p-s_2) + h_2 \end{aligned}\]

Note that the inputs q1 and q2 must be convex downward to make the function mathematical distance.

Examples

julia> using QuadraticOptimizer: center, distance

julia> q1 = Quadratic{2}(I(2), [-1.0, 0.0], 4.5)
Quadratic{2, Float64, 3}([1.0, 0.0, 1.0], [-1.0, 0.0], 4.5)

julia> q2 = Quadratic{2}(I(2), [1.0, 0.0], 4.5)
Quadratic{2, Float64, 3}([1.0, 0.0, 1.0], [1.0, 0.0], 4.5)

julia> q3 = Quadratic{2}(2I(2), [-2.0, 0.0], 4.5)
Quadratic{2, Float64, 3}([2.0, 0.0, 2.0], [-2.0, 0.0], 4.5)

julia> q4 = Quadratic{2}(2I(2), [2.0, 0.0], 4.5)
Quadratic{2, Float64, 3}([2.0, 0.0, 2.0], [2.0, 0.0], 4.5)

julia> distance(q1, q1), distance(q2, q2), distance(q3, q3), distance(q4, q4)  # a distance to itself is zero
(0.0, 0.0, 0.0, 0.0)

julia> distance(q1, q2), distance(q2, q1)  # symmetric
(2.0, 2.0)

julia> distance(q1, q3), distance(q2, q4)  # translation does not change distance
(1.5, 1.5)

hessian(q::Quadratic)

Calculate the (constant) hessian of the quadratic polynomial.

Examples

julia> using QuadraticOptimizer: hessian

julia> using ForwardDiff

julia> q = Quadratic{2}([2.0, 1.0, 3.0], [-1.2, -2.3], 4.5)
Quadratic{2, Float64, 3}([2.0, 1.0, 3.0], [-1.2, -2.3], 4.5)

julia> hessian(q)
2×2 StaticArrays.SHermitianCompact{2, Float64, 3} with indices SOneTo(2)×SOneTo(2):
 2.0  1.0
 1.0  3.0

julia> ForwardDiff.hessian(q, [1,2])
2×2 Matrix{Float64}:
 2.0  1.0
 1.0  3.0

optimize_qfm!(f, xs::Vector{<:Real}, fs::Vector{<:Real}, n_iter::Integer) -> xs, fs

Optimize a function f using the Quadratic Interpolation Method (QIM).

Arguments

• f: The objective function to be optimized.
• xs: A vector of points in $\mathbb{R}^D$ where f has been evaluated. This vector will be updated in-place during the optimization process.
• fs: A vector of function values corresponding to the points in xs. This vector will be updated in-place during the optimization process.
• n_iter: The number of optimizing iterations. After execution, the length of xs will be N + n_iter, where N = length(xs) before execution.

Examples

julia> using QuadraticOptimizer

julia> f(x) = sin(x) + x^2/10  # Function to minimize
f (generic function with 1 method)

julia> xs_init = [1.2, 0.1, -2.2, -1.0]  # Initial points
4-element Vector{Float64}:
  1.2
  0.1
 -2.2
 -1.0

julia> xs = copy(xs_init);

julia> fs = f.(xs);

julia> optimize_qfm!(f, xs, fs, 5);  # Optimize 5 steps

optimize_qfm!(f, ps::Vector{<:SVector{D, <:Real}}, fs::Vector{<:Real}, n_iter::Integer) -> ps, fs

Optimize a function f using the Quadratic Fitting Method (QFM).

Arguments

• f: The objective function to be optimized.
• ps: A vector of points in $\mathbb{R}^D$ where f has been evaluated. This vector will be updated in-place during the optimization process.
• fs: A vector of function values corresponding to the points in ps. This vector will be updated in-place during the optimization process.
• n_iter: The number of optimizing iterations. After execution, the length of ps will be N + n_iter, where N = length(ps) before execution.

Examples

julia> using QuadraticOptimizer, StaticArrays, Random

julia> Random.seed!(42);

julia> f(p) = p[1]^2 + sin(p[1]) + 1.5p[2]^2 + sinh(p[2]) - p[1]*p[2]/5
f (generic function with 1 method)

julia> ps_init = [@SVector rand(2) for _ in 1:10]
10-element Vector{SVector{2, Float64}}:
 [0.6293451231426089, 0.4503389405961936]
 [0.47740714343281776, 0.7031298490032014]
 [0.6733461456394962, 0.16589443479313404]
 [0.6134782250008441, 0.6683403279577278]
 [0.4570310908017041, 0.2993652953937611]
 [0.6611433726193705, 0.6394313620423493]
 [0.34264792290134793, 0.2678704383989201]
 [0.515871408349502, 0.09002301604339691]
 [0.27265744579429385, 0.191562202596938]
 [0.4235912564725989, 0.4847023673932017]

julia> ps = copy(ps_init);

julia> fs = f.(ps);

julia> optimize_qfm!(f, ps, fs, 20);

optimize_qfm(f, xs_init::Vector{<:Real}, n_iter::Integer) -> xs, fs

Optimize a function f using the Quadratic Interpolation Method (QIM).

Arguments

• f: The objective function to be optimized.
• xs_init: A vector of points in $\mathbb{R}^D$ where f has been evaluated.
• n_iter: The number of optimizing iterations. After execution, the length of xs will be N + n_iter, where N = length(xs) before execution.

Examples

julia> using QuadraticOptimizer

julia> f(x) = sin(x) + x^2/10  # Function to minimize
f (generic function with 1 method)

julia> xs_init = [1.2, 0.1, -2.2]  # Initial points (3 points are required to construct parabola)
3-element Vector{Float64}:
  1.2
  0.1
 -2.2

julia> xs = copy(xs_init)  # Keep initial points
3-element Vector{Float64}:
  1.2
  0.1
 -2.2

julia> xs, fs = optimize_qfm(f, xs, 5);  # Optimize 5 steps

optimize_qfm(f, xs_init::Vector{<:Real}, fs_init::Vector{<:Real}, n_iter::Integer) -> xs, fs

Optimize a function f using the Quadratic Interpolation Method (QIM).

Arguments

• f: The objective function to be optimized.
• xs_init: A vector of points in $\mathbb{R}^D$ where f has been evaluated.
• fs_init: A vector of function values corresponding to the points in xs_init.
• n_iter: The number of optimizing iterations. After execution, the length of xs will be N + n_iter, where N = length(xs) before execution.

Examples

julia> using QuadraticOptimizer

julia> f(x) = sin(x) + x^2/10  # Function to minimize
f (generic function with 1 method)

julia> xs_init = [1.2, 0.1, -2.2]  # Initial points (3 points are required to construct parabola)
3-element Vector{Float64}:
  1.2
  0.1
 -2.2

julia> xs, fs = optimize_qfm(f, xs_init, f.(xs_init), 5);  # Optimize 5 steps

optimize_qfm(f, ps_init::Vector{<:SVector{D, <:Real}}, n_iter::Integer) -> ps, fs

Optimize a function f using the Quadratic Fitting Method (QFM).

Arguments

• f: The objective function to be optimized.
• ps_init: A vector of points in $\mathbb{R}^D$ where f has been evaluated.
• n_iter: The number of optimizing iterations. After execution, the length of ps will be N + n_iter, where N = length(ps) before execution.

Examples

julia> using QuadraticOptimizer, StaticArrays, Random

julia> Random.seed!(42);

julia> f(p) = p[1]^2 + sin(p[1]) + 1.5p[2]^2 + sinh(p[2]) - p[1]*p[2]/5
f (generic function with 1 method)

julia> ps_init = [@SVector rand(2) for _ in 1:10]
10-element Vector{SVector{2, Float64}}:
 [0.6293451231426089, 0.4503389405961936]
 [0.47740714343281776, 0.7031298490032014]
 [0.6733461456394962, 0.16589443479313404]
 [0.6134782250008441, 0.6683403279577278]
 [0.4570310908017041, 0.2993652953937611]
 [0.6611433726193705, 0.6394313620423493]
 [0.34264792290134793, 0.2678704383989201]
 [0.515871408349502, 0.09002301604339691]
 [0.27265744579429385, 0.191562202596938]
 [0.4235912564725989, 0.4847023673932017]

julia> ps, fs = optimize_qfm(f, ps_init, 20);

optimize_qfm(f, ps_init::Vector{<:SVector{D, <:Real}}, fs_init::Vector{<:Real}, n_iter::Integer) -> ps, fs

Optimize a function f using the Quadratic Fitting Method (QFM).

Arguments

• f: The objective function to be optimized.
• ps_init: A vector of points in $\mathbb{R}^D$ where f has been evaluated.
• fs_init: A vector of function values corresponding to the points in ps_init.
• n_iter: The number of optimizing iterations. After execution, the length of ps will be N + n_iter, where N = length(ps) before execution.

Examples

julia> using QuadraticOptimizer, StaticArrays, Random

julia> Random.seed!(42);

julia> f(p) = p[1]^2 + sin(p[1]) + 1.5p[2]^2 + sinh(p[2]) - p[1]*p[2]/5
f (generic function with 1 method)

julia> ps_init = [@SVector rand(2) for _ in 1:10]
10-element Vector{SVector{2, Float64}}:
 [0.6293451231426089, 0.4503389405961936]
 [0.47740714343281776, 0.7031298490032014]
 [0.6733461456394962, 0.16589443479313404]
 [0.6134782250008441, 0.6683403279577278]
 [0.4570310908017041, 0.2993652953937611]
 [0.6611433726193705, 0.6394313620423493]
 [0.34264792290134793, 0.2678704383989201]
 [0.515871408349502, 0.09002301604339691]
 [0.27265744579429385, 0.191562202596938]
 [0.4235912564725989, 0.4847023673932017]

julia> ps, fs = optimize_qfm(f, ps_init, f.(ps_init), 20);

optimize_qim!(f, xs::Vector{<:Real}, fs::Vector{<:Real}, n_iter::Integer) -> xs, fs

Optimize a function f using the Quadratic Interpolation Method (QIM).

Arguments

• f: The objective function to be optimized.
• xs: A vector of points in $\mathbb{R}^D$ where f has been evaluated. This vector will be updated in-place during the optimization process.
• fs: A vector of function values corresponding to the points in xs. This vector will be updated in-place during the optimization process.
• n_iter: The number of optimizing iterations. After execution, the length of xs will be N + n_iter, where N = length(xs) before execution.

Examples

julia> using QuadraticOptimizer

julia> f(x) = sin(x) + x^2/10  # Function to minimize
f (generic function with 1 method)

julia> xs_init = [1.2, 0.1, -2.2]  # Initial points (3 points are required to construct parabola)
3-element Vector{Float64}:
  1.2
  0.1
 -2.2

julia> xs = copy(xs_init);

julia> fs = f.(xs);

julia> optimize_qim!(f, xs, fs, 10);  # Optimize 10 steps

optimize_qim!(f, ps::Vector{<:SVector{D, <:Real}}, fs::Vector{<:Real}, n_iter::Integer) -> ps, fs

Optimize a function f using the Quadratic Interpolation Method (QIM).

Arguments

• f: The objective function to be optimized.
• ps: A vector of points in $\mathbb{R}^D$ where f has been evaluated. This vector will be updated in-place during the optimization process.
• fs: A vector of function values corresponding to the points in ps. This vector will be updated in-place during the optimization process.
• n_iter: The number of optimizing iterations. After execution, the length of ps will be N + n_iter, where N = length(ps) before execution.

Examples

julia> using QuadraticOptimizer, StaticArrays, Random

julia> Random.seed!(42);

julia> f(p) = p[1]^2 + sin(p[1]) + 1.5p[2]^2 + sinh(p[2]) - p[1]*p[2]/5
f (generic function with 1 method)

julia> ps_init = [@SVector rand(2) for _ in 1:6]
6-element Vector{SVector{2, Float64}}:
 [0.6293451231426089, 0.4503389405961936]
 [0.47740714343281776, 0.7031298490032014]
 [0.6733461456394962, 0.16589443479313404]
 [0.6134782250008441, 0.6683403279577278]
 [0.4570310908017041, 0.2993652953937611]
 [0.6611433726193705, 0.6394313620423493]

julia> ps = copy(ps_init);

julia> fs = f.(ps);

julia> optimize_qim!(f, ps, fs, 20);

optimize_qim(f, xs_init::Vector{<:Real}, n_iter::Integer) -> xs, fs

Optimize a function f using the Quadratic Interpolation Method (QIM).

Arguments

• f: The objective function to be optimized.
• xs_init: A vector of points in $\mathbb{R}^D$ where f has been evaluated.
• n_iter: The number of optimizing iterations. After execution, the length of xs will be N + n_iter, where N = length(xs) before execution.

Examples

julia> using QuadraticOptimizer

julia> f(x) = sin(x) + x^2/10  # Function to minimize
f (generic function with 1 method)

julia> xs_init = [1.2, 0.1, -2.2]  # Initial points (3 points are required to construct parabola)
3-element Vector{Float64}:
  1.2
  0.1
 -2.2

julia> xs = copy(xs_init)  # Keep initial points
3-element Vector{Float64}:
  1.2
  0.1
 -2.2

julia> xs, fs = optimize_qim(f, xs, 10);  # Optimize 10 steps

optimize_qim(f, xs_init::Vector{<:Real}, fs_init::Vector{<:Real}, n_iter::Integer) -> xs, fs

Optimize a function f using the Quadratic Interpolation Method (QIM).

Arguments

• f: The objective function to be optimized.
• xs_init: A vector of points in $\mathbb{R}^D$ where f has been evaluated.
• fs_init: A vector of function values corresponding to the points in xs_init.
• n_iter: The number of optimizing iterations. After execution, the length of xs will be N + n_iter, where N = length(xs) before execution.

Examples

julia> using QuadraticOptimizer

julia> f(x) = sin(x) + x^2/10  # Function to minimize
f (generic function with 1 method)

julia> xs_init = [1.2, 0.1, -2.2]  # Initial points (3 points are required to construct parabola)
3-element Vector{Float64}:
  1.2
  0.1
 -2.2

julia> xs, fs = optimize_qim(f, xs_init, f.(xs_init), 10);  # Optimize 10 steps

optimize_qim(f, ps_init::Vector{<:SVector{D, <:Real}}, n_iter::Integer) -> ps, fs

Optimize a function f using the Quadratic Interpolation Method (QIM).

Arguments

• f: The objective function to be optimized.
• ps_init: A vector of points in $\mathbb{R}^D$ where f has been evaluated.
• n_iter: The number of optimizing iterations. After execution, the length of ps will be N + n_iter, where N = length(ps) before execution.

Examples

julia> using QuadraticOptimizer, StaticArrays, Random

julia> Random.seed!(42);

julia> f(p) = p[1]^2 + sin(p[1]) + 1.5p[2]^2 + sinh(p[2]) - p[1]*p[2]/5
f (generic function with 1 method)

julia> ps_init = [@SVector rand(2) for _ in 1:6]
6-element Vector{SVector{2, Float64}}:
 [0.6293451231426089, 0.4503389405961936]
 [0.47740714343281776, 0.7031298490032014]
 [0.6733461456394962, 0.16589443479313404]
 [0.6134782250008441, 0.6683403279577278]
 [0.4570310908017041, 0.2993652953937611]
 [0.6611433726193705, 0.6394313620423493]

julia> ps, fs = optimize_qim(f, ps_init, 10);

optimize_qim(f, ps_init::Vector{<:SVector{D, <:Real}}, fs_init::Vector{<:Real}, n_iter::Integer) -> ps, fs

Optimize a function f using the Quadratic Interpolation Method (QIM).

Arguments

• f: The objective function to be optimized.
• ps_init: A vector of points in $\mathbb{R}^D$ where f has been evaluated.
• fs_init: A vector of function values corresponding to the points in ps_init.
• n_iter: The number of optimizing iterations. After execution, the length of ps will be N + n_iter, where N = length(ps) before execution.

Examples

julia> using QuadraticOptimizer, StaticArrays, Random

julia> Random.seed!(42);

julia> f(p) = p[1]^2 + sin(p[1]) + 1.5p[2]^2 + sinh(p[2]) - p[1]*p[2]/5
f (generic function with 1 method)

julia> ps_init = [@SVector rand(2) for _ in 1:6]
6-element Vector{SVector{2, Float64}}:
 [0.6293451231426089, 0.4503389405961936]
 [0.47740714343281776, 0.7031298490032014]
 [0.6733461456394962, 0.16589443479313404]
 [0.6134782250008441, 0.6683403279577278]
 [0.4570310908017041, 0.2993652953937611]
 [0.6611433726193705, 0.6394313620423493]

julia> ps, fs = optimize_qim(f, ps_init, f.(ps_init), 20);

quadratic_fitting(ps::AbstractVector{<:StaticVector{D, <:Real}}, fs::AbstractVector{<:Real}) where D

Calculate quadratic fitting based on input values.

Examples

julia> using QuadraticOptimizer, StaticArrays, Random

julia> Random.seed!(42);

julia> q = Quadratic{2}([2,1,3], [1,2], 2)
Quadratic{2, Int64, 3}([2, 1, 3], [1, 2], 2)

julia> ps = [@SVector rand(2) for _ in 1:6]
6-element Vector{SVector{2, Float64}}:
 [0.6293451231426089, 0.4503389405961936]
 [0.47740714343281776, 0.7031298490032014]
 [0.6733461456394962, 0.16589443479313404]
 [0.6134782250008441, 0.6683403279577278]
 [0.4570310908017041, 0.2993652953937611]
 [0.6611433726193705, 0.6394313620423493]

julia> quadratic_fitting(vcat(ps, ps), vcat(q.(ps).-1, q.(ps).+1))
Quadratic{2, Float64, 3}([2.000000000387182, 0.9999999999890256, 2.999999999972893], [0.9999999997884512, 2.0000000000207985], 2.000000000052808)

quadratic_interpolation(ps::AbstractVector{<:StaticVector{D, <:Real}}, fs::AbstractVector{<:Real}) where D

Calculate quadratic interpolation based on input values.

Examples

julia> using QuadraticOptimizer, StaticArrays, Random

julia> Random.seed!(42);

julia> q = Quadratic{2}([2,1,3], [1,2], 2)
Quadratic{2, Int64, 3}([2, 1, 3], [1, 2], 2)

julia> ps = [@SVector rand(2) for _ in 1:6]
6-element Vector{SVector{2, Float64}}:
 [0.6293451231426089, 0.4503389405961936]
 [0.47740714343281776, 0.7031298490032014]
 [0.6733461456394962, 0.16589443479313404]
 [0.6134782250008441, 0.6683403279577278]
 [0.4570310908017041, 0.2993652953937611]
 [0.6611433726193705, 0.6394313620423493]

julia> quadratic_interpolation(ps, q.(ps))
Quadratic{2, Float64, 3}([1.9999999999997884, 0.999999999999996, 2.999999999999987], [1.0000000000001212, 2.0000000000000053], 1.999999999999966)