I am working on a very large optimisation problem. All variables are continuous, the objective is linear and the constraints convex, but I have many such constraints (on the order of $2^n$ — actually, one constraint per possible solution to a given combinatorial problem with $n$ variables). Due to the large number of constraints, I generate them lazily, one by one, as they are required (in case you're wondering, the separation problem involves solving a nonconvex MIQP, but I can approximate it).
I am trying to have any kind of bound on the number of lazy constraints to be generated. Do you have any idea of what techniques could be applied? I am not necessarily interested by an algorithm that could be computing this number (without actually solving the problem and seeing that there are no more lazy constraints to add). However, I would also be keen on getting any insight in the distance to the optimal value when adding $k$ lazy constraints (always found by the separation procedure as maximising the infeasibility).
There should be results like this, as it could be a way to tell whether a robust optimisation program or a TSP instance is hard to solve (i.e. requires an exponential number of lazy constraints, be they retrieved from the uncertainty set or subtour elimination). The only thing I could find was an application of robust optimisation in network routing (Optimal Oblivious Routing in Polynomial Time), but the article did not really provide the required details to fully understand what they are doing:
First, the polynomial bound on the number of iterations follows using the standard bounds on the size of the initial ellipsoid and the smallest “volume” of the feasible set.