betaFeedback

WorksMathematics

Sign Primal-Dual Gradient Dynamics for Supply-Demand Coordination under Binary Human Feedback

Abstract

This paper addresses supply-demand coordination, in which a supplier sets prices to balance the demands of multiple buyers against limited resources. Existing studies typically solve the supply-demand coordination problem with a distributed algorithm called primal-dual gradient dynamics (PDGD), assuming that each buyer discloses the value of its own utility or marginal utility function. In contrast, we assume that each buyer discloses only binary information, namely whether it wants more or less of the current amount, and propose Sign PDGD. Sign PDGD is a PDGD algorithm in which the buyers' update depends only on the sign information. We analyze the convergence of Sign PDGD by interpreting it as a sliding mode control (SMC). For a quadratic cost and linear constraints, we show that under a gain condition, the primal and dual variables converge to the optimal solution. Numerical simulations on a toy resource-sharing problem confirm the two-phase behavior of SMC and show that the primal and dual variables approach the optimal solution.

Introduction

Sharing limited resources such as networks, electricity, and water among multiple buyers has become an important societal problem. In such settings, price-based mechanisms that balance buyer-side demand with supply-side capacity have long been used. The mechanism is called supply-demand coordination [1][2].

Supply-demand coordination is typically modeled as a distributed gradient-based dynamics over the primal and dual variables of an optimization problem. This form arises naturally from the roles of the buyer side and the supply side. Each buyer adjusts its purchase to maximize its own utility, while the supplier sets prices to enforce the finite-resource constraint. Each side carries out its role independently, and as a result, the distributed gradient-based dynamics emerge.

Such price-based, iterative coordination has been studied in various application domains. In power systems, distributed schemes are developed for voltage determination in electric power networks [3], for dynamic price adjustment that eliminates power imbalance [4], and for real-time pricing that maximizes the users’ utility through the interaction between users and the provider [5]. In water resource management, allocation that maximizes the users’ utility is presented [6]. For computing resources, price adjustment that maximizes the users’ utility has been formulated based on user-provider interaction and solved by the Alternating Direction Method of Multipliers (ADMM) [7].

The work [8] applies the market equilibrium theory for partitioning of computer resources. From a theoretical viewpoint, the works [2] and [9] interpret supply-demand coordination for network resources within the mathematical framework of primal and dual decomposition, and analyze the stability of the resulting primal-dual dynamics. Their studies share a common structure: a loop in which the buyer side and the supplier side repeatedly exchange amounts and prices to reach a coordinated allocation.

However, most of these approaches implicitly assume that each buyer can quantitatively evaluate their own marginal utility or utility at any given resource amount. In other words, the quantity demanded is treated as a primal variable that the buyer adjusts continuously along the gradient of its utility. If the buyers are actual humans, this assumption is challenging to justify: a human buyer cannot know their own utility function precisely, nor can they express the magnitude of their marginal utility or change their demand smoothly and faithfully according to it. What a human buyer can realistically provide is much coarser information, such as whether they want to increase or decrease their current resource amount.

In this paper, we introduce a more realistic human buyer model that provides only coarse information. Figure 1 illustrates the supply-demand coordination considered in this paper. During the coordination process, the resource allocation amount is adjusted according to the buyers’ preferences, while the prices are adjusted by the supplier to satisfy resource constraints. The amount and the price are then updated repeatedly. The distinctive point in this paper is that the buyer’s means of expressing their intentions is narrow: at any given moment, a buyer is allowed to provide binary information, that is, whether they want “more” of the current amount or “less” of it. This motivates us to formulate a mathematical model in which information from the human buyer is available only as a sign signal.

Figure 1. The concept of the supply-demand coordination with human buyer feedback

We propose sign primal-dual gradient dynamics (Sign PDGD), a PDGD in which the primal variable increases or decreases at a constant rate. We also analyze the convergence of Sign PDGD. The key point of the analysis is that we incorporate the concept of sliding mode control (SMC): we divide the behavior of Sign PDGD into a reaching phase, in which the state reaches a certain manifold, and a sliding phase, in which the state moves along the manifold toward the optimum. We show that Sign PDGD converges to the optimum under a gain condition on the primal value update. Finally, we address a toy model of a supply-demand coordination problem as a numerical example and apply Sign PDGD.

Regarding the theoretical analysis, the convergence properties of general PDGD have been studied in several works [10][11][12][13][14]. However, to our knowledge, no existing work discusses the behavior and convergence of PDGD in which some of the variables evolve along a sign gradient, as in our Sign PDGD. The analysis in this paper fills this gap.

Sign PDGD

In this section, we formulate the supply-demand coordination problem and its corresponding primal-dual gradient dynamics (PDGD). Then, we modify the buyer’s model to reflect coarse human feedback, yielding our proposed dynamics, Sign PDGD.

Problem Setting

A general supply-demand coordination problem is formulated as follows:

{min⁡xf(x),s.t.g(x)=0,c(x)≤0,(1)\begin{cases} \min\limits_{x} \quad f(x),\\ \text{s.t.}\quad g(x)=0,\\ c(x)\le0, \tag*{(1)} \end{cases}

where x∈RNx \in\mathbb{R}^{N} denote the amounts purchased by the buyers, and f:RN→Rf:\mathbb{R}^{N}\to\mathbb{R} is a cost function representing the buyers’ dissatisfaction, i.e., the negative of the buyers’ utility. The smaller the value of ff, the greater the satisfaction. g:RN→RMg:\mathbb{R}^{N}\to\mathbb{R}^{M} and c:RN→RLc:\mathbb{R}^{N}\to\mathbb{R}^{L} are the supplier-side equality and inequality constraints, respectively. When there are multiple buyers, ff is separable across the buyers. Notably, −∇f(x)-\nabla f(x) is the buyers’ marginal utility: the rate at which satisfaction increases when a buyer acquires more of the resources. An example of gg is a constraint that requires the sum of the component ratios in the resource blending problem to equal 1. An example of cc is a constraint that the total resource demand does not exceed the available supply.

Remark 1: Problem (1) represents a setting in which several suppliers provide several types of resources, and these resources are divided among several buyers. For example, xx can be arranged as x=(x11,…,xLI)Tx=(x_{11},\ldots,x_{LI})^{\mathsf{T}}, where xlix_{li} is the amount of resource ll purchased by buyer ii. The constraints can be imposed per supplier or per resource type, depending on the situation.

We let the Lagrangian of (1) be

L(x,λ,μ)=f(x)+λTg(x)+μTc(x).(2)L(x,\lambda,\mu)=f(x)+\lambda^{\mathsf{T}}g(x)+\mu^{\mathsf{T}}c(x). \tag*{(2)}

where λ∈RM\lambda\in\mathbb{R}^{M} and μ∈RL\mu\in\mathbb{R}^{L} are the Lagrange multipliers of (1b) and (1c), respectively. In the general supply-demand coordination problem, the dual variables play the role of prices that the supplier updates [2][5][7].

Conventional PDGD

The roles of the buyer and the supplier in supply-demand coordination are often expressed as a distributed process in the form of PDGD [2][9][15]. In PDGD, the buyer and supplier roles are clearly divided. The buyer updates the primal variable xx to maximize their own benefit, and the supplier updates the dual variables (λ,μ)(\lambda,\mu) to satisfy the constraints.

The conventional continuous-time PDGD for (1) is given as follows:

x˙=−ηx∇xL(x,λ,μ),λ˙=∇λL(x,λ,μ)=g(x),μ˙=[∇μL(x,λ,μ)]μ+=[c(x)]μ+,(3)\begin{aligned} \dot{x}&=-\eta_x\nabla_xL(x,\lambda,\mu),\\ \dot{\lambda}&=\nabla_{\lambda}L(x,\lambda,\mu)=g(x),\\ \dot{\mu}&=[\nabla_{\mu}L(x,\lambda,\mu)]^{+}_{\mu}=[c(x)]^{+}_{\mu}, \tag*{(3)} \end{aligned}

where ηx\eta_x is a positive constant representing a gain of the xx update, and [⋅]μ+[\cdot]^{+}_{\mu} is the projection that keeps μ\mu nonnegative: for each element jj,

([c]μ+)j={cj,μj>0 or cj>0,0,else(4)\left([c]^{+}_{\mu}\right)_j= \begin{cases} c_j,&\mu_j>0\text{ or }c_j>0,\\ 0,&\text{else} \end{cases} \tag*{(4)}

Remark 2: To clarify the meaning of the dynamics (3), consider linear constraints g(x)=Ax+bg(x)=Ax+b and c(x)=Cx+dc(x)=Cx+d. Then, (3a) is reduced to

∇xL=∇f(x)+ATλ+CTμ.(5)\nabla_xL=\nabla f(x)+A^{\mathsf{T}}\lambda+C^{\mathsf{T}}\mu. \tag*{(5)}

where (−∇f(x))(-\nabla f(x)) is the marginal utility and ATλ+CTμA^{\mathsf{T}}\lambda+C^{\mathsf{T}}\mu is the marginal payment determined by the current prices. In this sense, (3a) represents that each buyer increases the acquired amount when the marginal utility exceeds the price, and decreases it otherwise. (3b) and (3c) imply that the supplier raises the price of a constraint when it is violated, and lowers it otherwise.

A fundamental assumption underlying coordination via conventional PDGD (3) is that buyers have access to their own utility or marginal utility value. Although this assumption is reasonable when buyers are automated agents, it becomes impractical when buyers are human decision makers. This motivates us to remodel the buyers’ dynamics in the next subsection.

Sign PDGD: Human Buyers with Coarse Feedback

We aim to update the dynamics of the primal variable xx in the PDGD (3). We assume that at the current prices, a human buyer only expresses whether he/she wants more or less of the resource. That means that a buyer reports only the sign of ∇xL\nabla_x L. The update logic of the primal variable (3a) is replaced by x˙=−ηxsgn⁡(∇xL(x,λ,μ))\dot{x}=-\eta_x\operatorname{sgn}(\nabla_xL(x,\lambda,\mu)), where sgn⁡\operatorname{sgn} is an element-wise sign function. Note that the update logic of the dual variables, (3b) and (3c), are unchanged.

The updated dynamics, called Sign PDGD, are described as

x˙=−ηxsgn⁡(∇xL(x,λ,μ)),λ˙=∇λL(x,λ,μ)=g(x),μ˙=[∇μL(x,λ,μ)]μ+=[c(x)]μ+.(6)\begin{aligned} \dot{x} &= -\eta_x\operatorname{sgn}(\nabla_xL(x,\lambda,\mu)),\\ \dot{\lambda} &= \nabla_{\lambda}L(x,\lambda,\mu)=g(x),\\ \dot{\mu} &= [\nabla_{\mu}L(x,\lambda,\mu)]_{\mu}^{+}=[c(x)]_{\mu}^{+}. \tag*{(6)} \end{aligned}

Sign-based gradient methods have also been studied in machine learning. A representative example is Sign Gradient Descent, which updates each parameter using the sign of its gradient. This approach avoids the vanishing gradient problem in training machine learning models [16][17][18][19].

Theoretical Analysis

In this section, we address the convergence analysis of Sign PDGD (6). A key feature of Sign PDGD is that the sign function is expected to induce finite-time convergence to a certain manifold. To exploit this property, we interpret the dynamics as a stabilization problem based on sliding mode control (SMC), which is widely used for control applications, such as robotics [20][21][22], networks [23], and power plants [24]. Then, we divide the convergence analysis into two phases. In the reaching phase, the state approaches the manifold called the sliding surface, and in the sliding phase, the state remains on the sliding surface [25][26].

Setting and Notation

Consider that ff is a separable quadratic objective function and (c,g)(c,g) are linear constraints.

f(x)=12(x−xˉ)TF(x−xˉ),(7)f(x)=\frac{1}{2}(x-\bar{x})^{\mathsf{T}}F(x-\bar{x}), \tag*{(7)}
g(x)=Ax+b,c(x)=Cx+d,g(x)=Ax+b,\qquad c(x)=Cx+d,

where F=diag⁡(F1,…,FN)F=\operatorname{diag}(F_1,\ldots,F_N) with Fi>0F_i>0 for all i∈{1,2,…,N}i\in\{1,2,\ldots,N\}, xˉ∈RN\bar{x}\in\mathbb{R}^{N}, A∈RM×NA\in\mathbb{R}^{M\times N}, C∈RL×NC\in\mathbb{R}^{L\times N}, b∈RMb\in\mathbb{R}^{M}, and d∈RLd\in\mathbb{R}^{L}. Let Fmin⁡:=min⁡iFiF_{\min}:=\min_iF_i.

The Lagrange multipliers λ∈RM\lambda\in\mathbb{R}^{M} and μ∈RL\mu\in\mathbb{R}^{L} are collected into z:=(λ,μ)z:=(\lambda,\mu). We let

G:=[AT CT],H:=GTF−1G,h:=[(Axˉ+b)T (Cxˉ+d)T]T.(8)\begin{aligned} G&:=[A^{\mathsf{T}}\ C^{\mathsf{T}}],\\ H&:=G^{\mathsf{T}}F^{-1}G,\\ h&:=[(A\bar{x}+b)^{\mathsf{T}}\ (C\bar{x}+d)^{\mathsf{T}}]^{\mathsf{T}}. \tag*{(8)} \end{aligned}

Then,

∇xL=F(x−xˉ)+v,(9)\nabla_xL=F(x-\bar{x})+v, \tag*{(9)}
v:=Gz=ATλ+CTμ.(10)v:=Gz=A^{\mathsf{T}}\lambda+C^{\mathsf{T}}\mu. \tag*{(10)}

We assume that H≻0H\succ0 and that there is no duality gap, so that an optimal primal solution x∗x^{*} and the dual solution z∗=(λ∗,μ∗)z^{*}=(\lambda^{*},\mu^{*}) exist. From the stationarity condition of the Lagrangian with respect to xx, we have F(x∗−xˉ)+Gz∗=0F(x^{*}-\bar{x})+Gz^{*}=0.

Assumption 1 (Price Velocity Limiter): For all t≥0t\geq0 and for all ii,

sup⁡t≥0∣v˙i(t)∣<ηxFi.(11)\sup_{t\geq0}|\dot{v}_i(t)|<\eta_xF_i. \tag*{(11)}

Remark 3: Assumption 1 requires that the gain of the buyers’ sign-based feedback, denoted by ηx\eta_x, be fast enough to cancel the price drift. This is systematically achieved by applying a speed filter to (6b) and (6c).

We let the variable ss be defined as follows:

s:=∇xL=F(x−xˉ)+v.(12)s:=\nabla_xL=F(x-\bar{x})+v. \tag*{(12)}

Sign PDGD first moves from s≠0s\ne0 toward s=0s=0, and then switches to a motion within s=0s=0, whose details are discussed in the following subsections. These two motions can be regarded as the phases of SMC. In this sense, ss is a sliding variable, and the set s=0s=0 is the sliding surface.

Reaching Phase

In this subsection, we let t=t0R:=0t=t_0^{\mathrm{R}}:=0 be the initial time of the reaching phase, and also the initial time of the whole control time. Consider that s(0)≠0s(0)\ne0, implying that the state variables (x(0),μ(0),λ(0))(x(0),\mu(0),\lambda(0)) are not on the sliding surface yet. We also let s0:=s(0)s_0:=s(0).

Lemma 1 (Finite-Time Reaching): Under Assumption 1, the sliding variable sis_i reaches zero no later than

TiR:=∣s0,i∣ηxFi−sup⁡t≥0∣v˙i(t)∣.(13)T_i^{\mathrm{R}}:=\frac{|s_{0,i}|}{\eta_xF_i-\sup_{t\geq0}|\dot{v}_i(t)|}. \tag*{(13)}

and all components have reached zero by

TR:=max⁡iTiR.(14)T^{\mathrm{R}}:=\max_iT_i^{\mathrm{R}}. \tag*{(14)}

Proof: Since FF is diagonal, differentiating (12) gives

s˙i=Fix˙i+v˙i=−ηxFisgn⁡(si)+v˙i.(15)\dot{s}_i=F_i\dot{x}_i+\dot{v}_i=-\eta_xF_i\operatorname{sgn}(s_i)+\dot{v}_i. \tag*{(15)}

for each ii. While in the reaching phase, i.e., si≠0s_i\ne0,

ddt∣si∣=sgn⁡(si)s˙i=−ηxFi+sgn⁡(si)v˙i<0.(16)\frac{\mathrm{d}}{\mathrm{d}t}|s_i|=\operatorname{sgn}(s_i)\dot{s}_i=-\eta_xF_i+\operatorname{sgn}(s_i)\dot{v}_i<0. \tag*{(16)}

Hence ∣si∣|s_i| decreases while it is nonzero, which gives the finite reaching time (13). ■

Sliding Phase

In this subsection, we assume the reaching phase is complete for all components of ss, and we set t=t0St=t_0^{\mathrm{S}} as the initial time of the sliding phase. Then, s(t0S)=0s(t_0^{\mathrm{S}})=0 holds, implying (x(t0S),λ(t0S),μ(t0S))(x(t_0^{\mathrm{S}}),\lambda(t_0^{\mathrm{S}}),\mu(t_0^{\mathrm{S}})) are on the sliding surface.

The following lemma shows that the sliding phase sustains once it starts.

Lemma 2 (Sustaining the Sliding Phase): Under Assumption 1, if s(t1)=0s(t_1)=0 at a time t1≥0t_1\geq0, then s(t)=0s(t)=0 for all t≥t1t\geq t_1.

Proof: We examine whether ss in (12) remains at 0. For each ii, differentiating (12) and using FF diagonal gives

s˙i=Fix˙i+v˙i=−ηxFisgn⁡(si)+v˙i.(17)\dot{s}_i=F_i\dot{x}_i+\dot{v}_i=-\eta_xF_i\operatorname{sgn}(s_i)+\dot{v}_i. \tag*{(17)}

On the sliding surface, the right-hand side is discontinuous, so the solution is understood in the sense of Filippov [25]. Then, sgn⁡(si)\operatorname{sgn}(s_i) is replaced by a set-valued map taking values in [−1,+1][-1,+1] at si=0s_i=0. Hence, sis_i can stay at 0 if there exists a value σi∈[−1,+1]\sigma_i \in[-1,+1] such that

0=−ηxFiσi+v˙i.(18)0=-\eta_xF_i\sigma_i+\dot{v}_i. \tag*{(18)}

This equality holds if and only if

σi=v˙iηxFi.(19)\sigma_i=\frac{\dot{v}_i}{\eta_xF_i}. \tag*{(19)}

By Assumption 1, we have −1<σi<1-1<\sigma_i<1, so it is an admissible Filippov selection. Therefore, si(t)=0s_i(t)=0 is sustained for all t≥t1t\geq t_1, and since this holds for every ii, the lemma holds.

Now, we discuss the dynamics of the state (x,z)(x,z) in the sliding phase. By Lemma 2, s(t)=0s(t)=0 for all t≥t0st\geq t_0^s, and the primal variable xx follows the equivalent dynamics

x=xˉ−F−1v=xˉ−F−1Gz.(20)x=\bar{x}-F^{-1}v=\bar{x}-F^{-1}Gz. \tag*{(20)}

Substituting xx into the dual variable dynamics in (6) gives

λ˙=Ax+b=−AF−1v+Axˉ+b,(21)\dot{\lambda}=Ax+b=-AF^{-1}v+A\bar{x}+b, \tag*{(21)}
μ˙=[Cx+d]μ+=[−CF−1v+Cxˉ+d]μ+.(22)\dot{\mu}=[Cx+d]_{\mu}^{+}=[-CF^{-1}v+C\bar{x}+d]_{\mu}^{+}. \tag*{(22)}

Writing u(z):=−Hz+hu(z):=-Hz+h, we have

z˙=Proj⁡μ(u),(23)\dot{z}=\operatorname{Proj}_{\mu}(u), \tag*{(23)}

where Proj⁡μ(z)\operatorname{Proj}_{\mu}(z) is the projection function [⋅]μ+[\cdot]_{\mu}^{+} only applying the μ\mu-part of zz. Let I(t)I(t) denote the set of indices ii with z˙i=ui(z(t))\dot{z}_i=u_i(z(t)), meaning the projection Proj⁡μ\operatorname{Proj}_{\mu} is inactive. This set always contains the indices of λ\lambda. Let IC(t)I^C(t) be its complement, which consists of the indices of μ\mu where the projection is active.

The dual function of (1) is D(z)=−12zTHz+hTzD(z)=-\frac{1}{2}z^{\mathsf{T}}Hz+h^{\mathsf{T}}z, and uu can be written using the dual gradient, u=∇zDu=\nabla_zD. In this sense, the dynamics of zz in the sliding phase can be viewed as a dual ascent dynamics. The following lemma shows that zz with the dual ascent dynamics converges to the optimum.

Lemma 3 (Convergence of the Dual Variable): Under the dual dynamics (23), for any initial value z(t0s)=z0z(t_0^s)=z_0, the dual variable zz converges to the optimum z∗z^* as t→∞t\to\infty.

Proof. Let W(z):=12∥z−z∗∥22W(z):=\frac{1}{2}\lVert z-z^*\rVert_2^2. Along the dual dynamics (23), the function satisfies

W˙=(z−z∗)Tz˙\dot{W}=(z-z^*)^{\mathsf{T}}\dot{z}
=(z−z∗)Tu−∑i∈IC(zi−zi∗)ui=(z-z^*)^{\mathsf{T}}u-\sum_{i\in I^C}(z_i-z_i^*)u_i
=(z−z∗)Tu+∑i∈ICzi∗ui(24)=(z-z^*)^{\mathsf{T}}u+\sum_{i\in I^C}z_i^*u_i \tag*{(24)}

The second equality follows because zi=0z_i=0 for i∈ICi\in I^C. The last sum is nonpositive because zi∗≥0z_i^*\geq0 and ui≤0u_i\leq0 for i∈ICi\in I^C.

Let u=u(z)u=u(z) and u∗=u(z∗)u^*=u(z^*). Since u−u∗=−H(z−z∗)u-u^*=-H(z-z^*),

(z−z∗)Tu=−(z−z∗)TH(z−z∗)+(z−z∗)Tu∗.(25)(z-z^*)^{\mathsf{T}}u=-(z-z^*)^{\mathsf{T}}H(z-z^*)+(z-z^*)^{\mathsf{T}}u^*. \tag*{(25)}

Now, we divide (z−z∗)Tu∗(z-z^*)^{\mathsf{T}}u^* into the λ\lambda-part and the μ\mu-part elements, as follows:

(z−z∗)Tu∗=∑i∈(λ-part)(zi−zi∗)ui∗+∑i∈(μ-part)(zi−zi∗)ui∗.(26)(z-z^*)^{\mathsf{T}}u^* =\sum_{i\in(\lambda\text{-part})}(z_i-z_i^*)u_i^* +\sum_{i\in(\mu\text{-part})}(z_i-z_i^*)u_i^*. \tag*{(26)}

The KKT conditions for the dual maximization give ui∗=0u_i^*=0 for ii in the λ\lambda-part, and zi∗ui∗=0z_i^*u_i^*=0 for ii in the μ\mu-part. Therefore

(z−z∗)Tu∗=∑i∈(μ-part)ziui∗.(27)(z-z^*)^{\mathsf{T}}u^* =\sum_{i\in(\mu\text{-part})}z_i u_i^*. \tag*{(27)}

Since zi≥0z_i\geq0 and ui∗≤0u_i^*\leq0 for ii in the μ\mu-part, (z−z∗)Tu∗(z-z^*)^{\mathsf{T}}u^* is nonpositive.

Combining them yields

W˙≤−(z−z∗)TH(z−z∗)≤−2λmin⁡(H)W.(28)\dot{W}\leq-(z-z^*)^{\mathsf{T}}H(z-z^*)\leq-2\lambda_{\min}(H)W. \tag*{(28)}

From Lemmas 2 and 3, we have the following theorem.

Theorem 1 (Convergence of Sliding Phase): Consider that s(t0s)=0s(t_0^s)=0, and we assume that the number of changes of I(t)I(t) is finite. Then, the state variables (x,λ,μ)(x,\lambda,\mu) converge to the optimal values (x∗,λ∗,μ∗)(x^*,\lambda^*,\mu^*) as t→∞t\to\infty.

Proof. By Lemma 2, the sliding phase sustains from t=t0st=t_0^s onward. During the sliding phase, the dual variable zz moves according to (23). Then, by Lemma 3, z(t)→z∗z(t)\to z^*, and

x(t)=xˉ−F−1Gz(t)→xˉ−F−1Gz∗=x∗;(29)x(t)=\bar{x}-F^{-1}Gz(t) \to\bar{x}-F^{-1}Gz^*=x^*; \tag*{(29)}

where the last equality follows from Fx∗+Gz∗=0F x^*+G z^*=0.

Remark 4. The analysis is addressed in continuous time. In practice, supply-demand coordination proceeds in discrete time, and the discontinuous update of the Sign PDGD causes chattering around the sliding surface. Therefore, a numerical analysis for the discrete-time case, including the convergence and the size of the chattering, needs to be considered separately.

Numerical Simulation

In this section, we apply the Sign PDGD (6) to a toy supply-demand coordination problem and compare their behavior with the theoretical analysis discussed in Section III.

Problem Setting

We consider a single supplier and a single finite resource, such as the CPU capacity of a single datacenter, whose total stock is V=7V=7. This resource is shared among N=4N=4 buyers, and xix_i denotes the amount determined by buyer ii. The cost function of buyer ii is fi(xi)=12Fi(xi−xˉi)2f_i(x_i)=\frac{1}{2}F_i(x_i-\bar{x}_i)^2, where xˉi>0\bar{x}_i>0 is the amount that the buyer ii ideally wants, and Fi>0F_i>0 represents the dissatisfaction factor of the buyer ii. Note that the value of xˉi\bar{x}_i is private, meaning that it is not open to other buyers or the supplier. The parameters are set to xˉ=[3.0,2.7,3.2,2.6]\bar{x}=[3.0,2.7,3.2,2.6] and F=diag⁡(0.5,0.6,1.0,1.5)F=\operatorname{diag}(0.5,0.6,1.0,1.5). We let the objective function as f(x)=12(x−xˉ)TF(x−xˉ)f(x)=\frac{1}{2}(x-\bar{x})^{\mathsf{T}}F(x-\bar{x}).

The only constraint is that the total amount must not exceed the stock VV, which is formulated as

1NTx−V≤0.(30)\mathbf{1}_N^{\mathsf{T}}x - V \le0. \tag*{(30)}

There is no equality constraint in this setup.

By letting C=1NTC = \mathbf{1}_N^{\mathsf{T}} and d=Vd = V, we reduce the optimization problem (1) to

{min⁡x∈R4f(x)s.t.(30).(31)\begin{cases} \min_{x\in\mathbb{R}^{4}} & f(x) \\ \text{s.t.} & (30). \tag*{(31)} \end{cases}
s.t.(30).(32)\text{s.t.} \quad(30). \tag*{(32)}

The dual variable μ∈R\mu\in\mathbb{R} is the scalar price of the resource, and z=μz = \mu, G=CT=1NG = C^{\mathsf{T}} = \mathbf{1}_N, and H=∑i1/FiH = \sum_i 1/F_i. The analytical optimum is

μ∗=∑ixˉi−V∑i1/Fi≈0.84,xi∗=xˉi−μ∗Fi,(33)\mu^* = \frac{\sum_i \bar{x}_i - V}{\sum_i 1/F_i} \approx0.84,\qquad x_i^* = \bar{x}_i - \frac{\mu^*}{F_i}, \tag*{(33)}

which we use as the reference for the simulation results.

Scenarios

We compare two scenarios: the Sign PDGD (6) with ηx=30.0\eta_x = 30.0 and 3.03.0. All the simulations are discretized with the time step Δt=0.001\Delta t = 0.001 s, and the initial values are x(0)=0x(0) = 0 and μ(0)=0\mu(0) = 0.

Results for ηx=30.0\eta_x = 30.0

Figure 2 shows the time evolution of xix_i. Solid lines show the buyers’ trajectories, and the dotted lines show the analytical optimum xi∗x_i^*. All trajectories converge to the analytical optimum. The allocation of each buyer increases almost linearly up to a certain time. Afterwards, the trajectories bend and settle smoothly to the optimum.

Figure 2. Primal variable xx of Sign PDGD with ηx=30.0\eta_x = 30.0

Figure 3 shows the time evolution of the sliding variable ss. The black solid line shows the value of ss and the dotted red line shows 00. Every element first has si≠0s_i \ne0, then reaches si=0s_i = 0, after which si=0s_i = 0 is maintained. This is the behavior predicted for the reaching phase followed by the sliding phase.

Figure 3. Sliding variable ss of Sign PDGD with ηx=30.0\eta_x = 30.0

Lemma 1 gives the upper bound of the reaching phase time as TR=0.136T^{\mathrm{R}} = 0.136 s. The observed time at which the sliding phase started for all elements was 0.123 s, which is consistent with the bound2.

Results for ηx=3.0\eta_x = 3.0

When ηx=3.0\eta_x = 3.0, the Assumption 1 does not hold. Table I shows the maximum of ∣v˙i(t)∣|\dot{v}_i(t)| and the bound ηxFi\eta_x F_i for each element and for both gains ηx\eta_x. For ηx=30.0\eta_x = 30.0, the maximum is below the bound for all elements, so the assumption holds. However, for ηx=3.0\eta_x = 3.0, the maximum exceeds the bound for i=1i = 1 and 22, so the assumption is violated for these elements, while it holds for i=3i = 3 and 44.

ηx=30.0\eta_x = 30.0ηx=3.0\eta_x = 3.0
Element ii12341234
max⁡t∣v˙i(t)∣\max_t |\dot{v}_i(t)|3.983.983.983.982.492.492.492.49
ηxFi\eta_x F_i15.0018.0030.0045.001.501.803.004.50

Table I. Check of Assumption 1: The maximum price speed and its upper bound

Figure 4 shows the sliding variable ss for ηx=3.0\eta_x = 3.0. Elements i=3i = 3 and 44, for which Assumption 1 holds, reach si=0s_i = 0 and stay there.

Figure 4. Sliding variable ss of Sign PDGD with ηx=3.0\eta_x = 3.0

The sliding phase started for all components at 0.898 s, which is later than in the ηx=30.0\eta_x = 30.0 scenario. This indicates that a smaller gain ηx\eta_x slows the reaching phase.

Elements i=1i = 1 and 22 reach si=0s_i = 0 but subsequently leave si=0s_i = 0. After that, they return to 0 only after a few seconds and converge to the optimum. The inequality ∣v˙i(t)∣<ηxFi|\dot{v}_i(t)| < \eta_x F_i in Assumption 1 was violated only temporarily. After the violation, the inequality held again, and the sliding phase is maintained. This suggests that Assumption 1 is sufficient but not necessary, and it may be conservative in this scenario.

Conclusion

In this paper, we proposed the Sign PDGD, a primal-dual gradient dynamics for supply-demand coordination in which human buyers provide only coarse feedback. We modeled the buyer’s signal as the sign of the gradient of the buyer utility and marginal utility. We analyzed the convergence property of the Sign PDGD by interpreting it as SMC. In the numerical simulation, we assumed a simple resource-sharing problem, and the Sign PDGD converged to the analytical optimum, reproducing the reaching and sliding phase predicted by the theoretical analysis.

Several works remain for future work. First, a theoretical analysis for the discrete-time system is needed to explain the chattering observed in the numerical simulation. Second, we assumed that the human intention is given as a sign signal. In practice, a mechanism for extracting this signal from the buyer’s behavior is required. For example, [27] and [28] study the use of language models to infer intentions from human language. Combining the intention-reading mechanism with Sign PDGD is a possible direction. Third is to derive a weaker sufficient condition than Assumption 1.

References

  1. [2]D. Palomar and M. Chiang, “A tutorial on decomposition methods for network utility maximization,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 8, pp. 1439–1451, 2006.DOI
  2. [3]Z. Wang, F. Liu, Y. Su, P. Yang, and B. Qin, “Asynchronous Distributed Voltage Control in Active Distribution Networks,” Automatica, vol. 122, p. 102969, 2020.arxiv.org/abs/1908.06548
  3. [4]J. Hansen, J. Knudsen, A. Kiani, A. Annaswamy, and J. Soustrup, “A Dynamic Market Mechanism for Markets with Shiftable Demand Response,” IFAC Proceedings Volumes, vol. 47, no. 3, pp. 1873–1878, 2014.
  4. [5]P. Samadi, A.-H. Mohsenian-Rad, R. Schober, V. W. S. Wong, and J. Jatskevich, “Optimal Real-Time Pricing Algorithm Based on Utility Maximization for Smart Grid,” in 2010 First IEEE International Conference on Smart Grid Communications (SmartGridComm), 2010, pp. 415–420.DOI
  5. [6]S. Janjua, D.-A. An-Vo, K. Reardon-Smith, and S. Mushtaq, “A Three-Stage Cooperative Game Model for Water Resource Allocation Under Scarcity Using Bankruptcy Rules, Nash Bargaining Solution and TOPSIS,” Water Resources Management, vol. 39, pp. 3553–3576, 2025.
  6. [7]D. T. Nguyen, L. B. Le, and V. K. Bhargava, “A Market-Based Framework for Multi-Resource Allocation in Fog Computing,” IEEE/ACM Transactions on Networking, vol. 27, no. 3, pp. 1151–1164, 2019.arxiv.org/abs/1807.09756
  7. [8]E. Moro and I. Filippini, “Joint Management of Compute and Radio Resources in Mobile Edge Computing: A Market Equilibrium Approach,” IEEE Transactions on Mobile Computing, vol. 22, no. 2, pp. 983–995, 2023.
  8. [9]D. Feijer and F. Paganini, “Stability of Primal–Dual Gradient Dynamics and Applications to Network Optimization,” Automatica, vol. 46, no. 12, pp. 1974–1981, 2010.DOI
  9. [10]S. Yamashita, T. Hatanaka, J. Yamauchi, and M. Fujita, “Passivity-Based Generalization of Primal–Dual Dynamics for Non-Strictly Convex Cost Functions,” Automatica, vol. 112, p. 108712, 2020.
  10. [11]D. Richert and J. Cortés, “Robust Distributed Linear Programming,” IEEE Transactions on Automatic Control, vol. 60, no. 10, pp. 2567–2582, 2015.arxiv.org/abs/1409.7140
  11. [12]S. A. Alghunaim and A. H. Sayed, “Linear convergence of primal–dual gradient methods and their performance in distributed optimization,” Automatica, vol. 117, p. 109003, 2020.arxiv.org/abs/1904.01196
  12. [13]G. Qu and N. Li, “On the Exponential Stability of Primal-Dual Gradient Dynamics,” IEEE Control Systems Letters, vol. 3, no. 1, pp. 43–48, 2019.DOI
  13. [14]A. Cherukuri, E. Mallada, and J. Cortés, “Asymptotic convergence of constrained primal–dual dynamics,” Systems & Control Letters, vol. 87, pp. 10–15, 2016.arxiv.org/abs/1510.02150
  14. [15]K. Shahgolzadeh and N. Momshizadeh, “Towards a Socially Acceptable Competitive Equilibrium in Energy Markets,” in 2024 IEEE 63rd Conference on Decision and Control (CDC). IEEE, 2025, pp. 4263–4268.
  15. [16]A. Mohammadi and M. Al Janaideh, “Sign Gradient Descent Algorithms for Kinetostatic Protein Folding,” in 2023 International Conference on Manipulation, Automation and Robotics at Small Scales (MARSS), 2023, pp. 1–6.arxiv.org/abs/2308.07453
  16. [17]E. Moulay, V. Léchappé, and F. Plestan, “Properties of the sign gradient descent algorithms,” Information Sciences, vol. 492, pp. 29–39, 2019.DOI
  17. [18]Y. Liao, N. Deng, H. Wu, B. Gao, Q. Zhang, and H. Qian, “Weighted synapses without carry operations for ram-based neuromorphic systems,” Frontiers in Neuroscience, vol. 12, 2018.DOI
  18. [19]M. Riedmiller and H. Braun, “A direct adaptive method for faster backpropagation learning: the RPROP algorithm,” in IEEE International Conference on Neural Networks, 1993, pp. 586–591 vol.1.
  19. [20]S. Li, Q. Chen, W. Li, M. Wang, S. Pang, and K. Wu, “Observer-based sliding mode admittance control for ultrasound robot force-tracking in complex interaction environments,” Control Engineering Practice, vol. 169, p. 106764, 2026.DOI
  20. [21]M. Farhat, Y. Kali, M. Saad, M. H. Rahman, and R. E. Lopez-Herrejon, “New Fixed-Time Observer-Based Model-Free Fixed-Time Sliding Mode of Joint Angle Commanded NAO Humanoid Robot,” IEEE Transactions on Control Systems Technology, vol. 33, no. 1, pp. 304–315, 2025.
  21. [22]L. Kang, G. Hongbo, J. Haibo, and H. Zhengyuan, “Adaptive Sliding Mode Based Disturbance Attenuation Tracking Control for Wheeled Mobile Robots,” International Journal of Control, Automation and Systems, vol. 18, no. 5, pp. 1288–1298, 2020.DOI
  22. [23]C. M. Labbadi and M. Bouzi, “A New Nonlinear Sliding Mode Controller for Congestion of TCP Networks,” IFAC-PapersOnLine, vol. 59, no. 14, pp. 244–249, 2025, 15th IFAC Workshop on Adaptive and Learning Control Systems ALCOS 2025.DOI
  23. [24]P. V. Surjagade, J. Deng, V. Vajpayee, V. M. Becerra, S. Shimjith, and A. J. Arul, “An arbitrary-order continuous sliding mode control technique for nonlinear PWR-type nuclear power plants,” Progress in Nuclear Energy, vol. 150, p. 104309, 2022.DOI
  24. [25]A. F. Filippov, Differential Equations with Discontinuous Righthand Sides, ser. Mathematics and its Applications. Springer, 1988, vol. 18.
  25. [26]G. Weibing and J. Hung, “Variable structure control of nonlinear systems: a new approach,” IEEE Transactions on Industrial Electronics, vol. 40, no. 1, pp. 45–55, 1993.
  26. [27]Y. Miyaoka, M. Inoue, and J. Maestre, “Chat-Driven Reconfiguration of Model Predictive Control,” IEEE Transactions on Control Systems Technology, pp. 1–12, 2026.
  27. [28]Y. Miyaoka, M. Inoue, K. Urata, and S. Harada, “Chat-Driven Optimal Management for Virtual Network Services,” IEEE Transactions on Network and Service Management, vol. 23, pp. 7576–7589, 2026.arxiv.org/abs/2512.24614

Paper details

vlnc:W_3m8ne675
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents