Tuple function for epigraph formulations

[matbesancon]

Problem

MOI favoured conic formulations for many constraints, lots of which are of the form:

(t,x) in K <==> t >= f(x)

Some solvers support compact constraints instead of conic ones, L2-norm ball instead of SOC, bound on the sum of absolute values instead of L1-norm constraint, etc. FrankWolfe.jl falls in that category, there might be others I'm not aware of.

Proposal

struct TupleFunction{TT <: Union{AbstractScalarFunction, Real}, TX <: AbstractVectorFunction} <: AbstractVectorFunction
    t::TT
    x::TX
end

If TT is a VariableIndex or scalar affine term, this is equivalent to what we currently do with VectorAffineFunction. This can be bridged easily from the type of the TupleFunction.
If TT is a Real and x is a vector of variables or vector affine function, then we create a compact set instead of a cone.

[odow]

The TupleFunction would be useful for the Complements and Indicator sets. But I'm hesitant about adding new function types. The quantity of associated work is much, much greater than adding a new set.

Can't FrankWolfe.jl look at the incoming function and decide to internally represent it as a compact set, but then tell MOI that it's a cone?

[matbesancon]

FrankWolfe has two cases with MOI: using MOI for an underlying generic solver, this part is fine because we just pass the solver a VectorAffineFunction-in-Set with a constant first term.

This issue comes with the motivation of building an MOI Optimizer on top of FW. This would mean pretending to support VAF-in-Cone, checking the first term, and then throw an error whenever it is not a real.

What part of introducing a new function are you most reluctant on, is it committing to keeping it as-is, building the bridges or supporting it in the solvers?

Two possible solutions:

• having it in a separate package at the beginning
• an experimental module in MOI that's not subject to the same semver requirements

[blegat]

The issue of defining new functions is that you need to define map_indices to work with the CachingOptimizer, substitute_variables to work with variable bridges. Then many constraint bridges work with any function type so they will call promote_operation and operate and if you don't implement these, you will get errors. You can try it out and see what you get.
For vector functions there might be less to implement though. One major blocker I see is scalar_type. What would you return since you might have two different scalar types ? Maybe we need a scalar_type that takes the index as second argument ?

[matbesancon]

one way to solve the scalar_type issue would be a promotion, if (VariableIndex, VectorOfVariables) -> scalar_type would be VariableIndex, in any other case, ScalarAffineTerm?

[odow]

This would mean pretending to support VAF-in-Cone, checking the first term, and then throw an error whenever it is not a real.

Yes. Similar to what we do for non-convex quadratics.

[gdalle]

Just bumping this because ball projections would be very useful and simpler to handle than cones

[odow]

So coming back to this, isn't the solution for t >= f(x) where t is a constant to encode t into the set? Why does it need to be part of the function?

[odow]

The classic case would be a' * x <= t becomes a' * x in LessThan(t).

So ||f(x)||_2 <= t could become f(x) in L2NormBall(t), and then you can bridge f(x) in L2NormBall(t) to [t, f(x)] in SecondOrderCone.

[matbesancon]

So coming back to this, isn't the solution for t >= f(x) where t is a constant to encode t into the set? Why does it need to be part of the function?

yes that works, that's the way I ended up implementing a workaround in MathOptSetDistances

[odow]

So is there still appetite for this in MOI, or can this issue be closed? The few-functions many-sets abstraction is working quite well, so I'm hesitant to add more functions.

[odow]

Closing because I don't think we want to add this to MOI. The solution is to create a new set.