The convergence of subspace trust region methods

The trust region method is an effective approach for solving optimization problems due to its robustness and strong convergence. However, the subproblem in the trust region method is difficult or time-consuming to solve in practical computation, especially in large-scale problems. In this paper we consider a new class of trust region methods, specifically subspace trust region methods. The subproblem in these methods has an adequate initial trust region radius and can be solved in a simple subspace. It is easier to solve than the original subproblem because the dimension of the subproblem in the subspace is reduced substantially. We investigate the global convergence and convergence rate of these methods.     

线性方程组l_1范数问题的松弛投影算法及其应用

考虑线性方程组l_1范数问题的求解,在分别将其转化为一个分裂可行问题和凸可行问题的基础上,设计了几种松弛投影算法,然后将所设计的求解方法用于信号处理问题的求解上.     

Approximate Subgradient Methods for Nonlinearly Constrained Network Flow Problems

The minimization of nonlinearly constrained network flow problems can be performed by using approximate subgradient methods. The idea is to solve this kind of problem by means of primal-dual methods, given that the minimization of nonlinear network flow problems can be done efficiently exploiting the network structure. In this work, it is proposed to solve the dual problem by using ε-subgradient methods, as the dual function is estimated by minimizing approximately a Lagrangian function, which includes the side constraints (nonnetwork constraints) and is subject only to the network constraints. Some well-known subgradient methods are modified in order to be used as ε-subgradient methods and the convergence properties of these new methods are analyzed. Numerical results appear very promising and effective for this kind of problems This research was partially supported by Grant MCYT DPI 2002-03330.     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

融入用户社交关系与信任关系的应用推荐方法研究

随着近年来互联网技术的快速发展,应用获取平台都面临着信息过载的问题.面对大量应用,解决用户不能快速准确地找到满足其偏好的应用的问题迫在眉睫.已有的如Cosine、Pearson等协同过滤方法普遍存在稀疏性、冷启动和可扩展性等问题,从而对推荐结果产生影响.文章在考虑用户社交关系、偏好及信任关系的基础上,提出了融合用户社交...     

A trust region-CG algorithm for deblurring problem in atmospheric image reconstruction

In this paper we solve large scale ill-posed problems, particularly the image restoration problem in atmospheric imaging sciences, by a trust region-CG algorithm. Image restoration involves the removal or minimization of degradation (blur, clutter, noise, etc.) in an image using a priori knowledge about the degradation phenomena. Our basic technique is the so-called trust region method, while the subproblem is solved by the truncated conjugate gradient method, which has been well developed for well-posed problems. The trust region method, due to its robustness in global convergence, seems to be a promising way to deal with ill-posed problems.     

有理函数积分的公式解法

被积函数为有理函数的不定积分求解通常是采用待定系数法。本文提出了这类积分的非待定系数公式解法，较完美地解决了这类积分问题。在实际应用中显示了这种新型方法是简捷的和有效的。它的优点还在于不仅对一些常规方法极为困难或无法解决的问题给以简明的解，而且借助于电子计算机可解决更复杂的问题。     

Three-term conjugate gradient method for the convex optimization problem over the fixed point set of a nonexpansive mapping

Many constrained sets in problems such as signal processing and optimal control can be represented as a fixed point set of a certain nonexpansive mapping, and a number of iterative algorithms have been presented for solving a convex optimization problem over a fixed point set. This paper presents a novel gradient method with a three-term conjugate gradient direction that is used to accelerate conjugate gradient methods for solving unconstrained optimization problems. It is guaranteed that the algorithm strongly converges to the solution to the problem under the standard assumptions. Numerical comparisons with the existing gradient methods demonstrate the effectiveness and fast convergence of this algorithm.     

A New Approximation of the Matrix Rank Function and Its Application to Matrix Rank Minimization

The matrix rank minimization problem is widely applied in many fields such as control, signal processing and system identification. However, the problem is NP-hard in general and is computationally hard to directly solve in practice. In this paper, we provide a new approximation function of the matrix rank function, and the corresponding approximation problems can be used to approximate the matrix rank minimization problem within any level of accuracy. Furthermore, the successive projected gradient method, which is designed based on the monotonicity and the Fréchet derivative of these new approximation function, can be used to solve the matrix rank minimization this problem by using the projected gradient method to find the stationary points of a series of approximation problems. Finally, the convergence analysis and the preliminary numerical results are given.     

无约束多目标规划的信赖域方法

本文将信赖域方法应用于多目标规划,提出了一类解多目标问题的新算法,并证明了全局收敛性。     

电力系统中地网腐蚀诊断的一种新的数学模型及其仿真计算

对电力系统中具有重大应用价值的地网腐蚀诊断问题抽象出仿真求解的一种新的数学模型:即求解带约束的非线性隐式方程组模型.但由于问题本身的物理特性决定了所建立的数学模型具有以下特点:一是非线性方程组为欠定方程组,而且非线性程度非常高;二是方程组的所有函数均为隐函数;三是方程组附加若干箱约束条件.这种特性给模型分析与算法设计带来巨大困难.对于欠定方程组的求解,文中根据工程实际背景,尽可能地扩充方程的个数,使之成为超定方程组,然后对欠定方程组和超定方程组分别求解并进行比较.将带约束的非线性隐函数方程组求解问题,转化为无约束非线性最小二乘问题,并采用矩阵求导等技术和各种算法设计技巧克服隐函数的计算困难,最后使用拟牛顿信赖域方法进行计算.大量的计算实例表明,文中所提出的数学模型及求解方法是可行的.与目前广泛采用的工程简化模型相比较,在模型和算法上具有很大优势.     

On the Computation of Optimal Static Output Feedback Controllers for Discrete-Time Systems

In this article, we consider the static output feedback problem for discrete-time systems when complete set of state variables is not available. It has been reported that quasi-Newton methods have substandard performance on this problem. A structured quasi-Newton method with trust region globalization is analyzed and studied for solving this problem. Moreover, the classical Anderson-Moore method is enhanced by using the trust region mechanism to ensure global convergence instead of the line search technique. The algorithms are tested numerically on test problems of engineering applications.     

CP decomposition for tensors via alternating least squares with QR decomposition

The CP tensor decomposition is used in applications such as machine learning and signal processing to discover latent low-rank structure in multidimensional data. Computing a CP decomposition via an alternating least squares (ALS) method reduces the problem to several linear least squares problems. The standard way to solve these linear least squares subproblems is to use the normal equations, which inherit special tensor structure that can be exploited for computational efficiency. However, the normal equations are sensitive to numerical ill-conditioning, which can compromise the results of the decomposition. In this paper, we develop versions of the CP-ALS algorithm using the QR decomposition and the singular value decomposition, which are more numerically stable than the normal equations, to solve the linear least squares problems. Our algorithms utilize the tensor structure of the CP-ALS subproblems efficiently, have the same complexity as the standard CP-ALS algorithm when the input is dense and the rank is small, and are shown via examples to produce more stable results when ill-conditioning is present. Our MATLAB implementation achieves the same running time as the standard algorithm for small ranks, and we show that the new methods can obtain lower approximation error.     

解非线性规划问题的不精确线性搜索SQP滤子方法

本文用序列二次规划方法(SQP)结合Wolfe-Powell不精确线性搜索准则求解非线性规划问题.Wolfe-Powell准则是一种能够使目标函数获得充分下降而运行时间较省的确定步长方法.不精确线性搜索滤子方法比较其它结合精确线性搜索和信赖域方法求解问题的滤子方法更灵活更易实现.如果目标函数的预测下降量为负,我们的工作将主要利用可行恢复项改善可行性.一般条件下,本文提出的算法较易实现,且具有全局收敛性.数值试验显示了算法的有效性.     

解线性约束优化问题的新锥模型信赖域法

本文提出了一个解线性等式约束优化问题的新锥模型信赖域方法.论文采用零空间技术消除了新锥模型子问题中的线性等式约束,用折线法求解转换后的子问题,并给出了解线性等式约束优化问题的信赖域方法.论文提出并证明了该方法的全局收敛性,并给出了该方法解线性等式约束优化问题的数值实验.理论和数值实验结果表明新锥模型信赖域方法是有效的,这给出了用新锥模型进一步研究非线性优化的基础.     

Multigrid solution of high order discretisation for three-dimensional biharmonic equation with Dirichlet boundary conditions of second kind

In this paper, we propose two compact finite difference approximations for three-dimensional biharmonic equation with Dirichlet boundary conditions of second kind. In these methods there is no need to define special formulas near the boundaries and boundary conditions are incorporated with these techniques. The unknown solution and its second derivatives are carried as unknowns at grid points. We derive second-order and fourth-order approximations on a 27 point compact stencil. Classical iteration methods such as Gauss–Seidel and SOR for solving the linear system arising from the second-order and fourth-order discretisation suffer from slow convergence. In order to overcome this problem we use multigrid method which exhibit grid-independent convergence and solve the linear system of equations in small amount of computer time. The fourth-order finite difference approximations are used to solve several test problems and produce high accurate numerical solutions.     

A globally convergent trust region algorithm for optimization with general constraints and simple bounds

1.IntroductionInthispaper,weconsiderthefollowingnonlinearprogr~ngproblemwherec(x)=(c,(x),c2(2),',We(.))',i(x)andci(x)(i=1,2,',m)arerealfunctions*ThisworkissupPOrtedbytheNationalNaturalScienceFOundationofChinaandtheManagement,DecisionandinformationSystemLab,theChineseAcademyofSciences.definedinD={xEReIISx5u}.Weassumethath相似文献   

Minimizing total tardiness in a scheduling problem with a learning effect

Minimizing of total tardiness is one of the most studied topics on single machine problems. Researchers develop a number of optimizing and heuristic methods to solve this NP-hard problem. In this paper, the problem of minimizing total tardiness is examined in a learning effect situation. The concept of learning effects describes the reduction of processing times arising from process repetition. A 0–1 integer programming model is developed to solve the problem. Also, a random search, the tabu search and the simulated annealing-based methods are proposed for the problem and the solutions of the large size problems with up to 1000 jobs are found by these methods. To the best of our knowledge, no works exists on the total tardiness problem with a learning effect tackled in this paper.     

Convergence of algorithms for perturbed optimization problems

Infinite-dimensional optimization problems occur in various applications such as optimal control problems and parameter identification problems. If these problems are solved numerically the methods require a discretization which can be viewed as a perturbation of the data of the optimization problem. In this case the expected convergence behavior of the numerical method used to solve the problem does not only depend on the discretized problem but also on the original one. Algorithms which are analyzed include the gradient projection method, conditional gradient method, Newton's method and quasi-Newton methods for unconstrained and constrained problems with simple constraints.     

A cutting plane method for bilevel linear programming with interval coefficients

This article considers the bilevel linear programming problem with interval coefficients in both objective functions. We propose a cutting plane method to solve such a problem. In order to obtain the best and worst optimal solutions, two types of cutting plane methods are developed based on the fact that the best and worst optimal solutions of this kind of problem occur at extreme points of its constraint region. The main idea of the proposed methods is to solve a sequence of linear programming problems with cutting planes that are successively introduced until the best and worst optimal solutions are found. Finally, we extend the two algorithms proposed to compute the best and worst optimal solutions of the general bilevel linear programming problem with interval coefficients in the objective functions as well as in the constraints.