I want to approach this topic the way a financial planner or portfolio manager would: given a limited budget and a set of possible investment opportunities, each with its own expected return and risk, how do I decide which investments to make (and how much to allocate to each) to maximize my overall return while respecting my constraints? Investment planning algorithms — most classically framed as capital budgeting via 0/1 knapsack-style dynamic programming, and more generally as portfolio optimization via Markowitz’s mean-variance framework — give me a rigorous way to answer that question rather than relying on gut feeling.
History and Background
The mathematical treatment of investment planning traces two main lineages I find useful to separate. The first is the capital budgeting problem, formalized through dynamic programming techniques developed by Richard Bellman in the 1950s, which treats investment selection as a discrete resource-allocation (knapsack) problem. The second, more famous in finance specifically, is Harry Markowitz’s Modern Portfolio Theory, published in his 1952 paper “Portfolio Selection” in The Journal of Finance, for which he later won the Nobel Memorial Prize in Economic Sciences in 1990. Markowitz’s contribution was showing that an investor should judge investments not in isolation but by how they contribute to the risk and return of the entire portfolio, formalizing the intuitive idea of diversification.
Problem Statement
I frame the discrete capital-budgeting version as: given a set of $n$ possible investment projects, each with a required capital outlay $c_i$ and an expected return $r_i$, and a total available budget $B$, choose a subset of projects to fund such that total outlay does not exceed $B$ and total expected return is maximized. The continuous portfolio-optimization version asks instead: given $n$ assets with expected returns $\mu_i$ and a covariance matrix $\Sigma$ describing how their returns move together, choose allocation weights $w_i$ (summing to 1) that either maximize expected return for a given risk tolerance, or minimize risk for a given target return.
Core Concepts
- Capital outlay: the amount of money required to fund a given investment project.
- Expected return: the anticipated profit or value generated by an investment, often expressed as a rate or absolute amount.
- Budget constraint: the total capital available, which limits how many/which projects can be funded.
- Risk (variance/covariance): in the portfolio approach, a measure of how much an asset’s returns fluctuate, and how those fluctuations correlate with other assets.
- Efficient frontier: the set of portfolios that offer the maximum expected return for each level of risk — no portfolio outside this frontier is optimal.
- Diversification: spreading investment across assets whose returns aren’t perfectly correlated, reducing overall portfolio risk without proportionally reducing return.
How It Works
A. Discrete capital-budgeting (0/1 knapsack) approach:
- I list all candidate projects with their cost and expected return.
- I build a table $DP[i][b]$ representing the maximum achievable return considering the first $i$ projects with budget $b$.
- For each project $i$ and each budget level $b$, I decide: either skip project $i$ (carry forward $DP[i-1][b]$), or fund it if $c_i \leq b$ (take $DP[i-1][b-c_i] + r_i$) — I choose whichever is larger.
- After filling the table, $DP[n][B]$ gives the maximum total return, and I backtrack through my choices to recover which specific projects were funded.
B. Markowitz portfolio optimization approach:
- I estimate expected returns $\mu_i$ and the covariance matrix $\Sigma$ for all candidate assets, typically from historical data.
- I define the portfolio’s expected return as $w^T \mu$ and its variance (risk) as $w^T \Sigma w$.
- I solve a constrained quadratic optimization problem: minimize portfolio variance subject to achieving a target expected return and the weights summing to 1 (and often, non-negativity constraints if short-selling isn’t allowed).
- I repeat this optimization across a range of target returns to trace out the efficient frontier, then select the point matching my actual risk tolerance.
Working Principle
Both approaches rest on optimization under constraints, but their internal logic differs meaningfully. The knapsack-style capital budgeting method uses dynamic programming: it exploits the principle of optimality by building up solutions to smaller budget sub-problems and reusing them, avoiding the combinatorial explosion of checking every possible subset of projects directly. The Markowitz approach instead uses quadratic programming: because portfolio variance is a quadratic function of the weights while the constraints are linear, the problem has a well-behaved convex structure, meaning any local optimum I find is guaranteed to be the global optimum.
Mathematical Foundation
Knapsack-style capital budgeting recurrence:
$$ DP[i][b] = \max\big(DP[i-1][b],\ DP[i-1][b-c_i] + r_i\big) \quad \text{if } c_i \leq b $$
$$ DP[i][b] = DP[i-1][b] \quad \text{if } c_i > b $$
Markowitz mean-variance optimization:
$$ \min_{w} \ w^T \Sigma w \quad \text{subject to} \quad w^T \mu = R_{\text{target}}, \quad \sum_i w_i = 1 $$
where portfolio expected return and risk are:
$$ E[R_p] = \sum_i w_i \mu_i, \qquad \sigma_p^2 = \sum_i \sum_j w_i w_j , \text{Cov}(r_i, r_j) $$
Diagrams
flowchart TD
A["Start"] --> B["Initialize dynamic programming table"]
B --> C["Process each project"]
C --> D{"Can the project fit the budget?"}
D -- No --> E["Skip the project"]
D -- Yes --> F["Choose the better option"]
E --> G{"More projects or budgets?"}
F --> G
G -- Yes --> C
G -- No --> H["Reconstruct the selected projects"]
H --> I["Return the optimal investment plan"]Pseudocode
function CapitalBudgeting(costs[1..n], returns[1..n], B):
for b from 0 to B:
DP[0][b] = 0
for i from 1 to n:
for b from 0 to B:
DP[i][b] = DP[i-1][b]
if costs[i] <= b:
candidate = DP[i-1][b - costs[i]] + returns[i]
if candidate > DP[i][b]:
DP[i][b] = candidate
// Backtrack to find which projects were funded
b = B
funded = []
for i from n downto 1:
if DP[i][b] != DP[i-1][b]:
add i to funded
b = b - costs[i]
return DP[n][B], funded
Step-by-Step Example
I’ll use 4 candidate projects and a budget of 10 (in units of, say, $10,000):
| Project | Cost | Return |
|---|---|---|
| 1 | 3 | 4 |
| 2 | 4 | 6 |
| 3 | 5 | 8 |
| 4 | 2 | 3 |
Following the DP recurrence, I fill the table budget-by-budget. I’ll summarize the key result rather than the full table: at budget 10, the best combination turns out to be projects 2 and 3 (cost 4+5=9, return 6+8=14), which beats other combinations like 1+2+4 (cost 3+4+2=9, return 4+6+3=13) or 1+3+4 (cost 3+5+2=10, return 4+8+3=15) — let me recheck: 1+3+4 costs exactly 10 and returns 15, which is actually better.
So the truly optimal choice is projects 1, 3, and 4: total cost = 3+5+2 = 10 (fits exactly within budget), total return = 4+8+3 = 15.
Time Complexity
The capital-budgeting DP runs in $O(nB)$ time, where $n$ is the number of projects and $B$ is the budget (this is pseudo-polynomial, since it depends on the numeric value of $B$, not just the input size). The Markowitz quadratic optimization, when solved via standard quadratic programming solvers, typically runs in polynomial time relative to the number of assets, often around $O(n^3)$ for dense covariance matrices using interior-point methods.
Space Complexity
The capital-budgeting DP table requires $O(nB)$ space in its full form, though this can be reduced to $O(B)$ using a rolling array if I don’t need to backtrack (or $O(B)$ with a separate choice-tracking structure if I do need to recover the actual project list). The Markowitz approach requires $O(n^2)$ space to store the covariance matrix.
Correctness Analysis
For the capital-budgeting DP, correctness follows from the standard 0/1 knapsack optimality argument: $DP[i][b]$ represents the true optimal return achievable using only the first $i$ projects within budget $b$, and the recurrence correctly considers both possibilities (fund project $i$ or don’t) at every step, so by induction over $i$, the final table entry $DP[n][B]$ is guaranteed optimal. For Markowitz optimization, correctness follows from convex optimization theory: because the objective (variance) is a positive semi-definite quadratic form and the constraints are linear (defining a convex feasible region), any solution satisfying the Karush–Kuhn–Tucker (KKT) conditions is guaranteed to be a global minimum, not merely a local one.
Advantages
- The capital-budgeting DP guarantees a truly optimal discrete selection of projects within a hard budget constraint.
- The Markowitz framework formally captures the benefit of diversification, something ad hoc investment heuristics miss.
- Both methods are well-established, mathematically rigorous, and widely taught, making results easy to explain and defend.
- The efficient frontier gives a full menu of risk/return trade-offs rather than a single answer, letting me match a solution to my actual risk appetite.
Disadvantages
- The capital-budgeting DP assumes discrete, all-or-nothing project selection — it doesn’t naturally handle partial funding or interdependent projects.
- Markowitz optimization is highly sensitive to the accuracy of estimated expected returns and covariances, which are notoriously hard to forecast reliably from historical data.
- Neither method inherently accounts for behavioral factors, liquidity constraints, or transaction costs without further extension.
- The pseudo-polynomial $O(nB)$ complexity of the knapsack DP can become impractical if the budget is expressed with very fine granularity (e.g., to the exact dollar) relative to the number of projects.
Applications
- Corporate capital budgeting: choosing which projects to fund from a limited capital pool.
- Personal and institutional portfolio construction and asset allocation.
- Venture capital and private equity fund allocation across candidate startups.
- Public sector budgeting for infrastructure or R&D project selection.
- Retirement and pension fund asset-liability management.
Implementation in C
#include <stdio.h>
#define N 4 // number of projects
#define B 10 // total budget
int main() {
int cost[N + 1] = {0, 3, 4, 5, 2}; // 1-indexed
int returnVal[N + 1] = {0, 4, 6, 8, 3};
int dp[N + 1][B + 1];
for (int b = 0; b <= B; b++)
dp[0][b] = 0;
for (int i = 1; i <= N; i++) {
for (int b = 0; b <= B; b++) {
dp[i][b] = dp[i - 1][b]; // skip project i
if (cost[i] <= b) {
int funded = dp[i - 1][b - cost[i]] + returnVal[i];
if (funded > dp[i][b])
dp[i][b] = funded;
}
}
}
printf("Maximum achievable return: %d\n", dp[N][B]);
// Backtrack to find funded projects
int b = B;
printf("Funded projects:\n");
for (int i = N; i >= 1; i--) {
if (dp[i][b] != dp[i - 1][b]) {
printf("Project %d (cost=%d, return=%d)\n", i, cost[i], returnVal[i]);
b -= cost[i];
}
}
return 0;
}
Sample Input and Output
Input: 4 projects with costs [3, 4, 5, 2] and returns [4, 6, 8, 3], budget = 10.
Output:
Maximum achievable return: 15
Funded projects:
Project 4 (cost=2, return=3)
Project 3 (cost=5, return=8)
Project 1 (cost=3, return=4)
This matches my manual analysis — projects 1, 3, and 4 together use the full budget of 10 and yield the maximum return of 15.
Optimization Techniques
- Reduce DP space from $O(nB)$ to $O(B)$ by iterating the budget dimension in reverse when only the maximum value (not the specific project list) is needed.
- For very large or fine-grained budgets, consider a greedy fractional-knapsack approximation (sorting by return-to-cost ratio) as a fast heuristic when near-optimality is acceptable.
- In portfolio optimization, use factor models (e.g., the Fama–French model) to reduce the effective dimensionality of the covariance matrix, making estimation more stable and computation faster.
- Apply regularization (e.g., shrinkage estimators) to covariance matrix estimates to reduce sensitivity to noisy historical data.
Common Mistakes
- Treating the capital-budgeting problem as if fractional investment is allowed when it’s actually a strict 0/1 (all-or-nothing) decision, leading to an incorrect greedy fractional-knapsack solution being applied where it doesn’t fit.
- Forgetting to backtrack correctly, ending up with the right maximum return value but the wrong (or no) list of specific funded projects.
- In Markowitz optimization, using historical average returns naively as future expected returns without adjustment, which can produce badly miscalibrated portfolios.
- Ignoring the difference between risk (variance) and downside risk — mean-variance optimization penalizes upside volatility just as much as downside volatility, which doesn’t always match real investor preferences.
Further Reading
- Markowitz, H. (1952). “Portfolio Selection.” The Journal of Finance, 7(1), 77–91.
- Bellman, R. (1957). Dynamic Programming, Princeton University Press.
- Bodie, Z., Kane, A., & Marcus, A. J. Investments, McGraw-Hill.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms (Knapsack DP chapter), MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
