共查询到20条相似文献,搜索用时 15 毫秒
1.
Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function 总被引:3,自引:0,他引:3
Interior-point methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity
and practical efficiency. Recently, J. Peng et al. introduced so-called self-regular kernel (and barrier) functions and designed
primal-dual interior-point algorithms based on self-regular proximities for linear optimization (LO) problems. They also extended
the approach for LO to SDO. In this paper we present a primal-dual interior-point algorithm for SDO problems based on a simple
kernel function which was first presented at the Proceedings of Industrial Symposium and Optimization Day, Australia, November 2002; the function is not self-regular. We derive the complexity analysis for algorithms based on this
kernel function, both with large- and small-updates. The complexity bounds are
and
, respectively, which are as good as those in the linear case.
Mathematics Subject Classifications (2000) 90C22, 90C31. 相似文献
2.
本文基于一个有限罚函数,设计了关于二阶锥优化问题的原始-对偶路径跟踪内点算法,由于该罚函数在可行域的边界取有限值,因而它不是常规的罚函数,尽管如此,它良好的解析性质使得我们能分析算法并得到基于大步校正和小步校正方法目前较好的多项式时间复杂性分别为O(N~(1/2)log N log N/ε)和O(N~(1/2)log N/ε),其中N为二阶锥的个数. 相似文献
3.
在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用。本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始。对偶内点算法。这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用。我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O(√n log n log n/c)和O(√n log n/ε),这里n是半正定规划问题的维数。最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性。 相似文献
4.
B. Kheirfam 《Numerical Functional Analysis & Optimization》2013,34(10):1322-1338
In this article, we present a new full Nesterov-Todd step infeasible interior-point method for second-order cone optimization based on a non-coercive kernel function. The main iteration consists of a so-called feasibility step and one centering step, whereas the earlier versions, in [4, 21], needed two additional centering steps. We use a kernel function to induce the feasibility step. The new algorithm reduces the searching steps in each iteration and tenders an interesting analysis for complexity bound. 相似文献
5.
由Nesterov和Nemirovski[4]创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的. 相似文献
6.
本文对经典对数障碍函数推广,给出了一个广义对数障碍函数.基于这个广义对数障碍函数设计了解半正定规划问题的原始-对偶内点算法.分析了该算法的复杂性,得到了一个理论迭代界,它与已有的基于经典对数障碍函数的算法的理论迭代界一致.同时,并给出了一个数值算例,阐明了函数的参数对算法运行时间的影响. 相似文献
7.
基于不可行内点法和预估-校正算法的思想,提出两个新的求解二阶锥规划的内点预估-校正算法.其预估方向分别是Newton方向和Euler方向,校正方向属于Alizadeh-Haeberly-Overton(AHO)方向的范畴.算法对于迭代点可行或不可行的情形都适用.主要构造了一个更简单的中心路径的邻域,这是有别于其它内点预估-校正算法的关键.在一些假设条件下,算法具有全局收敛性、线性和二次收敛速度,并获得了O(rln(ε0/ε))的迭代复杂性界,其中r表示二阶锥规划问题所包含的二阶锥约束的个数.数值实验结果表明提出的两个算法是有效的. 相似文献
8.
9.
Disjoint frames are interesting frames in Hilbert spaces, which were introduced by Han and Larson in [4]. In this article, we use disjoint frames to construct frames. In particular, we obtain some conditions for the linear combinations of frames to be frames where the coefficients in the combination may be operators. Our results generalize the corresponding results obtained by Han and Larson. Finally, we provide some examples to illustrate our constructions. 相似文献
10.
AbstractWe define a new interior-point method (IPM), which is suitable for solving symmetric optimization (SO) problems. The proposed algorithm is based on a new search direction. In order to obtain this direction, we apply the method of algebraically equivalent transformation on the centering equation of the central path. We prove that the associated barrier cannot be derived from a usual kernel function. Therefore, we introduce a new notion, namely the concept of the positive-asymptotic kernel function. We conclude that this algorithm solves the problem in polynomial time and has the same complexity as the best known IPMs for SO. 相似文献
11.
This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension
of the work of Roos (SIAM J. Optim. 16(4):1110–1136, 2006). The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel
function in the algorithm to induce the feasibility step. For parameter p∈[0,1], the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point
methods, that is, O(nlog n/ε).
This work was supported in part by the National Natural Science Foundation of China under Grant No. 10871098. 相似文献
12.
Petra Renáta Takács 《Optimization》2018,67(6):889-905
We introduce an interior-point method for symmetric optimization based on a new method for determining search directions. In order to accomplish this, we use a new equivalent algebraic transformation on the centring equation of the system which characterizes the central path. In this way, we obtain a new class of directions. We analyse a special case of this class, which leads to the new interior-point algorithm mentioned before. Another way to find the search directions is using barriers derived from kernel functions. We show that in our case the corresponding direction cannot be deduced from a usual kernel function. In spite of this fact, we prove the polynomial complexity of the proposed algorithm. 相似文献
13.
14.
Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation 总被引:2,自引:0,他引:2
Samuel Burer Renato D.C. Monteiro Yin Zhang 《Computational Optimization and Applications》2002,22(1):49-79
Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n × n matrix-valued function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed a first-order interior-point algorithm for solving a special class of linear semidefinite programs. In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectiveness of the first-order method are also presented. 相似文献
15.
We deal with the primal–dual Newton method for linear optimization (LO). Nowadays, this method is the working horse in all efficient interior point algorithms for LO, and its analysis is the basic element in all polynomiality proofs of such algorithms. At present there is still a gap between the practical behavior of the algorithms and the theoretical performance results, in favor of the practical behavior. This is especially true for so-called large-update methods. We present some new analysis tools, based on a proximity measure introduced by Jansen et al., in 1994, that may help to close this gap. This proximity measure has not been used in the analysis of large-update methods before. The new analysis does not improve the known complexity results but provides a unified way for the analysis of both large-update and small-update methods. 相似文献
16.
Complexity analysis of an interior point algorithm for the semidefinite optimization based on a kernel function with a double barrier term
下载免费PDF全文
![点击此处可从《数学学报(英文版)》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Mohamed Achache 《数学学报(英文版)》2015,31(3):543-556
In this paper, we establish the polynomial complexity of a primal-dual path-following interior point algorithm for solving semidefinite optimization(SDO) problems. The proposed algorithm is based on a new kernel function which differs from the existing kernel functions in which it has a double barrier term. With this function we define a new search direction and also a new proximity function for analyzing its complexity. We show that if q1 q2 1, the algorithm has O((q1 + 1) nq1+1/2(q1-q2)logn/ε)and O((q1 + 1)3q1-2q2+1/2(q1-q2)n~1/2 logn/ε) complexity results for large- and small-update methods, respectively. 相似文献
17.
Ximei Yang Yinkui Zhang Hongwei Liu Peiping Shen 《Numerical Functional Analysis & Optimization》2016,37(4):499-519
In this article, we propose a new second-order infeasible primal-dual path-following algorithm for symmetric cone optimization. The algorithm further improves the complexity bound of a wide infeasible primal-dual path-following algorithm. The theory of Euclidean Jordan algebras is used to carry out our analysis. The convergence is shown for a commutative class of search directions. In particular, the complexity bound is 𝒪(r5/4log ??1) for the Nesterov-Todd direction, and 𝒪(r7/4log ??1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ? is the required precision. If the starting point is strictly feasible, then the corresponding bounds can be reduced by a factor of r3/4. Some preliminary numerical results are provided as well. 相似文献
18.
Z. Y. Wu L. S. Zhang K. L. Teo F. S. Bai 《Journal of Optimization Theory and Applications》2005,125(1):181-203
In this paper, a class of global optimization problems is considered. Corresponding to each local minimizer obtained, we introduced a new modified function and construct a corresponding optimization subproblem with one constraint. Then, by applying a local search method to the one-constraint optimization subproblem and using the local minimizer as the starting point, we obtain a better local optimal solution. This process is continued iteratively. A termination rule is obtained which can serve as stopping criterion for the iterating process. To demonstrate the efficiency of the proposed approach, numerical examples are solved.This research was partially supported by the National Science Foundation of China, Grant 10271073. 相似文献
19.
20.
The paper analyzes the rate of local convergence of the augmented Lagrangian method for nonlinear second-order cone optimization
problems. Under the constraint nondegeneracy condition and the strong second order sufficient condition, we demonstrate that
the sequence of iterate points generated by the augmented Lagrangian method locally converges to a local minimizer at a linear
rate, whose ratio constant is proportional to 1/τ with penalty parameter τ not less than a threshold
. Importantly and interestingly enough, the analysis does not require the strict complementarity condition.
Supported by the National Natural Science Foundation of China under Project 10771026 and by the Scientific Research Foundation
for the Returned Overseas Chinese Scholars, State Education Ministry. 相似文献