On the Convergence of Inexact Projection Primal First-Order Methods for Convex Minimization.
Saved in:
| Title: | On the Convergence of Inexact Projection Primal First-Order Methods for Convex Minimization. |
|---|---|
| Authors: | Patrascu, Andrei, Necoara, Ion |
| Source: | IEEE Transactions on Automatic Control. Oct2018, Vol. 63 Issue 10, p3317-3329. 13p. |
| Subjects: | Stochastic convergence, Robust convex optimization, Mathematical optimization, Predictive control systems, Interior-point methods |
| Abstract: | It is well-known that primal first-order algorithms achieve sublinear (linear) convergence for smooth convex (smooth strongly convex) constrained minimization. However, these methods encounter numerical difficulties when the primal feasible set is complicated, since they require exact projection onto this set. Algorithmic alternatives to convex problems with complicated feasible set are the dual first-order methods. Dual methods are able to handle easily complicated constraints, but they have difficulties in convergence when the norm of the optimal Lagrange multiplier is large, since this norm appears linearly in the convergence estimates of these methods. Moreover, they have typically sublinear convergence rate in an average primal sequence, even when the primal problem has smooth and strongly convex objective function. Motivated by these issues, in this paper, we analyze the convergence of primal first-order methods with inexact projections for solving constrained convex problems with smooth and then strongly convex objective function. In particular, we consider the inexact variants of Projected Gradient and Projected Fast Gradient methods, where instead of computing an exact projection onto the complicated primal feasible set, an approximate projection, not necessarily feasible, is used. We prove that we can still achieve similar convergence rates for these inexact projection first-order algorithms with those given in the exact projection settings, provided that the approximate projection is sufficiently accurate. Our convergence analysis allows us to derive explicitly the accuracy of the inexact projection and the number of iterations we need to perform in order to obtain an approximate solution for our convex problem. Finally, practical performance on random quadratic problems show encouraging results. [ABSTRACT FROM AUTHOR] |
| Copyright of IEEE Transactions on Automatic Control is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 132099165 AccessLevel: 6 PubType: Periodical PubTypeId: serialPeriodical PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: On the Convergence of Inexact Projection Primal First-Order Methods for Convex Minimization. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Patrascu%2C+Andrei%22">Patrascu, Andrei</searchLink><br /><searchLink fieldCode="AR" term="%22Necoara%2C+Ion%22">Necoara, Ion</searchLink> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Automatic+Control%22">IEEE Transactions on Automatic Control</searchLink>. Oct2018, Vol. 63 Issue 10, p3317-3329. 13p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Stochastic+convergence%22">Stochastic convergence</searchLink><br /><searchLink fieldCode="DE" term="%22Robust+convex+optimization%22">Robust convex optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Predictive+control+systems%22">Predictive control systems</searchLink><br /><searchLink fieldCode="DE" term="%22Interior-point+methods%22">Interior-point methods</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: It is well-known that primal first-order algorithms achieve sublinear (linear) convergence for smooth convex (smooth strongly convex) constrained minimization. However, these methods encounter numerical difficulties when the primal feasible set is complicated, since they require exact projection onto this set. Algorithmic alternatives to convex problems with complicated feasible set are the dual first-order methods. Dual methods are able to handle easily complicated constraints, but they have difficulties in convergence when the norm of the optimal Lagrange multiplier is large, since this norm appears linearly in the convergence estimates of these methods. Moreover, they have typically sublinear convergence rate in an average primal sequence, even when the primal problem has smooth and strongly convex objective function. Motivated by these issues, in this paper, we analyze the convergence of primal first-order methods with inexact projections for solving constrained convex problems with smooth and then strongly convex objective function. In particular, we consider the inexact variants of Projected Gradient and Projected Fast Gradient methods, where instead of computing an exact projection onto the complicated primal feasible set, an approximate projection, not necessarily feasible, is used. We prove that we can still achieve similar convergence rates for these inexact projection first-order algorithms with those given in the exact projection settings, provided that the approximate projection is sufficiently accurate. Our convergence analysis allows us to derive explicitly the accuracy of the inexact projection and the number of iterations we need to perform in order to obtain an approximate solution for our convex problem. Finally, practical performance on random quadratic problems show encouraging results. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of IEEE Transactions on Automatic Control is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=132099165 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1109/TAC.2018.2805727 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 13 StartPage: 3317 Subjects: – SubjectFull: Stochastic convergence Type: general – SubjectFull: Robust convex optimization Type: general – SubjectFull: Mathematical optimization Type: general – SubjectFull: Predictive control systems Type: general – SubjectFull: Interior-point methods Type: general Titles: – TitleFull: On the Convergence of Inexact Projection Primal First-Order Methods for Convex Minimization. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Patrascu, Andrei – PersonEntity: Name: NameFull: Necoara, Ion IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 10 Text: Oct2018 Type: published Y: 2018 Identifiers: – Type: issn-print Value: 00189286 Numbering: – Type: volume Value: 63 – Type: issue Value: 10 Titles: – TitleFull: IEEE Transactions on Automatic Control Type: main |
| ResultId | 1 |
