共查询到19条相似文献,搜索用时 125 毫秒
1.
给出线性规划原始对偶内点算法的一个单变量指数型核函数.首先研究了这个指数型核函数的性质以及其对应的障碍函数.其次,基于这个指数型核函数,设计了求解线性规划问题的原始对偶内点算法,得到了目前小步算法最好的理论迭代界.最后,通过数值算例比较了基于指数型核函数的原始对偶内点算法和基于对数型核函数的原始对偶内点算法的计算效果. 相似文献
2.
由Nesterov和Nemirovski[4]创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的. 相似文献
3.
本文对广义线性模型中的连接函数引入新的形状参数,提出带有额外参数连接函数的一类广义线性模型;讨论了参数的极大似然估计,并给出了迭代公式;推广了关于广义Logistic 回归模型的额外参数估计的一个结果,并提出了广义对数线性模型. 相似文献
4.
基于一个自协调指数核函数, 设计求解二阶锥规划的原始-对偶内点算法. 根据自协调指数核函数的二阶导数与三阶导数的特殊关系, 在求解问题的中心路径时, 用牛顿方向代替了负梯度方向来确定搜索方向. 由于自协调指数核函数不具有``Eligible'性质, 在分析算法的迭代界时, 利用牛顿方法求解目标函数满足自协调性质的无约束优化问题的技术, 估计算法内迭代中自协调指数核函数确定的障碍函数的下降量, 得到原始-对偶内点算法大步校正的迭代界O(2N\frac{\log2N}{\varepsilon}), 这里N是二阶锥的个数. 这个迭代界与线性规划情形下的迭代界一致. 最后, 通过数值算例验证了算法的有效性. 相似文献
5.
6.
在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用.本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始-对偶内点算法.这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用.我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O(√n log n 10g n/ε)和O(√n log n/ε),这里n是半正定规划问题的维数.最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性. 相似文献
7.
对约束优化问题给出了一类光滑罚算法.它是基于一类光滑逼近精确罚函数 l_p(p\in(0,1]) 的光滑函数 L_p 而提出的.在非常弱的条件下, 建立了算法的一个摄动定理, 导出了算法的全局收敛性.特别地, 在广义Mangasarian-Fromovitz约束规范假设下, 证明了当 p=1 时, 算法经过有限步迭代后, 所有迭代点都是原问题的可行解; p\in(0,1) 时,算法经过有限迭代后, 所有迭代点都是原问题可行解集的内点. 相似文献
8.
首先提出用Lap lace逼近方法对非线性再生散度随机效应模型的边缘对数似然函数进行近似,然后基于近似的边缘对数似然函数利用F isher'sscoring迭代算法得到了模型参数的极大似然估计.模拟研究和实例分析表明了该算法的可行性. 相似文献
9.
10.
《数学的实践与认识》2017,(24)
利用不动点原理,得到了求解一类障碍问题的隐式投影算法.采用中心差分格式将障碍问题离散为一个线性互补问题,从而得到了基于投影形式的隐式算法.该方法的每一步迭代只需要求解一个线性方程组.用投影性质很容易证明算法收敛性.给出了具体的算法过程,数值算例结果和理论分析是一致的. 相似文献
11.
An infeasible interior-point method (IIPM) for solving linear optimization problems based on a kernel function with trigonometric barrier term is analysed. In each iteration, the algorithm involves a feasibility step and several centring steps. The centring step is based on classical Newton’s direction, while we used a kernel function with trigonometric barrier term in the algorithm to induce the feasibility step. The complexity result coincides with the best-known iteration bound for IIPMs. To our knowledge, this is the first full-Newton step IIPM based on a kernel function with trigonometric barrier term. 相似文献
12.
We describe a primal-dual interior point algorithm for linear programming problems which requires a total of
number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. 相似文献
13.
Ming Wang Zhang 《数学学报(英文版)》2012,28(11):2313-2328
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. 相似文献
14.
M. El Ghami Z.A. Guennoun S. Bouali T. Steihaug 《Journal of Computational and Applied Mathematics》2012
In this paper, we present a new barrier function for primal–dual interior-point methods in linear optimization. The proposed kernel function has a trigonometric barrier term. It is shown that in the interior-point methods based on this function for large-update methods, the iteration bound is improved significantly. For small-update interior-point methods, the iteration bound is the best currently known bound for primal–dual interior-point methods. 相似文献
15.
In this paper we list several useful properties of central points in linear programming problems. We study the logarithmic barrier function, the analytic center and the central path, relating the proximity measures and scaled Euclidean distances defined for the primal and primal–dual problems. We study the Newton centering steps, and show how large the short steps used in path following algorithms can actually be, and what variation can be ensured for the barrier function in each iteration of such methods. We relate the primal and primal–dual Newton centering steps and propose a primal-only path following algorithm for linear programming. 相似文献
16.
This paper extends prior work by the authors on solving nonlinear least squares unconstrained problems using a factorized
quasi-Newton technique. With this aim we use a primal-dual interior-point algorithm for nonconvex nonlinear programming. The
factorized quasi-Newton technique is now applied to the Hessian of the Lagrangian function for the transformed problem which
is based on a logarithmic barrier formulation. We emphasize the importance of establishing and maintaining symmetric quasi-definiteness
of the reduced KKT system. The algorithm then tries to choose a step size that reduces a merit function, and to select a penalty
parameter that ensures descent directions along the iterative process. Computational results are included for a variety of
least squares constrained problems and preliminary numerical testing indicates that the algorithm is robust and efficient
in practice. 相似文献
17.
Interior path following primal-dual algorithms. part II: Convex quadratic programming 总被引:4,自引:0,他引:4
We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of
number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. The total number of arithmetic operations is shown to be of the order of O(n
3
L). 相似文献
18.
We present an interior-point method for monotone linear complementarity problems over symmetric cones (SCLCP) that is based
on barrier functions which are defined by a large class of univariate functions, called eligible kernel functions. This class
is fairly general and includes the classical logarithmic function, the self-regular functions, as well as many non-self-regular
functions as special cases. We provide a unified analysis of the method and give a general scheme on how to calculate the
iteration bounds for the entire class. We also calculate the iteration bounds of both large-step and short-step versions of
the method for ten frequently used eligible kernel functions. For some of them we match the best known iteration bound for
large-step methods, while for short-step methods the best iteration bound is matched for all cases. The paper generalizes
results of Lesaja and Roos (SIAM J. Optim. 20(6):3014–3039, 2010) from P
∗(κ)-LCP over the non-negative orthant to monotone LCPs over symmetric cones. 相似文献
19.
最近,Salahi对线性规划提出了一个基于新的自适应参数校正策略的Mehrotra型预估-校正算法,该策略使其在不使用安全策略的情况下,证明了算法的多项式迭代复杂界.本文将这一算法推广到半定规划的情形.通过利用Zhang的对称化技术,得到了算法的多项式迭代复杂界,这与求解线性规划的相应算法有相同的迭代复杂性阶. 相似文献