Convex Hulls for Position-Constrained Trade Allocation
Summary
The document presents an approach to allocating partial fills across a sequence of stock trades when the final position must stay within a fixed share limit. The original formulation uses dynamic programming over possible positions and execution amounts, but the questioner reports that this approach is too slow for a large trade list despite its stated linear-time relationship to the position bound.
The proposed alternative represents each execution choice as a point in a plane: one coordinate is the resulting position change and the other is the cash balance change. Combining trades creates a set of attainable outcomes; the answer argues that keeping the convex hull of this set is sufficient as each trade is incorporated. At the end, the best flat-position outcome is found where the hull meets the zero-position axis. The post gives no proof, update procedure, complexity analysis, or benchmark, so the hull claim and its performance remain unverified.
Key ideas
- Each partial trade execution maps to a position change and a cash balance change.
- Combining trades expands the set of attainable position and balance outcomes.
- The proposed method retains the convex hull rather than every individual outcome.
- The desired final result is the highest cash balance among outcomes with zero net position.
- The answer does not establish correctness or provide complexity and performance evidence.
Tags
Full text
# Quant Interview - Best time to buy and short stock with position constraint
# Quant Interview - Best time to buy and short stock with position constraint
I was given a problem at a job interview, I'm trying to solve it afterwards
You are given a list of N trades for some stock, you need to determine how much volume for each trade an ideal strategy would execute, provided that you cannot buy or short more than K (=const) shares. The algorithm should work for O(N) and be constant in memory.
It is clear how to solve such a problem by dynamic programming (with memory O(K) and complexity O(N * K) = O(N)), but the running time on 1e5 trades is about a couple of hours, although it is necessary to work for a couple of seconds. Maybe there are some optimisations for such dynamics?
(fyi. $d[i][p] = max(d[i-1][p],\,\,\,\, d[i-1][p - \text{side_sign} * x] - \text{side_sign} \cdot x \cdot \text{trade['price']}$ $x \in [1, \text{ trade['amount']}])$, $\text{side_sign = (-1 if trade['side'] == 'short' else 1)}$)
## Answer by Mark Silverman (score 0)
https://quant.stackexchange.com/a/76693
A promising approach to solving this task involves using Cartesian coordinates to represent two variables: position and USD balance. The first trade generates a segment within these coordinates, defined as $(\text{side_sign} * x,\; -\; \text{side_sign} * \text{trade['price']} * x),\; x \in [0,\;\text{trade['amount']}]$ where $x$ ranges from 0 to the trade's amount. When we introduce a subsequent trade, also represented similarly, we expand the set to include all potential outcomes for position and USD balance after partially executing the two considered trades.
As we continue to add more trades, we generate a larger set of potential outcomes. The key insight is this: rather than maintaining a record of all individual points that could arise from these multiple combinations, it's sufficient to focus on the convex hull of this set. Each new trade can then be used to update this convex hull. Finally, once all trades have been considered, it's easy to identify the point on the convex hull that intersects the balance-axis at the highest USD balance while zeroing out the position.Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.