Source-linked AI summary
Computing B-Stationary Points of Nonsmooth DC Programs
Jong-Shi Pang, Meisam Razaviyayn, Alberth Alvarado
TL;DR
The paper addresses nonsmooth dc optimization motivated by physical-layer security and asks how stationary concepts relate and how sharp solutions can be computed. It develops convergent algorithms for d-stationarity, including randomized, distributed, penalty, and dc-constraint extensions, and introduces B-stationarity machinery for specially structured nonconvex constraints.
Problem
Nonsmooth dc programs have multiple stationarity concepts, and provably computing the sharp d-stationary solution for convex-constrained problems has been elusive.
Method
The paper analyzes stationarity relations and develops a convergent iterative algorithm with randomized, distributed, penalty, and structured dc-constraint extensions.
Results
The paper establishes convergence of its algorithms and characterizes B-stationarity for specially structured nonconvex dc constraints through convex programs.
Takeaways & Limitations
The framework provides computational routes for d-stationary solutions and for verifying or computing B-stationary points in the stated dc-program classes.
Takeaways & Limitations
A practically implementable and provably convergent algorithm remains an open challenge for the stated broader compact-convex-set case.
Abstract
from arXiv · showhide
Motivated by a class of applied problems arising from physical layer based security in a digital communication system, in particular, by a secrecy sum-rate maximization problem, this paper studies a nonsmooth, difference-of-convex (dc) minimization problem. The contributions of this paper are: (i) clarify several kinds of stationary solutions and their relations; (ii) develop and establish the convergence of a novel algorithm for computing a d-stationary solution of a problem with a convex feasible set that is arguably the sharpest kind among the various stationary solutions; (iii) extend the algorithm in several directions including: a randomized choice of the subproblems that could help the practical convergence of the algorithm, a distributed penalty approach for problems whose objective functions are sums of dc functions, and problems with a specially structured (nonconvex) dc constraint. For the latter class of problems, a pointwise Slater constraint qualification is introduced that facilitates the verification and computation of a B(ouligand)-stationary point.
1 Introduction
The paper studies nonsmooth dc optimization motivated by physical-layer security, clarifies competing stationarity concepts, and develops convergent algorithms for computing d-stationary solutions and extensions.
- Motivation: Nonsmooth dc optimization problems arise in physical-layer security and related joint base-station assignment and power-allocation applications.The motivating secrecy problem can be represented through auxiliary variables as a smooth, bi-concave, linearly constrained maximization problem.
- Research questions: The study asks how criticality, d-stationarity, and lifted stationarity are related, and whether d-stationary points can be computed provably.These questions organize the paper’s analysis of stationary solutions for convex-constrained dc programs.
- Core contributions: The paper argues that d-stationarity is the sharpest considered concept and proposes an iterative algorithm whose convergence is established.A randomized version selects subproblems to address a potential practical weakness of the basic algorithm.
- Algorithmic extensions: The algorithmic framework is extended to multi-agent objectives formed by sums of dc functions, enabling distributed optimization with private agent objectives and coupled variables.The distributed formulation seeks to let agents optimize independently with minimal communication.
- Algorithmic extensions: For nonsmooth dc constraints, the paper defines B-stationarity and characterizes it through a reasonable number of convex programs.This extension targets verification and computation for general dc programs with nonconvex dc constraints.
2 Motivating Applied Problems
The motivating communication problems can be expressed within a structured dc framework, while the paper highlights limits of continuum maxima and differences between equivalent formulations for stationary analysis.
- Applications: Power-allocation problems in digital communication systems motivate a unified class of value functions involving continuum families of bivariate functions.The applications include secrecy-rate maximization and joint base-station assignment with power allocation.
- Applications: The secrecy sum-rate objective is dc because its rate terms are differentiable differences of concave functions, and finite maxima and sums preserve the dc property.The plus-function appears in the formulation, while the objective’s dc structure follows from closure under finite pointwise maxima and sums.
- Structured dc representation: A continuum pointwise maximum of dc functions is not dc in general, unlike the finite case.The paper gives a Lipschitz function that is not directionally differentiable as a counterexample, whereas every dc function is directionally differentiable.
- Structured dc representation: The paper’s structured value-function result preserves dc structure for a multi-agent problem with compact, potentially nonconvex parameter sets and convex or concave component functions.The formulation accommodates products of parameter functions and component functions over a closed convex feasible set.
- Formulation and stationarity: The lifted bivariate formulation is globally optimal-solution equivalent to the x-alone formulation but can yield a less sharp d-stationarity concept.The lifted formulation is differentiable under differentiable component functions, while the x-alone formulation remains nondifferentiable because of the max operator.
3 Stationarity: Convex Constraints
For convex-constrained nonsmooth dc programs, the paper distinguishes several stationarity notions and establishes their relationships, emphasizing d-stationarity as the sharpest target. It also identifies when these notions coincide and highlights counterexamples showing why weaker notions may be inadequate.
- Motivation: Global optima are generally unavailable for nonconvex dc programs, so practical computation focuses on stationary solutions.The paper cautions that stationarity must be chosen carefully, especially with dc constraints.
- Directional stationarity: A constrained d-stationary point requires nonnegative directional derivatives of the dc objective along every feasible direction.For ζ=f−g, this is equivalently expressed through all v in the convex subdifferential ∂g(x), yielding a generalized KKT characterization.
- Relations among notions: For good dc functions, d-stationarity and C-stationarity are equivalent, whereas this implication can fail for general dc functions.The paper defines good dc functions through a strictly differentiable convex component in a dc representation.
- Relations among notions: The paper establishes that d-stationarity implies weak d-stationarity and criticality, with equivalence when the relevant argmax and subdifferential sets are singletons.These singleton conditions occur when the dc function is good.
- Lifted stationarity: Weak d-stationarity is equivalent to lifted stationarity when an auxiliary maximizing variable is exposed in the bivariate formulation.The lifted formulation can be interpreted through stationarity of the bivariate objective over X × M.
- Implications and limitations: Local minimizers imply d-stationarity, which in turn implies lifted stationarity, while weaker stationarity notions need not provide minimizing behavior.A counterexample shows that a weak d-stationary point can have no minimizing property for the original problem.
- Relations among notions: If the value function is strictly differentiable, all stationarity concepts discussed become equivalent.For finite maximizing sets, the value function is piecewise smooth, and strict differentiability is characterized using gradients at maximizing points.
4 dc Constrained dc Programs
The paper studies dc programs with a nondifferentiable, nonconvex dc constraint, develops a pointwise Slater-based tangent-cone characterization, and reduces B-stationarity verification to finitely many convex-constrained dc problems.
- Motivation: Dc constraints arise in applications including QoS-constrained power allocation and quadratic programs with linear complementarity constraints.The complementarity formulation is equivalent to two linear inequalities and one quadratic inequality, making the QPCC a linearly constrained dc program with one additional dc constraint.
- Problem setting: A nondifferentiable dc constraint makes the feasible set nonconvex and complicates both constraint qualifications and constructive descriptions of B-stationarity.B-stationarity is based on the Bouligand tangent cone, whose direct verification is difficult for this class of feasible sets.
- Piecewise structure: The feasible set can be decomposed into finitely many smooth pieces when the convex side of the dc constraint is a pointwise maximum of finitely many differentiable convex functions.Each piece has the form b Xj = {x ∈ X | φc(x) ≤ ψc,j(x)}.
- Constraint qualification: The pointwise Slater constraint qualification requires one feasible tangent direction satisfying strict inequalities for every active branch of the pointwise maximum.Under this condition, the relevant tangent cones coincide with explicit closed convex cones; the same conclusion also holds under the assumptions of Proposition 7.
- Stationarity characterization: Under the pointwise Slater condition or Proposition 7 assumptions, B-stationarity is equivalent to d-stationarity on every convex branch approximation.Thus, checking B-stationarity reduces to solving |Mc(x̄)| convex-constrained dc programs, while identifying such a point requires an algorithm adapted to the dc constraint.
- Computation: The resulting verification procedure checks d-stationarity for each active branch, providing the basis for an algorithm to compute B-stationary points.The paper notes that the algorithm must be extended to handle the dc constraint when identifying the candidate point itself.
5 Computing d-Stationary Points
The paper develops an algorithm for computing d-stationary points in convex-constrained nonsmooth dc programs and establishes subsequential convergence under boundedness assumptions. It also analyzes randomized subproblem selection and identifies limits of the current approach.
- 5.1 The basic algorithm: Without regularization, the DCA can remain at a non-d-stationary point because an unsuitable subgradient is selected.The paper's example shows the regularized DCA converging to x∞ = 0, which is not d-stationary.
- 5.1 The basic algorithm: Under a bounded-below objective and bounded initial level set, every accumulation point generated by Algorithm I is d-stationary.The sequence is well-defined and bounded; if it does not terminate finitely, its accumulation points cannot be local maximizers.
- 5.1 The basic algorithm: The basic algorithm replaces one subgradient choice with gradients of all nearly active convex components, requiring multiple convex subproblems.This additional per-iteration work enables subsequential convergence to a d-stationary point.
- 5.1 The basic algorithm: The method is not yet extended to continuum-family value functions with ϕ(x) represented as a maximum over a compact convex set.A practically implementable and provably convergent algorithm for this case remains open.
- 5.1 The basic algorithm: If an accumulation point is isolated, the entire sequence converges to it.This strengthens the general subsequential convergence result under the stated isolation condition.
- 5.2 A randomized version: Randomized selection reduces the number of subproblems solved per iteration while every limit point remains d-stationary with probability one.The objective-value sequence converges almost surely under the bounded-below assumption.
6 Algorithmic Extension: I
The paper extends its d-stationarity framework to dc-constrained programs, using pointwise Slater conditions to characterize B-stationarity and direct or penalized algorithms to compute it.
- 6.1 Feasibility assumed: Under the pointwise Slater constraint qualification, B-stationarity is characterized by convex optimization conditions for every active objective and constraint component pair.The characterization reduces verification to a family of convex programs.
- 6.1 Feasibility assumed: When a feasible starting point is available, Algorithm II solves strongly convex subproblems indexed by nearly active objective and constraint components.The next iterate is selected from the resulting candidate solutions while remaining feasible.
- 6.2 Feasibility not assumed: Without an available feasible solution, a double-loop penalty scheme solves convex-constrained penalized dc subproblems using Algorithm I or its randomized version.The penalty parameter increases toward infinity, and the limiting stationarity depends on the signs of the constraint violations.
- 6.1 Feasibility assumed: Under a bounded-below objective and bounded feasible level set, Algorithm II generates a bounded feasible sequence whose accumulation points are feasible.Any accumulation point satisfying pointwise Slater is B-stationary.
- 6.2 Feasibility not assumed: If constraint violation remains positive infinitely often and the constraint max-function is strictly differentiable at the limit, the limit is d-stationary for the penalized objective setting.The result assumes bounded X and global Lipschitz continuity of the objective.
- 6.2 Feasibility not assumed: If constraint violation is negative infinitely often, the penalty-limit point is d-stationary for the constraint function on X and therefore B-stationary.This conclusion is stated for the infeasible-side subsequence case.
7 Algorithmic Extension: II
The section extends dc algorithms to sum-structured objectives through randomized selection and a distributed penalty scheme. The method decomposes penalized subproblems across agents, while convergence recovers feasibility and, under strict differentiability, d-stationarity.
- Motivation: Sum-structured dc objectives motivate distributed optimization because each agent has a private performance function with coupled variables.The dc and nondifferentiable objective, together with variable coupling, create the main challenges.
- Randomized selection: When each of n agents has two component functions, enumerating all index tuples can require 2^n subproblems per iteration.Randomized selection avoids exhausting this potentially exponential set at every iteration.
- Randomized selection: Randomly selecting an admissible tuple reduces the number of subproblems, but solving the resulting global problem remains centralized.The distributed penalty approach is introduced to exploit the sum structure without requiring additional structural assumptions.
- Penalty approach: The penalty reformulation duplicates x into variables z_i, imposes z_i = x, and replaces these constraints with a sum-of-squares penalty weighted by ρ.Outer iterations increase ρ toward infinity, while inner iterations solve strongly convex approximations.
- Convergence: Every accumulation point of penalized d-stationary solutions recovers z_i = x; if each ϕ_i is strictly differentiable at the limit, x is d-stationary.The analysis assumes bounded gradients of the convex component functions on X.
- Distributed algorithm: Each inner iteration decomposes into I + 1 strongly convex subproblems that can be solved separately, enabling parallel processing across individual summands.The nonseparable penalty term is linearized at the current base tuple before decomposition.
- Limitations: The outer-inner scheme is distributedly implementable, but no provably convergent single-loop distributed algorithm is developed.This remains an explicit scope boundary of the algorithmic development.