求解张量随机互补问题的光滑牛顿算法

近年来, 越来越多的人意识到随机互补问题在经济管理中具有十分重要的作用。有学者已将随机互补问题由矩阵推广到张量, 并提出了张量随机互补问题。本文通过引入一类光滑函数, 提出了求解张量随机互补问题的一种光滑牛顿算法, 并证明了算法的全局和局部收敛性, 最后通过数值实验验证了算法的有效性。     

求解张量互补问题的一类光滑模系矩阵迭代方法

本文提出了求解张量互补问题的一类光滑模系矩阵迭代方法.其基本思想是,先将张量互补问题转化为等价的模系方程组,然后引入一个逼近的光滑函数进行求解.我们分析了算法的收敛性,并通过数值实验验证了所提出算法的有效性.     

基于模量重构的张量互补问题的光滑牛顿算法（英文）

近年来,张量作为矩阵的推广,得到了广泛的研究.在众多张量相关的问题中,张量互补问题(TCP)是许多学者研究的一个重要领域,人们提出了许多解决TCP的方法.本文在强P-张量张量和光滑逼近函数的基础上,提出一种基于基于模的重构的TCP光滑牛顿算法,证明光滑牛顿方法是全局收敛的.数值算例验证了光滑牛顿算法的有效性.     

张量空间上的线性互补问题

借助于一类张量收缩积,本文定义一类张量空间上的线性互补问题,简称张量线性互补问题.当所涉及的张量变量退化为向量时,所考虑的问题退化为经典的线性互补问题.对此,首先讨论张量收缩积的一些性质,然后建立张量线性互补问题的理论与算法.具体地,讨论张量线性互补问题的等价模型、可行性与可解性理论、解集的凸性等,提出一个求解张量线性互补问题的外梯度算法,在一定条件下证明算法的收敛性,并给出初步的数值实验结果.     

解非线性互补问题的光滑牛顿方法

由于退化解会导致再生方程的奇异性,非线性互补问题的求解通常采用基于半光滑技术的广义牛顿法.基于2-正则性的概念,提出了一类利用光滑互补函数求解互补问题的光滑牛顿算法.算法采用积极集技术,能在解的附近估计出退化指标,并把原问题降阶为一个非奇异方程组,从而保证了迭代效率.算法具有整体收敛性和局部超线性收敛性,数值实验显示算法是有效的.     

一类广义多项式互补问题的光滑化共轭梯度法

本文研究了一类广义多项式互补问题,在一定条件下,证明了其有唯一解.通过极大极小转化技术,将此类广义多项式互补问题转化为光滑化无约束优化问题进行求解,并提出了一种新的光滑化共轭梯度法.在一定假设条件下,证明了该方法的全局收敛性.最后相关的数值实验表明了算法可以有效求解广义多项式互补问题.     

非线性互补约束问题一个全局收敛的SQP算法

本文研究非线性互补约束优化问题,利用Fischer-Burmeister函数将非线性互补问题转化为非光滑方程,提出一个求解非线性互补约束问题的SQP算法,并在适当的假设下证明这个算法是全局收敛的.     

求解非线性互补问题的一类光滑Broyden-like方法

非线性互补问题可以等价地转换为光滑方程组来求解. 基于一种新的非单调线搜索准则, 提出了求解非线性互补问题等价光滑方程组的一类新的非单调光滑 Broyden-like 算法.在适当的假设条件下, 证明了该算法的全局收敛性与局部超线性收敛性. 数值实验表明所提出的算法是有效的.     

混合互补问题的光滑逼近法

提出了求解混合互补问题的一个光滑逼近算法，并在一定条件下证明了该算法的全局收敛性．     

非线性互补约束规划问题的一个新的QP-free算法

本文研究了非线性互补约束均衡问题.利用互补函数以及光滑近似法,把非线性互补约束均衡问题转化为一个光滑非线性规划问题,得到了超线性收敛速度,数值实验结果表明本文提出的算法是可行的.     

Nonnegative tensors revisited: plane stochastic tensors

In this paper, we develop and enrich the theory of nonnegative tensors. We define the sign nonsingular tensors and establish the relationship between the combinatorial determinant and the permanent of nonnegative tensors. We generalize the results from doubly stochastic matrices to totally plane stochastic tensors and obtain a probabilistic algorithm for locating a positive diagonal in a nonnegative tensor under certain conditions. We form a normalization algorithm to convert some nonnegative tensors to plane stochastic tensors. We obtain a lower bound for the minimum of the axial N-index assignment problem by means of the set of plane stochastic tensors.     

Feasible smooth method based on Barzilai–Borwein method for stochastic linear complementarity problem

In this paper, we propose a feasible smooth method based on Barzilai–Borwein (BB) for stochastic linear complementarity problem. It is based on the expected residual minimization (ERM) formulation for the stochastic linear complementarity problem. Numerical experiments show that the method is efficient.     

A general MPCC model and its solution algorithm for continuous network design problem

This paper formulates the continuous network design problem as a mathematical program with complementarity constraints (MPCC), with the upper level a nonlinear programming problem and the lower level a nonlinear complementarity problem. Unlike in most previous studies, the proposed framework is more general, in which both symmetric and asymmetric user equilibria can be captured. By applying the complementarity slackness condition of the lower-level problem, the original bilevel formulation can be converted into a single-level and smooth nonlinear programming problem. In order to solve the problem, a relaxation scheme is applied by progressively restricting the complementarity condition, which has been proven to be a rigorous approach under certain conditions. The model and solution algorithm are tested for well-known network design problems and promising results are shown.     

On a Class of Semi-Positive Tensors in Tensor Complementarity Problem

Recently, the tensor complementarity problem has been investigated in the literature. In this paper, we extend a class of structured matrices to higher-order tensors; the corresponding tensor complementarity problem has a unique solution for any nonzero nonnegative vector. We discuss their relationships with semi-positive tensors and strictly semi-positive tensors. We also study the property of such a structured tensor. We show that every principal sub-tensor of such a structured tensor is still a structured tensor in the same class, with a lower dimension. We also give two equivalent formulations of such a structured tensor.     

Unconstrained minimization approaches to nonlinear complementarity problems

The nonlinear complementarity problem can be reformulated as unconstrained minimization problems by introducing merit functions. Under some assumptions, the solution set of the nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. These results were presented by Mangasarian and Solodov, Yamashita and Fukushima, and Geiger and Kanzow. In this note, we generalize some results of Mangasarian and Solodov, Yamashita and Fukushima, and Geiger and Kanzow to the case where the considered function is only directionally differentiable. Some results are strengthened in the smooth case. For example, it is shown that the strong monotonicity condition can be replaced by the P-uniform property for ensuring a stationary point of the reformulated unconstrained minimization problems to be a solution of the nonlinear complementarity problem. We also present a descent algorithm for solving the nonlinear complementarity problem in the smooth case. Any accumulation point generated by this algorithm is proved to be a solution of the nonlinear complementarity under the monotonicity condition.     

Benders Decomposition for multi-stage stochastic mixed complementarity problems – Applied to a global natural gas market model

This paper presents and implements a Benders Decomposition type of algorithm for large-scale, stochastic multi-period mixed complementarity problems. The algorithm is applied to various multi-stage natural gas market models accounting for market power exertion by traders. Due to the non-optimization nature of the natural gas market problem, a straightforward implementation of the traditional Benders Decomposition is not possible. The master and subproblems can be derived from the underlying optimization problems and transformed into complementarity problems. However, to complete the master problems optimality cuts are added using the variational inequality-based method developed in Gabriel and Fuller (2010). In this manner, an alternative derivation of Benders Decomposition for Stochastic MCP is presented, thereby making this approach more applicable to a broader audience. The algorithm can successfully solve problems with up to 256 scenarios and more than 600 thousand variables, and problems with over 117 thousand variables with more than two thousand first-stage capacity expansion variables. The algorithm is efficient for solving two-stage problems. The computational time reduction for other stochastic problems is considerable and would be even larger if a parallel implementation of the algorithm were used. The paper concludes with a discussion of infrastructure expansion results, illustrating the impact of hedging on investment timing and optimal capacity sizes.     

High-order copositive tensors and its applications

With the coming of the big data era, high-order high-dimensional structured tensors received much attentions of researchers" in recent years, and now they are developed into a new research branch in mathematics named multilinear algebra. As a special kind of structured tensor, the copositive tensor receives a special concern due to its wide applications in vacuum stability of a general scalar potential, polynomial optimization, tensor complementarity problem and tensor eigenvalue complementarity problem. In this review, we will give a simple survey on recent advances of high-order copositive tensors and its applications. Some potential research directions in the future are also listed in the paper.     

On the ERM formulation and a stochastic approximation algorithm of the stochastic-R_0 EVLCP

In this paper, a class of stochastic extended vertical linear complementarity problems is studied as an extension of the stochastic linear complementarity problem. The expected residual minimization (ERM) formulation of this stochastic extended vertical complementarity problem is proposed based on an NCP function. We study the corresponding properties of the ERM problem, such as existence of solutions, coercive property and differentiability. Finally, we propose a descent stochastic approximation method for solving this problem. A comprehensive convergence analysis is given. A number of test examples are constructed and the numerical results are presented.     

CVaR-constrained stochastic programming reformulation for stochastic nonlinear complementarity problems

We reformulate a stochastic nonlinear complementarity problem as a stochastic programming problem which minimizes an expected residual defined by a restricted NCP function with nonnegative constraints and CVaR constraints which guarantee the stochastic nonlinear function being nonnegative with a high probability. By applying smoothing technique and penalty method, we propose a penalized smoothing sample average approximation algorithm to solve the CVaR-constrained stochastic programming. We show that the optimal solution of the penalized smoothing sample average approximation problem converges to the solution of the corresponding nonsmooth CVaR-constrained stochastic programming problem almost surely. Finally, we report some preliminary numerical test results.