This paper presents a subgradient-based algorithm for constrained nonsmooth convex optimization that does not require projections onto the feasible set. While the well-established Frank–Wolfe algorithm and its variants already avoid projections, they are primarily designed for smooth objective functions. In contrast, our proposed algorithm can handle nonsmooth problems with general convex functional inequality constraints. It achieves an
Nonsmooth Projection-Free Optimization with Functional Constraints
This paper presents a subgradient-based algorithm for constrained nonsmooth
convex optimization that does not require projections onto the feasible set.
While the well-established Frank-Wolfe algorithm and its variants already avoid
projections, they are primarily designed for smooth objective functions. In con-
trast, our proposed algorithm can handle nonsmooth problems with general
convex functional inequality constraints. It achieves an ϵ-suboptimal solution
in O(ϵ^−2) iterations, with each iteration requiring only a single (potentially
inexact) Linear Minimization Oracle (LMO) call and a (possibly inexact) subgra-
dient computation. This performance is consistent with existing lower bounds.
Similar performance is observed when deterministic subgradients are replaced
with stochastic subgradients. In the special case where there are no functional
inequality constraints, our algorithm competes favorably with a recent nonsmooth
projection-free method designed for constraint-free problems. Our approach uti-
lizes a simple separation scheme in conjunction with a new Lagrange multiplier
update rule.
more »
« less
- Award ID(s):
- 1824418
- PAR ID:
- 10494716
- Editor(s):
- arXiv:2311.11180v1
- Publisher / Repository:
- arXiv:2311.11180v1
- Date Published:
- Subject(s) / Keyword(s):
- Projection-free optimization, Frank-Wolfe method, Nonsmooth convex optimization, Stochastic optimization, Functional constraints
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract $$\epsilon $$ $$\mathcal {O}(\epsilon ^{-2})$$ -
The paper proposes and develops a novel inexact gradient method (IGD) for minimizing smooth functions with Lipschitzian gradients. We show that the sequence of gradients generated by IGD converges to zero. The convergence of iterates to stationary points is guaranteed under the Kurdyka- Lojasiewicz property of the objective function with convergence rates depending on the KL exponent. The newly developed IGD is applied to designing two novel gradient-based methods of nonsmooth convex optimization such as the inexact proximal point methods (GIPPM) and the inexact augmented Lagrangian method (GIALM) for convex programs with linear equality constraints. These two methods inherit global convergence properties from IGD and are confirmed by numerical experiments to have practical advantages over some well-known algorithms of nonsmooth convex optimizationmore » « less
-
We consider a class of nonsmooth convex composite optimization problems, where the objective function is given by the sum of a continuously differentiable convex term and a potentially non-differentiable convex regularizer. In [1], the authors introduced the proximal augmented Lagrangian method and derived the resulting continuous-time primal-dual dynamics that converge to the optimal solution. In this paper, we extend these dynamics from continuous to discrete time via the forward Euler discretization. We prove explicit bounds on the exponential convergence rates of our proposed algorithm with a sufficiently small step size. Since a larger step size can improve the convergence speed, we further develop a linear matrix inequality (LMI) condition which can be numerically solved to provide rate certificates with general step size choices. In addition, we prove that a large range of step size values can guarantee exponential convergence. We close the paper by demonstrating the performance of the proposed algorithm via computational experiments.more » « less
-
We develop a unified level-bundle method, called accelerated constrained level-bundle (ACLB) algorithm, for solving constrained convex optimization problems. where the objective and constraint functions can be nonsmooth, weakly smooth, and/or smooth. ACLB employs Nesterov’s accelerated gradient technique, and hence retains the iteration complexity as that of existing bundle-type methods if the objective or one of the constraint functions is nonsmooth. More importantly, ACLB can significantly reduce iteration complexity when the objective and all constraints are (weakly) smooth. In addition, if the objective contains a nonsmooth component which can be written as a specific form of maximum, we show that the iteration complexity of this component can be much lower than that for general nonsmooth objective function. Numerical results demonstrate the effectiveness of the proposed algorithm.more » « less
-
We develop a unified level-bundle method, called accelerated constrained level-bundle (ACLB) algorithm, for solving constrained convex optimization problems. where the objective and constraint functions can be nonsmooth, weakly smooth, and/or smooth. ACLB employs Nesterov’s accelerated gradient technique, and hence retains the iteration complexity as that of existing bundle-type methods if the objective or one of the constraint functions is nonsmooth. More importantly, ACLB can significantly reduce iteration complexity when the objective and all constraints are (weakly) smooth. In addition, if the objective contains a nonsmooth component which can be written as a specific form of maximum, we show that the iteration complexity of this component can be much lower than that for general nonsmooth objective function. Numerical results demonstrate the effectiveness of the proposed algorithm.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Workshop Report:
- The DOI is not currently available.
