Multiple-response agents: Fast, feasible, approximate primal recovery

for dual optimization methods

This repository accompanies the paper "Multiple-Response Agents: Fast, Feasible, Approximate Primal Recovery for Dual Optimization Methods".

The mra package implements multiple-response agents (MRA) method for primal variable recovery in dual optimization methods. We consider the following problem $$ \begin{array}{ll} \text{minimize} & \sum{i=1}^K fi(xi)\ \text{subject to} & \sum{i=1}^K Ai xi \leq b, \end{array} $$ where $fi:\mathbf{R}^{ni} \to \mathbf{R} \cup {\infty}$, $Ai:\mathbf{R}^{m \times ni}$ and $b:\mathbf{R}^{m}$ are given, for all $i=1, \ldots, K$. We refer to $fi$ as agent $i$. We assume each agent implements conjugate subgradient oracle $$ xi(yi) \in \argmin{zi \in \mathbf{dom} fi} \left( fi(zi) - yi^Tzi \right), \quad i=1,\ldots, K, $$ and approximate conjugate subgradient oracle that returns $x^{\text{apx}}(y)$ that approximately minimizes $f(z) - y^{T} z$ with respect to $z$, i.e., $$ -f^(y) \leq f(x^{\text{apx}}(y)) - y^{T} x^{\text{apx}}(y) \approx -f^(y). $$

Then MRA constructs a new primal point $\bar x^k$ based on current estimation of dual variables $\lambda^k$ that reduces the primal residuals. The figure below illustrates the overall optimization flow of MRA.

MRA_Primal_Recovery: - Key parameters: - fun_agents: List of agent functions that return responses for a given dual vector. - primal_var_size: Total dimension of the primal variable. - A_ineq, b_ineq, A_eq, b_eq: constraint matrices and vectors. - history: Number of past iterations to retain. - Methods: - query: - Inputs: - lamb_k: Current dual price vector. - K: Number of responses per agent: first response from the conjugate subgradient oracle, and K-1 responses from the approximate conjugate subgradient oracle. - epoch: Iteration index (updates history). - Outputs: - x_k: Primal solution vector. - Zs: List of candidate response matrices. - primal_recovery: - Process: 1. Determine weights (u_best) via convex relaxation (default) or MILP/greedy. 2. Combine responses: For each agent, compute Zs[i] @ u_best[i].

Usage:

python import mra fun_agents, primal_var_size, A_ineq, b_ineq = ... MRA = mra.MRA_Primal_Recovery(fun_agents, primal_var_size, A_ineq=A_ineq, b_ineq=b_ineq) x_k, Zs = MRA.query(lamb_k, K=10, epoch=0) bar_xk = MRA.primal_recovery(lamb_k, Zs)