A self-adaptive trust region method with line search based on a simple subproblem model

In this paper, based on a simple model of the trust region subproblem, we propose a new self-adaptive trust region method with a line search technique for solving unconstrained optimization problems. By use of the simple subproblem model, the new method needs less memory capacitance and computational complexity. And the trust region radius is adjusted with a new self-adaptive adjustment strategy which makes full use of the information at the current point. When the trial step results in an increase in the objective function, the method does not resolve the subproblem, but it performs a line search technique from the failed point. Convergence properties of the method are proved under certain conditions. Numerical experiments show that the new method is effective and attractive for large-scale optimization problems.     

A new nonmonotone adaptive trust region method based on simple quadratic models

Based on simple quadratic models of the trust region subproblem, we combine the trust region method with the nonmonotone and adaptive techniques to propose a new nonmonotone adaptive trust region algorithm for unconstrained optimization. Unlike traditional trust region method, our trust region subproblem is very simple by using a new scale approximation of the minimizing function??s Hessian. The new method needs less memory capacitance and computational complexity. The convergence results of the method are proved under certain conditions. Numerical results show that the new method is effective and attractive for large scale unconstrained problems.     

GLOBAL CONVERGENCE OF QPFTH METHOD FOR LARGE-SCALE NONLINEAR SPARSE CONSTRAINED OPTIMIZATION

1.IntroductionIn[6],aQPFTHmethodwasproposedforsolvingthefollowingnonlinearprogrammingproblemwherefunctionsf:R"-- RIandgi:R"-- R',jeJaretwicecontinuouslydifferentiable.TheQPFTHalgorithmwasdevelopedforsolvingsparselarge-scaleproblem(l.l)andwastwo-stepQ-quadraticallyandR-quadraticallyconvergent(see[6]).Theglobalconvergenceofthisalgorithmisdiscussedindetailinthispaper.Forthefollowinginvestigationwerequiresomenotationsandassumptions.TheLagrangianofproblem(1.1)isdefinedbyFOundationofJiangs…     

一个无约束有限内存信赖域方法及其实现

本文针对大规模无约束优化问题研究了一个新的有限内存信赖域实现方法,提出了一个在有限维（维数≤2m＋1）子空间上精确求解信赖域子问题的方法,大大减少了计算量;分析了方法的收敛性,并详细给出了数值计算方法,最后通过数值实验验证了方法的有效性.     

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.     

Nonmonotone adaptive trust region method based on simple conic model for unconstrained optimization

We propose a nonmonotone adaptive trust region method based on simple conic model for unconstrained optimization. Unlike traditional trust region methods, the subproblem in our method is a simple conic model, where the Hessian of the objective function is approximated by a scalar matrix. The trust region radius is adjusted with a new self-adaptive adjustment strategy which makes use of the information of the previous iteration and current iteration. The new method needs less memory and computational efforts. The global convergence and Q-superlinear convergence of the algorithm are established under the mild conditions. Numerical results on a series of standard test problems are reported to show that the new method is effective and attractive for large scale unconstrained optimization problems.     

A convergence proof for linear mean value cross decomposition

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition that eliminates the need for using the Benders or Dantzig-Wolfe master problem. It is a generalization of the Brown-Robinson method for a finite matrix game and can also be considered as a generalization of the Kornai-Liptak method. It is based on the subproblem phase in cross decomposition, where we iterate between the dual subproblem and the primal subproblem. As input to the dual subproblem we use the average of a part of all dual solutions of the primal subproblem, and as input to the primal subproblem we use the average of a part of all primal solutions of the dual subproblem. In this paper we give a new proof of convergence for this procedure. Previously convergence has only been shown for the application to a special separable case (which covers the Kornai-Liptak method), by showing equivalence to the Brown-Robinson method.     

Combining nonmonotone conic trust region and line search techniques for unconstrained optimization

In this paper, we propose a trust region method for unconstrained optimization that can be regarded as a combination of conic model, nonmonotone and line search techniques. Unlike in traditional trust region methods, the subproblem of our algorithm is the conic minimization subproblem; moreover, our algorithm performs a nonmonotone line search to find the next iteration point when a trial step is not accepted, instead of resolving the subproblem. The global and superlinear convergence results for the algorithm are established under reasonable assumptions. Numerical results show that the new method is efficient for unconstrained optimization problems.     

An adaptive trust region method and its convergence

In this paper, a new trust region subproblem is proposed. The trust radius in the new subproblem adjusts itself adaptively. As a result, an adaptive trust region method is constructed based on the new trust region subproblem. The local and global convergence results of the adaptive trust region method are proved. Numerical results indicate that the new method is very efficient.     

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

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

A new modified nonmonotone adaptive trust region method for unconstrained optimization

In this paper, we present an adaptive trust region method for solving unconstrained optimization problems which combines nonmonotone technique with a new update rule for the trust region radius. At each iteration, our method can adjust the trust region radius of related subproblem. We construct a new ratio to adjust the next trust region radius which is different from the ratio in the traditional trust region methods. The global and superlinear convergence results of the method are established under reasonable assumptions. Numerical results show that the new method is efficient for unconstrained optimization problems.     

带非线性不等式约束优化问题的信赖域算法

借助于KKT条件和NCP函数,提出了求解带非线性不等式约束优化问题的信赖域算法.该算法在每一步迭代时,不必求解带信赖域界的二次规划子问题,仅需求一线性方程组系统.在适当的假设条件下,它还是整体收敛的和局部超线性收敛的.数值实验结果表明该方法是有效的.     

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

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

张量方法在信赖域算法中的应用

信赖域算法是求解无约束优化问题的一种有效的算法.对于该算法的子问题,本文将原来目标函数的二次模型扩展成四次张量模型,提出了一个带信赖域约束的四次张量模型优化问题的求解算法.该方法的最大特点是:不仅在张量模型的非稳定点可以得到下降方向及相应的迭代步长,而且在非局部极小值点的稳定点也可以得到下降方向及相应的迭代步长,从而在算法产生的迭代点列中存在一个子列收敛到信赖域子问题的局部极小值点.     

一种具有非线性约束线性规划全局优化算法

本文提出了一种新的适用于处理非线性约束下线性规划问题的全局优化算法。该算法通过构造子问题来寻找优于当前局部最优解的可行解。该子问题可通过模拟退火算法来解决。通过求解一系列的子问题,当前最优解被不断地更新,最终求得全局最优解。最后,本算法应用于几个典型例题,并与罚函数法相比较,数值结果表明该算法是可行的,有效的。     

Solving Variational Inequality Problems with Linear Constraints by a Proximal Decomposition Algorithm

The alternating direction method solves large scale variational inequality problems with linear constraints via solving a series of small scale variational inequality problems with simple constraints. The algorithm is attractive if the subproblems can be solved efficiently and exactly. However, the subproblem is itself variational inequality problem, which is structurally also difficult to solve. In this paper, we develop a new decomposition algorithm, which, at each iteration, just solves a system of well-conditioned linear equations and performs a line search. We allow to solve the subproblem approximately and the accuracy criterion is the constructive one developed recently by Solodov and Svaiter. Under mild assumptions on the problem's data, the algorithm is proved to converge globally. Some preliminary computational results are also reported to illustrate the efficiency of the algorithm.     

Mean value cross decomposition applied to integer programming problems

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition, that eliminates the need for using the Benders or Dantzig-Wolfe master problems. As input to the dual subproblem the average of a part of all known dual solutions of the primal subproblem is used, and as input to the primal subproblem the average of a part of all known primal solutions of the dual subproblem. In this paper we study the lower bounds on the optimal objective function value of (linear) pure integer programming problems obtainable by the application of mean value cross decomposition, and find that this approach can be used to get lower bounds ranging from the bound obtained by the LP-relaxation to the bound obtained by the Lagrangean dual. We examplify by applying the technique to the clustering problem and give some preliminary computational results.     

A new method of moving asymptotes for large-scale linearly equality-constrained minimization

A new method of moving asymptotes for large-scale minimization subject to linear equality constraints is discussed.In this method,linear equality constraints are deleted with null space technique and the descending direction is obtained by solving a convex separable subproblem of moving asymptotes in each iteration. New rules for controlling the asymptotes parameters are designed and the global convergence of the method under some reasonable conditions is established and proved.The numerical results show that the new method may be capable of processing some large scale problems.     

Modified subspace limited memory BFGS algorithm for large-scale bound constrained optimization

In this paper, a subspace limited memory BFGS algorithm for solving large-scale bound constrained optimization problems is developed. It is modifications of the subspace limited memory quasi-Newton method proposed by Ni and Yuan [Q. Ni, Y.X. Yuan, A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization, Math. Comput. 66 (1997) 1509–1520]. An important property of our proposed method is that more limited memory BFGS update is used. Under appropriate conditions, the global convergence of the method is established. The implementations of the method on CUTE test problems are presented, which indicate the modifications are beneficial to the performance of the algorithm.     

An algorithm for solving new trust region subproblem with conic model

The new trust region subproblem with the conic model was proposed in 2005, and was divided into three different cases. The first two cases can be converted into a quadratic model or a convex problem with quadratic constraints, while the third one is a nonconvex problem. In this paper, first we analyze the nonconvex problem, and reduce it to two convex problems. Then we discuss some dual properties of these problems and give an algorithm for solving them. At last, we present an algorithm for solving the new trust region subproblem with the conic model and report some numerical examples to illustrate the efficiency of the algorithm.