Stochastic halfspace approximation method for convex optimization with nonsmooth functional constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929613005914112 |
|---|---|
| author | Singh, Nitesh Kumar Necoara, Ion |
| author_facet | Singh, Nitesh Kumar Necoara, Ion |
| contents | In this work, we consider convex optimization problems with smooth objective function and nonsmooth functional constraints. We propose a new stochastic gradient algorithm, called Stochastic Halfspace Approximation Method (SHAM), to solve this problem, where at each iteration we first take a gradient step for the objective function and then we perform a projection step onto one halfspace approximation of a randomly chosen constraint. We propose various strategies to create this stochastic halfspace approximation and we provide a unified convergence analysis that yields new convergence rates for SHAM algorithm in both optimality and feasibility criteria evaluated at some average point. In particular, we derive convergence rates of order $\mathcal{O} (1/\sqrt{k})$, when the objective function is only convex, and $\mathcal{O} (1/k)$ when the objective function is strongly convex. The efficiency of SHAM is illustrated through detailed numerical simulations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_02338 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Stochastic halfspace approximation method for convex optimization with nonsmooth functional constraints Singh, Nitesh Kumar Necoara, Ion Optimization and Control In this work, we consider convex optimization problems with smooth objective function and nonsmooth functional constraints. We propose a new stochastic gradient algorithm, called Stochastic Halfspace Approximation Method (SHAM), to solve this problem, where at each iteration we first take a gradient step for the objective function and then we perform a projection step onto one halfspace approximation of a randomly chosen constraint. We propose various strategies to create this stochastic halfspace approximation and we provide a unified convergence analysis that yields new convergence rates for SHAM algorithm in both optimality and feasibility criteria evaluated at some average point. In particular, we derive convergence rates of order $\mathcal{O} (1/\sqrt{k})$, when the objective function is only convex, and $\mathcal{O} (1/k)$ when the objective function is strongly convex. The efficiency of SHAM is illustrated through detailed numerical simulations. |
| title | Stochastic halfspace approximation method for convex optimization with nonsmooth functional constraints |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2412.02338 |