layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # 📏 Quasi-convex Programming @luk036 👨‍💻 · 2026 📅 --- ### 📋 Agenda .pull-left[ **Part 1: Fundamentals** 🧠 - Quasi-convex Functions - Properties & Examples **Part 2: Bisection Method** 📏 - Algorithm Overview - Convergence ] .pull-right[ **Part 3: Applications** 🔬 - EDA Applications - Circuit Design ] --- ### 🎯 What is Quasi-convex Programming? - 🎯 An extension of convex optimization - 🧩 Deals with quasi-convex functions and sets - 🌉 Bridges the gap between convex and non-convex optimization --- ### 📝 Definitions and Properties - 🧩 **Quasi-convex Functions** A function is quasi-convex if its sublevel sets are convex. This allows for more flexibility compared to traditional convex optimization. - ⚖️ **Key Properties** Quasi-convex functions preserve many desirable properties of convex functions, such as local optimality implying global optimality. - 🎯 **Practical Significance** Quasi-convex formulations enable solving a wide range of non-convex problems in EDA efficiently. --- ### 🧩 Quasi-convex Functions Definition: A function ${\color{blue} f}$ is quasi-convex if its sublevel sets are convex. Mathematically: ${\color{blue} f}(\lambda x + (1-\lambda)y) \leq \max\{f(x), f(y)\}$ for all $x, y$ and $\lambda \in [0,1]$ Key property: Every local minimum is a global minimum --- ### ⚖️ Quasiconvex Function Properties .mermaid[ <pre> graph TD A["Function f"] --> B{"Sublevel Sets\nConvex?"} B -->|Yes| C["f is\nQuasiconvex"] B -->|No| D["f is Not\nQuasiconvex"] C --> E["Every Local Min\nis Global Min"] C --> F["Bisection\nMethod Works"] style A fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440 style B fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440 style C fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px,color:#2e3440 style D fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440 style E fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px,color:#2e3440 style F fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440 </pre> ] --- ### 📐 Quasi-convex Programming Problem General form: - Minimize ${\color{blue} f_0(x)}$ - Subject to - ${\color{green} f_i(x)} \leq 0$, $i = 1,\ldots,m$ - ${\color{orange} h_j(x)} = 0$, $j = 1,\ldots,p$ Where ${\color{blue} f_0}$ is quasi-convex, ${\color{green} f_i}$ are convex, and ${\color{orange} h_j}$ are affine. --- ### 🧩 Convex Sublevel Sets .mermaid[ <pre> graph LR A["Domain"] --> B["Sublevel Set\nSα = {x | f(x) ≤ α}"] B --> C{"Sα is\nConvex for\nall α?"} C -->|Yes| D["f is\nQuasiconvex"] C -->|No| E["f is Not\nQuasiconvex"] style A fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px,color:#2e3440 style B fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440 style C fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440 style D fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px,color:#2e3440 style E fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440 </pre> ] A function is quasiconvex iff all its sublevel sets are convex. --- ### 🛠️ Solving Quasi-convex Problems 1. 📏 Bisection method 2. ✅ Convex feasibility problems 3. 🔄 Iterative methods (e.g., cutting-plane algorithms) --- ### 📏 Bisection Method Flow .mermaid[ <pre> graph TD A["Initialize\nl ≤ p* ≤ u"] --> B["t = (l + u)/2"] B --> C["Solve Feasibility\nProblem at t"] C --> D{"Feasible?"} D -->|Yes| E["u = t"] D -->|No| F["l = t"] E --> G{"u - l < ε?"} F --> G G -->|No| B G -->|Yes| H["Optimal\nValue ≈ t"] style A fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px,color:#2e3440 style B fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440 style C fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440 style D fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440 style E fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px,color:#2e3440 style F fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440 style G fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440 style H fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px,color:#2e3440 </pre> ] The bisection method solves a quasiconvex problem by repeatedly solving convex feasibility problems. --- ### 🏭 Quasi-convex Functions in EDA Common quasi-convex functions in circuit design: 1. 📐 Ratios of convex functions (e.g., gain, efficiency) 2. ⛰️ Maximum of convex functions 3. 🧮 Certain posynomial functions --- ### 🔬 Applications in Analog Circuit Design 🤔 1. 🎛️ Amplifier design - Maximize gain-bandwidth product - Minimize power-delay product 2. 🎚️ Filter design - Optimize cutoff frequency to bandwidth ratio 3. 🎵 Oscillator design - Maximize figure of merit (FOM) --- ### 📚 Example: Amplifier Design Objective: Maximize gain-bandwidth product (GBW) ${\color{blue} GBW} = \frac{{\color{green} g_m}}{{\color{orange} C_L}}$ Where: - ${\color{green} g_m}$ is transconductance (convex in design variables) - ${\color{orange} C_L}$ is load capacitance (affine in design variables) This ratio forms a quasi-convex function. --- ### 💻 Applications in Digital Circuit Design 1. 🚪 Gate sizing - Minimize area under delay constraints 2. 🌳 Clock tree synthesis - Minimize skew-to-delay ratio 3. ⚡ Power optimization - Minimize energy-delay product --- ### 📚 Example: Gate Sizing Objective: Minimize area subject to delay constraints Quasi-convex formulation: - Minimize ${\color{green} \sum_i A_i(x_i)}$ - Subject to ${\color{red} D(x)} \leq D_{\max}$ Where ${\color{green} A_i}$ is the area of gate $i$, and ${\color{red} D}$ is the path delay. --- ### 🗺️ Applications in Layout Design 🤔 1. 🧱 Floorplanning - Minimize aspect ratio of chip layout 2. 📍 Placement optimization - Minimize maximum wire length 3. 🛤️ Routing - Optimize wire width for delay-area trade-off --- ### 📚 Example: Floorplanning Objective: Minimize the aspect ratio of the chip layout Quasi-convex formulation: - Minimize $\max\{\frac{{\color{green} W}}{{\color{orange} H}}, \frac{{\color{orange} H}}{{\color{green} W}}\}$ - Subject to area and positioning constraints Where ${\color{green} W}$ and ${\color{orange} H}$ are the width and height of the chip. --- ### 💪 Advantages of Quasi-convex Programming in EDA 1. 🌐 Captures a wider range of problems than convex optimization 2. 🌍 Guarantees global optimality 3. ⚡ Efficient solution methods available 4. ⚖️ Handles trade-offs naturally (e.g., area vs. performance) --- ### 🛠️ Solving via Convex Feasibility .mermaid[ <pre> graph TD A["Quasiconvex\nProblem"] --> B["Pick t\n(objective value)"] B --> C["Construct\nFeasibility Problem"] C --> D{"Convex\nFeasibility?"} D -->|Yes| E["t is\nAchievable"] D -->|No| F["t is Not\nAchievable"] E --> G["Lower t\n(tighter bound)"] F --> H["Raise t"] G --> B H --> B B --> I["Bisection\nConverges"] I --> J["Global\nOptimum"] style A fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440 style B fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440 style C fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440 style D fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440 style E fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px,color:#2e3440 style F fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440 style G fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440 style H fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440 style I fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px,color:#2e3440 style J fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px,color:#2e3440 </pre> ] --- ### ⚠️ Challenges and Limitations 1. ⚠️ More complex to solve than convex problems 2. 🎛️ May require problem-specific solution methods 3. 🧰 Limited availability of general-purpose solvers 4. 🔍 Difficulty in identifying quasi-convexity in complex functions --- ### 🚀 Recent Advances 1. 🔗 Integration with geometric programming 2. 🏭 Development of specialized algorithms for EDA problems 3. 🤖 Incorporation of machine learning techniques 4. 🎯 Extension to multi-objective quasi-convex optimization --- ### 🛠️ Tools and Software 1. 🛠️ CVX (MATLAB-based modeling system) 2. 🐍 CVXPY (Python-based modeling system) 3. 🚀 MOSEK (Commercial optimizer with quasi-convex capabilities) 4. 🏭 Custom EDA tools incorporating quasi-convex solvers --- ### 🔮 Future Directions 1. Improved algorithms for large-scale quasi-convex problems 2. Integration with other optimization techniques (e.g., mixed-integer programming) 3. Application to emerging EDA challenges (e.g., 3D IC design) 4. Development of more user-friendly modeling tools for quasi-convex problems in EDA --- ### ✅ Conclusion - 🎯 Quasi-convex programming: powerful tool for complex EDA problems - 🌉 Bridges gap between convex and non-convex optimization - 🔬 Wide range of applications in analog, digital, and layout design - 🚀 Promising area for future research and development in EDA --- ### 📑 References - Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. - Hershenson, M. D., Boyd, S. P., & Lee, T. H. (2001). Optimal design of a CMOS op-amp via geometric programming. IEEE TCAD. - Relevant papers on quasi-convex optimization in EDA. --- count: false class: nord-dark, middle, center ## Q&A 🎤