Optimization

We invented DUPLEX, an optimization framework that can provide efficient numerical solutions to nonlinear, nonconvex and functional optimization problems. DUPLEX involves a clever technique to decompose the state, function and functional spaces. DUPLEX can be used to simultaneously navigate these three spaces, while maintaining homomorphic graphs in each space. When it searches the state space, it is more like a search algorithm with a goal. When it searches function space, it can solve nonconvex optimization problems, similar to stochastic gradient descent. When it is used in the functional space, it can solve complex functional problems. Examples of functional problems include planning for an optimal route in a car while avoiding obstacles. Closed form solutions for functional optimization do not exist, and numerical methods are not effective. Due to its ability to solve functional optimization problems, Duplex can be used for path planning.
We were inspired by the rapidly exploring random trees (RRTs) used in robot motion planning, and investigated adding a goal/objective to RRTs. We found the first directed simulation algorithm for analog and mixed signal system (IPs in embedded systems) using our goal oriented RRTs. We found that the goal oriented RRTs or MORRTs converged faster and produced much higher quality solutions than randomized simulations/sampling. Soon we were applying this algorithm to other analog and mixed signal problems like eye diagram optimization, test compression etc and design optimization, with results that surpassed randomized sampling by orders of magnitude in each case. We stepped away from the traditional RRTs and adapted the randomized tree sampling heuristics as per the problem, and called the structures as random trees (not to be confused with random forests!).
We generalized this as DUPLEX, an optimization framework by separating the goal/objective space from the state space. The principle of DUPLEX is to simultaneously and periodically (every iteration) visit both spaces, so the goal space can keep track of the global objective and the state space can track the local traversal. We could also traverse the “function space”, or the space of functions composed of state space variables. The goal space could be in the function space, or the space of functionals, which are functions of functions (higher order functions). For instance, the state space of a car would comprise its location, orientation, inputs from perception and vision units etc., its function space goal would comprise reaching a destination in the shortest time, and functional space goal would be to reach the destination in the shortest time with least energy spent. The separation between these spaces makes the navigation between them more fluid and controllable. We grow random trees in all the spaces simultaneously and maintain the same structure for them
  1. Seyed Nematollah Ahmadyan and Shobha Vasudevan, Duplex: simultaneous parameter-performance exploration for optimizing analog circuits. International Conference on Computer Aided Design (ICCAD) 2016: 19
  2. Seyed Nematollah Ahmadyan, Shobha Vasudevan, Eli Chiprout, Chenjie Gu and Suriyaprakash Natarajan, Fast Eye Diagram Analysis for High-Speed CMOS Circuits. Design Automation and Test in Europe (DATE) 2015: 1377-1382. Best paper nomination (6 out of 600).
  3. Seyed Nematollah Ahmadyan, Suriyaprakash Natarajan and Shobha Vasudevan, Compressing Analog Tests One-at-a-time to Lower Production Costs. Asia South Pacific Design Automation Conference (ASP-DAC) 2016: 539-544
  4. Seyed Nematollah Ahmadyan, Suriyaprakash Natarajan and Shobha Vasudevan, A novel test compression algorithm for analog circuits to decrease production costs. Integration 58: 538-548 (2017)
Non convex optimization of the “egg holder” function using Duplex
Binary classification and clustering using DUPLEX
Test time compression for each test
Random tree