首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 125 毫秒
1.
在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用.本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始-对偶内点算法.这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用.我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O(√n log n 10g n/ε)和O(√n log n/ε),这里n是半正定规划问题的维数.最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性.  相似文献   

2.
在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用。本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始。对偶内点算法。这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用。我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O(√n log n log n/c)和O(√n log n/ε),这里n是半正定规划问题的维数。最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性。  相似文献   

3.
本文研究了P*(κ)线性互补问题的大步校正原始-对偶内点算法.基于一个强凸且不同于通常的对数函数和自正则函数的新核函数,对具有严格可行初始点的该问题,算法获得的迭代复杂性√为O(1+2κ)n(log n)2lognε,该结果缩小了大步校正内点算法的实际计算与理论复杂性界之间的差距.  相似文献   

4.
基于邻近度量函数的最小值,对P*(κ)阵线性互补问题提出了一种新的宽邻域预估-校正算法,在较一般的条件下,证明了算法的迭代复杂性为O(κ+1)23n log(x0ε)Ts0.算法既可视为Miao的P*(κ)阵线性互补问题Mizuno-Todd-Ye预估-校正内点算法的一种变形,也可以视为最近Zhao提出的线性规划基于邻近度量函数最小值的宽邻域内点算法的推广.  相似文献   

5.
由Nesterov和Nemirovski[4]创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的.  相似文献   

6.
本文采用一簇新的核函数设计原始-对偶内点算法用于解决P*(κ)线性互补问题.通过利用一些优良、简洁的分析工具,证明该算法具有O(q(2κ+1)n1/p(logn)1+1/qlog(n/ε))迭代复杂性.  相似文献   

7.
基于一类带有参数θ的新方向,提出了求解单调线性互补问题的宽邻域路径跟踪内点算法,且当θ=1时即为经典牛顿方向.当取θ为与问题规模n无关的常数时,算法具有O(nL)迭代复杂性,其中L是输入数据的长度,这与经典宽邻域算法的复杂性相同;当取θ=(n/βτ)~(1/2)时,算法具有O(n~(1/2)L)迭代复杂性,这里的β,τ是邻域参数,这与窄邻域算法的复杂性相同.这是首次研究包括经典宽邻域路径跟踪算法的一类内点算法,给出了统一的算法框架和收敛性分析方法.  相似文献   

8.
本文通过使用高界校正技术,给出了一个求解P*(k)阵线性互补问题的宽域路径跟踪算法,其迭代复杂性为渐近O((k+1)L).通过使用秩-1校正技术,其每步的计算复杂性从常规的O(n3)约减到O(n2.5);因此,算法总的计算复杂性为渐近O((k+1)n3L).  相似文献   

9.
本文提出一个二阶锥线性互补问题的长步原始对偶内点法,搜索方向由一个一般的核函数来定义.如果给出初始的严格内点,可以得到本算法的复杂性为O((1+2k)llog(lμ0/ε)).  相似文献   

10.
本文对P_*(κ)线性互补问题设计了一种基于核函数的全-Newton步不可行内点算法,是对Mansouri等人提出的单调线性互补问题全-Newton步不可行内点算法的改进与推广.算法的主迭代由一个可行步和几个中心步构成且可行步采用小步校正.通过建立和应用一些新的技术性结果,证明了算法的多项式复杂性为O((1+2κ)~(3/2)(1og_2log_264(1+2κ))nlogmax{(x0)Ts0,||r0||}/ε),当k=0时,与当前单调线性互补问题的不可行内点算法最好的迭代复杂性界一致.最后,用Matlab数值实验验证了算法的可行性.  相似文献   

11.
12.
In this paper, we present a large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. The proposed function is strongly convex. It is not self-regular function and also the usual logarithmic function. The goal of this paper is to investigate such a kernel function and show that the algorithm has favorable complexity bound in terms of the elegant analytic properties of the kernel function. The complexity bound is shown to be $O\left( {\sqrt n \left( {\log n} \right)^2 \log \frac{n} {\varepsilon }} \right)$ . This bound is better than that by the classical primal-dual interior-point methods based on logarithmic barrier function and recent kernel functions introduced by some authors in optimization fields. Some computational results have been provided.  相似文献   

13.
In this paper, we propose a large-update primal-dual interior point algorithm for P*(κ)-linear complementarity problem. The method is based on a new class of kernel functions which is neither classical logarithmic function nor self-regular functions. It is determines both search directions and the proximity measure between the iterate and the center path. We show that if a strictly feasible starting point is available, then the new algorithm has \(o\left( {(1 + 2k)p\sqrt n {{\left( {\frac{1}{p}\log n + 1} \right)}^2}\log \frac{n}{\varepsilon }} \right)\)iteration complexity which becomes \(o\left( {(1 + 2k)\sqrt n log{\kern 1pt} {\kern 1pt} n\log \frac{n}{\varepsilon }} \right)\)with special choice of the parameter p. It is matches the currently best known iteration bound for P*(κ)-linear complementarity problem. Some computational results have been provided.  相似文献   

14.
In this paper, we introduce the notion of a self-regular function. Such a function is strongly convex and smooth coercive on its domain, the positive real axis. We show that any such function induces a so-called self-regular proximity function and a corresponding search direction for primal-dual path-following interior-point methods (IPMs) for solving linear optimization (LO) problems. It is proved that the new large-update IPMs enjoy a polynomial ?(n log) iteration bound, where q≥1 is the so-called barrier degree of the kernel function underlying the algorithm. The constant hidden in the ?-symbol depends on q and the growth degree p≥1 of the kernel function. When choosing the kernel function appropriately the new large-update IPMs have a polynomial ?(lognlog) iteration bound, thus improving the currently best known bound for large-update methods by almost a factor . Our unified analysis provides also the ?(log) best known iteration bound of small-update IPMs. At each iteration, we need to solve only one linear system. An extension of the above results to semidefinite optimization (SDO) is also presented. Received: March 2000 / Accepted: December 2001?Published online April 12, 2002  相似文献   

15.
16.
基于一个自协调指数核函数, 设计求解二阶锥规划的原始-对偶内点算法. 根据自协调指数核函数的二阶导数与三阶导数的特殊关系, 在求解问题的中心路径时, 用牛顿方向代替了负梯度方向来确定搜索方向. 由于自协调指数核函数不具有``Eligible'性质, 在分析算法的迭代界时, 利用牛顿方法求解目标函数满足自协调性质的无约束优化问题的技术, 估计算法内迭代中自协调指数核函数确定的障碍函数的下降量, 得到原始-对偶内点算法大步校正的迭代界O(2N\frac{\log2N}{\varepsilon}), 这里N是二阶锥的个数. 这个迭代界与线性规划情形下的迭代界一致. 最后, 通过数值算例验证了算法的有效性.  相似文献   

17.
In this paper we propose a class of new large-update primal-dual interior-point algorithms for P *(κ) nonlinear complementarity problem (NCP), which are based on a class of kernel functions investigated by Bai et al. in their recent work for linear optimization (LO). The arguments for the algorithms are followed as Peng et al.’s for P *(κ) complementarity problem based on the self-regular functions [Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms, Princeton University Press, Princeton, 2002]. It is worth mentioning that since this class of kernel functions includes a class of non-self-regular functions as special case, so our algorithms are different from Peng et al.’s and the corresponding analysis is simpler than theirs. The ultimate goal of the paper is to show that the algorithms based on these functions have favorable polynomial complexity.  相似文献   

18.
In this paper, we propose a large-update primal-dual interior point method for solving a class of linear complementarity problems based on a new kernel function. The main aspects distinguishing our proposed kernel function from the others are as follows: Firstly, it incorporates a specific trigonometric function in its growth term, and secondly, the corresponding barrier term takes finite values at the boundary of the feasible region. We show that, by resorting to relatively simple techniques, the primal-dual interior point methods designed for a specific class of linear complementarity problems enjoy the so-called best-known iteration complexity for the large-update methods.  相似文献   

19.
Recent studies on the kernel function-based primal-dual interior-point algorithms indicate that a kernel function not only represents a measure of the distance between the iteration and the central path, but also plays a critical role in improving the computational complexity of an interior-point algorithm. In this paper, we propose a new class of parameterized kernel functions for the development of primal-dual interior-point algorithms for solving linear programming problems. The properties of the proposed kernel functions and corresponding parameters are investigated. The results lead to a complexity bounds of ${O\left(\sqrt{n}\,{\rm log}\,n\,{\rm log}\,\frac{n}{\epsilon}\right)}$ for the large-update primal-dual interior point methods. To the best of our knowledge, this is the best known bound achieved.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号