Performance is far from satisfying #344
Comments
|
The default implementation has not be thoroughly optimized, you should try using QHull or CDDLib by using, e.g, |
|
But it seems doesn't work. The response is very slow, and it cannot give the correct result. (It reports an error) julia> poly = Polyhedra.polyhedron(v, CDDLib.Library());
julia> Polyhedra.in(y, poly) # way too slow
ERROR: ddf_DDMatrix2Poly : Numerically inconsistent
Stacktrace:
[1] error(::String, ::String, ::String)
@ Base .\error.jl:44
[2] myerror
@ K:\judepot1102\packages\CDDLib\OpQiu\src\error.jl:25 [inlined]
[3] myerror
@ K:\judepot1102\packages\CDDLib\OpQiu\src\error.jl:29 [inlined]
[4] macro expansion
@ K:\judepot1102\packages\CDDLib\OpQiu\src\ccall.jl:30 [inlined]
[5] dd_matrix2poly(matrix::Ptr{CDDLib.Cdd_MatrixData{Float64}})
@ CDDLib K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedra.jl:51
[6] CDDPolyhedra
@ K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedra.jl:72 [inlined]
[7] CDDLib.CDDPolyhedra(matrix::CDDLib.CDDGeneratorMatrix{Float64, Float64})
@ CDDLib K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedra.jl:87
[8] getpoly(p::CDDLib.Polyhedron{Float64}, inepriority::Bool)
@ CDDLib K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedron.jl:63
[9] getpoly
@ K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedron.jl:57 [inlined]
[10] getine(p::CDDLib.Polyhedron{Float64})
@ CDDLib K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedron.jl:46
[11] hrep
@ K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedron.jl:150 [inlined]
[12] hyperplanetype(p::CDDLib.Polyhedron{Float64})
@ Polyhedra K:\judepot1102\packages\Polyhedra\2LLjF\src\iterators.jl:175
[13] _broadcast_getindex_evalf
@ .\broadcast.jl:709 [inlined]
[14] _broadcast_getindex
@ .\broadcast.jl:682 [inlined]
[15] #31
@ .\broadcast.jl:1118 [inlined]
[16] ntuple
@ .\ntuple.jl:48 [inlined]
[17] copy
@ .\broadcast.jl:1118 [inlined]
[18] materialize
@ .\broadcast.jl:903 [inlined]
[19] hyperplanes
@ K:\judepot1102\packages\Polyhedra\2LLjF\src\iterators.jl:183 [inlined]
[20] hreps
@ K:\judepot1102\packages\Polyhedra\2LLjF\src\iterators.jl:356 [inlined]
[21] _vinh(v::Vector{Float64}, hr::CDDLib.Polyhedron{Float64}, infun::Function)
@ Polyhedra K:\judepot1102\packages\Polyhedra\2LLjF\src\repelemop.jl:73
[22] in(v::Vector{Float64}, hr::CDDLib.Polyhedron{Float64})
@ Polyhedra K:\judepot1102\packages\Polyhedra\2LLjF\src\repelemop.jl:92
[23] top-level scope
@ REPL[10]:1But the The convex combination coefficient vector is coeff_vector = [0.043901908463998135, 0.009383080458039943, 0.0019659622876165143, 0.0, 0.0, 0.0010766715940339843, 0.004546357113973881, 0.004219574124540232, 0.0, 0.0, 0.008897391678412287, 0.0, 0.012389289363110581, 0.013938483117636598, 0.0007807186713566161, 0.0, 0.4264848350991656, 0.0, 0.0, 0.05146837567758367, 0.0, 0.0, 0.0, 0.0, 0.02086821068261842, 0.06927183311122961, 0.0, 0.0501483710506711, 0.26147224196738755, 0.0, 0.019186695538625183, 0.0]which is generated by the following code, which is in moderate size import Polyhedra
import Gurobi
import JuMP
import LinearAlgebra
GRB_ENV = Gurobi.Env()
function ip(x, y) return LinearAlgebra.dot(x, y) end
function m2vov(mat) return [Vector(c) for c in eachcol(mat)] end
function JumpModel() return ø = JuMP.Model(() -> Gurobi.Optimizer(GRB_ENV)) end
function is_in(y, yM)
N, S = size(yM)
ø = JumpModel()
JuMP.@variable(ø, c[1:S] >= 0.)
JuMP.@constraint(ø, sum(c) == 1.)
JuMP.@constraint(ø, [i = 1:N], y[i] == ip(yM[i, :], c))
JuMP.unset_silent(ø)
(_, status) = (JuMP.optimize!(ø), JuMP.termination_status(ø))
if status == JuMP.OPTIMAL
return JuMP.value.(c)
end
end
coeff_vector = is_in(y, yM)
|
|
We have the LP implemented in Polyhedra and it's used to remove the redundant points in a V-representation: Polyhedra.jl/src/redundancy.jl Lines 191 to 226 in 460b4f0 Unfortunately, at the moment, it's only used to check which points are redundant inside a representation, and no check if a point is redundant wrt a given representation, but it should be easy to hook it up. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The performance of the utility functions are not satisfying (they don't give results in reasonable time).
Especially the
infunction, which should has be very easy to give results (If use Gurobi to write a simple convex-combination program, this should be verified in a second).I conduct the experiment in Euclidean-16 space. The poly is defined by 32 points defined in the 16-by-32 matrix
yM.A test point (in the 16-dim space) is defined in the vector
y.Please check out the code, it just doesn't give results.
Could you give any method to address this issue?
The text was updated successfully, but these errors were encountered: