Network Utility Maximization with Nonconcave Utilities

12 concepts16 papers

For decades, the mathematical foundation of network resource allocation relied on a elegant simplification: the assumption of elastic traffic. In traditional Network Utility Maximization (NUM) frameworks, a user's satisfaction or "utility" $U(x)$ as a function of their allocated data rate $x$ is modeled as a strictly concave function (such as a logarithmic curve). Concavity represents the law of diminishing returns: every additional bit per second helps, but it helps a little less than the previous one.

This assumption makes network optimization highly tractable. Because the sum of concave functions is concave, a global network optimum is guaranteed to exist, and simple distributed algorithms—like standard dual decomposition, where routers adjust link prices based on congestion and users adjust rates based on price—smoothly converge to the global optimum.

However, modern networks are dominated by inelastic traffic: real-time video streaming, voice-over-IP, cloud computing, and interactive gaming. These applications do not experience smooth, diminishing returns. Instead, they exhibit threshold-based behaviors.

The Intuition of the S-Curve

Consider a high-definition video stream. If the network allocates $500\text{ Kbps}$ to a stream that requires a minimum of $2\text{ Mbps}$ to decode, the utility to the user is effectively zero; the video simply buffers or drops out. Once the allocation crosses the $2\text{ Mbps}$ threshold, utility jumps sharply. Past a certain point (say, $5\text{ Mbps}$), the human eye can no longer perceive quality improvements, and the utility flattens out.

This behavior is mathematically captured by a sigmoidal (S-curve) utility function, which is fundamentally nonconcave. It contains a convex region at low data rates (where marginal utility is increasing) and a concave region at high data rates.

Utility U(x)
  ^
  |          /----------------- (Diminishing returns)
  |         /
  |        /  <- Threshold
  |       /
  |_____/     (Unusable below threshold)
  +----------------------------> Data Rate x

When utility functions are nonconcave, the mathematical guarantees of classical network optimization collapse:

  1. Local Optima: The optimization landscape becomes riddled with local maxima. Standard gradient-descent or pricing mechanisms can easily get trapped in sub-optimal configurations.
  2. The Starvation Dilemma: As noted by Vo et al., traditional fair-sharing algorithms designed for concave utilities will attempt to distribute scarce bandwidth equally. In a network choked with inelastic traffic, this can result in every user receiving a sub-threshold allocation. Instead of maximizing welfare, fair-sharing renders the service unusable for everyone. Managing these networks requires mechanisms that can prioritize specific flows to ensure at least some users meet their operational thresholds.
  3. Economic Instability: In market-driven architectures like 5G network slicing, nonconcave utility functions make it mathematically difficult to guarantee a stable economic equilibrium or an optimal allocation of resources, as demonstrated by Tassiulas et al..

To make modern networks functional, researchers have had to reinvent NUM from the ground up, developing alternative optimization frameworks capable of navigating nonconcave landscapes.

Bypassing Nonconcavity: Global and Local Relaxations

How do you optimize a network when the objective function violates the basic rules of convex optimization? Researchers have developed two primary strategies: finding the true global optimum via convex relaxations, or finding high-quality local optima via sequential approximations.

Global Optimization via Sum-of-Squares (SOS)

To find the absolute best resource allocation without getting trapped in local optima, Fazel et al. introduced a centralized framework utilizing the Sum-of-Squares (SOS) method.

The core idea behind SOS is to transform a non-convex polynomial optimization problem into a sequence of convex semidefinite programs (SDPs). Instead of searching for the optimal rates directly in a nonconcave landscape, the problem is reframed as finding a certificate (a polynomial that is a sum of squares) that proves an upper bound on the utility. Remarkably, the authors demonstrated that minimal-order relaxations frequently find the exact global optimum, bypassing the typical NP-hard complexity of non-convex optimization.

Local Optimization via Sequential Convex Programming (SCP)

While global methods are powerful, they can be computationally heavy for real-time, distributed network control. As an alternative, Sehati et al. proposed a distributed rate-allocation algorithm for streaming traffic using Sequential Convex Programming (SCP).

Instead of tackling the nonconcave S-curve all at once, SCP linearizes or convexifies the nonconcave utility functions around a current operating point. The network then solves a localized, valid convex optimization problem, updates the rates, and repeats the process. This transforms a mathematically "hard" non-convex problem into a series of easily solvable convex ones that rapidly converge to a locally optimal solution. Similarly, Brehmer et al. exploited the monotonic nature of data rates in multi-antenna (MIMO) broadcast channels to design fast local gradient methods that treat the capacity boundary as a smooth manifold.

Rethinking Network Architecture and Control

Moving beyond the math of a single link, nonconcave utilities force a complete rethinking of distributed network protocols, scheduling, and economics.

Alternative Distributed Decompositions

In standard network engineering, dual decomposition acts as a decentralized "congestion pricing" mechanism. However, when utilities are nonconcave, a massive "duality gap" emerges—meaning the price-based feedback loop may never converge to a stable or optimal state.

To solve this, Palomar et al. introduced a systematic framework for alternative mathematical decompositions, including primal, multilevel, and indirect methods. By shifting from dual decomposition (which decomposes by prices) to primal decomposition (which decomposes by directly allocating quantities or capacities), engineers can design distributed algorithms that bypass the duality gap entirely, ensuring stable convergence even for inelastic traffic.

The Failure of Opportunistic Scheduling

In wireless networks, cellular base stations often use "opportunistic scheduling"—waiting to transmit data to a user until their moving device enters a crisp, high-signal area. Bonald demonstrated that while this opportunistic mechanism yields massive capacity gains for elastic file transfers, it completely breaks down for real-time, inelastic traffic. Because voice and video conferencing have strict latency constraints, they cannot defer data transmission until a user enters a high-signal area.

To bridge this gap, Hou proposed a framework that treats delivery ratios as tunable parameters within a decentralized bidding game, achieving global optimality without requiring prior information about underlying channel conditions. On a larger scale, Spang et al. designed a two-tiered overlay network architecture called MON. By pairing a global offline optimizer with a fast, distributed online transport protocol, MON explicitly balances the trade-offs between high-priority inelastic flows and best-effort elastic traffic during periods of heavy congestion.

Market and Pricing Distortions

The shift from concave to nonconcave utility also distorts network economics. Game-theoretic models of network pricing traditionally assume elastic user demand modeled via logarithmic utility functions.

When analyzing WiFi markets, Duan et al. showed that this assumption fails to capture the reality of video conferencing and streaming. By modeling users with sigmoid utility functions, the authors demonstrated why local WiFi providers are driven to prefer flat-rate pricing, while global aggregators must opt for usage-based models to avoid destructive competition.

Furthermore, Dube et al. proved that when networks exhibit inelastic demand and user impatience (reneging), advanced quality-of-service frameworks like Differentiated Services (DiffServ) do not necessarily improve social welfare under market competition compared to simpler, non-differentiated services.

Learning the Unknown

The ultimate frontier in nonconcave utility modeling is handling the unknown. Most classical frameworks assume that the network operator knows the exact mathematical formula of a user's utility function. In reality, a user's satisfaction with a cloud computing application or a high-fidelity video stream is highly subjective and hidden.

+----------------------------------------------------+
|               Bilevel Optimization                 |
|                                                    |
|  Upper Level: Learn Unknown Utility Functions      |
|               (Data-Driven Parameter Updates)      |
|                      |             ^               |
|                      v             |               |
|  Lower Level: Optimize Network Resource Allocation |
|               (Solve Nonconcave NUM Instance)      |
+----------------------------------------------------+

To address this, Ji et al. developed a distributed, data-driven bilevel optimization approach called DBiNUM. The algorithm operates in a two-level loop: the lower level runs a distributed resource allocation algorithm based on current estimates, while the upper level uses network performance data to learn and update the complex, nonconcave utility functions on the fly.

By moving away from rigid, mathematically convenient concavity assumptions, this body of research provides the tools necessary to optimize modern networks for the applications that actually define the modern internet experience.

Key Foundational Work

Network Utility Maximization With Nonconcave Utilities Using Sum-of-Squares Method (2005) — contributed 1 concept elements to this direction.
Alternative Distributed Algorithms for Network Utility Maximization: Framework and Applications (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_nonconcave_utility_modeling_69f012c3,
  title = {nonconcave utility modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/nonconcave-utility-modeling/rdr_69f012c3e4ed42b192356cbb91bdeca7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_nonconcave_utility_modeling_69f012c3_v1,
  title = {nonconcave utility modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/nonconcave-utility-modeling/rdr_69f012c3e4ed42b192356cbb91bdeca7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}

See something wrong? Report a mistake