检索结果-内蒙古大学图书馆

first-order algorithms FOR A CLASS OF FRACTIONAL OPTIMIZATION PROBLEMS

SIAM JOURNAL ON OPTIMIZATION 2022年第1期32卷 100-129页

作者： Zhang, Na Li, Qia South China Agr Univ Coll Math & Informat Dept Appl Math Guangzhou 510642 Peoples R China Sun Yat Sen Univ Sch Comp Sci & Engn Guangdong Prov Key Lab Computat Sci Guangzhou 510275 Peoples R China

In this paper, we consider a class of single-ratio fractional minimization problems, in which the numerator of the objective is the sum of a nonsmooth nonconvex function and a smooth nonconvex function while the denominator is a nonsmooth convex function. In this work, we first derive its first-order necessary optimality condition, by using the first-order operators of the three functions involved. Then we develop first-order algorithms, namely, the proximity-gradientsubgradient algorithm (PGSA), PGSA with monotone line search (PGSA ML), and PGSA with nonmonotone line search (PGSA NL). It is shown that any accumulation point of the sequence generated by them is a critical point of the problem under mild assumptions. Moreover, we establish global convergence of the sequence generated by PGSA or PGSA ML and analyze its convergence rate, by further assuming the local Lipschitz continuity of the nonsmooth function in the numerator, the smoothness of the denominator, and the Kurdyka--\Lojasiewicz (KL) property of the objective. The proposed algorithms are applied to the sparse generalized eigenvalue problem associated with a pair of symmetric positive semidefinite matrices, and the corresponding convergence results are obtained according to their general convergence theorems. We perform some preliminary numerical experiments to demonstrate the efficiency of the proposed algorithms.

关键词： fractional optimization first-order algorithms proximity algorithms sparse generalized eigenvalue problem KL property

来源：评论

学校读者我要写书评

暂无评论

first-order algorithms for Convex Optimization with Nonseparable Objective and Coupled Constraints

引用

Journal of the Operations Research Society of China 2017年第2期5卷 131-159页

作者： Xiang Gao Shu-Zhong Zhang Department of Industrial and Systems Engineering University of MinnesotaMinneapolisMN 55455USA

In this paper,we consider a block-structured convex optimization model,where in the objective the block variables are nonseparable and they are further linearly coupled in the *** the 2-block case,we propose a number of first-order algorithms to solve this ***,the alternating direction method of multipliers(ADMM)is extended,assuming that it is easy to optimize the augmented Lagrangian function with one block of variables at each time while fixing the other *** prove that O(1/t)iteration complexity bound holds under suitable conditions,where t is the number of *** the subroutines of the ADMM cannot be implemented,then we propose new alternative algorithms to be called alternating proximal gradient method of multipliers,alternating gradient projection method of multipliers,and the hybrids *** suitable conditions,the O(1/t)iteration complexity bound is shown to hold for all the newly proposed ***,we extend the analysis for the ADMM to the general multi-block case.

关键词： first-order algorithms ADMM Proximal gradient method Convex optimization Iteration complexity

来源：评论

学校读者我要写书评

暂无评论

Tradeoffs Between Convergence Rate and Noise Amplification for Momentum-Based Accelerated Optimization algorithms

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2025年第2期70卷 889-904页

作者： Mohammadi, Hesameddin Razaviyayn, Meisam Jovanovic, Mihailo R. Univ Southern Calif Ming Hsieh Dept Elect & Comp Engn Los Angeles CA 90089 USA Univ Southern Calif Daniel J Epstein Dept Ind & Syst Engn Los Angeles CA 90089 USA

In this article, we study momentum-based first-order optimization algorithms in which the iterations utilize information from the two previous steps and are subject to an additive white noise. This setup uses noise to account for uncertainty in either gradient evaluation or iteration updates, and it includes Polyak's heavy-ball and Nesterov's accelerated methods as special cases. For strongly convex quadratic problems, we use the steady-state variance of the error in the optimization variable to quantify noise amplification and identify fundamental stochastic performance tradeoffs. Our approach utilizes the Jury stability criterion to provide a novel geometric characterization of conditions for linear convergence, and it reveals the relation between the noise amplification and convergence rate as well as their dependence on the condition number and the constant algorithmic parameters. This geometric insight leads to simple alternative proofs of standard convergence results and allows us to establish "uncertainty principle" of strongly convex optimization: for the two-step momentum method with linear convergence rate, the lower bound on the product between the settling time and noise amplification scales quadratically with the condition number. Our analysis also identifies a key difference between the gradient and iterate noise models: while the amplification of gradient noise can be made arbitrarily small by sufficiently decelerating the algorithm, the best achievable variance for the iterate noise model increases linearly with the settling time in the decelerating regime. Finally, we introduce two parameterized families of algorithms that strike a balance between noise amplification and settling time while preserving orderwise Pareto optimality for both noise models.

关键词： Noise Convergence Optimization Stochastic processes Steady-state Uncertainty Heuristic algorithms Convergence rate convex optimization first-order algorithms heavy-ball method Nesterov's accelerated algorithm noise amplification performance tradeoffs settling time

来源：评论

学校读者我要写书评

暂无评论

Exterior-Point Optimization for Sparse and Low-Rank Optimization

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2024年第2期202卷 795-833页

作者： Gupta, Shuvomoy Das Stellato, Bartolomeo Van Parys, Bart P. G. MIT Operat Res Ctr Cambridge MA 02139 USA Princeton Univ Dept Operat Res & Financial Engn Princeton NJ 08544 USA MIT Sloan Sch Management Cambridge MA 02139 USA

Many problems of substantial current interest in machine learning, statistics, and data science can be formulated as sparse and low-rank optimization problems. In this paper, we present the nonconvex exterior-point optimization solver (NExOS)-a first-order algorithm tailored to sparse and low-rank optimization problems. We consider the problem of minimizing a convex function over a nonconvex constraint set, where the set can be decomposed as the intersection of a compact convex set and a nonconvex set involving sparse or low-rank constraints. Unlike the convex relaxation approaches, NExOS finds a locally optimal point of the original problem by solving a sequence of penalized problems with strictly decreasing penalty parameters by exploiting the nonconvex geometry. NExOS solves each penalized problem by applying a first-order algorithm, which converges linearly to a local minimum of the corresponding penalized formulation under regularity conditions. Furthermore, the local minima of the penalized problems converge to a local minimum of the original problem as the penalty parameter goes to zero. We then implement and test NExOS on many instances from a wide variety of sparse and low-rank optimization problems, empirically demonstrating that our algorithm outperforms specialized methods.

关键词： Nonconvex optimization Sparse optimization Low-rank optimization first-order algorithms

来源：评论

学校读者我要写书评

暂无评论

GENERALIZING THE OPTIMIZED GRADIENT METHOD FOR SMOOTH CONVEX MINIMIZATION

引用

SIAM JOURNAL ON OPTIMIZATION 2018年第2期28卷 1920-1950页

作者： Kim, Donghwan Fessler, Jeffrey A. Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

This paper generalizes the optimized gradient method (OGM) [Y. Drori and M. Teboulle, Math. Program., 145 (2014), pp. 451-482], [D. Kim and J. A. Fessler, Math. Program., 159 (2016), pp. 81-107], [D. Kim and J. A. Fessler, J. Optim. Theory Appl., 172 (2017), pp. 187205] that achieves the optimal worst-case cost function bound of first-order methods for smooth convex minimization [Y. Drori, J. Complexity, 39 (2017), pp. 1-16]. Specifically, this paper studies a generalized formulation of OGM and analyzes its worst-case rates in terms of both the function value and the norm of the function gradient. This paper also develops a new algorithm called OGM-OG that is in the generalized family of OGM and that has the best known analytical worst-case bound with rate O(1/N-1.5) on the decrease of the gradient norm among fixed-step first-order methods. This paper also proves that Nesterov's fast gradient method [Y. Nesterov, Dokl. Akad. Nauk. USSR, 269 (1983), pp. 543-547], [Y. Nesterov, Math. Program., 103 (2005), pp. 127-152] has an O(1/N-1.5) worst-case gradient norm rate but with constant larger than OGM-OG. The proof is based on the worst-case analysis called the Performance Estimation Problem in [Y. Drori and M. Teboulle, Math. Program., 145 (2014), pp. 451-482].

关键词： first-order algorithms gradient methods smooth convex minimization worst-case performance analysis

来源：评论

学校读者我要写书评

暂无评论

ANOTHER LOOK AT THE FAST ITERATIVE SHRINKAGE/THRESHOLDING ALGORITHM (FISTA)

引用

SIAM JOURNAL ON OPTIMIZATION 2018年第1期28卷 223-250页

作者： Kim, Donghwan Fessler, Jeffrey A. Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

This paper provides a new way of developing the fast iterative shrinkage/thresholding algorithm (FISTA) [A. Beck and M. Teboulle, SIAM T. Imaging Sci., 2 (2009), pp. 183-202] that is widely used for minimizing composite convex functions with a nonsmooth term such as the l(1) regularizer. In particular, this paper shows that FISTA corresponds to an optimized approach to accelerating the proximal gradient method with respect to a worst-case bound of the cost function. This paper then proposes a new algorithm that is derived by instead optimizing the step coefficients of the proximal gradient method with respect to a worst-case bound of the composite gradient mapping. The proof is based on the worst-case analysis called the performance estimation problem in [Y. Drori and M. Teboulle, Math. Program., 145 (2014), pp. 451-482].

关键词： first-order algorithms proximal gradient methods convex minimization worst-case performance analysis

来源：评论

学校读者我要写书评

暂无评论

INTERPOLATION CONDITIONS FOR LINEAR OPERATORS AND APPLICATIONS TO PERFORMANCE ESTIMATION PROBLEMS*

引用

SIAM JOURNAL ON OPTIMIZATION 2024年第3期34卷 3033-3063页

作者： Bousselmi, Nizar Hendrickx, Julien m. Glineur, Francois UCLouvain ICTEAM Louvain La Neuve Belgium UCLouvain CORE Louvain LaNeuve Belgium

The performance estimation problem methodology makes it possible to determine the exact worst-case performance of an optimization method. In this work, we generalize this framework to first-order methods involving linear operators. This extension requires an explicit formulation of interpolation conditions for those linear operators. We consider the class of linear operators M : x H- Mx, where matrix M has bounded singular values, and the class of linear operators, where M is symmetric and has bounded eigenvalues. We describe interpolation conditions for these classes, i.e., necessary and sufficient conditions that, given a list of pairs {(xi, yi)}, characterize the existence of a linear operator mapping xito yifor all i. Using these conditions, we first identify the exact worst-case behavior of the gradient method applied to the composed objective h \circ M, and observe that it always corresponds to M being a scaling operator. We then investigate the Chambolle-Pock method applied to f + g \circ M, and improve the existing analysis to obtain a proof of the exact convergence rate of the primal-dual gap. In addition, we study how this method behaves on Lipschitz convex functions, and obtain a numerical convergence rate for the primal accuracy of the last iterate. We also show numerically that averaging iterates is beneficial in this setting.

关键词： first-order algorithms performance estimation exact convergence rates interpola- tion conditions linear operators primal-dual algorithms quadratic functions

来源：评论

学校读者我要写书评

暂无评论

Optimized first-order methods for smooth convex minimization

引用

MATHEMATICAL PROGRAMMING 2016年第1-2期159卷 81-107页

作者： Kim, Donghwan Fessler, Jeffrey A. Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

We introduce new optimized first-order methods for smooth unconstrained convex minimization. Drori and Teboulle (Math Program 145(1-2):451-482, 2014. doi: 10.1007/s10107-013-0653-0"10.1007/s10107-013-0653-0" TargetType=) recently described a numerical method for computing the N-iteration optimal step coefficients in a class of first-order algorithms that includes gradient methods, heavy-ball methods (Polyak in USSR Comput Math Math Phys 4(5):1-17, 1964. doi: 10.1016/0041-5553(64)90137-510.1016/0041-5553(64)90137-5" TargetType="DOI), and Nesterov's fast gradient methods (Nesterov in Sov Math Dokl 27(2):372-376, 1983;Math Program 103(1):127-152, 2005. doi: 10.1007/s10107-004-0552-510.1007/s10107-004-0552-5" TargetType=). However, the numerical method in Drori and Teboulle (2014) is computationally expensive for large N, and the corresponding numerically optimized first-order algorithm in Drori and Teboulle (2014) requires impractical memory and computation for large-scale optimization problems. In this paper, we propose optimized first-order algorithms that achieve a convergence bound that is two times smaller than for Nesterov's fast gradient methods;our bound is found analytically and refines the numerical bound in Drori and Teboulle (2014). Furthermore, the proposed optimized first-order methods have efficient forms that are remarkably similar to Nesterov's fast gradient methods.

关键词： first-order algorithms Convergence bound Smooth convex minimization Fast gradient methods

来源：评论

学校读者我要写书评

暂无评论

A first-order PRIMAL-DUAL ALGORITHM WITH LINESEARCH

引用

SIAM JOURNAL ON OPTIMIZATION 2018年第1期28卷 411-432页

作者： Malitsky, Yura Pock, Thomas Graz Univ Technol Inst Comp Graph & Vis A-8010 Graz Austria

The paper proposes a linesearch for a primal-dual method. Each iteration of the linesearch requires an update of only the dual (or primal) variable. For many problems, in particular for regularized least squares, the linesearch does not require any additional matrix-vector multiplications. We prove convergence of the proposed method under standard assumptions. We also show an ergodic O(1/N) rate of convergence for our method. In the case when one or both of the prox-functions are strongly convex, we modify our basic method to get a better convergence rate. Finally, we propose a linesearch for a saddle-point problem with an additional smooth term. Several numerical experiments confirm the efficiency of our proposed methods.

关键词： saddle-point problems first-order algorithms primal-dual algorithms linesearch convergence rates backtracking

来源：评论

学校读者我要写书评

暂无评论

On the Convergence Analysis of the Optimized Gradient Method

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2017年第1期172卷 187-205页

作者： Kim, Donghwan Fessler, Jeffrey A. Univ Michigan Ann Arbor MI 48109 USA

This paper considers the problem of unconstrained minimization of smooth convex functions having Lipschitz continuous gradients with known Lipschitz constant. We recently proposed the optimized gradient method for this problem and showed that it has a worst-case convergence bound for the cost function decrease that is twice as small as that of Nesterov's fast gradient method, yet has a similarly efficient practical implementation. Drori showed recently that the optimized gradient method has optimal complexity for the cost function decrease over the general class of first-order methods. This optimality makes it important to study fully the convergence properties of the optimized gradient method. The previous worst-case convergence bound for the optimized gradient method was derived for only the last iterate of a secondary sequence. This paper provides an analytic convergence bound for the primary sequence generated by the optimized gradient method. We then discuss additional convergence properties of the optimized gradient method, including the interesting fact that the optimized gradient method has two types of worst-case functions: a piecewise affine-quadratic function and a quadratic function. These results help complete the theory of an optimal first-order method for smooth convex minimization.

关键词： first-order algorithms Optimized gradient method Convergence bound Smooth convex minimization Worst-case performance analysis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：