layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # When "Convex Optimization" Meets "Network Flow" 🔄 @luk036 👨‍💻 · 2026 📅 --- class: nord-light, middle, center ## 🎬 Introduction --- ### Overview 📋 - Network flow problems can be solved efficiently and have a wide range of applications. 🌐 - Unfortunately, some problems may have other additional constraints that make them impossible to solve with current network flow techniques. 🚧 - In addition, in some problems, the objective function is quasi-convex rather than convex. 📈 - In this lecture, we will investigate some problems that can still be solved by network flow techniques with the help of convex optimization. 🔍 --- class: nord-light, middle, center ### Parametric Potential Problems --- ### Parametric potential problems 🧮 Consider: $$ \begin{array}{ll} \text{maximize} & {\color{purple}g}({\color{darkblack}z}), \\ \text{subject to} & {\color{blue}y} \leq {\color{purple}d}({\color{darkblack}z}), \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, \end{array} $$ where ${\color{purple}g}({\color{darkblack}z})$ and ${\color{purple}d}({\color{darkblack}z})$ are concave. 👉 Note: the parametric flow problems can be defined in a similar way. 🔄 --- ### Network Flow insights: 🔍 - For fixed ${\color{darkblack}z}$, the problem is feasible precisely when there exists no negative cycle 🔄 - Negative cycle detection can be done efficiently using the Bellman-Ford-like methods ⚡ - If a negative cycle ${\color{lime}C}$ is found, then $\sum_{(i,j)\in {\color{lime}C} } {\color{purple}d}_{ij}({\color{darkblack}z}) < 0$ --- ### Convex Optimization insights: 🧠 - If both sub-gradients of ${\color{purple}g}({\color{darkblack}z})$ and ${\color{purple}d}({\color{darkblack}z})$ are known, then the *bisection method* can be used for solving the problem efficiently. ✂️ - Also, for multi-parameter problems, the *ellipsoid method* can be used. 🏈 --- ### Quasi-convex Minimization Consider: $$ \begin{array}{ll} \text{minimize} & {\color{purple}f}({\color{darkblack}z}), \\ \text{subject to} & {\color{blue}y} \leq {\color{purple}d}({\color{darkblack}z}), \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, \end{array} $$ where ${\color{purple}f}({\color{darkblack}z})$ is *quasi-convex* and ${\color{purple}d}({\color{darkblack}z})$ are concave. --- ### 📚 Example of Quasi-Convex Functions 📈 - $\sqrt{|y|}$ is quasi-convex on $\mathbb{R}$ ➗ - $\log(y)$ is quasi-linear on $\mathbb{R}_{++}$ - $f(x, y) = x y$ is quasi-concave on $\mathbb{R}_{++}^2$ ✖️ - Linear-fractional function: - $f(x)$ = $(a^\mathsf{T} x + b)/(c^\mathsf{T} x + d)$ ➗ - dom $f$ = $\{x \,|\, c^\mathsf{T} x + d > 0 \}$ ✅ - Distance ratio function: - $f(x)$ = $\| x - a\|_2 / \| x - b \|_2$ 📏 - dom $f$ = $\{x \,|\, \| x - a\|_2 \le \| x - b \|_2 \}$ 🎯 --- ### Convex Optimization insights: 🧠 If ${\color{purple}f}$ is quasi-convex, there exists a family of functions ${\color{purple}\Phi}_{\color{coral}\gamma}$ such that: - ${\color{purple}\Phi}_{\color{coral}\gamma}({\color{darkblack}z})$ is convex w.r.t. ${\color{darkblack}z}$ for fixed ${\color{coral}\gamma}$ 📈 - ${\color{purple}\Phi}_{\color{coral}\gamma}({\color{darkblack}z})$ is non-increasing w.r.t. ${\color{coral}\gamma}$ for fixed ${\color{darkblack}z}$ - ${\color{coral}\gamma}$-sublevel set of ${\color{purple}f}$ is $0$-sublevel set of ${\color{purple}\Phi}_{\color{coral}\gamma}$, - i.e., ${\color{purple}f}({\color{darkblack}z}) \le {\color{coral}\gamma}$ iff ${\color{purple}\Phi}_{\color{coral}\gamma}({\color{darkblack}z}) \le 0$ ↔️ For example: - ${\color{purple}f}({\color{darkblack}z}) = {\color{purple}p}({\color{darkblack}z})/{\color{purple}q}({\color{darkblack}z})$ with $p$ convex, $q$ concave ${\color{purple}p}({\color{darkblack}z}) \ge 0$, ${\color{purple}q}({\color{darkblack}z}) > 0$ on dom ${\color{purple}f}$, - can take ${\color{purple}\Phi}_{\color{coral}\gamma}({\color{darkblack}z})$ = ${\color{purple}p}({\color{darkblack}z}) - {\color{coral}\gamma} \cdot {\color{purple}q}({\color{darkblack}z})$ --- ### Convex Optimization insights: 🧠 Consider a convex feasibility problem: $$ \begin{array}{ll} \text{find} & {\color{darkblack}z}, \\ \text{s. t.} & {\color{purple}\Phi}_{\color{coral}\gamma}({\color{darkblack}z}) \le 0, \\ & {\color{blue}y} \leq {\color{purple}d}({\color{darkblack}z}), {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, \end{array} $$ - If feasible, we conclude that ${\color{coral}\gamma} \ge p^*$; ✅ - If infeasible, ${\color{coral}\gamma} < p^*$. ❌ Binary search on ${\color{coral}\gamma}$ can be used for obtaining $p^*$. 🔍 --- ### Quasi-convex Network Problem 🌐 - Again, the feasibility problem ([eq:quasi]) can be solved efficiently by the bisection method or the ellipsoid method, together with the negative cycle detection technique. ⚡ - Any EDA's applications ??? 💻 --- ### Monotonic Minimization - Consider the following problem: $$\begin{array}{ll} \text{minimize} & \max_{ij} {\color{olive}f}_{ij}({\color{blue}y}_{ij}), \\ \text{subject to} & {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, \end{array}$$ where ${\color{olive}f}_{ij}({\color{blue}y}_{ij})$ is non-decreasing. 📈 - The problem can be recast as: $$\begin{array}{ll} \text{maximize} & {\color{coral}\beta}, \\ \text{subject to} & {\color{blue}y} \leq {\color{olive}f^{-1} }({\color{coral}\beta}), \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, \end{array}$$ where ${\color{olive}f^{-1} }({\color{coral}\beta})$ is non-decreasing w.r.t. ${\color{coral}\beta}$. 🔄 --- ### E.g. Yield-driven Optimization 🎯 - Consider the following problem: $$\begin{array}{ll} \text{maximize} & \min_{ij} {\color{olive}\Pr}({\color{blue}y}_{ij} \leq \tilde{\color{blue}d}_{ij}) \\ \text{subject to} & {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, \end{array}$$ where $\tilde{\color{blue}d}_{ij}$ is a random variable. 🎲 - Equivalent to the problem: $$\begin{array}{ll} \text{maximize} & {\color{coral}\beta}, \\ \text{subject to} & {\color{coral}\beta} \leq {\color{olive}\Pr}({\color{blue}y}_{ij} \leq \tilde{\color{blue}d}_{ij}), \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, \end{array}$$ --- ### E.g. Yield-driven Optimization (II) 🎯 - Let ${\color{olive}F}(x)$ is the cdf of $\tilde{\color{blue}d}$. - Then: $$\begin{array}{lll} & & {\color{coral}\beta} \leq {\color{olive}\Pr}({\color{blue}y}_{ij} \leq \tilde{\color{blue}d}_{ij}) \\ & \Rightarrow & {\color{coral}\beta} \leq 1 - F_{ij}({\color{blue}y}_{ij}) \\ & \Rightarrow & {\color{blue}y}_{ij} \leq {\color{olive}F_{ij}^{-1} }(1 - {\color{coral}\beta}) \end{array}$$ - The problem becomes: $$\begin{array}{ll} \text{maximize} & {\color{coral}\beta}, \\ \text{subject to} & {\color{blue}y}_{ij} \leq {\color{olive}F_{ij}^{-1} }(1 - {\color{coral}\beta}), \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, \end{array}$$ --- ### Network Flow insights 🌐 - Monotonic problem can be solved efficiently using cycle-cancelling methods such as Howard's algorithm. ⚡ --- ### 📚 Example - clock period & yield-driven co-optimization ⏰🎯 $$ \begin{array}{cll} \text{minimize} & {\color{darkblack}T_\text{CP} } / {\color{darkblack}\beta} \\ \text{subject to} & {\color{blue}y_{ij} } \le {\color{darkblack}T_\text{CP} } - {\color{olive}F_{ij}^{-1} }({\color{darkblack}\beta}), & \forall (i,j) \in {\color{lime}E_s} \,,\\ & {\color{blue}y_{ji} } \le {\color{olive}F_{ij}^{-1} }(1 - {\color{darkblack}\beta}), & \forall (j,i) \in {\color{lime}E_h} \,, \\ & {\color{darkblack}T_\text{CP} } \ge 0, \, 0 \le {\color{darkblack}\beta} \le 1 \, . \end{array} $$ - 👉 Note that ${\color{olive}F_{ij}^{-1} }(x)$ is not concave in general in $[0, 1]$. ⚠️ - Fortunately, we are most likely interested in optimizing circuits for high yield rather than the low one in practice. 🎯 - Therefore, by imposing an additional constraint to ${\color{darkblack}\beta}$, say ${\color{darkblack}\beta} \geq 0.8$, the problem becomes convex. ✅ --- ### 📚 Example - clock period & yield-driven co-optimization ⏰🎯 The problem can be reformulated as: $$ \begin{array}{cll} \text{minimize} & {\color{coral}\gamma} \\ \text{subject to} & {\color{darkblack}T_\text{CP} } - {\color{coral}\gamma} {\color{darkblack}\beta} \le 0\\ & {\color{blue}y_{ij} } \le {\color{darkblack}T_\text{CP} } - {\color{purple}F_{ij}^{-1} }({\color{darkblack}\beta}), & \forall (i,j) \in {\color{lime}E_s} \,,\\ & {\color{blue}y_{ji} } \le {\color{purple}F_{ij}^{-1} }(1 - {\color{darkblack}\beta}), & \forall (j,i) \in {\color{lime}E_h} \,, \\ & {\color{darkblack}T_\text{CP} } \ge 0, \, 0.8 \le {\color{darkblack}\beta} \le 1 \, . \end{array} $$ --- class: nord-light, middle, center ## Min-cost flow problems 💰🌊 --- ### Min-Cost Flow Problem (linear) 📈 Consider: $$\begin{array}{ll} \text{min} & {\color{blue}d}^\mathsf{T} {\color{green}x} + {\color{blue}p} \\ \text{s. t.} & {\color{green}c^-} \leq {\color{green}x} \leq {\color{green}c^+}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ - some ${\color{green}c^+}$ could be $+\infty$ some ${\color{green}c^-}$ could be $-\infty$. - ${\color{blue}A^\mathsf{T} } $ is the incidence matrix of a network $G$. 🌐 --- ### Conventional Algorithms ⚙️ - Augmented-path based: - Start with an infeasible solution 🚧 - Inject minimal flow into the augmented path while maintaining infeasibility in each iteration 🔄 - Stop when there is no flow to inject into the path. 🛑 - Cycle cancelling based: - Start with a feasible solution ${\color{green}x_0}$ ✅ - find a better sol'n ${\color{green}x_1} = {\color{green}x_0} + \alpha \triangle {\color{green}x}$, where $\alpha$ is positive and $\triangle {\color{green}x}$ is a negative cycle indicator. 🔄 --- ### General Descent Method 1. **Input**: a starting $x \in$ dom $f$ 🏁 2. **Output**: $x^*$ 🎯 3. **repeat** 1. Determine a descent direction $p$. 🔽 2. Line search. Choose a step size $\alpha > 0$. 📏 3. Update. $x := x + \alpha \cdot p$ 🔄 4. **until** a stopping criterion is satisfied. 🛑 --- ### Common Descent Directions 🧭 - Gradient descent: $p = -\nabla f(x)^\mathsf{T}$ - Steepest descent: - $\triangle x_{nsd}$ = argmin$\{\nabla f(x)^\mathsf{T} v \mid \|v\|=1 \}$ 🏔️ - $\triangle x$ = $\|\nabla f(x)\| \triangle x_{nsd}$ (un-normalized) 📏 - Newton's method: - $p = -\nabla^2 f(x)^{-1} \nabla f(x)$ 🧮 - Levenberg-Marquardt: - Hybrid of Newton and Gradient Descent 🔀 - $p = -(\nabla^2 f(x) + \lambda I)^{-1} \nabla f(x)$ ⚖️ - Conjugate gradient method: - $p$ is "orthogonal" to all previous $p$'s ↔️ - Stochastic subgradient method: - $p$ is calculated from a set of sample data (instead of using all data) 🎲 --- ### Network Flow insights (II) 🌐 - Here, there is a better way to choose ${\color{green}p}$! 💡 - Let ${\color{green}x} := {\color{green}x} + \alpha {\color{green}p}$, then we have: $$\begin{array}{lll} \text{min} & {\color{blue}d}^\mathsf{T} {\color{green}x_0} + \alpha {\color{blue}d}^\mathsf{T} {\color{green}p} & \Rightarrow {\color{blue}d}^\mathsf{T} < 0 \\ \text{s. t.} & -{\color{green}x_0} \leq \alpha {\color{green}p} \leq {\color{green}c}-{\color{green}x_0} & \Rightarrow \text{residual graph} \\ & {\color{blue}A^\mathsf{T} } {\color{green}p} = 0 & \Rightarrow {\color{green}p} \text{ is a cycle!} \end{array}$$ - In other words, choose ${\color{green}p}$ to be a negative cycle with cost $d$! 🔄 - Simple negative cycle, or - Minimum mean cycle ⚖️ --- ### Network Flow insights (III) 🌐 - Step size is limited by the capacity constraints: ⚖️ - $\alpha_1 = \min_{ij} \{ {\color{green}c^+} - {\color{green}x}^0\}$, for $\triangle {\color{green}x}_{ij} > 0$ ➕ - $\alpha_2 = \min_{ij} \{ {\color{green}x}^0 - {\color{green}c^-}\}$, for $\triangle {\color{green}x}_{ij} < 0$ ➖ - $\alpha_\mathrm{lin}$ = min$\{\alpha_1, \alpha_2\}$ ↔️ - If $\alpha_\mathrm{lin} = +\infty$, the problem is unbounded. ∞ --- ### Network Flow insights (IV) 🌐 - An initial feasible solution can be obtained by a similar construction of the residual graph and cost vector. 🏗️ - The LEMON package implements this cycle cancelling algorithm. 🍋 --- ### Min-Cost Flow Convex Problem 📈 - Problem Formulation: $$\begin{array}{ll} \text{min} & {\color{purple}f}({\color{green}x}) \\ \text{s. t.} & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ where ${\color{purple}f}({\color{green}x})$ is now non-linear but convex. --- ### Common Types of Line Search 🔍 - Exact line search: $t$ = argmin$_{t>0} {\color{purple}f}(x + t\triangle x)$ 🎯 - Backtracking line search (with parameters $\alpha \in (0,1/2), \beta \in (0,1)$) ↩️ - starting from $t = 1$, repeat $t := \beta t$ until $${\color{purple}f}(x + t\triangle x) \le {\color{purple}f}(x) + \alpha t \nabla {\color{purple}f}(x)^\mathsf{T} \triangle x$$ - graphical interpretation: backtrack until $t \leq t_0$ --- ### Network Flow insights (V) 🌐 - The step size is further limited by the following: ⚖️ - $\alpha_\mathrm{cvx} = \min\{\alpha_\mathrm{lin}, t\}$ ↔️ - In each iteration, choose $\triangle {\color{green}x}$ as a negative cycle of $G_x$, with cost $\nabla {\color{purple}f}({\color{green}x})$ such that $\nabla {\color{purple}f}({\color{green}x})^\mathsf{T} \triangle {\color{green}x} < 0$ 🔄 --- ### Quasi-convex Minimization - Problem Formulation: $$\begin{array}{ll} \text{min} & {\color{purple}f}({\color{green}x}) \\ \text{s. t.} & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ - The problem can be recast as: $$\begin{array}{ll} \text{min} & {\color{coral}\gamma} \\ \text{s. t.} & {\color{purple}f}({\color{green}x}) \leq {\color{coral}\gamma}, \\ & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ --- ### Convex Optimization insights (II) - Consider a convex feasibility problem: $$\begin{array}{ll} \text{find} & {\color{green}x} \\ \text{s. t.} & {\color{purple}\Phi}_{\color{coral}\gamma}({\color{green}x}) \leq 0, \\ & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ - If feasible, we conclude that ${\color{coral}\gamma} \ge p^*$; ✅ - If infeasible, ${\color{coral}\gamma} < p^*$. ❌ - Binary search on ${\color{coral}\gamma}$ can be used for obtaining $p^*$. 🔍 --- ### Network Flow insights (VI) 🌐 - Choose $\triangle {\color{green}x}$ as a negative cycle of $G_x$ - with cost $\nabla {\color{purple}\Phi}_{\color{coral}\gamma}({\color{green}x})$ 🔄 - If no negative cycle is found, and ${\color{purple}\Phi}_{\color{coral}\gamma}({\color{green}x}) > 0$, we conclude that the problem is infeasible. 🚫 - Iterate until ${\color{green}x}$ becomes feasible, i.e. ${\color{purple}\Phi}_{\color{coral}\gamma}({\color{green}x}) \leq 0$. ✅ --- ### E.g. Linear-Fractional Cost ➗ - Problem Formulation: $$\begin{array}{ll} \text{min} & (e^\mathsf{T} {\color{green}x} + f) / (g^\mathsf{T} {\color{green}x} + h) \\ \text{s. t.} & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ - The problem can be recast as: $$\begin{array}{ll} \text{min} & {\color{coral}\gamma} \\ \text{s. t.} & (e^\mathsf{T} {\color{green}x} + f) - {\color{coral}\gamma}(g^\mathsf{T} {\color{green}x} + h) \leq 0 \\ & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ --- ### Convex Optimization insights (III) - Consider a convex feasibility problem: $$\begin{array}{ll} \text{find} & {\color{green}x} \\ \text{s. t.} & (e - {\color{coral}\gamma}\cdot g)^\mathsf{T} {\color{green}x} + (f - {\color{coral}\gamma}\cdot h) \leq 0, \\ & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ - If feasible, we conclude that ${\color{coral}\gamma} \ge p^*$; ✅ - If infeasible, ${\color{coral}\gamma} < p^*$. ❌ - Binary search on ${\color{coral}\gamma}$ can be used for obtaining $p^*$. 🔍 --- ### Network Flow insights (VII) 🌐 - Choose $\triangle {\color{green}x}$ to be a negative cycle of $G_x$ - with cost $(e - {\color{coral}\gamma}\cdot g)$, i.e. $(e - {\color{coral}\gamma}\cdot g)^\mathsf{T}\triangle {\color{green}x} < 0$ 🔄 - If no negative cycle is found, and $(e - {\color{coral}\gamma}\cdot g)^\mathsf{T} {\color{green}x_0} + (f - {\color{coral}\gamma}\cdot h) > 0$, we conclude that the problem is infeasible. 🚫 - Iterate until $(e - {\color{coral}\gamma}\cdot g)^\mathsf{T} {\color{green}x_0} + (f - {\color{coral}\gamma}\cdot h) \leq 0$. ✅ --- ### E.g. Statistical Optimization - Consider the quasi-convex problem: $$\begin{array}{ll} \text{min} & {\color{purple}\Pr}(\mathbf{\color{blue}d}^\mathsf{T} {\color{green}x} > \alpha) \\ \text{s. t.} & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ - $\mathbf{\color{blue}d}$ is random vector with mean $d$ and covariance $\Sigma$. 🎲 - Hence, $\mathbf{\color{blue}d}^\mathsf{T} {\color{green}x}$ is a random variable with mean ${\color{blue}d}^\mathsf{T} {\color{green}x}$ and variance ${\color{green}x}^\mathsf{T} \Sigma {\color{green}x}$. --- ### Statistical Optimization 📈 - The problem can be recast as: $$\begin{array}{ll} \text{min} & {\color{coral}\gamma} \\ \text{s. t.} & {\color{purple}\Pr}(\mathbf{\color{blue}d}^\mathsf{T} {\color{green}x} > \alpha) \leq {\color{coral}\gamma} \\ & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array}$$ 👉 Note: $$\begin{array}{lll} & & {\color{purple}\Pr}(\mathbf{\color{blue}d}^\mathsf{T} {\color{green}x} > \alpha) \leq {\color{coral}\gamma} \\ & \Rightarrow & {\color{blue}d}^\mathsf{T} {\color{green}x} + {\color{purple}F^{-1} }(1-{\color{coral}\gamma}) \| \Sigma^{1/2} {\color{green}x} \|_2 \leq \alpha \end{array}$$ (convex quadratic constraint w.r.t ${\color{green}x}$) - Recall that the gradient of ${\color{blue}d}^\mathsf{T} {\color{green}x} + {\color{purple}F^{-1} }(1-{\color{coral}\gamma}) \| \Sigma^{1/2} {\color{green}x} \|_2$ is: $${\color{blue}d} + {\color{purple}F^{-1} }(1-{\color{coral}\gamma}) (\| \Sigma^{1/2} {\color{green}x} \|_2)^{-1} \Sigma {\color{green}x}$$. --- ### Problem with additional Constraints 🚧 - Problem Formulation: $$\begin{array}{ll} \text{min} & {\color{purple}f}({\color{green}x}) \\ \text{s. t.} & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \\ & \color{red}{s^\mathsf{T} x \leq \gamma} \end{array}$$ --- ### E.g. Yield-driven Delay Padding ⏳🎯 - Consider the following problem: $$\begin{array}{ll} \text{maximize} & \gamma\,\beta - {\color{green}c}^\mathsf{T} {\color{blue}p}, \\ \text{subject to} & \beta \leq {\color{purple}\Pr}({\color{blue}y}_{ij} \leq \mathbf{\color{blue}d}_{ij} + {\color{blue}p}_{ij}), \\ & A {\color{firebrick}u} = {\color{blue}y}, \; {\color{blue}p} \geq 0 \end{array}$$ - ${\color{blue}p}$: delay padding ⏳ - $\gamma$: weight ⚖️ - $\mathbf{\color{blue}d}_{ij}$: Gaussian random variable, with - mean ${\color{blue}d}_{ij}$, and - variance $s_{ij}$. --- ### E.g. Yield-driven Delay Padding (II) ⏳🎯 .pull-left[ - The problem is equivalent to: $$\begin{array}{ll} \text{max} & {\color{red}\gamma\,\beta} - {\color{green}c}^\mathsf{T} {\color{blue}p}, \\ \text{s.t.} & {\color{blue}y} \leq {\color{blue}d} {\color{red}- \beta s} + {\color{blue}p}, \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, {\color{blue}p} \geq 0 \end{array}$$ ] .pull-right[ - or its dual: $$\begin{array}{ll} \text{min} & {\color{blue}d}^\mathsf{T} {\color{green}x} \\ \text{s.t.} & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \\ & {\color{red}s^\mathsf{T} x \leq \gamma} \end{array}$$ ] --- ### Recall ... 🔄 - Yield drive CSS: $$\begin{array}{ll} \text{max} & \beta, \\ \text{s.t.} & {\color{blue}y} \leq {\color{blue}d} - \beta s, \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, \end{array}$$ - Delay padding $$\begin{array}{ll} \text{max} & -{\color{green}c}^\mathsf{T} {\color{blue}p}, \\ \text{s.t.} & {\color{blue}y} \leq {\color{blue}d} + {\color{blue}p}, \\ & {\color{green}A} {\color{firebrick}u} = {\color{blue}y}, \; {\color{blue}p} \geq 0 \end{array}$$ --- ### Considering Barrier Method 🚧 - Approximation via logarithmic barrier: $$ \begin{array}{ll} \text{min} & {\color{purple}f}({\color{green}x}) + (1/t) {\color{purple}\phi}({\color{green}x})\\ \text{s. t.} & 0 \leq {\color{green}x} \leq {\color{green}c}, \\ & {\color{blue}A^\mathsf{T} } {\color{green}x} = {\color{firebrick}b}, \; {\color{firebrick}b}({\color{salmon}V})=0 \end{array} $$ - where ${\color{purple}\phi}({\color{green}x}) = -\log (\gamma - s^\mathsf{T} {\color{green}x})$ - Approximation improves as $t \rightarrow \infty$ - Here, $\nabla {\color{purple}\phi}({\color{green}x}) = s / (\gamma - s^\mathsf{T} {\color{green}x})$ ➗ --- ### Barrier Method ⚙️ - **Input**: a feasible $x$, $t := t^{(0)}$, $\mu > 1$, tolerance $\varepsilon > 0$ 🏁 - **Output**: $x^*$ 🎯 - **repeat** 1. Centering step. Compute $x^*(t)$ by minimizing $t\,{\color{purple}f} + {\color{purple}\phi}$ ⚖️ 2. Update $x := x^*(t)$. 🔄 3. Increase $t$. $t := \mu t$ 📈 - **until** $1/t < \varepsilon$. 🛑 👉 Note: Centering is usually done by Newton's method in general. 🧮 --- ### Network Flow insights (VIII) 🌐 In the centering step, instead of using the Newton descent direction, we can replace it with a negative cycle on the residual graph. 🔄 --- ### 🌐 Convex Optimization meets Network Flow .mermaid[ <pre> graph LR A(Network Flow Problem) --> B(Convex Formulation) B --> C(Solve) C --> D(Optimal Flow) 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 </pre> ] --- ### Conclusion: A Synergistic Future 🔄✨ The intersection of convex optimization and network flow theory provides a powerful framework for tackling a wide range of optimization problems that exhibit both network structure and convex (or quasi-convex) characteristics. By leveraging the efficient algorithms and structural insights from network flow theory, combined with the generality and robustness of convex optimization techniques, we can address problems that would be intractable using either approach alone. 💪 --- class: nord-dark, middle, center ## Q&A 🎤 =====