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

An APPA-based descent method with optimal step-sizes for monotone variational inequalities

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第2期186卷 486-495页

作者： Li, Min Yuan, Xiao-Ming Nanjing Univ Dept Math Nanjing 210093 Peoples R China Shanghai Jiao Tong Univ Antai Coll Econ & Management Shanghai 200052 Peoples R China

To solve monotone variational inequalities, some existing APPA-based descent methods utilize the iterates generated by the well-known approximate proximal point algorithms (APPA) to construct descent directions. This paper aims at improving these APPA-based descent methods by incorporating optimal step-sizes in both the extra-gradient steps and the descent steps. Global convergence is proved under mild assumptions. The superiority to existing methods is verified both theoretically and computationally. (C) 2007 Elsevier B.V. All rights reserved.

关键词： variational inequalities proximal point algorithm descent method optimal step-size

来源：评论

学校读者我要写书评

暂无评论

A partially proximal S-ADMM for separable convex optimization with linear constraints

引用

APPLIED NUMERICAL MATHEMATICS 2021年 160卷 65-83页

作者： Shen, Yuan Zuo, Yannian Yu, Aolin Nanjing Univ Finance & Econ Sch Appl Math Nanjing 210023 Peoples R China

A classical approach to solving two-block separable convex optimization could be the symmetric alternating direction method of multipliers (S-ADMM). However, its convergence may not be guaranteed for a general multi-block case without additional assumptions. Bai et al. proposed a variant of S-ADMM entitled the generalized symmetric ADMM (GS-ADMM), in which the variables are regrouped into two groups firstly. The two groups of variables are updated in a Gauss-Seidel scheme, while the variables within each group are updated in a Jacobi scheme and the Lagrangian multipliers are updated two times. In order to derive its convergence property, the authors add a special proximal term to each subproblem. In this paper, inspired by the partial PPA block-wise ADMM (PPBADMM) [32] proposed by Shen et al., we propose a partially proximal S-ADMM (PPSADMM). In PPSADMM, the special proximal term is only added to the subproblems in the first group as PPBADMM. We perform an extension step on all variables with a fixed step size at the end of each iteration. Without stringent assumptions, we establish the global convergence result and the O(1/t) convergence rate in the ergodic sense for PPSADMM. Its numerical performance is justified on two types of problems. (C) 2020 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： Separable convex optimization Multiple blocks Symmetric alternating direction method of multipliers proximal point algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximate generalized proximal-type method for convex vector optimization problem in Banach spaces

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2009年第7期57卷 1196-1203页

作者： Chen, Zhe Huang, Haiqiao Zhao, Kequan Chongqing Normal Univ Dept Math & Comp Sci Chongqing 400047 Peoples R China Hong Kong Polytech Univ Dept Appl Math Hong Kong Hong Kong Peoples R China Beijing Inst Clothing Technol Sch Fash Art & Engn Beijing 100029 Peoples R China

in this paper, we consider a convex vector optimization problem of finding weak Pareto optimal solutions for an extended vector-valued map from a uniformly convex and uniformly smooth Banach space to a real Banach space, with respect to the partial order induced by a closed, convex and pointed cone with a nonempty interior. We propose an inexact vector-valued proximal-type point algorithm based on a Lyapunov functional when the iterates are computed approximately and prove the sequence generated by the algorithm weakly converges to a weak Pareto optimal solution of the vector optimization problem under some mild conditions. Our results improve and generalize some known results. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Vector optimization proximal point algorithm Lyapunov functional Banach spaces Weakly converge Weak Pareto optimal solution Error term

来源：评论

学校读者我要写书评

暂无评论

Solving a class of constrained 'black-box' inverse variational inequalities

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第3期204卷 391-401页

作者： He, Bingsheng He, Xiao-Zheng Liu, Henry X. Nanjing Univ Dept Math Nanjing 210093 Peoples R China Univ Minnesota Dept Civil Engn Minneapolis MN 55455 USA

It is well known that a general network economic equilibrium problem can be formulated as a variational inequality (VI) and solving the VI will result in a description of network equilibrium state. In this paper, however, we discuss a class of normative control problem that requires the network equilibrium state to be in a linearly constrained set. We formulate the problem as an inverse variational inequality (IVI) because the variables and the mappings in the IVI are in the opposite positions of a classical VI. In addition, the mappings in IVI usually do not have any explicit forms and only implicit information on the functional value is available through exogenous evaluation or direct observation. For such class of network equilibrium control problem, we present a linearly constrained implicit IVI formulation and a solution method based on proximal point algorithm (PPA) that only needs functional values for given variables in the solution process. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Black-box Inverse variational inequality Nonlinear programming proximal point algorithm

来源：评论

学校读者我要写书评

暂无评论

AN INEXACT algorithm WITH proximal DISTANCES FOR VARIATIONAL INEQUALITIES

引用

RAIRO-OPERATIONS RESEARCH 2018年第1期52卷 159-176页

作者： Papa Quiroz, E. A. Mallma Ramirez, L. Oliveira, P. R. San Marcos Natl Univ Dept Math Lima Peru Univ Fed Rio de Janeiro COPPE PESC Rio Of Janeiro Brazil

In this paper we introduce an inexact proximal point algorithm using proximal distances for solving variational inequality problems when the mapping is pseudomonotone or quasimonotone. Under some natural assumptions we prove that the sequence generated by the algorithm is convergent for the pseudomonotone case and assuming an extra condition on the solution set we prove the convergence for the quasimonotone case. This approach unifies the results obtained by Auslender et al. [Math Oper. Res. 24 (1999) 644-688] and Brito et al. [J. Optim. Theory Appl. 154 (2012) 217-234] and extends the convergence properties for the class of phi-divergence distances and Bregman distances.

关键词： Variational inequalities proximal distance proximal point algorithm quasimonotone and pseudomonotone mapping

来源：评论

学校读者我要写书评

暂无评论

CONVERGENCE RATE ANALYSIS OF PRIMAL-DUAL SPLITTING SCHEMES

引用

SIAM JOURNAL ON OPTIMIZATION 2015年第3期25卷 1912-1943页

作者： Davis, Damek Univ Calif Los Angeles Dept Math Los Angeles CA 90025 USA Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14850 USA

Primal-dual splitting schemes are a class of powerful algorithms that solve complicated monotone inclusions and convex optimization problems that are built from many simpler pieces. They decompose problems that are built from sums, linear compositions, and infimal convolutions of simple functions so that each simple term is processed individually via proximal mappings, gradient mappings, and multiplications by the linear maps. This leads to easily implementable and highly parallelizable or distributed algorithms, which often obtain nearly state-of-the-art performance. In this paper, we analyze a monotone inclusion problem that captures a large class of primal-dual splittings as a special case. We introduce a unifying scheme and use some abstract analysis of the algorithm to prove convergence rates of the proximal point algorithm, forward-backward splitting, Peaceman-Rachford splitting, and forward-backward-forward splitting applied to the model problem. Our ergodic convergence rates are deduced under variable metrics, stepsizes, and relaxation parameters. Our nonergodic convergence rates are the first shown in the literature. Finally, we apply our results to a large class of primal-dual algorithms that are a special case of our scheme and deduce their convergence rates.

关键词： primal-dual algorithms convergence rates proximal point algorithm forward-backward splitting forward-backward-forward splitting nonexpansive operator Douglas-Rachford splitting Peaceman-Rachford splitting averaged operator fixed-point algorithm

来源：评论

学校读者我要写书评

暂无评论

DUALITY RESULTS AND DUAL BUNDLE METHODS BASED ON THE DUAL METHOD OF CENTERS FOR MINIMAX FRACTIONAL PROGRAMS

引用

SIAM JOURNAL ON OPTIMIZATION 2019年第2期29卷 1578-1602页

作者： Boufi, Karima Roubi, Ahmed Univ Hassan 1 Fac Sci & Tech Lab MISI Settat Morocco

We propose new duality results for generalized fractional programs (GFP) for a wide class of problems, not limited only to the convex case. Our approach does not use Lagrangian duality, but only an equivalent form of the GFP. We present a general approximating scheme, based on the proximal point algorithm, for solving this dual program. We take advantage of the convexity property of the dual, independently of the primal properties, to build implementable bundle methods with the support of the general scheme. However, it is well known that the principal difficulty with the duality is the evaluation of the dual function. To mitigate this difficulty, we propose bundle methods that need only approximate values and approximate subgradients of the objective dual function. We prove the convergence and the rate of convergence of these algorithms. As is the case for dual algorithms, the proposed methods generate a sequence of values that converges from below to the minimal value of the GFP, and a sequence of approximate solutions that converges to a solution of the dual problem. For certain classes of problems, the convergence is at least linear.

关键词： minimax fractional programs dual method of centers proximal point algorithm bundle methods quadratic programming

来源：评论

学校读者我要写书评

暂无评论

COMPUTING MEDIANS AND MEANS IN HADAMARD SPACES

引用

SIAM JOURNAL ON OPTIMIZATION 2014年第3期24卷 1542-1566页

作者： Bacak, Miroslav Max Planck Inst Math Sci D-04103 Leipzig Germany

The geometric median as well as the Frechet mean of points in a Hadamard space are important in both theory and applications. Surprisingly, no algorithms for their computation are hitherto known. To address this issue, we use a splitting version of the proximal point algorithm for minimizing a sum of convex functions and prove that this algorithm produces a sequence converging to a minimizer of the objective function, which extends a recent result of Bertsekas [Math. Program., 129 (2011), pp. 163-195] into Hadamard spaces. The method is quite robust, and not only does it yield algorithms for the median and the mean, but also it applies to various other optimization problems. We, moreover, show that another algorithm for computing the Frechet mean can be derived from the law of large numbers due to Sturm [Ann. Probab., 30 (2002), pp. 1195-1222]. In applications, computing medians and means is probably most needed in tree space, which is an instance of a Hadamard space, invented by Billera, Holmes, and Vogtmann [Adv. in Appl. Math., 27 (2001), pp. 733-767] as a tool for averaging phylogenetic trees. Since there now exists a polynomial-time algorithm for computing geodesics in tree space due to Owen and Provan [IEEE/ACM Trans. Comput. Biol. Bioinform., 8 (2011), pp. 2-13], we obtain efficient algorithms for computing medians and means of trees, which can be directly used in practice.

关键词： Hadamard space mean median proximal point algorithm the law of large numbers tree space computational phylogenetics diffusion tensor imaging

来源：评论

学校读者我要写书评

暂无评论

proximal bundle methods based on approximate subgradients for solving Lagrangian duals of minimax fractional programs

引用

JOURNAL OF GLOBAL OPTIMIZATION 2019年第2期74卷 255-284页

作者： Boualam, H. Roubi, A. Univ Hassan 1 Fac Sci & Tech Lab MISI Settat Morocco

We are interested in this work to solve the Lagrangian dual of a generalized fractional program (GFP), which gives the minimal value of the primal problem, thanks to some duality results. With the help of a general minimax equality assumption, we give duality results under minimal assumptions. Since the associated parametric programs of the dual of GFP are always concave, we use a general approximating proximal scheme to these subproblems and construct bundle methods by means of approximate values and approximate subgradients of the dual parametric function. As for all dual algorithms, the proposed methods generate a sequence of values that converges from below to the minimal value of the GFP and a sequence of approximate solutions that converges to a solution of the Lagrangian dual of the GFP. For certain classes of problems, the convergence is at least linear.

关键词： Minimax fractional programs Lagrangian duality proximal point algorithm Bundle methods

来源：评论

学校读者我要写书评

暂无评论

A multi-parameter parallel ADMM for multi-block linearly constrained separable convex optimization

引用

APPLIED NUMERICAL MATHEMATICS 2022年 171卷 369-388页

作者： Shen, Yuan Gao, Qianming Yin, Xue Nanjing Univ Finance & Econ Sch Appl Math Nanjing 210023 Peoples R China

The alternating direction method of multipliers (ADMM) has been proved to be effective for solving two-block convex minimization model subject to linear constraints. However, the convergence of multiple-block convex minimization model with linear constraints may not be guaranteed without additional assumptions. Recently, some parallel multi-block ADMM algorithms which solve the subproblems in a parallel way have been proposed. This paper is a further study on this method with the purpose of improving the parallel multi-block ADMM algorithm by introducing more parameters. We propose two multi-parameter parallel ADMM algorithms with proximal point terms attached to all subproblems. Comparing with some popular parallel ADMM-based algorithms, the parameter conditions of the new algorithms are relaxed. Experiments on both real and synthetic problems are conducted to justify the effectiveness of the proposed algorithms compared to several efficient ADMM-based algorithms for multi-block problems. (C) 2021 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： Multi-block Convex optimization Parallel computing proximal point algorithm Alternating direction method of multipliers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：