Performance issue with Quadratic objective to SOC constraint

[migarstka]

Hi,

I am trying to solve some large QPs and I noticed quite a big performance issue when I use MOI to pass the problem to solvers that don't support quadratic objectives. For very large problems the reformulation takes 10 - 100x the solve time.

Here is a MWE of moderate size:

using MathOptInterface, SCS
const MOI = MathOptInterface
const MOIU = MOI.Utilities
const MOIB = MOI.Bridges
using Random, SparseArrays, LinearAlgebra

rng = Random.MersenneTwister(123123)

# create random problem data
n = 300
P = spdiagm(0 => ones(n^2))
q = rand(rng, n^2)

# make MOI model
model = MOI.Utilities.Model{Float64}()
x = MOI.add_variables(model, n^2);

# define the quadratic objective 1/2 x'x + q'x
affine_terms = MOI.ScalarAffineTerm{Float64}.(q, x)
quadratic_terms = MOI.ScalarQuadraticTerm{Float64}.(1., x, x)
quad_func = MOI.ScalarQuadraticFunction{Float64}(affine_terms, quadratic_terms, 0.)
MOI.set(model, MOI.ObjectiveSense(), MOI.MIN_SENSE);
MOI.set(model, MOI.ObjectiveFunction{MOI.ScalarQuadraticFunction{Float64}}(), quad_func);

# add inequality constraints (not important here)
MOI.add_constraint(model, MOI.VectorOfVariables(x), MOI.Nonnegatives(n));

# copy to a solver that doesn't support quadratic objectives to invoke the bridging
cache = MOI.Utilities.CachingOptimizer(
        MOI.Utilities.Model{Float64}(), SCS.Optimizer())
bridged = MOI.Bridges.full_bridge_optimizer(cache, Float64)
@time MOI.copy_to(bridged, model)

#@profile MOI.copy_to(bridged, model)

For n=300 this takes about 39s. I am trying to solve problems with up to n=1200 in which case this step takes up to an hour. (Notice, that I am actually using n^2)

Looking at the profile results, I get:

it seems like all the time is spent to map indices in

MathOptInterface.jl/src/Utilities/functions.jl

Lines 274 to 277 in c602677

	function scalar_terms_at_index(terms::Vector{<:Union{MOI.VectorAffineTerm, MOI.VectorQuadraticTerm}}, i::Int)
	I = findall(t -> t.output_index == i, terms)
	map(i -> terms[i].scalar_term, I)
	end

in the findall() function. I am wondering if anything could be done to make this more efficient.

[blegat]

Does the solver need the bridge to RSOC to SOC ?
Then it might come from:

MathOptInterface.jl/src/Bridges/Constraint/rsoc.jl

Lines 68 to 70 in 746b2e1

	t = scalars[1]
	u = scalars[2]
	x = scalars[3:end]

and should be improved by #418