🔢 mathematics

Hidden Convexity in Multi-Retailer Cold-Chain Allocation: A Cholesky-Spectral Second-Order Cone Programming Approach

This paper introduces the HSDI algorithm, which leverages a Cholesky-spectral transform to exploit hidden convexity in multi-retailer cold-chain allocation games, thereby converting a generally NP-hard generalized Nash equilibrium problem into a tractable second-order cone program with certified global convergence and superior computational efficiency.

Original authors: Thinh Nguyen Hoang Pham, Boris Mordukhovich, Son Hoang Truong, Ngoc Anh Tran, Quyen Phuong Le

Published 2026-10-28✓ Author reviewed ⓘ

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Thinh Nguyen Hoang Pham, Boris Mordukhovich, Son Hoang Truong, Ngoc Anh Tran, Quyen Phuong Le

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a network of refrigerated trucks and warehouses moving milk from farms to store shelves. This cold chain is the lifeblood of the dairy industry, but it is fragile. If a truck breaks down or a warehouse door is left open, the temperature rises, and the milk spoils. The speed of this spoilage is not random; it follows a strict physical law where even a tiny rise in heat can drastically accelerate the decay of the product. For the retailers who sell this milk, the challenge is to decide how much of each type of product to send through this network. They must balance the cost of logistics against the risk of losing their inventory to heat. If they send too much of a heat-sensitive product during a risky time, they lose money. If they send too little, they miss sales. The goal is to find the perfect mix that minimizes waste while keeping costs low, a task that becomes incredibly difficult when multiple retailers are competing for the same limited cooling capacity.

This is the problem a team of researchers set out to solve. They looked at the complex mathematics behind these decisions, which usually involve a tangled web of non-linear equations that are notoriously hard to solve. In the world of optimization, these equations are often described as "non-convex," meaning they have many local dips and peaks, making it easy for a computer to get stuck in a bad solution and miss the best one. The researchers focused on a specific type of efficiency score used by businesses, which compares the risk of spoilage to the cost of moving the goods. Because this score is a ratio of two complex formulas, it creates a mathematical puzzle that is generally considered impossible to solve perfectly in a reasonable amount of time for large networks.

However, the researchers discovered a hidden simplicity within this complexity. They realized that the way heat affects different types of milk products follows a specific pattern. While every product has its own unique sensitivity to heat, they all react to the same underlying temperature shock in the supply chain. This shared reaction creates a mathematical structure that looks like a single dominant factor plus some small, individual variations. By exploiting this structure, the team developed a new method that transforms the impossible puzzle into a solvable one. They used a combination of two standard mathematical techniques to straighten out the tangled equations, effectively turning the difficult problem into a form that computers can solve quickly and with a guarantee of finding the absolute best answer.

The team tested their method, which they named HSDI, against the best existing tools used by engineers and data scientists. They ran simulations using real-world data from dairy markets in both Vietnam and the United States. In these tests, the new method consistently found the same best solution as the older, more time-consuming tools, but it did so without needing to guess and check multiple times. While the older tools often had to restart their calculations dozens of times to avoid getting stuck, the new method worked in a single, smooth pass. In the specific cases where the mathematical conditions were perfect, the method was proven to find the global optimum, the single best possible allocation of products. Even when the conditions were not perfect, the method provided a clear, calculated limit on how far off the solution might be, ensuring that the result was always trustworthy.

Beyond just finding the best mix of products, the method also produced a valuable number that acts as a "shadow price" for the entire system. This number tells retailers and policymakers exactly how much extra value they would gain by adding one more unit of cooling capacity to their network. The researchers found that this value is much higher in emerging markets like Vietnam compared to developed ones like the United States. This suggests that investing in better refrigeration infrastructure in these developing regions would yield a much higher return, as the current lack of capacity is causing significant losses. The method also proved to be stable; small changes in the data, such as a slight shift in the estimated temperature fluctuations, did not cause the recommended plan to swing wildly. Instead, the solution adjusted smoothly, giving decision-makers confidence that their plans would hold up in the real world.

The significance of this work lies in its ability to turn a theoretical mathematical insight into a practical tool for the food industry. By recognizing that the physics of spoilage creates a hidden order in the data, the researchers were able to bypass the usual computational roadblocks. They showed that what looks like a chaotic, unsolvable problem is actually structured in a way that allows for a precise, efficient solution. This means that retailers can now make better, faster decisions about how to move their products, potentially saving millions of dollars in wasted food and ensuring that more milk reaches consumers fresh. The approach also offers a clear, data-driven way to prioritize where to build new cold storage facilities, guiding investment to where it is needed most. In a world where food security and supply chain efficiency are critical, this method provides a reliable compass for navigating the complex trade-offs between cost, risk, and the relentless physics of heat.

Technical Summary: Hidden Convexity in Multi-Retailer Cold-Chain Allocation

Problem Formulation
The paper addresses the allocation of dairy products across a shared refrigerated cold-chain network involving multiple retailers ( $n$ ). Each retailer must allocate products across heat-sensitivity subgroups ( $K$ ) and planning periods ( $T$ ) to maximize a quadratic-fractional efficiency metric. This metric, inspired by Data Envelopment Analysis (DEA), is defined as the ratio of spoilage risk (numerator) to logistics cost (denominator). The numerator incorporates physical spoilage kinetics via the Arrhenius law with a $Q_{10}$ coefficient, while the denominator accounts for storage and market-impact costs.

The individual optimization problem for each retailer is a non-convex fractional quadratically-constrained quadratic program (QCQP). When multiple retailers share a global risk-budget constraint (representing a common thermal shock or capacity limit), the system constitutes a Generalized Nash Equilibrium Problem (GNEP). The authors formulate the solution concept as a Variational Equilibrium (VE), which ensures a common Lagrange multiplier (shadow price) for the shared constraint, providing economic interpretability and computational tractability.

Methodology: Hidden Convexity and HSDI
The core methodological insight is the identification of "hidden convexity" arising from the physical structure of thermal risk. The Arrhenius spoilage law implies that the thermal-risk covariance matrix ( $\Sigma_i$ ) for any retailer follows a rank-one-plus-diagonal structure ( $\Sigma_i = b_i b_i^\top + D_i$ ), where the rank-one term captures the shared thermal shock and the diagonal term captures idiosyncratic risks.

To exploit this structure, the authors propose the Hidden SOCP Dinkelbach Iteration (HSDI) algorithm, which proceeds in two levels:

Simultaneous Diagonalization (Cholesky-Spectral Transform):
Unlike previous approaches that require the risk matrix ( $\Sigma_i$ ) and cost matrix ( $H_i$ ) to commute, the paper establishes a theorem for the simultaneous diagonalization of the pair $(\Sigma_i, H_i)$ without commutativity. By applying a Cholesky decomposition to $H_i$ followed by a spectral decomposition of the transformed $\Sigma_i$ , the authors construct a change of variables that transforms the non-convex fractional QCQP into a sequence of convex Second-Order Cone Programming (SOCP) problems.
Dinkelbach Iteration with SOCP Relaxation:
The fractional objective is handled via the Dinkelbach algorithm. At each iteration, the inner problem is solved as an SOCP.
- Exactness: If the eigenvalues of the transformed risk matrix satisfy a specific condition relative to the current efficiency estimate, the SOCP relaxation is exact, recovering the global optimum.
- Inexactness: If the condition is not met, the algorithm provides a closed-form suboptimality bound based on the magnitude of the violated eigenvalues.
Coupled Variational Equilibrium:
The individual solutions are coupled through the shared risk budget. The authors prove that the aggregate risk map is monotone, allowing the use of projected pseudo-gradient or bisection methods to find the equilibrium multiplier $\mu$ with linear convergence rates.

Key Contributions

Structural Theory: The paper proves a simultaneous diagonalization theorem for non-commuting pairs $(\Sigma_i, H_i)$ where $\Sigma_i$ has a rank-one-plus-diagonal structure. This removes the restrictive commutativity assumption found in prior literature (e.g., Akkaya and Pınar, 2025).
Exactness and Error Bounds: It provides an explicit, verifiable sufficient condition for the SOCP relaxation to be exact. When exactness fails, a closed-form suboptimality bound is derived.
Convergence Analysis: The paper establishes global convergence for the HSDI algorithm. The outer Dinkelbach loop converges Q-superlinearly when the relaxation is exact and at least R-linearly otherwise. The coupled VE iteration converges R-linearly under strong monotonicity. The overall complexity is polynomial, specifically $O(nd^{3.5} \log^3(1/\varepsilon))$ .
Stability: Using second-order variational analysis, the authors prove the Lipschitz stability of the primal-dual pair $(x^\star, \mu)$ , ensuring that the shadow price is a robust quantitative signal for decision-making.

Experimental Results
The model was calibrated on two distinct market regimes: Vietnam (emerging market with higher thermal noise) and the United States (developed market with lower thermal noise). Six numerical experiments were conducted:

Global Optimality: HSDI matched the best values found by multi-start non-linear solvers (SLSQP, trust-constr) within $5.5 \times 10^{-3}$ on all instances without random restarts, while providing a convergence certificate.
Spectral Structure: Empirical data confirmed the rank-one-plus-diagonal structure, with the top eigenvalue capturing over 99% of the spectrum.
Near-Optimality: The SOCP relaxation was exact (or near-optimal with gap $< 10^{-3}$ ) on 77% of the Vietnam grid and 42% of the US grid.
Scaling: The empirical scaling exponent for HSDI was $\hat{\gamma} \approx 0.93$ , significantly lower than the SLSQP exponent of $\hat{\gamma} \approx 1.30$ , suggesting HSDI will outperform non-linear solvers at larger scales.
Convergence Rates: Empirical convergence rates matched theoretical predictions: R-linear decay for the Dinkelbach loop (factor $\approx 0.4$ ) and the VE multiplier (factor $\approx 0.5$ ).
Stability: The shadow price $\mu$ was found to be Lipschitz-stable, with the emerging market (Vietnam) exhibiting a higher marginal value for cold-chain capacity than the US market.

Significance and Claims
The paper claims to provide a deterministic, convergence-certified tool for cold-chain allocation that avoids the pitfalls of non-convex local solvers. Its primary significance lies in transforming a generally NP-hard GNEP into a tractable polynomial-time problem by leveraging the specific algebraic structure imposed by physical spoilage laws.

The authors emphasize that the resulting shadow price $\mu$ serves as a reliable, Lipschitz-stable quantitative indicator for infrastructure investment. Unlike heuristic baselines, HSDI offers a guaranteed global optimum (under specific conditions) and a stable dual variable that policymakers can use to prioritize capacity expansion in markets where thermal constraints are binding. The work bridges physical principles (Arrhenius kinetics) with advanced optimization theory (variational analysis and conic programming) to solve a practical supply chain problem.

More like this