Parallel Multi-Start Optimization: Finding Global Optima

Part 32 of 12-Week BusinessMath Series

What You’ll Learn

• Why single-start optimization can get stuck in local minima
• Using ParallelOptimizer to try multiple starting points simultaneously
• Leveraging Swift Concurrency (async/await) for parallel execution
• Choosing optimal number of starting points
• Analyzing success rates and result distributions
• When multi-start optimization provides the biggest benefit

The Problem

Many optimization problems have multiple local minima:

• Portfolio optimization with transaction costs → discrete jumps create local traps
• Complex business models with discontinuities → gradient methods get stuck
• Non-convex objectives → single-start methods find nearest local minimum, not global

Example: Portfolio optimization starting from equal weights might find a local optimum with Sharpe ratio 0.85. The global optimum with Sharpe ratio 1.12 exists, but gradient-based methods can’t escape the local basin.

Your optimization finds a solution, but not necessarily the best solution.

The Solution

BusinessMath’s ParallelOptimizer runs the same optimization algorithm from multiple random starting points in parallel, then returns the best result found. This dramatically increases the chance of finding the global optimum.

Automatic Parallel Multi-Start Optimization

Business Problem: Optimize portfolio allocation, but don’t get stuck in local minima.

import BusinessMath
import Foundation

let assets = ["US Stocks", "Intl Stocks", "Bonds", "Real Estate"]
let expectedReturns = VectorN([0.10, 0.12, 0.04, 0.09])
let riskFreeRate = 0.03

// Covariance matrix
let covarianceMatrix = [
	[0.0400, 0.0150, 0.0020, 0.0180],  // US Stocks
	[0.0150, 0.0625, 0.0015, 0.0200],  // Intl Stocks
	[0.0020, 0.0015, 0.0036, 0.0010],  // Bonds
	[0.0180, 0.0200, 0.0010, 0.0400]   // Real Estate
]

// Objective: Maximize Sharpe ratio
let portfolioObjective: @Sendable (VectorN
            
              ) -> Double = { weights in let expectedReturn = weights.dot(expectedReturns) var variance = 0.0 for i in 0..
              
                >.budgetConstraint let longOnlyConstraints = MultivariateConstraint
                
                  >.nonNegativity(dimension: assets.count) let constraints: [MultivariateConstraint
                  
                    >] = [budgetConstraint] + longOnlyConstraints // Create parallel multi-start optimizer let parallelOptimizer = ParallelOptimizer
                    
                      >( algorithm: .inequality, // Use inequality-constrained optimizer numberOfStarts: 20, // Try 20 different starting points maxIterations: 1000, tolerance: 1e-6 ) // Define search region for random starting points let searchRegion = ( lower: VectorN(repeating: 0.0, count: assets.count), upper: VectorN(repeating: 1.0, count: assets.count) ) // Run optimization in parallel (async/await) // Note: Wrap in Task for playground execution Task { do { let result = try await parallelOptimizer.optimize( objective: portfolioObjective, searchRegion: searchRegion, constraints: constraints ) print("Parallel Multi-Start Optimization:") print(" Attempts: \(result.allResults.count)") print(" Converged: \(result.allResults.filter(\.converged).count)") print(" Success rate: \(result.successRate.percent())") print(" Best Sharpe ratio: \((-result.objectiveValue).number())") print("\nBest Solution:") for (asset, weight) in zip(assets, result.solution.toArray()) { if weight > 0.01 { print(" \(asset): \(weight.percent())") } } } catch { print("Optimization failed: \(error)") } } 
                    
                  
                
              
            

Comparing Single-Start vs Multi-Start

Pattern: See how multi-start improves over single-start optimization.

// Single-start optimization (baseline)
let singleStartOptimizer = AdaptiveOptimizer
            
              >() let singleResult = try singleStartOptimizer.optimize( objective: portfolioObjective, initialGuess: VectorN.equalWeights(dimension: assets.count), constraints: constraints ) print("Single-Start Result:") print(" Sharpe ratio: \((-singleResult.objectiveValue).number())") print(" Algorithm: \(singleResult.algorithmUsed)") // Multi-start optimization Task { do { let multiStartResult = try await parallelOptimizer.optimize( objective: portfolioObjective, searchRegion: searchRegion, constraints: constraints ) print("\nMulti-Start Result (20 starting points):") print(" Best Sharpe ratio: \((-multiStartResult.objectiveValue).number())") print(" Success rate: \(multiStartResult.successRate.percent())") // Compare let improvement = (-multiStartResult.objectiveValue) / (-singleResult.objectiveValue) - 1.0 print("\nImprovement: \(improvement.percent(1))") } catch { print("Multi-start optimization failed: \(error)") } } 
            

Analyzing Result Distribution

Pattern: Understand variation across different starting points.

Task {
	do {
		// Run multi-start optimization
		let result = try await parallelOptimizer.optimize(
			objective: portfolioObjective,
			searchRegion: searchRegion,
			constraints: constraints
		)

		// Analyze distribution of objectives found
		let objectives = result.allResults.map(\.value)
		let sortedObjectives = objectives.sorted()

		print("Result Distribution:")
		print("  Best: \(sortedObjectives.first?.number() ?? "N/A")")
		print("  Median: \(sortedObjectives[sortedObjectives.count / 2].number())")
		print("  Worst: \(sortedObjectives.last?.number() ?? "N/A")")
		print("  Range: \((sortedObjectives.last! - sortedObjectives.first!).number())")

		// Show how many found the global optimum (within 1% of best)
		let globalThreshold = sortedObjectives.first! * 1.01
		let globalCount = sortedObjectives.filter { $0 <= globalThreshold }.count

		print("\nFound global optimum: \(globalCount)/\(sortedObjectives.count) attempts")
		print("  (\((Double(globalCount) / Double(sortedObjectives.count)).percent(0)))")
	} catch {
		print("Analysis failed: \(error)")
	}
}

Choosing Number of Starting Points

Pattern: Trade off between solution quality and computation time.

Task {
	// Test different numbers of starting points
	for numStarts in [5, 10, 20, 50] {
		do {
			let optimizer = ParallelOptimizer
            
              >( algorithm: .inequality, numberOfStarts: numStarts, maxIterations: 500, tolerance: 1e-5 ) let startTime = Date() let result = try await optimizer.optimize( objective: portfolioObjective, searchRegion: searchRegion, constraints: constraints ) let elapsedTime = Date().timeIntervalSince(startTime) print("\n\(numStarts) starting points:") print(" Best objective: \(result.objectiveValue.number())") print(" Success rate: \(result.successRate.percent())") print(" Time: \(elapsedTime.number(2))s") print(" Time per start: \((elapsedTime / Double(numStarts)).number(2))s") } catch { print("\n\(numStarts) starting points: FAILED") } } } 
            

Rule of Thumb:

• 5-10 starts: Quick exploration, may miss global optimum
• 20-30 starts: Good balance for most problems
• 50-100 starts: Thorough search for critical applications
• More starts: Diminishing returns (20 → 40 often finds same optimum)

How It Works

Parallel Execution with Swift Concurrency

BusinessMath uses Swift’s async/await and TaskGroup to run optimizations in parallel:

// Inside ParallelOptimizer (simplified)
let results = try await withThrowingTaskGroup(
	of: (startingPoint: V, result: MultivariateOptimizationResult
            
              ).self ) { group in // Add a task for each starting point for start in startingPoints { group.addTask { let result = try ParallelOptimizer.runSingleOptimization( algorithm: algorithm, objective: objective, initialGuess: start, constraints: constraints ) return (startingPoint: start, result: result) } } // Collect all results as they complete var allResults: [(V, MultivariateOptimizationResult
              
                )] = [] for try await (start, result) in group { allResults.append((start, result)) } return allResults } // Find best result (lowest objective value) let best = results.min(by: { $0.1.value < $1.1.value })! 
              
            

Algorithm Selection

ParallelOptimizer supports multiple base algorithms:

public enum Algorithm {
	case gradientDescent(learningRate: Double)
	case newtonRaphson
	case constrained
	case inequality
}

// Choose based on problem characteristics
let optimizer = ParallelOptimizer
            
              >( algorithm: .inequality, // For problems with inequality constraints numberOfStarts: 20 ) // Or use gradient descent for unconstrained problems let unconstrainedOptimizer = ParallelOptimizer
              
                >( algorithm: .gradientDescent(learningRate: 0.01), numberOfStarts: 20 ) 
              
            

Performance Characteristics

Speedup depends on:

1. Number of CPU cores: 8-core M3 can run 8 optimizations simultaneously
2. Objective function cost: Expensive functions (>10ms) benefit most
3. Number of starting points: 20 starts on 8 cores ≈ 2.5× speedup

Typical Results (M3 MacBook Pro, 8 cores):

Key Insight: Speedup plateaus around number of physical cores (8 for M3).

When to Use Multi-Start Optimization

Strong Candidates

Use multi-start when:

• Objective has multiple local minima
• Problem is non-convex
• Single-start results vary significantly with initial guess
• Solution quality is critical (willing to spend more time)

Examples:

• Portfolio optimization with transaction costs
• Facility location problems
• Machine learning hyperparameter tuning
• Supply chain network design

Weak Candidates

Don’t use multi-start when:

• Problem is convex (single local minimum = global minimum)
• Objective is very expensive (>1 minute per evaluation)
• Quick approximate solution is acceptable
• Single-start consistently finds good solutions

Examples:

• Simple least-squares regression (convex)
• Linear programming (convex)
• Unconstrained quadratic problems (convex)

Hybrid Approach

Pattern: Use multi-start to find good region, then refine with single-start.

Task {
	do {
		// Phase 1: Broad search with low accuracy
		let explorationOptimizer = ParallelOptimizer
            
              >( algorithm: .gradientDescent(learningRate: 0.01), numberOfStarts: 50, maxIterations: 100, // Low iterations tolerance: 1e-3 // Loose tolerance ) let roughSolution = try await explorationOptimizer.optimize( objective: portfolioObjective, searchRegion: searchRegion, constraints: constraints ) print("Phase 1 (exploration): Sharpe \((-roughSolution.objectiveValue).number())") // Phase 2: Refine best solution with high accuracy let refinementOptimizer = AdaptiveOptimizer
              
                >( maxIterations: 2000, tolerance: 1e-8 ) let finalSolution = try refinementOptimizer.optimize( objective: portfolioObjective, initialGuess: roughSolution.solution, constraints: constraints ) print("Phase 2 (refinement): Sharpe \((-finalSolution.objectiveValue).number())") } catch { print("Hybrid optimization failed: \(error)") } } 
              
            

Real-World Application

Investment Firm: Quarterly Rebalancing

Company: Mid-sized investment firm managing $2B across 80 assets Challenge: Optimize portfolio quarterly, accounting for:

• Non-linear transaction costs
• Tax-loss harvesting opportunities
• Regulatory diversification requirements

Problem Characteristics:

• 80 variables (asset weights)
• Non-convex objective (transaction costs create discontinuities)
• 50+ constraints (position limits, sector allocations, tax rules)

Single-Start Results (10 trials from different starting points):

• Best Sharpe ratio: 0.94
• Worst Sharpe ratio: 0.78
• Average: 0.85
• High variance suggests local minima problem

Multi-Start Solution:

import BusinessMath
import Foundation

// Simplified 80-asset portfolio problem
let numAssets = 80
let portfolioValue = 2_000_000_000.0  // $2B AUM

// Generate realistic expected returns (4% to 15%, mean ~9%)
let expectedReturns80 = VectorN((0..
            
              ) -> Double = { weights in // Expected return let expectedReturn = weights.dot(expectedReturns80) // Portfolio variance var variance = 0.0 for i in 0..
              
                >.budgetConstraint let longOnlyConstraints80 = MultivariateConstraint
                
                  >.nonNegativity(dimension: numAssets) // Position limits: no more than 5% per asset (diversification requirement) let positionLimits80 = (0..
                  
                    >.inequality { w in w[i] - 0.05 // w[i] ≤ 5% } } let allConstraints80 = [budgetConstraint80] + longOnlyConstraints80 + positionLimits80 // Multi-start optimization Task { do { print(String(repeating: "=", count: 70)) print("REAL-WORLD EXAMPLE: 80-ASSET PORTFOLIO REBALANCING") print(String(repeating: "=", count: 70)) print("Portfolio value: $\((portfolioValue / 1_000_000_000).number(1))B") print("Number of assets: \(numAssets)") print("Transaction costs: \(transactionCostBps) bps") print() let robustOptimizer = ParallelOptimizer
                    
                      >( algorithm: .inequality, numberOfStarts: 30, maxIterations: 1500, tolerance: 1e-6 ) let startTime = Date() let result = try await robustOptimizer.optimize( objective: objectiveWithCosts, searchRegion: ( lower: VectorN(repeating: 0.0, count: numAssets), upper: VectorN(repeating: 0.05, count: numAssets) // Max 5% per asset ), constraints: allConstraints80 ) let elapsedTime = Date().timeIntervalSince(startTime) print("Multi-Start Optimization (30 starts):") print(" Best Sharpe ratio: \((-result.objectiveValue).number())") print(" Success rate: \(result.successRate.percent())") print(" Total time: \((elapsedTime / 60).number(1)) minutes") // Calculate turnover var totalTurnover = 0.0 var numPositions = 0 for i in 0..
                      
                         0.001 { numPositions += 1 } } print("\nPortfolio Characteristics:") print(" Active positions: \(numPositions)/\(numAssets)") print(" Total turnover: \(totalTurnover.percent(1))") print(" Trading costs: $\((portfolioValue * totalTurnover * transactionCostBps / 10000).currency(0))") // Show top 10 positions let topPositions = result.solution.toArray() .enumerated() .sorted { $0.element > $1.element } .prefix(10) print("\nTop 10 Positions:") for (i, (idx, weight)) in topPositions.enumerated() { print(" \(i+1). Asset \(idx): \(weight.percent(2))") } } catch { print("Robust optimization failed: \(error)") } } 
                      
                    
                  
                
              
            

Results:

• Best Sharpe ratio found: 1.08 (14% better than single-start average)
• Consistent across rebalancing periods
• Success rate: 85% of starts converged
• Computation time: 12 minutes (acceptable for quarterly rebalancing)
• Annual alpha improvement: +$16M (0.8% on $2B AUM)

Try It Yourself

import BusinessMath
import Foundation

let assets = ["US Stocks", "Intl Stocks", "Bonds", "Real Estate"]
let expectedReturns = VectorN([0.10, 0.12, 0.04, 0.09])
let riskFreeRate = 0.03

// Covariance matrix
let covarianceMatrix = [
	[0.0400, 0.0150, 0.0020, 0.0180],  // US Stocks
	[0.0150, 0.0625, 0.0015, 0.0200],  // Intl Stocks
	[0.0020, 0.0015, 0.0036, 0.0010],  // Bonds
	[0.0180, 0.0200, 0.0010, 0.0400]   // Real Estate
]

// Objective: Maximize Sharpe ratio
let portfolioObjective: @Sendable (VectorN
              
                ) -> Double = { weights in let expectedReturn = weights.dot(expectedReturns) var variance = 0.0 for i in 0..
                
                  >.budgetConstraint let longOnlyConstraints = MultivariateConstraint
                  
                    >.nonNegativity(dimension: assets.count) let constraints: [MultivariateConstraint
                    
                      >] = [budgetConstraint] + longOnlyConstraints // Create parallel multi-start optimizer let parallelOptimizer = ParallelOptimizer
                      
                        >( algorithm: .inequality, // Use inequality-constrained optimizer numberOfStarts: 20, // Try 20 different starting points maxIterations: 1000, tolerance: 1e-6 ) // Define search region for random starting points let searchRegion = ( lower: VectorN(repeating: 0.0, count: assets.count), upper: VectorN(repeating: 1.0, count: assets.count) ) // Run optimization in parallel (async/await) // Note: Playgrounds require Task wrapper for async code Task { do { let result = try await parallelOptimizer.optimize( objective: portfolioObjective, searchRegion: searchRegion, constraints: constraints ) print("Parallel Multi-Start Optimization:") print(" Attempts: \(result.allResults.count)") print(" Converged: \(result.allResults.filter(\.converged).count)") print(" Success rate: \(result.successRate.percent())") print(" Best Sharpe ratio: \((-result.objectiveValue).number())") print("\nBest Solution:") for (asset, weight) in zip(assets, result.solution.toArray()) { if weight > 0.01 { print(" \(asset): \(weight.percent())") } } } catch { print("Optimization failed: \(error)") } // MARK: - Single-Start vs. Multi-Start Optimization // Single-start optimization (baseline) let singleStartOptimizer = AdaptiveOptimizer
                        
                          >() let singleResult = try singleStartOptimizer.optimize( objective: portfolioObjective, initialGuess: VectorN.equalWeights(dimension: assets.count), constraints: constraints ) print("Single-Start Result:") print(" Sharpe ratio: \((-singleResult.objectiveValue).number())") print(" Algorithm: \(singleResult.algorithmUsed)") print() // Multi-start optimization do { let multiStartResult = try await parallelOptimizer.optimize( objective: portfolioObjective, searchRegion: searchRegion, constraints: constraints ) print("\nMulti-Start Result (20 starting points):") print(" Best Sharpe ratio: \((-multiStartResult.objectiveValue).number())") print(" Success rate: \(multiStartResult.successRate.percent())") // Compare let improvement = (-multiStartResult.objectiveValue) / (-singleResult.objectiveValue) - 1.0 print("\nImprovement: \((improvement.percent(1)))") } catch { print("Multi-start optimization failed: \(error)") } // MARK: - Analyzing Result Distribution do { // Run multi-start optimization let result = try await parallelOptimizer.optimize( objective: portfolioObjective, searchRegion: searchRegion, constraints: constraints ) // Analyze distribution of objectives found let objectives = result.allResults.map(\.value) let sortedObjectives = objectives.sorted() print("Result Distribution:") print(" Best: \(sortedObjectives.first?.number() ?? "N/A")") print(" Median: \(sortedObjectives[sortedObjectives.count / 2].number())") print(" Worst: \(sortedObjectives.last?.number() ?? "N/A")") print(" Range: \((sortedObjectives.last! - sortedObjectives.first!).number())") // Show how many found the global optimum (within 1% of best) let globalThreshold = sortedObjectives.first! * 1.01 let globalCount = sortedObjectives.filter { $0 <= globalThreshold }.count print("\nFound global optimum: \(globalCount)/\(sortedObjectives.count) attempts") print(" (\((Double(globalCount) / Double(sortedObjectives.count)).percent(0)))") } catch { print("Analysis failed: \(error)") } // MARK: - Choosing Number of Starting Points // Test different numbers of starting points for numStarts in [5, 10, 20, 50] { do { let optimizer = ParallelOptimizer
                          
                            >( algorithm: .inequality, numberOfStarts: numStarts, maxIterations: 500, tolerance: 1e-5 ) let startTime = Date() let result = try await optimizer.optimize( objective: portfolioObjective, searchRegion: searchRegion, constraints: constraints ) let elapsedTime = Date().timeIntervalSince(startTime) print("\n\(numStarts) starting points:") print(" Best objective: \(result.objectiveValue.number())") print(" Success rate: \(result.successRate.percent())") print(" Time: \(elapsedTime.number(2))s") print(" Time per start: \((elapsedTime / Double(numStarts)).number(2))s") } catch { print("\n\(numStarts) starting points: FAILED") } } // MARK: - Hybrid Approach do { // Phase 1: Broad search with low accuracy let explorationOptimizer = ParallelOptimizer
                            
                              >( algorithm: .gradientDescent(learningRate: 0.01), numberOfStarts: 50, maxIterations: 100, // Low iterations tolerance: 1e-3 // Loose tolerance ) let roughSolution = try await explorationOptimizer.optimize( objective: portfolioObjective, searchRegion: searchRegion, constraints: constraints ) print("Phase 1 (exploration): Sharpe \((-roughSolution.objectiveValue).number())") // Phase 2: Refine best solution with high accuracy let refinementOptimizer = AdaptiveOptimizer
                              
                                >( maxIterations: 2000, tolerance: 1e-8 ) let finalSolution = try refinementOptimizer.optimize( objective: portfolioObjective, initialGuess: roughSolution.solution, constraints: constraints ) print("Phase 2 (refinement): Sharpe \((-finalSolution.objectiveValue).number())") } catch { print("Hybrid optimization failed: \(error)") } // MARK: - Real-World Example 80-Asset Portfolio Rebalancing // Simplified 80-asset portfolio problem let numAssets = 80 let portfolioValue = 2_000_000_000.0 // $2B AUM // Generate realistic expected returns (4% to 15%, mean ~9%) let expectedReturns80 = VectorN((0..
                                
                                  ) -> Double = { weights in // Expected return let expectedReturn = weights.dot(expectedReturns80) // Portfolio variance var variance = 0.0 for i in 0..
                                  
                                    >.budgetConstraint let longOnlyConstraints80 = MultivariateConstraint
                                    
                                      >.nonNegativity(dimension: numAssets) // Position limits: no more than 5% per asset (diversification requirement) let positionLimits80 = (0..
                                      
                                        >.inequality { w in w[i] - 0.05 // w[i] ≤ 5% } } let allConstraints80 = [budgetConstraint80] + longOnlyConstraints80 + positionLimits80 // Multi-start optimization do { print(String(repeating: "=", count: 70)) print("REAL-WORLD EXAMPLE: 80-ASSET PORTFOLIO REBALANCING") print(String(repeating: "=", count: 70)) print("Portfolio value: $\((portfolioValue / 1_000_000_000).number(1))B") print("Number of assets: \(numAssets)") print("Transaction costs: \(transactionCostBps) bps") print() let robustOptimizer = ParallelOptimizer
                                        
                                          >( algorithm: .inequality, numberOfStarts: 30, maxIterations: 1500, tolerance: 1e-6 ) let startTime = Date() let result = try await robustOptimizer.optimize( objective: objectiveWithCosts, searchRegion: ( lower: VectorN(repeating: 0.0, count: numAssets), upper: VectorN(repeating: 0.05, count: numAssets) // Max 5% per asset ), constraints: allConstraints80 ) let elapsedTime = Date().timeIntervalSince(startTime) print("Multi-Start Optimization (30 starts):") print(" Best Sharpe ratio: \((-result.objectiveValue).number())") print(" Success rate: \(result.successRate.percent())") print(" Total time: \((elapsedTime / 60).number(1)) minutes") // Calculate turnover var totalTurnover = 0.0 var numPositions = 0 for i in 0..
                                          
                                             0.001 { numPositions += 1 } } print("\nPortfolio Characteristics:") print(" Active positions: \(numPositions)/\(numAssets)") print(" Total turnover: \(totalTurnover.percent(1))") print(" Trading costs: $\((portfolioValue * totalTurnover * transactionCostBps / 10000).currency(0))") // Show top 10 positions let topPositions = result.solution.toArray() .enumerated() .sorted { $0.element > $1.element } .prefix(10) print("\nTop 10 Positions:") for (i, (idx, weight)) in topPositions.enumerated() { print(" \(i+1). Asset \(idx): \(weight.percent(2))") } } catch { print("Robust optimization failed: \(error)") } } // Keep playground alive long enough for async task to complete RunLoop.main.run(until: Date().addingTimeInterval(30)) 
                                          
                                        
                                      
                                    
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              

→ Full API Reference: BusinessMath Docs – Parallel Optimization

Experiments to Try

1. Starting Point Sensitivity: Run single-start from 10 different random starting points. How much does the result vary?
2. Scaling Study: Compare 5, 10, 20, 50 starting points. When do diminishing returns start?
3. Algorithm Comparison: Try different base algorithms (.gradientDescent vs .inequality vs .constrained). Which works best for your problem?
4. Search Region Impact: Try narrow vs wide search regions. Does a tighter region around a good initial guess help?

Next Steps

Next Week: Week 10 explores Advanced Optimization Algorithms including L-BFGS for large-scale problems, conjugate gradient methods, and simulated annealing for global optimization.

Case Study Coming: Week 11 includes Real-Time Portfolio Optimization with streaming market data and dynamic constraints.

Series: [Week 9 of 12] | Topic: [Part 5 - Business Applications] | Completed: [4/6]

Topics Covered: Multi-start optimization • Parallel execution • Swift concurrency • Global optimization • Success rate analysis

Playgrounds: [Week 1-9 available] • [Next: Advanced algorithms]