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

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2023年第2期84卷 295-318页

作者： Bello-Cruz, Yunier Goncalves, Max L. N. Krislock, Nathan Northern Illinois Univ Dept Math Sci De Kalb IL 60115 USA Univ Fed Goias IME BR-74001970 Goiania Go Brazil

The fast iterative shrinkage/thresholding algorithm (FISTA) is one of the most popular first-order iterations for minimizing the sum of two convex functions. FISTA is known to improve the complexity of the classical proximal gradient method (PGM) from O(k(-1)) to the optimal complexity O(k(-2)) in terms of the sequence of the functional values. When the evaluation of the proximal operator is hard, inexact versions of FISTA might be used to solve the problem. In this paper, we proposed an inexact version of FISTA by solving the proximal subproblem inexactly using a relative error criterion instead of exogenous and diminishing error rules. The introduced relative error rule in the FISTA iteration is related to the progress of the algorithm at each step and does not increase the computational burden per iteration. Moreover, the proposed algorithm recovers the same optimal convergence rate as FISTA. Some numerical experiments are also reported to illustrate the numerical behavior of the relative inexact method when compared with FISTA under an absolute error criterion.

关键词： FISTA Inexact accelerated proximal gradient method iteration complexity Nonsmooth and convex optimization problems Proximal gradient method Relative error rule

来源：评论

学校读者我要写书评

暂无评论

Accelerated inexact composite gradient methods for nonconvex spectral optimization problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2022年第3期82卷 673-715页

作者： Kong, Weiwei Monteiro, Renato D. C. Oak Ridge Natl Lab Comp Sci & Math Div Oak Ridge TN 37830 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

This paper presents two inexact composite gradient methods, one inner accelerated and another doubly accelerated, for solving a class of nonconvex spectral composite optimization problems. More specifically, the objective function for these problems is of the form f(1) + f(2) + h, where f(1) and f(2) are differentiable nonconvex matrix functions with Lipschitz continuous gradients, h is a proper closed convex matrix function, and both f(2) and h can be expressed as functions that operate on the singular values of their inputs. The methods essentially use an accelerated composite gradient method to solve a sequence of proximal subproblems involving the linear approximation of f(1) and the singular value functions underlying f(2) and h. Unlike other composite gradient-based methods, the proposed methods take advantage of both the composite and spectral structure underlying the objective function in order to efficiently generate their solutions. Numerical experiments are presented to demonstrate the practicality of these methods on a set of real-world and randomly generated spectral optimization problems.

关键词： Composite nonconvex problem iteration complexity Inexact composite gradient method First-order accelerated gradient method Spectral optimization

来源：评论

学校读者我要写书评

暂无评论

A Strictly Contractive Peaceman-Rachford Splitting Method with Logarithmic-Quadratic Proximal Regularization for Convex Programming

引用

MATHEMATICS OF OPERATIONS RESEARCH 2015年第4期40卷 842-858页

作者： Li, Min Yuan, Xiaoming Southeast Univ Sch Econ & Management Nanjing 210096 Jiangsu Peoples R China Hong Kong Baptist Univ Dept Math Hong Kong Hong Kong Peoples R China

Recently, a strictly contractive Peaceman-Rachford splitting method (PRSM) was proposed for a separable convex minimization model whose variables are subject to some linear constraints and two additional generic constraints. In general, the strictly contractive PRSM requires to solve two constrained minimization subproblems at each iteration. In this paper, we consider the case where the additional constraints on variables are positive orthants and apply the well-developed logarithmic-quadratic proximal (LQP) regularization to regularize the subproblems of the strictly contractive PRSM. A new algorithm in combination with the strictly contractive PRSM and the LQP regularization is thus proposed. The new algorithm only needs to solve two unconstrained subproblems at each iteration. An inexact version allowing the unconstrained subproblems to be solved approximately subject to certain inexactness criterion is also studied. We prove the global convergence and establish a worst-case convergence rate measured by the iteration complexity for both the exact and inexact versions of the new algorithm.

关键词： convex programming Peaceman-Rachford splitting method logarithmic-quadratic proximal regularization convergence rate iteration complexity

来源：评论

学校读者我要写书评

暂无评论

A GLOBAL DUAL ERROR BOUND AND ITS APPLICATION TO THE ANALYSIS OF LINEARLY CONSTRAINED NONCONVEX OPTIMIZATION

引用

SIAM JOURNAL ON OPTIMIZATION 2022年第3期32卷 2319-2346页

作者： Zhang, Jiawei Luo, Zhi-Quan Chinese Univ Hong Kong Shenzhen Res Inst Big Data Shenzhen Peoples R China

Error bound analysis, which estimates the distance of a point to the solution set of an optimization problem4 using the optimality residual, is a powerful tool for the analysis of first-order optimization algorithms. In this paper, we use global error bound analysis to study the iteration complexity of a first-order algorithm for a linearly constrained nonconvex minimization problem. We develop a global dual error bound analysis for a regularized version of this nonconvex problem by using a novel "decomposition" technique. Equipped with this global dual error bound, we prove that a suitably designed primal-dual first-order method can generate an epsilon-stationary solution of the linearly constrained nonconvex minimization problem within O(1/epsilon(2)) iterations, which is the best known iteration complexity for this class of nonconvex problems. The iteration complexity of our algorithm for finding an epsilon-stationary solution is O(1/epsilon(2)), which improves the best known complexity of O(1/epsilon(3)) for the problem under consideration. Furthermore, when the objective function is quadratic, we establish the linear convergence of the algorithm. Our proof is based on a new potential function and a novel use of error bounds.

关键词： nonconvex primal dual iteration complexity first order global error bound

来源：评论

学校读者我要写书评

暂无评论

AN ACCELERATED INEXACT PROXIMAL POINT METHOD FOR SOLVING NONCONVEX-CONCAVE MIN-MAX PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2021年第4期31卷 2558-2585页

作者： Kong, Weiwei Monteiro, Renato D. C. Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

This paper presents smoothing schemes for obtaining approximate stationary points of unconstrained or linearly constrained composite nonconvex-concave min-max (and hence non smooth) problems by applying well-known algorithms to composite smooth approximations of the original problems. More specifically, in the unconstrained (resp., constrained) case, approximate stationary points of the original problem are obtained by applying, to its composite smooth approximation, an accelerated inexact proximal point (resp., quadratic penalty) method presented in a previous paper by the authors. iteration complexity bounds for both smoothing schemes are also established. Finally, numerical results are given to demonstrate the efficiency of the unconstrained smoothing scheme.

关键词： quadratic penalty method composite nonconvex problem iteration complexity inexact proximal point method first-order accelerated gradient method minimax problem

来源：评论

学校读者我要写书评

暂无评论

DECENTRALIZED GRADIENT DESCENT MAXIMIZATION METHOD FOR COMPOSITE NONCONVEX STRONGLY-CONCAVE MINIMAX PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2024年第1期34卷 1006-1044页

作者： Xu, Yangyang Rensselaer Polytech Inst Dept Math Sci Troy NY 12180 USA

Minimax problems have recently attracted a lot of research interests. A few efforts have been made to solve decentralized nonconvex strongly -concave (NCSC) minimax-structured optimization;however, all of them focus on smooth problems with at most a constraint on the maximization variable. In this paper, we make the first attempt on solving composite NCSC minimax problems that can have convex nonsmooth terms on both minimization and maximization variables. Our algorithm is designed based on a novel reformulation of the decentralized minimax problem that introduces a multiplier to absorb the dual consensus constraint. The removal of dual consensus constraint enables the most aggressive (i.e., local maximization instead of a gradient ascent step) dual update that leads to the benefit of taking a larger primal stepsize and better complexity results. In addition, the decoupling of the nonsmoothness and consensus on the dual variable eases the analysis of a decentralized algorithm;thus our reformulation creates a new way for interested researchers to design new (and possibly more efficient) decentralized methods on solving NCSC minimax problems. We show a global convergence result of the proposed algorithm and an iteration complexity result to produce a (near) stationary point of the reformulation. Moreover, a relation is established between the (near) stationarities of the reformulation and the original formulation. With this relation, we show that when the dual regularizer is smooth, our algorithm can have lower complexity results (with reduced dependence on a condition number) than existing ones to produce a near -stationary point of the original formulation. Numerical experiments are conducted on a distributionally robust logistic regression to demonstrate the performance of the proposed algorithm.

关键词： composite minimax problem nonconvex strongly-concave decentralized algorithm iteration complexity

来源：评论

学校读者我要写书评

暂无评论

An approximation proximal gradient algorithm for nonconvex-linear minimax problems with nonconvex nonsmooth terms

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第1期90卷 73-92页

作者： He, Jiefei Zhang, Huiling Xu, Zi Shanghai Univ Coll Sci Dept Math Shanghai 200444 Peoples R China Shanghai Univ Newtouch Ctr Math Shanghai 200444 Peoples R China

Nonconvex minimax problems have attracted significant attention in machine learning, wireless communication and many other fields. In this paper, we propose an efficient approximation proximal gradient algorithm for solving a class of nonsmooth nonconvex-linear minimax problems with a nonconvex nonsmooth term, and the number of iteration to find an epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-stationary point is upper bounded by O(epsilon-3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}}(\varepsilon <^>{-3})$$\end{document}. Some numerical results on one-bit precoding problem in massive MIMO system and a distributed non-convex optimization problem demonstrate the effectiveness of the proposed algorithm.

关键词： Nonconvex-linear minimax problem Nonsmooth problem iteration complexity Approximation proximal gradient algorithm

来源：评论

学校读者我要写书评

暂无评论

PROXIMAL GRADIENT METHOD FOR NONSMOOTH OPTIMIZATION OVER THE STIEFEL MANIFOLD

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第1期30卷 210-239页

作者： Chen, Shixiang Ma, Shiqian So, Anthony Man-Cho Zhang, Tong Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA Univ Calif Davis Dept Math Davis CA 95616 USA Chinese Univ Hong Kong Dept Syst Engn & Engn Management Sha Tin Hong Kong Peoples R China Chinese Univ Hong Kong CUHK BGI Innovat Inst Trans Sha Tin Hong Kong Peoples R China Hong Kong Univ Sci & Technol Clear Water Bay Hong Kong Peoples R China

We consider optimization problems over the Stiefel manifold whose objective function is the summation of a smooth function and a nonsmooth function. Existing methods for solving this kind of problem can be classified into three categories. Algorithms in the first category rely on information of the subgradients of the objective function and thus tend to converge slowly in practice. Algorithms in the second category are proximal point algorithms, which involve subproblems that can be as difficult as the original problem. Algorithms in the third category are based on operator-splitting techniques, but they usually lack rigorous convergence guarantees. In this paper, we propose a retraction-based proximal gradient method for solving this class of problems. We prove that the proposed method globally converges to a stationary point. iteration complexity for obtaining an epsilon-stationary solution is also analyzed. Numerical results on solving sparse PCA and compressed modes problems are reported to demonstrate the advantages of the proposed method.

关键词： manifold optimization Stiefel manifold nonsmooth proximal gradient method iteration complexity semismooth Newton method sparse PCA compressed modes

来源：评论

学校读者我要写书评

暂无评论

THE CYCLIC BLOCK CONDITIONAL GRADIENT METHOD FOR CONVEX OPTIMIZATION PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2015年第4期25卷 2024-2049页

作者： Beck, Amir Pauwels, Edouard Sabach, Shoham Technion Israel Inst Technol Fac Ind Engn & Management IL-3200003 Haifa Israel

In this paper we study the convex problem of optimizing the sum of a smooth function and a compactly supported nonsmooth term with a specific separable form. We analyze the block version of the generalized conditional gradient method when the blocks are chosen in a cyclic order. A global sublinear rate of convergence is established for two different stepsize strategies commonly used in this class of methods. Numerical comparisons of the proposed method to both the classical conditional gradient algorithm and its random block version demonstrate the effectiveness of the cyclic block update rule.

关键词： conditional gradient cyclic block decomposition iteration complexity linear oracle nonsmooth convex minimization support vector machine

来源：评论

学校读者我要写书评

暂无评论

A flexible coordinate descent method

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2018年第2期70卷 351-394页

作者： Fountoulakis, Kimon Tappenden, Rachael Univ Calif Berkeley Int Comp Sci Inst Dept Stat 1947 Ctr StSte 600 Berkeley CA 94704 USA Univ Canterbury Sch Math & Stat Private Bag Christchurch 8041 New Zealand

We present a novel randomized block coordinate descent method for the minimization of a convex composite objective function. The method uses (approximate) partial second-order (curvature) information, so that the algorithm performance is more robust when applied to highly nonseparable or ill conditioned problems. We call the method Flexible Coordinate Descent (FCD). At each iteration of FCD, a block of coordinates is sampled randomly, a quadratic model is formed about that block and the model is minimized approximately/inexactly to determine the search direction. An inexpensive line search is then employed to ensure a monotonic decrease in the objective function and acceptance of large step sizes. We present several high probability iteration complexity results to show that convergence of FCD is guaranteed theoretically. Finally, we present numerical results on large-scale problems to demonstrate the practical performance of the method.

关键词： Large scale optimization Second-order methods Curvature information Block coordinate descent Nonsmooth problems iteration complexity Randomized

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：