A Generalized Alternating Linearization Bundle Method for Structured Convex Optimization with Inexact First-Order Oracles
In this paper, we consider a class of structured optimization problems whose objective function is the summation of two convex functions: <i>f</i> and <i>h</i>, which are not necessarily differentiable. We focus particularly on the case where the function <i>f</i>...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-04-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/4/91 |
| _version_ | 1797570717960634368 |
|---|---|
| author | Chunming Tang Yanni Li Xiaoxia Dong Bo He |
| author_facet | Chunming Tang Yanni Li Xiaoxia Dong Bo He |
| author_sort | Chunming Tang |
| collection | DOAJ |
| description | In this paper, we consider a class of structured optimization problems whose objective function is the summation of two convex functions: <i>f</i> and <i>h</i>, which are not necessarily differentiable. We focus particularly on the case where the function <i>f</i> is general and its exact first-order information (function value and subgradient) may be difficult to obtain, while the function <i>h</i> is relatively simple. We propose a generalized alternating linearization bundle method for solving this class of problems, which can handle inexact first-order information of on-demand accuracy. The inexact information can be very general, which covers various oracles, such as inexact, partially inexact and asymptotically exact oracles, and so forth. At each iteration, the algorithm solves two interrelated subproblems: one aims to find the proximal point of the polyhedron model of <i>f</i> plus the linearization of <i>h</i>; the other aims to find the proximal point of the linearization of <i>f</i> plus <i>h</i>. We establish global convergence of the algorithm under different types of inexactness. Finally, some preliminary numerical results on a set of two-stage stochastic linear programming problems show that our method is very encouraging. |
| first_indexed | 2024-03-10T20:29:17Z |
| format | Article |
| id | doaj.art-b1ce32f581bc4c68a1f92483e67ee324 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T20:29:17Z |
| publishDate | 2020-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-b1ce32f581bc4c68a1f92483e67ee3242023-11-19T21:32:33ZengMDPI AGAlgorithms1999-48932020-04-011349110.3390/a13040091A Generalized Alternating Linearization Bundle Method for Structured Convex Optimization with Inexact First-Order OraclesChunming Tang0Yanni Li1Xiaoxia Dong2Bo He3College of Mathematics and Information Science, Guangxi University, Nanning 540004, ChinaCollege of Mathematics and Information Science, Guangxi University, Nanning 540004, ChinaCollege of Mathematics and Information Science, Guangxi University, Nanning 540004, ChinaCollege of Mathematics and Information Science, Guangxi University, Nanning 540004, ChinaIn this paper, we consider a class of structured optimization problems whose objective function is the summation of two convex functions: <i>f</i> and <i>h</i>, which are not necessarily differentiable. We focus particularly on the case where the function <i>f</i> is general and its exact first-order information (function value and subgradient) may be difficult to obtain, while the function <i>h</i> is relatively simple. We propose a generalized alternating linearization bundle method for solving this class of problems, which can handle inexact first-order information of on-demand accuracy. The inexact information can be very general, which covers various oracles, such as inexact, partially inexact and asymptotically exact oracles, and so forth. At each iteration, the algorithm solves two interrelated subproblems: one aims to find the proximal point of the polyhedron model of <i>f</i> plus the linearization of <i>h</i>; the other aims to find the proximal point of the linearization of <i>f</i> plus <i>h</i>. We establish global convergence of the algorithm under different types of inexactness. Finally, some preliminary numerical results on a set of two-stage stochastic linear programming problems show that our method is very encouraging.https://www.mdpi.com/1999-4893/13/4/91nonsmooth convex optimizationbundle methodalternating linearizationon-demand accuraryglobal convergence |
| spellingShingle | Chunming Tang Yanni Li Xiaoxia Dong Bo He A Generalized Alternating Linearization Bundle Method for Structured Convex Optimization with Inexact First-Order Oracles Algorithms nonsmooth convex optimization bundle method alternating linearization on-demand accurary global convergence |
| title | A Generalized Alternating Linearization Bundle Method for Structured Convex Optimization with Inexact First-Order Oracles |
| title_full | A Generalized Alternating Linearization Bundle Method for Structured Convex Optimization with Inexact First-Order Oracles |
| title_fullStr | A Generalized Alternating Linearization Bundle Method for Structured Convex Optimization with Inexact First-Order Oracles |
| title_full_unstemmed | A Generalized Alternating Linearization Bundle Method for Structured Convex Optimization with Inexact First-Order Oracles |
| title_short | A Generalized Alternating Linearization Bundle Method for Structured Convex Optimization with Inexact First-Order Oracles |
| title_sort | generalized alternating linearization bundle method for structured convex optimization with inexact first order oracles |
| topic | nonsmooth convex optimization bundle method alternating linearization on-demand accurary global convergence |
| url | https://www.mdpi.com/1999-4893/13/4/91 |
| work_keys_str_mv | AT chunmingtang ageneralizedalternatinglinearizationbundlemethodforstructuredconvexoptimizationwithinexactfirstorderoracles AT yannili ageneralizedalternatinglinearizationbundlemethodforstructuredconvexoptimizationwithinexactfirstorderoracles AT xiaoxiadong ageneralizedalternatinglinearizationbundlemethodforstructuredconvexoptimizationwithinexactfirstorderoracles AT bohe ageneralizedalternatinglinearizationbundlemethodforstructuredconvexoptimizationwithinexactfirstorderoracles AT chunmingtang generalizedalternatinglinearizationbundlemethodforstructuredconvexoptimizationwithinexactfirstorderoracles AT yannili generalizedalternatinglinearizationbundlemethodforstructuredconvexoptimizationwithinexactfirstorderoracles AT xiaoxiadong generalizedalternatinglinearizationbundlemethodforstructuredconvexoptimizationwithinexactfirstorderoracles AT bohe generalizedalternatinglinearizationbundlemethodforstructuredconvexoptimizationwithinexactfirstorderoracles |