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 $g(v)$ such that: - $g(v)$ is convex - $g(v)$ best fits the data - $g(v)$ is easy to construct - $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:#ff9800 style B fill:#2196f3 style C fill:#4caf50 style D fill:#f44336 style E fill:#9c27b0 style F fill:#f44336 style G fill:#4caf50 </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 - $\mu v_i + \lambda v_{i+1} = v_q$ - Then $g_{PWL}(v_q) = \mu f_i + \lambda f_{i+1} = f_i + \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:#2196f3 style B fill:#4caf50 style C fill:#ff9800 style D fill:#9c27b0 style E fill:#f44336 style F fill:#4caf50 </pre> ] --- Enforce Convexity in PWL Fitting -------------------------------- - Recall that a function $g(v)$ is convex iff for all $v$, $w$ - $(1 - \lambda) g(v) + \lambda g(w) \geq g((1 - \lambda) v + \lambda w)$, $\lambda \in [0, 1]$ .pull-left70[ - In PWL, fitting problem can be formulated as a quadratic programming: - Minimize $\sum_i (f_i - p_i)^2$, subject to: - For each non-boundary vertex $v_i$ - impose $(1 - \lambda) p_{i-1} + \lambda p_{i+1} \geq p_i$ - where $\lambda$ can be found by solving - $(1 - \lambda) v_{i-1} + \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 \lambda_k v_k = v_q$, ($k=1,2,3,\ldots,n+1$) - $\sum_k \lambda_k = 1$ - Then $g_{PWL}(v_q) = \sum_k \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 - \lambda) p_4 + \lambda p_5 \geq \sum_k \mu_k p_k$, $k=1,2,3$ - where $\lambda, \mu_k$ can be found by solving - $(1 - \lambda) v_4 + \lambda v_5 = \sum_k \mu_k v_k$ - $\sum_k \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 - \lambda) p_a + \lambda p_b \geq \sum_k \mu_k p_k$, $k=1,2,\ldots,n$ - where $\lambda, \mu_k$ can be found by solving - $(1 - \lambda) v_a + \lambda v_b = \sum_k \mu_k v_k$ - $\sum_k \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:#ff9800 style B fill:#4caf50 style C fill:#2196f3 style D fill:#9c27b0 style E fill:#9c27b0 style F fill:#9c27b0 style G fill:#9c27b0 style H fill:#4caf50 style I fill:#2196f3 </pre> ] --- class: nord-dark, middle, center Q&A 🎤 ==========