共查询到20条相似文献,搜索用时 15 毫秒
1.
In this paper, we proposed an implementation of stochastic perturbation of reduced gradient and bisection (SPRGB) method for optimizing a non-convex differentiable function subject to linear equality constraints and non-negativity bounds on the variables. In particular, at each iteration, we compute a search direction by reduced gradient, and optimal line search by bisection algorithm along this direction yields a decrease in the objective value. SPRGB method is desired to establish the global convergence of the algorithm. An implementation and tests of SPRGB algorithm are given, and some numerical results of large-scale problems are presented, which show the efficient of this approach. 相似文献
2.
Jin-bao Jian Xing-de Mo Li-juan Qiu Su-ming Yang Fu-sheng Wang 《Journal of Optimization Theory and Applications》2014,160(1):158-188
In this paper, the nonlinear minimax problems with inequality constraints are discussed. Based on the idea of simple sequential quadratically constrained quadratic programming algorithm for smooth constrained optimization, an alternative algorithm for solving the discussed problems is proposed. Unlike the previous work, at each iteration, a feasible direction of descent called main search direction is obtained by solving only one subprogram which is composed of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the constrained functions. Then a high-order correction direction used to avoid the Maratos effect is computed by updating the main search direction with a system of linear equations. The proposed algorithm possesses global convergence under weak Mangasarian–Fromovitz constraint qualification and superlinear convergence under suitable conditions with the upper-level strict complementarity. At last, some preliminary numerical results are reported. 相似文献
3.
PSB (Powell-Symmetric-Broyden) algorithm is a very important algorithm and has been extensively used in trust region methods. However, there are few studies on the line search type PSB algorithm. The primary reason is that the direction generated by this class of algorithms is not necessarily a descent direction of the objective function. In this paper, by combining a nonmonotone line search technique with the PSB method, we propose a nonmonotone PSB algorithm for solving unconstrained optimization. Under proper conditions, we establish global convergence and superlinear convergence of the proposed algorithm. At the same time we verify the efficiency of the proposed algorithm by some numerical experiments. 相似文献
4.
5.
投影信赖域策略结合非单调线搜索算法解有界约束非线性半光滑方程组.基于简单有界约束的非线性优化问题构建信赖域子问题,半光滑类牛顿步在可行域投影得到投影牛顿的试探步,获得新的搜索方向,结合非单调线搜索技术得到回代步,获得新的步长.在合理的条件下,证明算法不仅具有整体收敛性且保持超线性收敛速率.引入非单调技术能克服高度非线性的病态问题,加速收敛性进程,得到超线性收敛速率. 相似文献
6.
7.
A new subspace minimization conjugate gradient algorithm with a nonmonotone Wolfe line search is proposed and analyzed. In the scheme, we propose two choices of the search direction by minimizing a quadratic approximation of the objective function in special subspaces, and state criterions on how to choose the direction. Under given conditions, we obtain the significant conclusion that each choice of the direction satisfies the sufficient descent property. Based on the idea on how the function is close to a quadratic function, a new strategy for choosing the initial stepsize is presented for the line search. With the used nonmonotone Wolfe line search, we prove the global convergence of the proposed method for general nonlinear functions under mild assumptions. Numerical comparisons are given with well-known CGOPT and CG_DESCENT and show that the proposed algorithm is very promising. 相似文献
8.
《Optimization》2012,61(2):137-150
An algorithm for addressing multiple objective linear programming (MOLP) problems is presented. The algorithm modifies the path-following primal-dual algorithm to MOLP problems by using the single objective algorithm to generate interior search directions and later combine them to derive a single direction along which to step to the next iterate. Combining the different interior search directions is done by interacting with a Decision Maker (DM) to obtain locally-relevant preference information for the value vectors along these directions. This preference information is then used to derive an approximation to the gradient of an implicity-known utility function, and using a projection of this gradient provides a direction gradient of an implicitly-known utility function, and using a projection of this gradient provides a direction vector along which we step to the next iterate. At each iteration the algorithm also generates boundary points that aid in deriving the combined search direction. We refer to these boundary points, generated sequentially during the process, as anchor points that serve as candidate solutions at which to terminate the iterative process. 相似文献
9.
Changyu Wang Chengyun Gao Zhenjun Shi 《Computational Optimization and Applications》1997,7(2):239-253
In this paper, we extend the ordinary discrete type facility location problems to continuous type ones. Unlike the discrete type facility location problem in which the objective function isn't everywhere differentiable, the objective function in the continuous type facility location problem is strictly convex and continuously differentiable. An algorithm without line search for solving the continuous type facility location problems is proposed and its global convergence, linear convergence rate is proved. Numerical experiments illustrate that the algorithm suggested in this paper have smaller amount of computation, quicker convergence rate than the gradient method and conjugate direction method in some sense. 相似文献
10.
本文结合次梯度选取技术及割平面法和强次可行方向法的思想,提出了一个求解目标函数非光滑约束优化问题的强次可行方向算法.通过设计一个新的寻找搜索方向子问题和构造新型线搜索,算法不仅能接受不可行的初始点,而且能保持迭代点的强次可行性,同时避免在可行域外目标函数值的不适度增加.算法具备全局收敛性,且初步的数值试验表明算法是稳定有效的. 相似文献
11.
In this paper, a new spectral PRP conjugate gradient algorithm has been developed for solving unconstrained optimization problems, where the search direction was a kind of combination of the gradient and the obtained direction, and the steplength was obtained by the Wolfe-type inexact line search. It was proved that the search direction at each iteration is a descent direction of objective function. Under mild conditions, we have established the global convergence theorem of the proposed method. Numerical results showed that the algorithm is promising, particularly, compared with the existing several main methods. 相似文献
12.
In this paper, we are concerned with the conjugate gradient methods for solving unconstrained optimization problems. It is well-known that the direction generated by a conjugate gradient method may not be a descent direction of the objective function. In this paper, we take a little modification to the Fletcher–Reeves (FR) method such that the direction generated by the modified method provides a descent direction for the objective function. This property depends neither on the line search used, nor on the convexity of the objective function. Moreover, the modified method reduces to the standard FR method if line search is exact. Under mild conditions, we prove that the modified method with Armijo-type line search is globally convergent even if the objective function is nonconvex. We also present some numerical results to show the efficiency of the proposed method.Supported by the 973 project (2004CB719402) and the NSF foundation (10471036) of China. 相似文献
13.
A successive quadratic programming method for a class of constrained nonsmooth optimization problems
Masao Fukushima 《Mathematical Programming》1990,49(1-3):231-251
In this paper we present an algorithm for solving nonlinear programming problems where the objective function contains a possibly nonsmooth convex term. The algorithm successively solves direction finding subproblems which are quadratic programming problems constructed by exploiting the special feature of the objective function. An exact penalty function is used to determine a step-size, once a search direction thus obtained is judged to yield a sufficient reduction in the penalty function value. The penalty parameter is adjusted to a suitable value automatically. Under appropriate assumptions, the algorithm is shown to produce an approximate optimal solution to the problem with any desirable accuracy in a finite number of iterations. 相似文献
14.
《European Journal of Operational Research》1998,105(1):236-246
This paper introduces an algorithm for univariate optimization using linear lower bounding functions (LLBF's). An LLBF over an interval is a linear function which lies below the given function over an interval and matches the given function at one end point of the interval. We first present an algorithm using LLBF's for finding the nearest root of a function in a search direction. When the root-finding method is applied to the derivative of an objective function, it is an optimization algorithm which guarantees to locate the nearest extremum along a search direction. For univariate optimization, we show that this approach is a Newton-type method, which is globally convergent with superlinear convergence rate. The applications of this algorithm to global optimization and other optimization problems are also discussed. 相似文献
15.
一种修正的谱CD共轭梯度算法的全局收敛性 总被引:2,自引:0,他引:2
In this paper,we present a new nonlinear modified spectral CD conjugate gradient method for solving large scale unconstrained optimization problems.The direction generated by the method is a descent direction for the objective function,and this property depends neither on the line search rule,nor on the convexity of the objective function.Moreover,the modified method reduces to the standard CD method if line search is exact.Under some mild conditions,we prove that the modified method with line search is globally convergent even if the objective function is nonconvex.Preliminary numerical results show that the proposed method is very promising. 相似文献
16.
Sequential quadratically constrained quadratic programming norm-relaxed algorithm of strongly sub-feasible directions 总被引:1,自引:0,他引:1
Jin-Bao Jian Chun-Ming Tang Hai-Yan Zheng 《European Journal of Operational Research》2010,200(3):645-657
In this paper, we present a sequential quadratically constrained quadratic programming (SQCQP) norm-relaxed algorithm of strongly sub-feasible directions for the solution of inequality constrained optimization problems. By introducing a new unified line search and making use of the idea of strongly sub-feasible direction method, the proposed algorithm can well combine the phase of finding a feasible point (by finite iterations) and the phase of a feasible descent norm-relaxed SQCQP algorithm. Moreover, the former phase can preserve the “sub-feasibility” of the current iteration, and control the increase of the objective function. At each iteration, only a consistent convex quadratically constrained quadratic programming problem needs to be solved to obtain a search direction. Without any other correctional directions, the global, superlinear and a certain quadratic convergence (which is between 1-step and 2-step quadratic convergence) properties are proved under reasonable assumptions. Finally, some preliminary numerical results show that the proposed algorithm is also encouraging. 相似文献
17.
一种改进的禁忌搜索算法及其在选址问题中的应用 总被引:2,自引:0,他引:2
本文研究了选址问题中无容量限制的p-中值问题,在Rolland等人提出的有效禁忌搜索算法基础上,提出了一种以目标函数变化量作为评价函数的改进禁忌搜索算法,并进行了理论分析,然后将其与有效禁忌搜索算法作了性能比较.通过比较三个公共测试数据集的计算结果,验证了本文提出的禁忌搜索算法的可行性和有效性. 相似文献
18.
A new adaptive subspace minimization three-term conjugate gradient algorithm with nonmonotone line search is introduced and analyzed in this paper.The search directions are computed by minimizing a quadratic approximation of the objective function on special subspaces,and we also proposed an adaptive rule for choosing different searching directions at each iteration.We obtain a significant conclusion that the each choice of the search directions satisfies the sufficient descent condition.With the used nonmonotone line search,we prove that the new algorithm is globally convergent for general nonlinear functions under some mild assumptions.Numerical experiments show that the proposed algorithm is promising for the given test problem set. 相似文献
19.
Based on Fermat’s principle and the automatic optimization mechanism in the propagation process of light,an optimal searching algorithm named light ray optimization is presented,where the laws of refraction and reflection of light rays are integrated into searching process of optimization.In this algorithm,coordinate space is assumed to be the space that is full of media with different refractivities,then the space is divided by grids,and finally the searching path is assumed to be the propagation path of light rays.With the law of refraction,the search direction is deflected to the direction that makes the value of objective function decrease.With the law of reflection,the search direction is changed,which makes the search continue when it cannot keep going with refraction.Only the function values of objective problems are used and there is no artificial rule in light ray optimization,so it is simple and easy to realize.Theoretical analysis and the results of numerical experiments show that the algorithm is feasible and effective. 相似文献
20.
M. Sahba 《Journal of Optimization Theory and Applications》1987,52(2):291-309
A new globally convergent algorithm for minimizing an objective function subject to equality and inequality constraints is presented. The algorithm determines a search direction by first solving a linear program and using the information gained thereby to define a quadratic approximation, with a guaranteed solution, to the original problem; the solution of the quadratic problem is the desired search direction. The algorithm incorporates a new method for choosing the penalty parameter. Numerical results illustrate the performance of the algorithm.The author wishes to thank Professor D. Q. Mayne and Dr. F. A. Pantoja for critically reviewing the first draft of this paper, for their suggestions, criticism, and contributions to some of the proofs. Support of the UK Science Research and Engineering Council is gratefully acknowledged. 相似文献