layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # Introduction to Convex Optimization @luk036 👨‍💻 · 2026 📅 --- ### 📋 Agenda .pull-left[ **Part 1: Fundamentals** 🧠 - What is Convex Optimization? - Key Concepts & Formulation **Part 2: Tools & CVXPY** 🛠️ - CVXPY Features - Basic Usage Examples ] .pull-right[ **Part 3: Applications** 🔬 - EDA Applications - Circuit Design ] --- ### What is Convex Optimization? - Convex optimization is a subfield of mathematical optimization that deals with problems where the objective function and the feasible region are both convex. - A problem is convex if the objective function $f(x)$ is convex (i.e., $f(\theta x_1 + (1-\theta) x_2) \leq \theta f(x_1) + (1-\theta) f(x_2)$ for all $x_1, x_2$ in the domain and $\theta$ in [0, 1]) and the feasible set defined by the constraints is a convex set. .mermaid[ <pre> graph LR subgraph "Convex Set" CS["∀ x₁, x₂ ∈ C, θx₁ + (1-θ)x₂ ∈ C"] end subgraph "Non-Convex Set" NS["∃ x₁, x₂ ∈ C, θx₁ + (1-θ)x₂ ∉ C"] end style CS fill:#4caf50 style NS fill:#f44336 </pre> ] --- ### Key Concepts 1. Convex Functions 2. Convex Sets 3. Convex Optimization Problem 4. Duality 5. KKT Conditions .mermaid[ <pre> graph TD A[Convex Function f] --> B["f(θx₁ + (1-θ)x₂) ≤ θf(x₁) + (1-θ)f(x₂)"] B --> C[Jensen's Inequality] B --> D[Global Minimum Property] style A fill:#4caf50 style B fill:#2196f3 style C fill:#9c27b0 style D fill:#9c27b0 </pre> ] --- ### Key Characteristics of Convex Optimization 1. **Global Optimum**: Any local minimum is also a global minimum. 2. **Efficient Algorithms**: There are well-established algorithms like Gradient Descent, Interior-Point Methods, and Subgradient Methods to solve these problems efficiently. 3. **Wide Applicability**: Convex optimization is widely used in various fields such as machine learning, finance, engineering, and operations research. --- ### Basic Formulation A standard convex optimization problem can be formulated as: $$ \begin{array}{ll} \text{minimize} & \quad f(x) \\ \text{subject to} & \quad g_i(x) \leq 0, \quad i = 1, \ldots, m \\ & \quad h_j(x) = 0, \quad j = 1, \ldots, p \end{array} $$ where $f(x)$ is a convex objective function, $g_i(x)$ are convex inequality constraint functions, and $h_j(x)$ are affine equality constraint functions. .mermaid[ <pre> graph TD OP[Optimization] --> LP[Linear Programming] OP --> QP[Quadratic Programming] OP --> CP[Convex Programming] OP --> NLP[Non-Linear Programming] CP --> GP[Geometric Programming] CP --> SDP[Semidefinite Programming] style OP fill:#ff9800 style LP fill:#4caf50 style QP fill:#2196f3 style CP fill:#4caf50 style NLP fill:#f44336 style GP fill:#9c27b0 style SDP fill:#9c27b0 </pre> ] --- ### Tools and Software 1. CVX (MATLAB-based modeling system) 2. CVXPY (Python-based modeling system) 3. MOSEK (Commercial optimizer) 4. Gurobi (Commercial optimizer) 5. Custom EDA tools with integrated convex solvers --- ### Introduction to CVXPY CVXPY is an open-source Python library designed for convex optimization. It provides a user-friendly interface for defining and solving convex optimization problems, making it accessible to both researchers and practitioners. --- ### Key Features of CVXPY 1. **Expressive Syntax**: Allows users to define optimization problems in a natural mathematical syntax. 2. **Automatic Differentiation**: Supports automatic differentiation, making it easier to define complex objective functions and constraints. 3. **Solver Integration**: Interfaces with various solvers like ECOS, SCS, and OSQP, allowing users to choose the most appropriate solver for their problem. 4. **Extensibility**: Supports extensions for advanced optimization problems, including mixed-integer programming and stochastic optimization. --- ### Basic Usage Here's a simple example of how to use CVXPY: ```python import cvxpy as cp # Define the variables x = cp.Variable() y = cp.Variable() # Define the objective function objective = cp.Minimize((x - 1)**2 + (y - 2.5)**2) # Define the constraints constraints = [x + y == 1, x - y >= 1] # Formulate the problem problem = cp.Problem(objective, constraints) # Solve the problem result = problem.solve() # Output the results print(f"Optimal value: {result}") print(f"Optimal x: {x.value}") print(f"Optimal y: {y.value}") ``` --- ### Advantages of Using CVXPY 1. **Ease of Use**: Simplifies the process of formulating and solving optimization problems. 2. **Flexibility**: Can handle a wide range of convex optimization problems. 3. **Community and Support**: Backed by a strong community and extensive documentation, making it easier to get help and find resources. --- ### Applications 1. **Machine Learning**: Regularization, support vector machines, and neural network training. 2. **Finance**: Portfolio optimization, risk management, and asset allocation. 3. **Engineering**: Control systems, signal processing, and network design. 4. **Operations Research**: Supply chain management, logistics, and scheduling. --- ### Applications in Electronic Design Automation 1. Circuit Design and Sizing 🤔 2. Power Optimization 3. Signal and Power Integrity 4. Digital filter design 5. Statistical Optimization --- ### 🎛️ Circuit Design and Sizing 🤔 - Transistor sizing - Analog circuit design (e.g., op-amps, filters) - Digital gate sizing 📚 Example: Minimize: Area Subject to: - Delay ≤ Target_Delay - Power ≤ Max_Power --- ### Power Optimization - Dynamic and static power minimization - Voltage scaling - Clock gating optimization 📚 Example: Minimize: Total_Power = Dynamic_Power + Static_Power Subject to: Performance ≥ Target_Performance --- ### Signal and Power Integrity - Crosstalk minimization - IR drop optimization - Decoupling capacitor placement 📚 Example: Minimize: Max_Crosstalk Subject to: - Signal_Integrity_Constraints - Power_Integrity_Constraints --- ### Case Study: Op-Amp Design 🤔 Objective: Design an op-amp with optimal performance Variables: Transistor sizes, bias currents Constraints: - Gain ≥ Min_Gain - Bandwidth ≥ Min_Bandwidth - Slew Rate ≥ Min_Slew_Rate - Power ≤ Max_Power Formulated as a geometric program and solved using convex optimization techniques. .mermaid[ <pre> graph TD A[Optimization Problem] --> B[Lagrangian Function] B --> C[Stationarity] B --> D[Primal Feasibility] B --> E[Complementary Slackness] C --> F["∇f + Σλᵢ∇gᵢ + Σμⱼ∇hⱼ = 0"] D --> G["gᵢ(x) ≤ 0, hⱼ(x) = 0"] E --> H["λᵢgᵢ(x) = 0, λᵢ ≥ 0"] style A fill:#ff9800 style B fill:#ff9800 style C fill:#4caf50 style D fill:#2196f3 style E fill:#9c27b0 style F fill:#4caf50 style G fill:#2196f3 style H fill:#9c27b0 </pre> ] --- ### Challenges and Limitations 1. Modeling non-convex constraints 2. Handling discrete variables (e.g., in digital design) 3. Scalability for very large designs 4. Integration with existing EDA workflows --- ### Recent Advances 1. Robust optimization for handling uncertainties 2. Mixed-integer convex programming for digital design 3. Machine learning integration for problem formulation 4. Distributed and parallel algorithms for large-scale problems --- ### 🔮 Future Directions 1. Automated convex modeling of complex EDA problems 2. Integration of convex optimization in commercial EDA tools 3. Application to emerging technologies (e.g., quantum computing, neuromorphic hardware) 4. Multi-objective optimization for complex trade-offs --- ### Conclusion - Convex programming: powerful tool for various EDA problems - Enables efficient, globally optimal solutions - Wide range of applications from circuit design to layout optimization - Ongoing research to address challenges and expand capabilities - Promising future in enhancing EDA methodologies --- ### 📑 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. --- class: nord-dark, middle, center ## Q&A 🎤