大型稀疏无约束最优化问题的行列修正算法

本文提出了一类适用于大型稀疏最优化问题的简单易行的行列修正算法，获得了新算法的局部超一性收敛性，大量的数值试验表明这是一个较为理想的修正算不。新算法同样可以用来求解大型对称性非线性方程组。     

Research on exponential regularization approach for nonnegative Tucker3 decomposition

Methods of nonnegative tensor factorization (NTF), such as NTF1, NTF2, etc., are extension of nonnegative matrix factorization (NMF) for multi-way data analysis. As an existing NTF method, nonnegative Tucker3 decomposition (NTD) is researched for three-way decomposition in this paper. Firstly, an approach utilizing matrix exponentials built on Tikhonov-type regularization to enforce sparseness is proposed to extract image features instead of exclusively using Tucker tensor decomposition. Meanwhile, updating algorithms, derived from updating rules of NMF, are allowed to efficiently implement updating of mode matrices and core tensors alternatively for accuracy. Then, experimental cases of alternating least squares (ALS) and conjugate nonnegative constraints, called nonnegative alternating least squares (NALS), are studied to remedy data overfitting in computing procedures. Lastly, the proposed method exhibits more advantageous results than other algorithms of Tucker3 for feature extraction, thanks to computer simulations performed in the context of data analysis.     

Fast Algorithms for Nonparametric Curve Estimation

Abstract

Naive implementations of local polynomial fits and kernel estimators require almost O(n ²) operations. In this article two fast O(n) algorithms for nonparametric local polynomial fitting are presented. They are based on updating normal equations. Numerical stability is guaranteed by controlling ill-conditioned situations for small bandwidths and data-tuned restarting of the updating procedure. Restarting at every output point results in a moderately fast but highly stable O(n ^7/5) algorithm. Applicability of algorithms is evaluated for estimation of regression curves and their derivatives. The idea is also applied to kernel estimators of regression curves and densities.     

DYNAMICAL ADJUSTMENT OF THE PROX-PARAMETER IN BUNDLE METHODS

Abstract

Proximal bundle methods are well known for their efficiency in nondifferentiable optimization. Their interpretation as approximate proximal methods yields a certain reversal poor-man formula for the regularization parameter in the proximal term. A new updating rule for this prox-parameter is introduced, based on the same scheme but making use of all the information available at each iteration. Numerical results assessing the validity of the approach are reported.     

A degeneracy exploiting LU factorization for the simplex method

For general sparse linear programs two of the most efficient implementations of the LU factorization with Bartels—Golub updating are due to Reid and Saunders. This paper presents an alternative approach which achieves fast execution times for degenerate simplex method iterations, especially when used with multiple pricing. The method should have wide applicability since the simplex method performs a high proportion of degenerate iterations on most practical problems. A key feature of Saunders' method is combined with the updating strategy of Reid so as to make the scheme suitable for implementation out of core. Its efficiency is confirmed by experimental results.     

A note about sparsity exploiting quasi-Newton updates

This paper is concerned with two questions relating to quasi-Newton updates for unconstrained optimization that exploit any sparsity present in the second derivative matrix of the objective function. First, a family of such updates is derived, that reduces to any a priori known dense update formula when no sparsity is imposed. This family uses the Frobenius projection of the desired update on the subspace of matrices that satisfy all the needed conditions. In the second part, we prove that, under mild assumptions, a positive definite sparse quasi-Newton update always exists. The proof of this result includes the explicit determination of such an update.     

General conditions for strategy abundance through a self-referential mechanism under weak selection

We examine stochastic evolutionary game dynamics of two-player m×m$m\times m$ symmetric and m×n$m\times n$ asymmetric games in finite populations assuming that a player decides to change her current strategy on the basis of her dissatisfaction, which we call a self-referential mechanism. We derive the general expression for the stationary distribution of strategy under weak selection and compare it with the counterpart of a Moran process. As a result, we find that both in symmetric games and in asymmetric games, the self-referential mechanism always generates a greater gap between the favored and unfavored strategies’ frequencies for a fixed parameter set than does a Moran process. Further, we found that for small mutation rates, our results are almost identical to the counterpart of a Moran process.     

一类新的非线性比式和问题的分枝定界算法(英文)

对一类新的非线性比式和问题(SNR)提出分枝定界算法,该问题的研究还很少.首先,通过两层线性化技术,构造一个松弛线性规划,求解该线性规划问题,得到问题(SNR)最优值的下界.其次,介绍新的下界更新技术,证明所给算法的收敛性.数值试验显示了算法的可行性和有效性