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

Perseus: a simple and optimal high-order method for variational inequalities

MATHEMATICAL PROGRAMMING 2025年第1-2期209卷 609-650页

作者： Lin, Tianyi Jordan, Michael I. MIT Lab Informat & Decis Syst LIDS Cambridge MA 02139 USA Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA USA

This paper settles an open and challenging question pertaining to the design of simple and optimal high-order methods for solving smooth and monotone variational inequalities (VIs). A VI involves finding x ⋆is an element of X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x<^>\star \in {\mathcal {X}}$$\end{document} such that ⟨F(x),x-x ⋆⟩>= 0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle F(x), x - x<^>\star \rangle \ge 0$$\end{document} for all x is an element of X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x \in {\mathcal {X}}$$\end{document}. We consider the setting in which F:Rd -> Rd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F: {\mathbb {R}}<^>d \rightarrow {\mathbb {R}}<^>d$$\end{document} is smooth with up to (p-1)th\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(p-1)<^>{\text {th}}$$\end{document}-order derivatives. For p=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$

关键词： Variational inequality Simple and optimal high-order method Acceleration iteration complexity Local superlinear convergence

来源：评论

学校读者我要写书评

暂无评论

Proximal gradient method for convex multiobjective optimization problems without Lipschitz continuous gradients

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2025年第1期91卷 27-66页

作者： Zhao, Xiaopeng Raushan, Ravi Ghosh, Debdas Yao, Jen-Chih Qi, Min Tiangong Univ Sch Math Sci Tianjin 300387 Peoples R China Indian Inst Technol BHU Dept Math Sci Varanasi 221005 India China Med Univ China Med Univ Hosp Res Ctr Interneural Comp Taichung 40447 Taiwan Acad Romanian Scientists Bucharest 50044 Romania

This paper analyzes a proximal gradient method for nondifferentiable convex multiobjective optimization problems, where the components of the objective function are the sum of a proper lower semicontinuous function and a continuously differentiable function. By adopting a typical line search procedure, it is found that without a Lipschitz continuity of the gradients of the smooth part of the objective function, the proposed method is able to generate sequences that converge to weakly Pareto optimal points. The convergence rate of the method is found to be O(1/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(1/k)$$\end{document}. Further, if the smooth component in the objective function is strongly convex, then the convergence rate is O(rk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(r<^>k)$$\end{document} for some r is an element of(0,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r\in (0,1)$$\end{document}. Moreover, in the absence of a strong convexity assumption, we also consider the accelerated version of the proposed approach based on the Nesterov step strategy. We obtain the improved convergence rate of O(1/k2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(1/k<^>2)$$\end{document}, which is measured

关键词： Multiobjective optimization Proximal gradient method Pareto optimality iteration complexity

来源：评论

学校读者我要写书评

暂无评论

An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2025年第2期90卷 557-582页

作者： 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

Stochastic nonconvex minimax problems have attracted wide attention in machine learning, signal processing and many other fields in recent years. In this paper, we propose an accelerated first-order regularized momentum descent ascent algorithm (FORMDA) for solving stochastic nonconvex-concave minimax problems. The iteration complexity of the algorithm is proved to be (O) over tilde(epsilon(-6.5)) to obtain an epsilon-stationary point, which achieves the best-known complexity bound for single-loop algorithms to solve the stochastic nonconvex-concave minimax problems under the stationarity of the objective function.

关键词： Stochastic nonconvex minimax problem Accelerated momentum projection gradient algorithm iteration complexity Machine learning

来源：评论

学校读者我要写书评

暂无评论

Optimal Approximation of Average Reward Markov Decision Processes

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2025年第3期65卷 567-581页

作者： Sapronov, Y. F. Yudin, N. E. Moscow Inst Phys & Technol Dolgoprudnyi 141701 Russia Higher Sch Econ Univ Moscow 109028 Russia Innopolis Univ Innopolis 420500 Russia Russian Acad Sci Inst Informat Transmiss Problems Kharkevich Inst Moscow 127051 Russia Russian Acad Sci Ivannikov Inst Syst Programming Moscow 109004 Russia Russian Acad Sci Fed Res Ctr Informat & Control Moscow 119333 Russia

We continue to develop the concept of studying the epsilon-optimal policy for Average Reward Markov Decision Processes (AMDP) by reducing it to Discounted Markov Decision Processes (DMDP). Existing research often stipulates that the discount factor must not fall below a certain threshold. Typically, this threshold is close to one, and as is well-known, iterative methods used to find the optimal policy for DMDP become less effective as the discount factor approaches this value. Our work distinguishes itself from existing studies by allowing for inaccuracies in solving the empirical Bellman equation. Despite this, we have managed to maintain the sample complexity that aligns with the latest results. We have succeeded in separating the contributions from the inaccuracy of approximating the transition matrix and the residuals in solving the Bellman equation in the upper estimate so that our findings enable us to determine the total complexity of the epsilon-optimal policy analysis for DMDP across any method with a theoretical foundation in iterative complexity.

关键词： Markov decision processes reinforcement learning sample complexity iteration complexity ICOMP2024

来源：评论

学校读者我要写书评

暂无评论

STOCHASTIC NESTED PRIMAL-DUAL METHOD FOR NONCONVEX CONSTRAINED COMPOSITION OPTIMIZATION

引用

MATHEMATICS OF COMPUTATION 2025年第351期94卷 305-358页

作者： Jin, Lingzi Wang, Xiao Hong Kong Polytech Univ Dept Appl Math Kowloon Hong Kong Peoples R China Peng Cheng Lab Shenzhen 518066 Peoples R China

In this paper we study the nonconvex constrained composition optimization, in which the objective contains a composition of two expectedvalue functions whose accurate information is normally expensive to calculate. We propose a STochastic nEsted Primal-dual (STEP) method for such problems. In each iteration, with an auxiliary variable introduced to track the inner layer function values we compute stochastic gradients of the nested function using a subsampling strategy. To alleviate difficulties caused by possibly nonconvex constraints, we construct a stochastic approximation to the linearized augmented Lagrangian function to update the primal variable, which further motivates to update the dual variable in a weighted-average way. Moreover, to better understand the asymptotic dynamics of the update schemes we consider a deterministic continuous-time system from the perspective of ordinary differential equation (ODE). We analyze the Karush-Kuhn-Tucker measure at the output by the STEP method with constant parameters and establish its iteration and sample complexities to find an epsilon-stationary point, ensuring that expected stationarity, feasibility as well as complementary slackness are below accuracy E. To leverage the benefit of the (near) initial feasibility in the STEP method, we propose a two-stage framework incorporating a feasibilityseeking phase, aiming to locate a nearly feasible initial point. Moreover, to enhance the adaptivity of the STEP algorithm, we propose an adaptive variant by adaptively adjusting its parameters, along with a complexity analysis. Numerical results on a risk-averse portfolio optimization problem and an orthogonal nonnegative matrix decomposition reveal the effectiveness of the proposed algorithms.

关键词： Composition nonconvex constraints augmented Lagrangian function stationarity feasibility complementary slackness iteration complexity sample complexity

来源：评论

学校读者我要写书评

暂无评论

On the convergence analysis of a proximal gradient method for multiobjective optimization

引用

TOP 2025年第1期33卷 102-132页

作者： Zhao, Xiaopeng Ghosh, Debdas Qin, Xiaolong Tammer, Christiane Yao, Jen-Chih Tiangong Univ Sch Math Sci Tianjin 300387 Peoples R China Indian Inst Technol BHU Dept Math Sci Varanasi 221005 Uttar Pradesh India Zhejiang Normal Univ Dept Math Jinhua 321004 Peoples R China Martin Luther Univ Halle Wittenberg Dept Math D-06099 Halle Saale Germany China Med Univ China Med Univ Hosp Res Ctr Interneural Comp Taichung 40447 Taiwan Acad Romanian Scientists Bucharest 50044 Romania

We propose a proximal gradient method for unconstrained nondifferentiable multiobjective optimization problems with the objective function being the sum of a proper lower semicontinuous convex function and a continuously differentiable function. We have shown under appropriate assumptions that each accumulation point of the sequence generated by the algorithm is Pareto stationary. Further, when imposing convexity on the smooth component of the objective function, the convergence of the generated iterative sequence to a weak Pareto optimal point of the problem is established. Meanwhile, the convergence rate of the proposed method is analyzed when the smooth component function in the objective function is non-convex (O(1/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(\sqrt{1/k})$$\end{document}), convex (O(1/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(1/k)$$\end{document}), and strongly convex (O(rk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(r<^>k)$$\end{document} for some r is an element of(0,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r\in (0,1)$$\end{document}), respectively, here k is the number of iterations. The performance of the proposed method on a few test problems with an & ell;1\docum

关键词： Multiobjective optimization Proximal gradient method Pareto optimality iteration complexity

来源：评论

学校读者我要写书评

暂无评论

An efficient parametric kernel function of IPMs for Linear optimization problems

引用

RESULTS IN CONTROL AND OPTIMIZATION 2025年 18卷

作者： Houas, Amrane Merahi, Fateh Univ Mohamed Khider Fac Exact Sci Nat & Life Sci Dept Math Lab Appl Math Biskra 07000 Algeria Mustapha Ben Boulaid Batna II Univ Fac Math & Comp Sci Dept Stat & Data Sci Batna Algeria

In this manuscript, we examine linear optimization problems formulated in the standard format. A novel kernel function is employed to devise a new interior-point algorithm for these problems. The proposed method reduces the number of iterations required for the Netlib test problems. The outcomes are subsequently derived using the self-dual embedding technique. The application of the kernel function facilitates the determination of search directions and the quantification of the distance between the current iteration and the mu-center of the algorithm. Incorporating specific lemmas tailored to this methodology is essential for establishing the optimal limit on iteration complexity. The methodology delineated in the work of K. Roos provides the framework for our investigation. Finally, numerical instances were examined to elucidate the theoretical findings and demonstrate the efficacy of the proposed innovative approach.

关键词： Interior point algorithm Kernel function Linear optimization Large-update iteration number iteration complexity

来源：评论

学校读者我要写书评

暂无评论

Majorization-minimization-based Levenberg-Marquardt method for constrained nonlinear least squares

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2023年第3期84卷 833-874页

作者： Marumo, Naoki Okuno, Takayuki Takeda, Akiko Univ Tokyo Grad Sch Informat Sci & Technol Tokyo Japan Seikei Univ Fac Sci & Technol Tokyo Japan RIKEN Ctr Adv Intelligence Project Tokyo Japan

A new Levenberg-Marquardt (LM) method for solving nonlinear least squares problems with convex constraints is described. Various versions of the LM method have been proposed, their main differences being in the choice of a damping parameter. In this paper, we propose a new rule for updating the parameter so as to achieve both global and local convergence even under the presence of a convex constraint set. The key to our results is a new perspective of the LM method from majorization-minimization methods. Specifically, we show that if the damping parameter is set in a specific way, the objective function of the standard subproblem in LM methods becomes an upper bound on the original objective function under certain standard assumptions. Our method solves a sequence of the subproblems approximately using an (accelerated) projected gradient method. It finds an epsilon-stationary point after O(epsilon(-2)) computation and achieves local quadratic convergence for zero-residual problems under a local error bound condition. Numerical results on compressed sensing and matrix factorization show that our method converges faster in many cases than exist-ing methods.

关键词： Nonconvex optimization Constrained optimization Nonlinear least squares Levenberg-Marquardt method iteration complexity Local quadratic convergence

来源：评论

学校读者我要写书评

暂无评论

OPTIMALITY CONDITIONS AND NUMERICAL ALGORITHMS FOR A CLASS OF LINEARLY CONSTRAINED MINIMAX OPTIMIZATION PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2024年第3期34卷 2883-2916页

作者： Dai, Yu-Hong Wang, Jiani Zhang, Liwei Chinese Acad Sci LSEC AMSS Beijing 100190 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China Beijing Univ Posts & Telecommun Sch Sci Beijing 100876 Peoples R China Northeastern Univ Natl Frontiers Sci Ctr Ind Intelligence & Syst Opt Shenyang 110819 Peoples R China Northeastern Univ Key Lab Data Analyt & Optimizat Smart Ind Minist Educ Shenyang 110819 Peoples R China

It is well known that there have been many numerical algorithms for solving non- smooth minimax problems;however, numerical algorithms for non-smooth minimax problems with joint linear constraints are very rare. This paper aims to discuss optimality conditions and develop practical numerical algorithms for minimax problems with joint linear constraints. First, we use the properties of proximal mapping and the KKT system to establish optimality conditions. Second, we propose a framework of an alternating coordinate algorithm for the minimax problem and analyze its convergence properties. Third, we develop a proximal gradient multistep ascent descent method point for this kind of nonsmooth problem in O(epsilon(-2) log epsilon(-1))( )iterations. Finally, we apply PGmsAD (PGmsAD) as a numerical algorithm and demonstrate that the method can find an epsilon-stationary to generalized absolute value equations, generalized linear projection equations, and linear regression problems, and we report the efficiency of PGmsAD on large-scale optimization.

关键词： minimax optimization proximal mapping proximal gradient multi-step ascent descent method iteration complexity generalized absolute value equations linear regression generalized linear projection equations

来源：评论

学校读者我要写书评

暂无评论

A second-order method for strongly convex -regularization problems

引用

MATHEMATICAL PROGRAMMING 2016年第1-2期156卷 189-219页

作者： Fountoulakis, Kimon Gondzio, Jacek Univ Edinburgh Sch Math Peter Guthrie Tait Rd Edinburgh EH9 3FD Midlothian Scotland Univ Edinburgh Maxwell Inst Peter Guthrie Tait Rd Edinburgh EH9 3FD Midlothian Scotland

In this paper a robust second-order method is developed for the solution of strongly convex -regularized problems. The main aim is to make the proposed method as inexpensive as possible, while even difficult problems can be efficiently solved. The proposed approach is a primal-dual Newton conjugate gradients (pdNCG) method. Convergence properties of pdNCG are studied and worst-case iteration complexity is established. Numerical results are presented on synthetic sparse least-squares problems and real world machine learning problems.

关键词： l(1)-Regularization Strongly convex optimization Second-order methods iteration complexity Newton conjugate-gradients method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：