Source-linked AI summary
Distributed Nonsmooth Optimization with Coupled Inequality Constraints via Modified Lagrangian Function
Shu Liang, Xianlin Zeng, Yiguang Hong
TL;DR
For nonsmooth convex optimization with coupled inequality constraints, the paper constructs a modified Lagrangian using local multipliers and a nonsmooth penalty, then proposes a distributed continuous-time algorithm. Under its stated assumptions, the algorithm is stable and its solutions converge to the set of saddle points; numerical examples illustrate its effectiveness.
Problem
The paper considers distributed nonsmooth convex optimization with coupled inequality constraints, where agents may not have access to the aggregate constraint function.
Source: §I · p. 2Method
The approach combines local multipliers and a nonsmooth penalty in a modified Lagrangian, then uses projected primal-dual subgradient dynamics in a distributed continuous-time algorithm.
Source: §I · p. 2, A. Lagrangian Function and Distributed… · pp. 6–7Results
Under Assumption 3.1, the algorithm is stable and every solution converges to the set of saddle points of the modified Lagrangian.
Source: B. Existence and Convergence · p. 10Takeaways & Limitations
The paper reports that two numerical examples illustrate the algorithm’s effectiveness and that its nonsmooth dynamics’ convergence rate is analyzed.
Source: §VI · p. 15
Abstract
from arXiv · showhide
This technical note considers a distributed convex optimization problem with nonsmooth cost functions and coupled nonlinear inequality constraints. To solve the problem, we first propose a modified Lagrangian function containing local multipliers and a nonsmooth penalty function. Then we construct a distributed continuous-time algorithm by virtue of a projected primal-dual subgradient dynamics. Based on the nonsmooth analysis and Lyapunov function, we obtain the existence of the solution to the nonsmooth algorithm and its convergence.
I. INTRODUCTION
The introduction motivates distributed optimization with coupled constraints that may be unavailable to individual agents. It presents a fully distributed nonsmooth continuous-time approach using local multipliers and a penalty function.
I. INTRODUCTION
- When agents do not know coupled constraints, existing distributed approaches may require auxiliary dynamics that complicate the design, especially for coupled inequalities.Prior work addressed coupled equalities or used average consensus to estimate inequality constraints.Source: §I · p. 2
- The paper targets distributed optimization with separable costs and coupled constraints that make each agent’s feasible decisions depend on other agents’ decisions.The introduction situates continuous-time distributed algorithms in part through their hardware implementation and application in continuous-time physical systems,.Source: §I · p. 2
- The proposed algorithm uses local multipliers and a nonsmooth penalty in a modified Lagrangian, with agents updating from local data and neighbor information without a central coordinator.It uses only primal variables and local multipliers, yielding lower-order dynamics than existing algorithms.Source: §I · p. 2
II. PRELIMINARIES
The preliminaries establish notation and tools from convex analysis, differential inclusions, and graph theory for the subsequent algorithm and convergence analysis.
II. PRELIMINARIES
- The section defines upper semicontinuity and the graph of a set-valued map, then states results used to relate differential inclusions and establish solution existence under compactness and convexity conditions.The stated existence result requires an upper semicontinuous map and a compact, convex constraint set.Source: §II · pp. 3–4
- For a convex function on a closed convex set, optimality is characterized by zero belonging to the sum of its subdifferential and the set’s normal cone.The section also introduces tangent and normal cones, projection operators, and convexity notions.Source: §II · pp. 3–4
- A Lyapunov-stable equilibrium that is a cluster point of a differential-inclusion solution is its limit as time tends to infinity.Source: §II · p. 4
III. PROBLEM FORMULATION
The paper formulates a distributed convex optimization problem with separable local costs and coupled inequality constraints. It distinguishes the setting by nonsmoothness, heterogeneous decision-variable dimensions, and constraints that may not be locally available.
III. PROBLEM FORMULATION
- The problem minimizes the sum of local costs over agents’ local constraint sets, subject to a coupled inequality formed by summing their constraint mappings.Each agent can access its own g_i(x_i), rather than the aggregate g(x).Source: §III · pp. 4–5
- The formulation assumes compact convex local sets, strictly convex local costs, convex constraint mappings, local Lipschitz continuity, Slater’s condition, and a connected undirected communication graph.Source: §III · p. 5
- The decision variables may have heterogeneous dimensions, and both cost and constraint functions may be nonsmooth.Source: §III · p. 5
- The setting includes coupled inequality constraints that may be unavailable to local agents, unlike cited work on coupled equality constraints –[18].Source: §III · p. 5
IV. MAIN RESULTS
The main-results section introduces a modified Lagrangian and a distributed continuous-time algorithm, then addresses solution existence, convergence, and convergence rate.
IV. MAIN RESULTS
- The section proposes a modified Lagrangian function for the considered distributed optimization problem.Source: §IV · p. 5
- It presents a distributed continuous-time algorithm based on the modified Lagrangian.Source: §IV · p. 5
- The analysis addresses solution existence, convergence, and the convergence rate of the nonsmooth algorithm.Source: §IV · p. 5
A. Lagrangian Function and Distributed Algorithm Design
The section constructs a modified Lagrangian with local multipliers and a nonsmooth consensus penalty, then uses it to design a fully distributed continuous-time algorithm. Its saddle points correspond to those of the original Lagrangian and thus to optimal primal-dual solutions.
A. Lagrangian Function and Distributed Algorithm Design
- The cited passage states that because f(x) is strictly convex, the primal solution x∗ is unique, while the corresponding optimal multiplier λ∗ may not be unique.Source: A. Lagrangian Function and Distributed… · p. 6
- The modified Lagrangian uses local multipliers and a nonsmooth penalty to decouple local cost and constraint terms for distributed design.The penalty is an exact penalty for multiplier consensus.Source: A. Lagrangian Function and Distributed… · pp. 6, 7, 9
- The nonsmooth penalty φ(λ) measures multiplier consensus, and Kφ(λ) acts as an exact penalty for reaching consensus.The stated bound S(λ) ≤ Nφ²(λ) has equality if and only if λ ∈ S.Source: A. Lagrangian Function and Distributed… · p. 7
- The modified and original Lagrangians have matching saddle points, which correspond to optimal primal-dual solutions.The equivalence is established under Assumption 3.1.Source: A. Lagrangian Function and Distributed… · pp. 7–8
- Each agent updates only its local primal variable and multiplier using local functions and neighboring multipliers, without a central coordinator.The centralized projected primal-dual update requires a center to broadcast multipliers and gather constraint information.Source: A. Lagrangian Function and Distributed… · pp. 6, 8
B. Existence and Convergence
The section establishes that the nonsmooth projected algorithm has solutions and that its trajectories converge to modified-Lagrangian saddle points. It also gives an O(1/t) convergence rate for the time-averaged Lagrangian value.
B. Existence and Convergence
- Theorem 4.2 establishes existence of a solution to algorithm (14) for any initial primal and dual values.The proof establishes upper semicontinuity of a set-valued map and obtains a solution to an auxiliary system that is also a solution to (14).Source: B. Existence and Convergence · pp. 9–10
- Any solution of algorithm (14) converges to the set of saddle points of the modified Lagrangian, and the algorithm is stable.The theorem also states that a saddle point exists to which each solution converges.Source: B. Existence and Convergence · pp. 10–11
- The modified- and original-Lagrangian saddle points match, and are consistent with optimal primal-dual solutions.The proof identifies the equilibrium primal variable with the unique solution of the primal problem.Source: B. Existence and Convergence · p. 10
- A Lyapunov-function derivative is bounded above by the negative of a nonnegative function, supporting stability and convergence analysis.The derivative inequality is stated along solutions of algorithm (14).Source: B. Existence and Convergence · pp. 10–11
- Theorem 4.4 gives an O(1/t) rate for the time-averaged Lagrangian value to converge to its value at saddle points.The rate concerns the value along time-average trajectories.Source: B. Existence and Convergence · pp. 11–12
V. NUMERICAL EXAMPLES
The numerical section presents a four-agent nonsmooth optimization example and a further randomly generated problem setting. In the four-agent example, the primal trajectories remain within local constraint sets and the Lyapunov functions decrease monotonically; average results are also reported as indicating effectiveness.
Example 5.1
- In the four-agent example, primal trajectories stay within local constraint sets and both algorithms' Lyapunov functions decrease monotonically.The comparison is between the centralized primal-dual algorithm and the distributed algorithm.Source: §V · p. 13, Figure 2 · p. 14, Figure 3 · p. 14
Example 5.2
- The second example uses local constraints x_i in [0, 1] and coupled inequalities g(x) = Px − q ≤ 0.It considers network sizes N = 10, 20, 50 with M = 5 coupled constraints and randomly generated communication graphs.Source: §V · p. 13
- Average results are reported in Table II, and the text says they indicate the distributed algorithm's effectiveness.The supplied passage does not provide the table's values.Source: §V · p. 14
VI. CONCLUSION
The note studies distributed nonsmooth convex optimization with coupled inequality constraints using a modified Lagrangian built via local multipliers. It proposes a distributed continuous-time algorithm and reports convergence analysis and numerical examples.
VI. CONCLUSION
- A distributed continuous-time algorithm is proposed using a modified Lagrangian constructed via local multipliers and a nonsmooth penalty technique.Source: §VI · pp. 14–15
- The convergence of the nonsmooth dynamics is proved and its convergence rate is analyzed.Source: §VI · p. 15
- The algorithm's effectiveness is illustrated by two numerical examples.Source: §VI · p. 15