共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions 总被引:5,自引:0,他引:5
In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family
of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the
polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following
algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the
context of SOCP, that is they have an O( logε-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh,
Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms
for SOCP based on this search direction.
Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000 相似文献
3.
An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints 总被引:12,自引:0,他引:12
Le Thi Hoai An 《Mathematical Programming》2000,87(3):401-426
In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids.
The first approach is the d.c. (difference of convex functions) optimization algorithm (abbr. DCA) whose main tools are the
proximal point algorithm and/or the projection subgradient method in convex minimization. The second is a branch-and-bound
scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham
Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting
point, it provides often a global solution. This motivates us to combine the DCA and our branch and bound algorithm in order
to obtain a good initial point for the DCA and to prove the globality of the DCA. In both approaches we attempt to use the
ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can
be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting
procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems.
Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA
and the combined DCA-branch-and-bound algorithm.
Received: April 22, 1999 / Accepted: November 30, 1999?Published online February 23, 2000 相似文献
4.
Self-regular functions and new search directions for linear and semidefinite optimization 总被引:11,自引:0,他引:11
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 相似文献
5.
This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows
exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively,
the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First,
we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a
simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify
several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide
variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy
to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the
QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP.
Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000 相似文献
6.
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 相似文献
7.
In high-multiplicity scheduling problems, identical jobs are encoded in the efficient format of describing one of the jobs
and the number of identical jobs. Similarly, identical machines are efficiently encoded in the same manner. We investigate
parallel-machine, high-multiplicity problems, where there are three possible machine speed structures: identical, proportional,
or unrelated. For the objectives of minimizing the sum of job completion times and minimizing the makespan, we consider both
nonpreemptive and preemptive problems. For some problems, we develop polynomial time algorithms. For several problems, we
demonstrate that the recognition versions can be solved in polynomial time, while the optimization versions require pseudo-polynomial
time. We also show that changing from standard binary encoding to high-multiplicity encoding does not affect the complexity
class of NP-complete problems.
Received: April 1996 / Accepted: July 2000?Published online January 17, 2001 相似文献
8.
On the complexity of a class of combinatorial optimization problems with uncertainty 总被引:2,自引:0,他引:2
Igor Averbakh 《Mathematical Programming》2001,90(2):263-272
We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of m elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p,m-p})2
m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is
NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This
is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented
uncertainty but is polynomially solvable in the case of the interval representation of uncertainty.
Received: July 1998 / Accepted: May 2000?Published online March 22, 2001 相似文献
9.
Submodular flow problems, introduced by Edmonds and Giles [2], generalize network flow problems. Many algorithms for solving
network flow problems have been generalized to submodular flow problems (cf. references in Fujishige [4]), e.g. the cycle
canceling method of Klein [9]. For network flow problems, the choice of minimum-mean cycles in Goldberg and Tarjan [6], and
the choice of minimum-ratio cycles in Wallacher [12] lead to polynomial cycle canceling methods. For submodular flow problems,
Cui and Fujishige [1] show finiteness for the minimum-mean cycle method while Zimmermann [16] develops a pseudo-polynomial
minimum ratio cycle method. Here, we prove pseudo-polynomiality of a larger class of the minimum-ratio variants and, by combining
both methods, we develop a polynomial cycle canceling algorithm for submodular flow problems.
Received July 22, 1994 / Revised version received July 18, 1997? Published online May 28, 1999 相似文献
10.
This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality
constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods
for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the
iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal
set is ensured when the barrier parameter tends to zero, provided strict complementarity holds.
Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002 相似文献
11.
Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods 总被引:6,自引:0,他引:6
The paper extends prior work by the authors on loqo, an interior point algorithm for nonconvex nonlinear programming. The
specific topics covered include primal versus dual orderings and higher order methods, which attempt to use each factorization
of the Hessian matrix more than once to improve computational efficiency. Results show that unlike linear and convex quadratic
programming, higher order corrections to the central trajectory are not useful for nonconvex nonlinear programming, but that
a variant of Mehrotra’s predictor-corrector algorithm can definitely improve performance.
Received: May 3, 1999 / Accepted: January 24, 2000?Published online March 15, 2000 相似文献
12.
Satoru Fujishige 《Mathematical Programming》2000,88(1):217-220
U. Faigle and W. Kern have recently extended the work of their earlier paper and of M. Queyranne, F. Spieksma and F. Tardella
and have shown that a dual greedy algorithm works for a system of linear inequalities with {:0,1}-coefficients defined in
terms of antichains of an underlying poset and a submodular function on the set of ideals of the poset under some additional
condition on the submodular function.?In this note we show that Faigle and Kern’s dual greedy polyhedra belong to a class
of submodular flow polyhedra, i.e., Faigle and Kern’s problem is a special case of the submodular flow problem that can easily
be solved by their greedy algorithm.
Received: February 1999 / Accepted: December 1999?Published online February 23, 2000 相似文献
13.
Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints 总被引:9,自引:0,他引:9
We will propose a branch and bound algorithm for calculating a globally optimal solution of a portfolio construction/rebalancing
problem under concave transaction costs and minimal transaction unit constraints. We will employ the absolute deviation of
the rate of return of the portfolio as the measure of risk and solve linear programming subproblems by introducing (piecewise)
linear underestimating function for concave transaction cost functions. It will be shown by a series of numerical experiments
that the algorithm can solve the problem of practical size in an efficient manner.
Received: July 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000 相似文献
14.
Basis- and partition identification for quadratic programming and linear complementarity problems 总被引:1,自引:0,他引:1
Arjan B. Berkelaar Benjamin Jansen Kees Roos Tamás Terlaky 《Mathematical Programming》1999,86(2):261-282
Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide
maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other
hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification
algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification
algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from
any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski
and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity
problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality
property of basis tableaus.
Received April 9, 1996 / Revised version received April 27, 1998?
Published online May 12, 1999 相似文献
15.
16.
Nonlinear programming without a penalty function 总被引:57,自引:0,他引:57
In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm
is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead,
a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or
the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm
compares favourably with LANCELOT and an implementation of Sl1QP.
Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001 相似文献
17.
On the core of ordered submodular cost games 总被引:5,自引:0,他引:5
A general ordertheoretic linear programming model for the study of matroid-type greedy algorithms is introduced. The primal
restrictions are given by so-called weakly increasing submodular functions on antichains. The LP-dual is solved by a Monge-type
greedy algorithm. The model offers a direct combinatorial explanation for many integrality results in discrete optimization.
In particular, the submodular intersection theorem of Edmonds and Giles is seen to extend to the case with a rooted forest
as underlying structure. The core of associated polyhedra is introduced and applications to the existence of the core in cooperative
game theory are discussed.
Received: November 2, 1995 / Accepted: September 15, 1999?Published online February 23, 2000 相似文献
18.
In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP)
problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints
by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems
includes instances of SDP relaxations of combinatorial optimization problems with binary variables as well as other important
SDP problems. We also derive gradient formulas for the objective function of the resulting nonlinear optimization problem
and show that both function and gradient evaluations have affordable complexities that effectively exploit the sparsity of
the problem data. This transformation, together with the efficient gradient formulas, enables the solution of very large-scale
SDP problems by gradient-based nonlinear optimization techniques. In particular, we propose a first-order log-barrier method
designed for solving a class of large-scale linear SDP problems. This algorithm operates entirely within the space of the
transformed problem while still maintaining close ties with both the primal and the dual of the original SDP problem. Global
convergence of the algorithm is established under mild and reasonable assumptions.
Received: January 5, 2000 / Accepted: October 2001?Published online February 14, 2002 相似文献
19.
Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model
for this problem is given by the vertex-disjoint packing of two Steiner trees (2VPST), which is known to be NP-complete. This
work presents an investigation on the 2VPST polyhedra. The main idea is to start from facet-defining inequalities for a vertex-weighted
Steiner tree polyhedra. Some of these inequalities are proven to also define facets for the packing polyhedra, while others
are lifted to derive new important families of inequalities, including proven facets. Separation algorithms are provided.
Branch-and-cut implementation issues are also discussed, including some new practical techniques to improve the performance
of the algorithm. The resulting code is capable of solving problems on grid graphs with up to 10000 vertices and 5000 terminals
in a few minutes.
Received: August 1999 / Accepted: January 2001?Published online April 12, 2001 相似文献
20.
The well-known Undirected Rural Postman Problem is considered and a binary linear problem using new dominance relations is
presented. Polyhedral properties are investigated and a branch-and-cut algorithm is developed. Extensive computational results
indicate that the algorithm is capable of solving much larger instances than previously reported.
Received: December 1, 1997 / Accepted: October 13, 1999?Published online January 27, 2000 相似文献