layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # 🥚 Convex Piecewise-Linear Fitting @luk036 👨‍💻 · 2026 📅 --- ### 💡 Convex PWL Fitting: Why? - LP modeling 📈 - Max-monomial fitting to circuit models (for geometric programming based optimization) (Kim et al. ICCAD 2004) 🏭 - Previous work which uses max-affine function may fail to converge (Magnani and Boyd 2009) ⚠️ (need update) --- ### 📋 Problem Formulation - Given $m$ data points $V = \{ v_1, v_2, \ldots, v_m \}$ in $R^n$. 📍 - Look for a function ${\color{blue} g(v)}$ such that: - ${\color{blue} g(v)}$ is convex ✅ - ${\color{blue} g(v)}$ best fits the data 🎯 - ${\color{blue} g(v)}$ is easy to construct 🏗️ - ${\color{blue} g(v)}$ is easy to evaluate (all previous works forget this point) ⚡ --- ### 🔄 PWL Fitting Process .mermaid[ <pre> graph TD A[Data Points] --> B[Sort & Triangulate] B --> C[PWL Interpolation] C --> D{Convex?} D -->|Yes| E[QP: Minimize error] D -->|No| F[Add convex constraints] F --> C E --> G[Convex PWL Fit] style A fill:#fff3e0,stroke:#e65100,stroke-width:3px style B fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style C fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style D fill:#ffcdd2,stroke:#c62828,stroke-width:3px style E fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px style F fill:#ffcdd2,stroke:#c62828,stroke-width:3px style G fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] --- ### 📏 Piecewise Linear Interpolation - Recall a simple univariate problem (i.e. $n=1$) without convexity requirements. Piecewise linear (PWL) interpolation (table lookup) is widely used in engineering community: 🔍 - Construction: organize the data in a lienar order (i.e. sorting), which takes $O(m \log m)$ time. ⏱️ - Evaulation at $v_q$: - Locate the interval $[v_1, v_{i+1}]$ such that $v_i \leq v_q < v_{i+1}$ - Find the barycentric coordinate $(\lambda, \mu)$ of $v_q$ by solving - ${\color{orange} \lambda} v_{i+1} + {\color{green} \mu} v_i = v_q$ - Then $g_{PWL}(v_q) = {\color{green} \mu} f_i + {\color{orange} \lambda} f_{i+1} = f_i + {\color{orange} \lambda} (f_{i+1} - f_i)$  --- ### 📐 Convexity Enforcement .mermaid[ <pre> graph TD A[Neighboring Simplices] --> B[Find barycentric coords] B --> C[Form linear inequality] C --> D[Add to QP constraints] D --> E[Solve QP] E --> F[Convex PWL function] style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style C fill:#fff3e0,stroke:#e65100,stroke-width:3px style D fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px style E fill:#ffcdd2,stroke:#c62828,stroke-width:3px style F fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] --- ### ✅ Enforce Convexity in PWL Fitting - Recall that a function ${\color{blue} g(v)}$ is convex iff for all $v$, $w$ - $(1 - {\color{orange} \lambda}) {\color{blue} g(v)} + {\color{orange} \lambda} {\color{blue} g(w)} \geq {\color{blue} g}((1 - {\color{orange} \lambda}) v + {\color{orange} \lambda} w)$, ${\color{orange} \lambda} \in [0, 1]$ .pull-left70[ - In PWL, fitting problem can be formulated as a quadratic programming: - Minimize $\sum_i ({\color{blue} f_i} - {\color{coral} p_i})^2$, subject to: - For each non-boundary vertex $v_i$ - impose $(1 - {\color{orange} \lambda}) {\color{coral} p_{i-1}} + {\color{orange} \lambda} {\color{coral} p_{i+1}} \geq {\color{coral} p_i}$ - where ${\color{orange} \lambda}$ can be found by solving - $(1 - {\color{orange} \lambda}) v_{i-1} + {\color{orange} \lambda} v_{i+1} \geq v_i$ - 👉 Note: linear constraint ] .pull-right30[  ] --- ### 📊 Multivariate Case ($n > 1$) - Recall that *barycentric triangulated interpolation* is a natural extension of PWL interpolation: 🔺 - Construction: organize the data in Delaunay Triangulation, which takes $O(m \log m)$ time. ⏱️ - Evaulation at $v_q$: - Locate the simplex $[v_1, v_2, v_3, \ldots, v_{i+1}]$ that contains $v_q$ - Find the barycentric coordinate of $v_q$ by solving - $\sum_k {\color{orange} \lambda_k} v_k = v_q$, ($k=1,2,3,\ldots,n+1$) - $\sum_k {\color{orange} \lambda_k} = 1$ - Then $g_{PWL}(v_q) = \sum_k {\color{orange} \lambda_k} f_k$ - In Python, `scipy.interpolate.LinearNDInterpolator` can perform this interpolation. 🐍 --- ### 🔷 Delaunay Triangulation (DT) - The Delaunay triangulation of a set of points in d-dimensional spaces is in fact the projection of the points of convex hull onto a (d+1)-dimensional paraboloid. Therefore, it can be constructed by constructiong a convex hull. 🌐 - Python provides basic functions of DT (check `scipy.spatial.Delaunay`) 🐍 .pull-left70[ - For bivariate can ($n=2$), to enforce convexity: - For each non-boundary edge $(v_1, v_2)$, - impose $(1 - \lambda) p_3 + \lambda p_4 \geq (1 - \mu) p_1 + \mu p_2$ - where $\lambda, \mu$ can be found by solving - $(1 - \lambda) v_3 + \lambda v_4 = (1 - \mu) v_1 + \mu v_2$ - 👉 Note: linear constraint ] .pull-right30[  ] --- ### 📐 Enforce Convexity for $n = 3$ .pull-left70[ - For $n=3$, to enforce convexity: - For each non-boundary triangle $(v_1, v_2, v_3)$ - impose $(1 - {\color{orange} \lambda}) {\color{coral} p_4} + {\color{orange} \lambda} {\color{coral} p_5} \geq \sum_k {\color{green} \mu_k} {\color{coral} p_k}$, $k=1,2,3$ - where ${\color{orange} \lambda}, {\color{green} \mu_k}$ can be found by solving - $(1 - {\color{orange} \lambda}) v_4 + {\color{orange} \lambda} v_5 = \sum_k {\color{green} \mu_k} v_k$ - $\sum_k {\color{green} \mu_k} = 1$ - 👉 Note: linear constraint! ] .pull-right30[  ] --- ### 🔄 Enforce Convexity for general cases - In general, - For each non-boundary n-simplex $(v_1, v_2, \ldots, v_n)$, - impose $(1 - {\color{orange} \lambda}) {\color{coral} p_a} + {\color{orange} \lambda} {\color{coral} p_b} \geq \sum_k {\color{green} \mu_k} {\color{coral} p_k}$, $k=1,2,\ldots,n$ - where ${\color{orange} \lambda}, {\color{green} \mu_k}$ can be found by solving - $(1 - {\color{orange} \lambda}) v_a + {\color{orange} \lambda} v_b = \sum_k {\color{green} \mu_k} v_k$ - $\sum_k {\color{green} \mu_k} = 1$ --- ### 🔬 Numerical Experiment .pull-left[  without convex fitting ] .pull-right[  with convex fitting ] --- ### 📊 Univariate vs Multivariate .mermaid[ <pre> graph TD A[PWL Interpolation] --> B[Univariate n=1] A --> C["Multivariate n > 1"] B --> D["Sort data O(m log m)"] B --> E[Interval lookup] C --> F["Delaunay Tri. O(m log m)"] C --> G[Simplex containment] D --> H[Interpolate] E --> H F --> I[Interpolate] G --> I style A fill:#fff3e0,stroke:#e65100,stroke-width:3px style B fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style C fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style D fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px style E fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px style F fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px style G fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px style H fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style I fill:#e3f2fd,stroke:#1565c0,stroke-width:3px </pre> ] --- count: false class: nord-dark, middle, center ## Q&A 🎤