Convex Optimization in Workforce Planning

Convex optimization deals with minimizing a convex function over a convex set — a problem class where every local minimum is guaranteed to be the global minimum. This guarantee is absent in general optimization and is the reason convex problems are considered "tractable" while non-convex problems are "hard." Many core WFM problems — quadratic staffing cost minimization, portfolio-style skill-mix optimization, continuous relaxations of scheduling IPs — are convex or can be made convex through careful reformulation.

Understanding convexity is not merely academic. It determines whether your optimizer's answer is the answer or merely an answer — and whether the solution landscape contains traps that heuristics might fall into.

Overview

Convex vs non-convex optimization landscapes

A function $f:{\mathbb{ℝ}}^n\to \mathbb{ℝ}$ is convex if for all $x,y$ and $\lambda \in [0,1]$:

$f(\lambda x+(1-\lambda )y)\le \lambda f(x)+(1-\lambda )f(y)$

Geometrically: the function lies on or below the chord between any two points. A set $C$ is convex if the line segment between any two points in $C$ lies entirely within $C$.

When both the objective function and the feasible region are convex, any algorithm that finds a local minimum has found the global minimum. Gradient descent converges. Interior point methods converge. There are no false summits.

The practical implication for WFM: if you can formulate your problem as a convex optimization, you can solve it to certified global optimality in polynomial time. If your problem is non-convex, you need heuristics, multiple restarts, or convex relaxations — and you must accept that the solution may not be globally optimal.

Mathematical Foundation

Convex Functions in WFM

Quadratic cost functions are the most common convex functions in WFM. The cost of deviation from the staffing target is naturally modeled as:

$C(x)=\alpha (x-d{)}^2$

where $x$ is staff count and $d$ is demand. This function is strictly convex: understaffing by 3 agents costs more than three times understaffing by 1 agent. Overstaffing follows the same pattern. The quadratic penalty captures the non-linear pain of large deviations.

Asymmetric quadratic costs reflect that understaffing is typically worse than overstaffing:

$C(x)=\{\begin{array}{ll}{\alpha }_u(d-x{)}^2& \text{if }x<d\\ {\alpha }_o(x-d{)}^2& \text{if }x\ge d\end{array}$

with ${\alpha }_u>{\alpha }_o$. This piecewise quadratic is convex (both pieces are convex and they meet at $x=d$ with ${\alpha }_u>{\alpha }_o$ ensuring the left piece is steeper).

Log-barrier penalties model soft capacity constraints:

$C(x)=-\mu \ln (K-x)$

where $K$ is maximum capacity. As $x\to K$, the cost goes to infinity — a smooth approximation of a hard constraint. This is the basis of interior point methods.

Quadratic Programming

A quadratic program (QP) minimizes a quadratic objective subject to linear constraints:

$\min \frac{1}{2}{\mathbf{𝐱}}^{T}Q\mathbf{𝐱}+{\mathbf{𝐜}}^T\mathbf{𝐱}\text{subject to}A\mathbf{𝐱}\le \mathbf{𝐛},\mathbf{𝐱}\ge 0$

If $Q$ is positive semidefinite ($Q⪰0$), the problem is convex and solvable in polynomial time. The KKT (Karush-Kuhn-Tucker) conditions are both necessary and sufficient:

$Q{\mathbf{𝐱}}^{*}+\mathbf{𝐜}-A^T{\mathit{\lambda }}^{*}=0$

${\lambda }_i^{*}(A_i{\mathbf{𝐱}}^{*}-b_i)=0\mathrm{\forall }i$

${\mathit{\lambda }}^{*}\ge 0$

WFM application: minimize total quadratic staffing cost across intervals subject to service-level constraints. The quadratic penalty naturally discourages solutions that overstaff some intervals while understaff others, producing smoother coverage profiles than LP (which is indifferent to the distribution of slack).

Convex Relaxations

Many WFM problems are naturally integer programs (you cannot hire 3.7 agents). Integer programming is NP-hard. Convex relaxation replaces integrality constraints with continuous bounds:

$x_i\in \{0,1,2,\dots \}\to x_i\ge 0,x_i\in \mathbb{ℝ}$

The resulting LP or QP relaxation provides:

• A lower bound on the optimal integer solution (for minimization)
• A fractional solution that can be rounded to produce a feasible integer solution
• The integrality gap — the ratio between the relaxed and integer optima — measures how much is lost by relaxing

For WFM scheduling problems, the integrality gap is typically small (1-3%) because staffing quantities are large enough that fractional solutions round without significant loss.

Semidefinite relaxation (SDP): For harder problems (e.g., multi-skill assignment with quadratic interaction terms), SDP relaxations provide tighter bounds than LP relaxations by optimizing over the cone of positive semidefinite matrices.

Gradient Descent

For unconstrained convex minimization, gradient descent updates:

${\mathbf{𝐱}}_{k+1}={\mathbf{𝐱}}_k-{\eta }_k\mathrm{\nabla }f({\mathbf{𝐱}}_k)$

Convergence rate for a convex function with L-Lipschitz gradient:

$f({\mathbf{𝐱}}_k)-f({\mathbf{𝐱}}^{*})\le \frac{L\Vert {\mathbf{𝐱}}_0-{\mathbf{𝐱}}^{*}{\Vert }^2}{2k}$

This is $O(1/k)$ — slow but guaranteed. For strongly convex functions (minimum curvature bounded below), the rate improves to linear convergence: $O({\rho }^k)$ for some $\rho <1$.

Variants relevant to large-scale WFM:

• Stochastic gradient descent (SGD): Uses a random subset of constraints per iteration — essential when the problem has millions of interval-skill combinations
• Proximal gradient methods: Handle non-smooth regularizers (e.g., L1 penalty for sparse shift selection)
• ADMM (Alternating Direction Method of Multipliers): Decomposes large problems into smaller subproblems solved in parallel — natural for multi-site WFM

WFM Applications

Quadratic Staffing Optimization

Objective: Minimize total cost across T intervals:

$\underset{\mathbf{𝐱}}{\min }\sum _{t=1}^T[{\alpha }_u\max (0,d_t-x_t{)}^2+{\alpha }_o\max (0,x_t-d_t{)}^2]$

subject to shift structure constraints (each agent works a contiguous set of intervals), labor rules, and budget limits.

This is a convex QP. The asymmetric quadratic penalty ensures the optimizer balances understaffing pain (high ${\alpha }_u$) against overstaffing cost (lower ${\alpha }_o$), producing solutions that slightly overstaff peak intervals rather than understaff them.

Skill-Mix Portfolio Optimization

Analogous to Markowitz portfolio theory: each skill group has an expected "return" (coverage capability) and "variance" (demand volatility). Cross-trained agents provide diversification (they can cover multiple skill groups, reducing total variance).

The quadratic formulation:

$\underset{\mathbf{𝐰}}{\min }{\mathbf{𝐰}}^T\mathrm{\Sigma }\mathbf{𝐰}\text{subject to}{\mathit{\mu }}^T\mathbf{𝐰}\ge R_{\min },{\mathbf{𝟏}}^T\mathbf{𝐰}=N$

where $\mathbf{𝐰}$ is the allocation across skill groups, $\mathrm{\Sigma }$ is the demand covariance matrix, and $R_{\min }$ is the minimum coverage requirement. This is a standard QP — globally solvable.

When WFM Problems Are Not Convex

Non-convexity arises in:

• Integer constraints: Shift counts must be whole numbers
• Multi-pool interactions: Agent A being available in pool 1 changes the optimal assignment in pool 2 — the interaction creates non-convex coupling
• Erlang-based service level: The Erlang C function is non-convex in staffing count — service level is not a concave function of agents
• Combinatorial shift design: Choosing which shift templates to offer from a large candidate set is a combinatorial (non-convex) problem

Strategies for non-convex WFM problems:

• Solve the convex relaxation for a lower bound and warm-start heuristics
• Decompose into convex subproblems (e.g., Benders decomposition)
• Use metaheuristics (simulated annealing, genetic algorithms) with the convex relaxation solution as the starting point

Worked Example

Problem: Allocate 200 agents across 4 skill groups to minimize total coverage variance, given:

Skill Group	Expected Demand	Demand Std Dev	Min Allocation
Billing	80	12	60
Technical	60	15	45
Sales	35	8	25
General	25	5	20

Demand correlation matrix:

	Billing	Technical	Sales	General
Billing	1.00	0.30	0.15	0.40
Technical	0.30	1.00	0.10	0.35
Sales	0.15	0.10	1.00	0.20
General	0.40	0.35	0.20	1.00

Formulation: Minimize ${\mathbf{𝐰}}^T\mathrm{\Sigma }\mathbf{𝐰}$ subject to $\sum w_i=200$, $w_i\ge w_i^{\min }$, and $w_i\le 100$.

Covariance matrix:

$\mathrm{\Sigma }=\left(\begin{array}{cccc}144& 54& 14.4& 24\\ 54& 225& 12& 26.25\\ 14.4& 12& 64& 8\\ 24& 26.25& 8& 25\end{array}\right)$

Solution (via QP solver): ${\mathbf{𝐰}}^{*}=(76,55,40,29)$

The optimizer allocates more than minimum to Sales and General (which have lower variance and lower correlation with other groups) and less than proportional demand to Billing and Technical (which are more volatile and more correlated). This mirrors portfolio diversification: overweight low-variance, low-correlation assets.

Total portfolio variance: 18,420 (optimized) vs. 21,800 (proportional allocation) — a 15.5% reduction in coverage risk for the same total headcount.

Maturity Model Position

• Level 2 (Developing): Linear cost models; LP-based scheduling with no recognition of convexity properties
• Level 3 (Advanced): Quadratic cost models for staffing; LP relaxation bounds used to evaluate integer solutions
• Level 4 (Leading): Formal convex optimization for continuous workforce allocation; portfolio-style skill-mix optimization; ADMM for multi-site decomposition
• Level 5 (Innovating): Convex relaxation hierarchies (LP → QP → SDP) for progressively tighter bounds; real-time convex optimization for intraday reallocation; non-convexity maps identifying where heuristics are necessary

See Also

• Linear Programming in WFM
• Integer Programming in WFM
• Multi-Objective Optimization in WFM
• Sensitivity Analysis and Duality in WFM
• Operations Research in Workforce Management

References

• Boyd, S. & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. (Available free: https://web.stanford.edu/~boyd/cvxbook/)
• Nesterov, Y. (2004). Introductory Lectures on Convex Optimization: A Basic Course. Springer.
• Ben-Tal, A. & Nemirovski, A. (2001). Lectures on Modern Convex Optimization. SIAM.
• Nocedal, J. & Wright, S.J. (2006). Numerical Optimization. 2nd ed. Springer.
• Markowitz, H. (1952). "Portfolio Selection." The Journal of Finance, 7(1), 77-91.