1 of 13

Introduction to Optimization Theory

Karthik Suresh, for AID(2)E Collaboration

Department of Data Science

College of William and Mary

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

2 of 13

What is optimization?

The process of finding the best values for the variables of a particular problem to minimize or maximize the objective function
It is a technique to squeeze the best performance out of provided current state of model.
Any predictive studies is an optimization problem,

Classification
Regression
Curve Fitting
Literally anything………..

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

3 of 13

Components of optimization

Objectives

A function expressing the performance of a system, Need to be minimized or maximized

Variable

Design or Decision Variable. A set of unknowns that define the objective function and variable constraints. It can be continuous, discrete or even boolean

Constraints

They are conditions, these allow the variables to take a certain value and exclude regions that are infeasible.

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

4 of 13

Components of Optimization

Optimization Problem

Variables

Constraints

Continuous

Discrete

Constrained

Unconstrained

Objective function

Single

Multi

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

5 of 13

Taxonomy of Optimization Techniques

Its insane !!

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

6 of 13

Taxonomy of Optimization Techniques. My view

Optimization Techniques

Mathematical Optimization

Meta Heuristic Optimization

Heuristic Optimization

Mathematical Optimization

The objective function functional form is known.

Heuristic Optimization

Approximate solutions over exact solutions
Problem specific “rules”. Like building a Gaussian Process model that is specific to the problem

Meta Heuristic Optimization

Approximate solutions over exact solutions
More generalizable. Like GA.

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

7 of 13

Mathematical Optimization

Precise Formulation: Problems are mathematically formulated with an objective function and constraints that are typically well-defined and understood. Mostly optimizes concave or convex functions.

Exact Solutions: Aim to find the globally optimal solution, often using algorithms that guarantee optimality under certain conditions. Hence, struggles with multi modal surfaces.

Structured Problems: Well-suited for problems with clear objectives, known constraints, and where computational resources allow for rigorous solution methods.

Linear Programming
Nonlinear Programming
Combinatorics
Dynamic Programming

Reference:

Hands on Mathematical Optimization in python

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

8 of 13

Heuristic Optimization

Rule-Based Strategies: Intuitive strategies, or domain-specific knowledge to guide the search.. These rules are simple and from experience rather than rigorous mathematical formulations.

Approximate Solutions: No guarantee for global optimal. The solution quality may vary

Exploration vs. Exploitation: Heuristic methods balance between exploration (searching for new potential solutions) and exploitation (focusing on promising areas of the solution space). This balance helps in navigating complex, high-dimensional search spaces efficiently.

Imagine you visit a new city and would like to go to the “best” restaurant. How would you do?

Greedy algorithm
Local Search
Simulated annealing
Tabu search
Bayesian optimization

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

9 of 13

Heuristic Optimization

Imagine you visit a new city and would like to go to the “best” restaurant. How would you do?

You might ask locals for recommendations
Follow crowds of people
Look for places with good reviews posted

These methods don't guarantee you'll find the absolute best restaurant, but they help you quickly find a good one based on available information and your intuition..

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

10 of 13

Selected quick examples on when to use what

Mathematical Optimization

Microchip production problem

Finance: Maximizing gains

Operations: Supply chain optimization

Heuristic (or metaheuristic)

Multi modal objective optimization

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

11 of 13

Metaheuristic Optimization

Evolutionary algorithms
Particle Swarm Optimization
Ant Colony Optimization
Bee Colony optimization
Harmony Search

Similar to heuristic: They work as well to find near optimal solutions. No guarantee for global optimal.

Not the entire experience: Unlike heuristic approaches, it may not directly use all of the past experience.

Scope and Generality: Metaheuristics are designed to be applicable across a wide range of optimization problems without requiring problem-specific adaptations. They provide a framework or strategy rather than a specific algorithm tailored to a particular problem.

Iterative Improvement: refine candidate solutions over “generations”. They are often parallel search strategic in nature

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

12 of 13

Parallel vs Sequential (metaheuristic vs heuristic)

Has been widely used for solving MOO problems
population /off spring — diversity —
Relatively easier to implement
Complexity relatively easy to compute
Ideal — Cost of computing “cheap”
Successful with large Design and Objective parameters
No Map : “Design” “Objectives”

Has been around for a while, gaining popularity
Sequential Strategy — global minimization
Relatively harder to implement
Complexity relatively easy to compute
Ideal — simulations can be heavily parallelized
Currently, Not recommended beyond 4-5 Objective parameters
Can Map : “Design” “Objectives” — Fast simulator can be built

Parallel

Sequetial

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC

Here is how the optimisation workflow works. We use NSGA2 to suggest new design points. We simulate the new design point in the Geant4 based framework (Fun4All). Once that is done we perform an analysis on the result. So for the problem in hand we have 3 objectives namely the momentum resolution, theta resolution, Kalman Filtering inefficiency, This is a measure on the ability of tracking reconstruction. Without much math, these resolution measures are a ratio with respect to the baseline detector that is currently proposed in ECCE. The errors on these fits are also promptly carried over into the calculation.

As mentioned the problem also has Geometric constraints, The outermost barrel layer could have the radii less than 51cm the outer vertex layer should be less than 15 cms, the 4th barrel layer has to be less than 45 cms. The forward most Z disk has to be less than 125 cms, Minimum distance between any 2 layers of the detector has to be greater than or equal to 1 cm.

Finally once we have the optimal set of solutions then we can validate our solutions against other objectives such as the vertex resolution, reconstruction efficiency etc.

13 of 13

Multi Objective Optimization : Visual Intro

What is “Optimal”?

Non-dominated (Pareto) Solutions
How to compute them? What is its computational complexity?

How to rank solutions?

“Fronts” of solutions

How can we distinguish between the fronts here?

Hyper volume metric

AID2E Boot camp July 8 - 19 2024

AI Assisted Detector Design for EIC