An Alternating Direction Method for Nash Equilibrium of Two-Person Games with Alternating Offers

In this paper, we propose a method for finding a Nash equilibrium of two-person games with alternating offers. The proposed method is referred to as the inexact proximal alternating direction method. In this method, the idea of alternating direction method simulates alternating offers in the game, while the inexact solutions of subproblems can be matched to the assumptions of incomplete information and bounded individual rationality in practice. The convergence of the proposed method is proved under some suitable conditions. Numerical tests show that the proposed method is competitive to the state-of-the-art algorithms.     

一类单调变分不等式的非精确交替方向法

交替方向法适合于求解大规模问题.该文对于一类变分不等式提出了一种新的交替方向法.在每步迭代计算中,新方法提出了易于计算的子问题,该子问题由强单调的线性变分不等式和良态的非线性方程系统构成.基于子问题的精确求解,该文证明了算法的收敛性.进一步,又提出了一类非精确交替方向法,每步迭代计算只需非精确求解子问题.在一定的非精确条件下,算法的收敛性得以证明.     

Inexact Alternating Direction Methods of Multipliers with Logarithmic–Quadratic Proximal Regularization

In the literature, it was shown recently that the Douglas–Rachford alternating direction method of multipliers can be combined with the logarithmic-quadratic proximal regularization for solving a class of variational inequalities with separable structures. This paper studies the inexact version of this combination, where the resulting subproblems are allowed to be solved approximately subject to different inexactness criteria. We prove the global convergence and establish worst-case convergence rates for the derived inexact algorithms.     

On the convergence of inexact Newton methods for discrete-time algebraic Riccati equations

In this paper, we present a convergence analysis of the inexact Newton method for solving Discrete-time algebraic Riccati equations (DAREs) for large and sparse systems. The inexact Newton method requires, at each iteration, the solution of a symmetric Stein matrix equation. These linear matrix equations are solved approximatively by the alternating directions implicit (ADI) or Smith?s methods. We give some new matrix identities that will allow us to derive new theoretical convergence results for the obtained inexact Newton sequences. We show that under some necessary conditions the approximate solutions satisfy some desired properties such as the d-stability. The theoretical results developed in this paper are an extension to the discrete case of the analysis performed by Feitzinger et al. (2009) [8] for the continuous-time algebraic Riccati equations. In the last section, we give some numerical experiments.     

An Inexact Alternating Direction Method for Structured Variational Inequalities

Recently, the alternating direction method of multipliers has attracted great attention. For a class of variational inequalities (VIs), this method is efficient, when the subproblems can be solved exactly. However, the subproblems could be too difficult or impossible to be solved exactly in many practical applications. In this paper, we propose an inexact method for structured VIs based on the projection and contraction method. Instead of solving the subproblems exactly, we use the simple projection to get a predictor and correct it to approximate the subproblems’ real solutions. The convergence of the proposed method is proved under mild assumptions and its efficiency is also verified by some numerical experiments.     

An inexact alternating direction method of multipliers for the solution of linear complementarity problems arising from free boundary problems

A large number of free boundary problems can be formulated as linear-complementarity problems. In this paper, we propose an inexact alternating direction method of multipliers for solving linear complementarity problem arising from free boundary problems by using the special structure of these problems. The convergence of our proposed method is proved. Numerical results show that the proposed method is feasible and effective, and it is significantly faster than modified alternating direction implicit algorithm and many other methods, especially when dimension of the problem being solved is large.     

An inexact parallel splitting augmented Lagrangian method for monotone variational inequalities with separable structures

Splitting methods have been extensively studied in the context of convex programming and variational inequalities with separable structures. Recently, a parallel splitting method based on the augmented Lagrangian method (abbreviated as PSALM) was proposed in He (Comput. Optim. Appl. 42:195?C212, 2009) for solving variational inequalities with separable structures. In this paper, we propose the inexact version of the PSALM approach, which solves the resulting subproblems of PSALM approximately by an inexact proximal point method. For the inexact PSALM, the resulting proximal subproblems have closed-form solutions when the proximal parameters and inexact terms are chosen appropriately. We show the efficiency of the inexact PSALM numerically by some preliminary numerical experiments.     

An Accelerated Inexact Proximal Point Algorithm for Convex Minimization

The proximal point algorithm is classical and popular in the community of optimization. In practice, inexact proximal point algorithms which solve the involved proximal subproblems approximately subject to certain inexact criteria are truly implementable. In this paper, we first propose an inexact proximal point algorithm with a new inexact criterion for solving convex minimization, and show its O(1/k) iteration-complexity. Then we show that this inexact proximal point algorithm is eligible for being accelerated by some influential acceleration schemes proposed by Nesterov. Accordingly, an accelerated inexact proximal point algorithm with an iteration-complexity of O(1/k ²) is proposed.     

一种求解双目标规划的非精确交替方向法

本文提出了一种求解双目标规划的直接算法---非精确交替方向方法,并证明了算法的收敛性.初步的数值实验说明了所提出的算法是有效可行的.     

可分离凸优化问题的非精确平行分裂算法

针对一类可分离凸优化问题提出了一种非精确平行分裂算法.该算法充分利用了所求解问题的可分离结构,并对子问题进行非精确求解.在适当的条件下,证明了所提出的非精确平行分裂算法的全局收敛性,初步的数值实验说明了算法有效性.     

An inexact alternating direction method of multipliers with relative error criteria

In this paper, we study an inexact version of the alternating direction method of multipliers (ADMM) for solving two-block separable linearly constrained convex optimization problems. Specifically, the two subproblems in the classic ADMM are allowed to be solved inexactly by certain relative error criteria, in the sense that only two parameters are needed to control the inexactness. Related convergence analysis are established under the assumption that the solution set to the KKT system of the problem is not empty. Numerical results on solving a class of sparse signal recovery problems are also provided to demonstrate the efficiency of the proposed algorithm.     

An implementable proximal point algorithmic framework for nuclear norm minimization

The nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact proximal point algorithms in the primal, dual and primal-dual forms for solving the nuclear norm minimization with linear equality and second order cone constraints. We design efficient implementations of these algorithms and present comprehensive convergence results. In particular, we investigate the performance of our proposed algorithms in which the inner sub-problems are approximately solved by the gradient projection method or the accelerated proximal gradient method. Our numerical results for solving randomly generated matrix completion problems and real matrix completion problems show that our algorithms perform favorably in comparison to several recently proposed state-of-the-art algorithms. Interestingly, our proposed algorithms are connected with other algorithms that have been studied in the literature.     

An inexact logarithmic-quadratic proximal augmented Lagrangian method for a class of constrained variational inequalities

The augmented Lagrangian method is attractive in constraint optimizations. When it is applied to a class of constrained variational inequalities, the sub-problem in each iteration is a nonlinear complementarity problem (NCP). By introducing a logarithmic-quadratic proximal term, the sub-NCP becomes a system of nonlinear equations, which we call the LQP system. Solving a system of nonlinear equations is easier than the related NCP, because the solution of the NCP has combinatorial properties. In this paper, we present an inexact logarithmic-quadratic proximal augmented Lagrangian method for a class of constrained variational inequalities, in which the LQP system is solved approximately under a rather relaxed inexactness criterion. The generated sequence is Fejér monotone and the global convergence is proved. Finally, some numerical test results for traffic equilibrium problems are presented to demonstrate the efficiency of the method.      

一种求解合作博弈最公平核心的非精确平行分裂算法

针对合作博弈核心和Shapley值的特点, 将最公平核心问题转化为带有两个变 量的可分离凸优化问题, 引入结构变分不等式的算子分裂方法框架, 提出了求解最公平核心的一种非精确平行分裂算法. 而且, 该算法充分利用了所求解问题的可行域的简单闭凸性, 子问题的非精确求解是容易的. 最后, 简单算例的数值实验表明了算法的收敛性和有效性.     

A HOMOTOPY-BASED ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR STRUCTURED CONVEX OPTIMIZATION

The alternating direction method of multipliers(ADMM for short) is efficient for linearly constrained convex optimization problem. The practical computational cost of ADMM depends on the sub-problem solvers. The proximal point algorithm is a common sub-problem-solver. However, the proximal parameter is sensitive in the proximal ADMM. In this paper, we propose a homotopy-based proximal linearized ADMM, in which a homotopy method is used to solve the sub-problems at each iteration. Under some suitable conditions, the global convergence and the convergence rate of O(1/k) in the worst case of the proposed method are proven. Some preliminary numerical results indicate the validity of the proposed method.     

核范数和谱范数下广义Sylvester方程最小二乘问题的一类改进算法

在文献[10]中,作者从数值角度讨论核范数和谱范数下的广义Sylvester方程约束最小二乘问题min X∈ S|NΣI=1A_iXB_i-C|的算法,其中s为闭凸集合.采用的数值算法是非精确交替方向法,并结合阈值算法、 MoreauYosida正则化算法、谱投影算法、LSQR, SPG等算法求解相应子问题.本文在文献[10]的基础上,通过引入新变量,应用交替方向法简化子问题的求解,其中每个子问题都可以精确求解,更重要的是每个变量都具有显式的表达式.在理论方面我们证明了算法的收敛性,数值试验表明改进后的算法不管是在时间上还是在迭代步上,运行的结果得到很大的改善.     

Inexact Alternating-Direction-Based Contraction Methods for Separable Linearly Constrained Convex Optimization

Alternating direction method of multipliers has been well studied in the context of linearly constrained convex optimization. In the last few years, we have witnessed a number of novel applications arising from image processing, compressive sensing and statistics, etc., where the approach is surprisingly efficient. In the early applications, the objective function of the linearly constrained convex optimization problem is separable into two parts. Recently, the alternating direction method of multipliers has been extended to the case where the number of the separable parts in the objective function is finite. However, in each iteration, the subproblems are required to be solved exactly. In this paper, by introducing some reasonable inexactness criteria, we propose two inexact alternating-direction-based contraction methods, which substantially broaden the applicable scope of the approach. The convergence and complexity results for both methods are derived in the framework of variational inequalities.     

A truncated conjugate gradient method with an inexact Gauss-Newton technique for solving nonlinear systems

In this paper, a truncated conjugate gradient method with an inexact Gauss-Newton technique is proposed for solving nonlinear systems.?The iterative direction is obtained by the conjugate gradient method solving the inexact Gauss-Newton equation.?Global convergence and local superlinear convergence rate of the proposed algorithm are established under some reasonable conditions. Finally, some numerical results are presented to illustrate the effectiveness of the proposed algorithm.     

Symmetric Alternating Direction Method with Indefinite Proximal Regularization for Linearly Constrained Convex Optimization

The proximal alternating direction method of multipliers is a popular and useful method for linearly constrained, separable convex problems, especially for the linearized case. In the literature, convergence of the proximal alternating direction method has been established under the assumption that the proximal regularization matrix is positive semi-definite. Recently, it was shown that the regularizing proximal term in the proximal alternating direction method of multipliers does not necessarily have to be positive semi-definite, without any additional assumptions. However, it remains unknown as to whether the indefinite setting is valid for the proximal version of the symmetric alternating direction method of multipliers. In this paper, we confirm that the symmetric alternating direction method of multipliers can also be regularized with an indefinite proximal term. We theoretically prove the global convergence of the indefinite method and establish its worst-case convergence rate in an ergodic sense. In addition, the generalized alternating direction method of multipliers proposed by Eckstein and Bertsekas is a special case in our discussion. Finally, we demonstrate the performance improvements achieved when using the indefinite proximal term through experimental results.     

Accelerated schemes for a class of variational inequalities

We propose a novel stochastic method, namely the stochastic accelerated mirror-prox (SAMP) method, for solving a class of monotone stochastic variational inequalities (SVI). The main idea of the proposed algorithm is to incorporate a multi-step acceleration scheme into the stochastic mirror-prox method. The developed SAMP method computes weak solutions with the optimal iteration complexity for SVIs. In particular, if the operator in SVI consists of the stochastic gradient of a smooth function, the iteration complexity of the SAMP method can be accelerated in terms of their dependence on the Lipschitz constant of the smooth function. For SVIs with bounded feasible sets, the bound of the iteration complexity of the SAMP method depends on the diameter of the feasible set. For unbounded SVIs, we adopt the modified gap function introduced by Monteiro and Svaiter for solving monotone inclusion, and show that the iteration complexity of the SAMP method depends on the distance from the initial point to the set of strong solutions. It is worth noting that our study also significantly improves a few existing complexity results for solving deterministic variational inequality problems. We demonstrate the advantages of the SAMP method over some existing algorithms through our preliminary numerical experiments.