首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
Primal-dual interior-point methods (IPMs) have shown their power in solving large classes of optimization problems. However, at present there is still a gap between the practical behavior of these algorithms and their theoretical worst-case complexity results, with respect to the strategies of updating the duality gap parameter in the algorithm. The so-called small-update IPMs enjoy the best known theoretical worst-case iteration bound, but work very poorly in practice. To the contrary, the so-called large-update IPMs have superior practical performance but with relatively weaker theoretical results. In this paper we discuss the new algorithmic variants and improved complexity results with respect to the new family of Self-Regular proximity based IPMs for Linear Optimization problems, and their generalizations to Conic and Semidefinite Optimization This research was supported by the MITACS project “New IPMs and Software for Convex Conic-Linear Optimization and Their Application to Solve VLSI Circuit Layout Problems”, by an NSERC discovery grant, and the CRC program. The first author would also like to thank the Iranian Ministry of Science, Research and Technology for supporting his research.  相似文献   

2.
For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n k-1 F(n,m))=O(mn k log(n 2 /m)) time and O(n 2) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn 3) for weighted graphs, but improves the bound ?(mn 3) to O(n 2 F(n,m))=O(min{mn 8/3,m 3/2 n 2}) for unweighted graphs. The bound ?(mn 4) for k=4 improves the previous best randomized bound ?(n 6) (for m=o(n 2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Received: April 1999 / Accepted: February 2000?Published online August 18, 2000  相似文献   

3.
In this paper, motivated by the complexity results of Interior Point Methods (IPMs) for Linear Optimization (LO) based on kernel functions, we present a polynomial time IPM for solving P.(a)-linear complementarity problem, using a new class of kernel functions. The special case of our new class was considered earlier for LO by Y. Q. Bai et al. in 2004. Using some appealing properties of the new class, we show that the iteration bound for IPMs matches the so far best known theoretical iteration bound for both large and small updates by choosing special values for the parameters of the new class.  相似文献   

4.
Primal-Dual Interior-Point Methods (IPMs) have shown their power in solving large classes of optimization problems. In this paper a self-regular proximity based Infeasible Interior Point Method (IIPM) is proposed for linear optimization problems. First we mention some interesting properties of a specific self-regular proximity function, studied recently by Peng and Terlaky, and use it to define infeasible neighborhoods. These simple but interesting properties of the proximity function indicate that, when the current iterate is in a large neighborhood of the central path, large-update IIPMs emerge as the only natural choice. Then, we apply these results to design a specific self-regularity based dynamic large-update IIPM in large neighborhood. The new dynamic IIPM always takes large-updates and does not utilize any inner iteration to get centered. An worst-case iteration bound of the algorithm is established. Finally, we report the main results of our computational experiments.  相似文献   

5.
M. Reza Peyghami 《PAMM》2007,7(1):2060081-2060082
One of the main ingredients of interior point methods is the proximity functions to measure the distance of the iterates from the central path of linear optimization problems. In this paper, an interior point method for solving P*(κ)-linear complementarity problem, κ ≥ 0, is proposed. For this version, we use a new class of proximity functions induced by new kernel functions. Using some mild and easy to check conditions, we show that the large-update primal-dual interior point methods for solving P*(κ)-linear complementarity problem enjoy the so far best worst case theoretical complexity, namely O (κn log n log n /ε) iteration bound, with special choices of the parameters p, q ≥ 1. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)  相似文献   

6.
In this paper we propose primal-dual interior-point algorithms for semidefinite optimization problems based on a new kernel function with a trigonometric barrier term. We show that the iteration bounds are $O(\sqrt{n}\log(\frac{n}{\epsilon}))$ for small-update methods and $O(n^{\frac{3}{4}}\log(\frac{n}{\epsilon}))$ for large-update, respectively. The resulting bound is better than the classical kernel function. For small-update, the iteration complexity is the best known bound for such methods.  相似文献   

7.
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.  相似文献   

8.
A class of polynomial primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, with parameters p and q, is presented. Its growth term is between linear and quadratic. Some new tools for the analysis of the algorithms are proposed. The complexity bounds of O(√Nlog N log N/ε) for large-update methods and O(√Nlog N/ε) for smallupdate methods match the best known complexity bounds obtained for these methods. Numerical tests demonstrate the behavior of the algorithms for different results of the parameters p and q.  相似文献   

9.
10.
Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations. Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000  相似文献   

11.
Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()α≤≤ () n −ω. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() n −ω≤μ(G)≤n−α() α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002  相似文献   

12.
Given a set of positive integers Q=q 1, q 2, we develop a general method to find an upper bound for the function s(N), where N s(N) is the size of the largest subset A of 1,N such that A - A does not contain any elements of Q. We combine ergodic-theoretical ideas with the standard Hardy-Littlewood approach, and in particular prove that s(M)=O(1/log log log M) when q i=P(i), where P is a polynomial with integer coefficients, P(0)=0. This revised version was published online in June 2006 with corrections to the Cover Date.  相似文献   

13.
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.  相似文献   

14.
We describe an O(n 4 hmin{logU,n 2logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow. Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001  相似文献   

15.
16.
Let {X n } n ≥0 be a Harris recurrent Markov chain with state space E and invariant measure π. The law of the iterated logarithm and the law of weak convergence are given for the additive functionals of the form
where ƒ is a real π-centered function defined on E. Some similar results are also obtained for additive functionals which are martingales associated with {X n } n ≥0. Received: 15 September 1998 / Revised version: 1 April 1999  相似文献   

17.
In this paper we propose a weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem. The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path. At each iteration, we only use full-Newton step. Finally, the currently best known iteration bound for the algorithm with a small-update method, namely, O(√nlog n/ε) is derived, which is as good as the bound for the linear optimization analogue.  相似文献   

18.
19.
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.  相似文献   

20.
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号