共查询到20条相似文献,搜索用时 0 毫秒
1.
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 相似文献
2.
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 相似文献
3.
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 相似文献
4.
Zoltán Miklós 《Discrete Mathematics》2013,313(22):2650-2655
5.
Feasible descent algorithms for mixed complementarity problems 总被引:6,自引:0,他引:6
In this paper we consider a general algorithmic framework for solving nonlinear mixed complementarity problems. The main features
of this framework are: (a) it is well-defined for an arbitrary mixed complementarity problem, (b) it generates only feasible
iterates, (c) it has a strong global convergence theory, and (d) it is locally fast convergent under standard regularity assumptions.
This framework is applied to the PATH solver in order to show viability of the approach. Numerical results for an appropriate
modification of the PATH solver indicate that this framework leads to substantial computational improvements.
Received April 9, 1998 / Revised version received November 23, 1998?Published online March 16, 1999 相似文献
6.
Krzysztof C. Kiwiel 《Mathematical Programming》1999,85(2):241-258
k } by taking xk to be an approximate minimizer of , where is a piecewise linear model of f constructed from accumulated subgradient linearizations of f, Dh is the D-function of a generalized Bregman function h and tk>0. Convergence under implementable criteria is established by extending our recent framework of Bregman proximal minimization,
which is of independent interest, e.g., for nonquadratic multiplier methods for constrained minimization. In particular, we
provide new insights into the convergence properties of bundle methods based on h=?|·|2.
Received September 18, 1997 / Revised version received June 30, 1998
Published online November 24, 1998 相似文献
7.
A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints 总被引:12,自引:0,他引:12
A trust region and affine scaling interior point method (TRAM) is proposed for a general nonlinear minimization with linear
inequality constraints [8]. In the proposed approach, a Newton step is derived from the complementarity conditions. Based
on this Newton step, a trust region subproblem is formed, and the original objective function is monotonically decreased.
Explicit sufficient decrease conditions are proposed for satisfying the first order and second order necessary conditions.?The
objective of this paper is to establish global and local convergence properties of the proposed trust region and affine scaling
interior point method. It is shown that the proposed explicit decrease conditions are sufficient for satisfy complementarity,
dual feasibility and second order necessary conditions respectively. It is also established that a trust region solution is
asymptotically in the interior of the proposed trust region subproblem and a properly damped trust region step can achieve
quadratic convergence.
Received: January 29, 1999 / Accepted: November 22, 1999?Published online February 23, 2000 相似文献
8.
Andrzej Cegielski 《Mathematical Programming》1999,85(3):469-490
Received November 11, 1995 / Revised version received June 2, 1998
Published online March 16, 1999 相似文献
9.
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 相似文献
10.
The variational inequality problem (VIP) can be reformulated as an unconstrained minimization problem through the D-gap function.
It is proved that the D-gap function has bounded level sets for the strongly monotone VIP. A hybrid Newton-type method is
proposed for minimizing the D-gap function. Under some conditions, it is shown that the algorithm is globally convergent and
locally quadratically convergent.
Received May 6, 1997 / Revised version received October 30, 1998?Published online June 11, 1999 相似文献
11.
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 相似文献
12.
13.
Supermemory descent methods for unconstrained minimization 总被引:11,自引:0,他引:11
The supermemory gradient method of Cragg and Levy (Ref. 1) and the quasi-Newton methods with memory considered by Wolfe (Ref. 4) are shown to be special cases of a more general class of methods for unconstrained minimization which will be called supermemory descent methods. A subclass of the supermemory descent methods is the class of supermemory quasi-Newton methods. To illustrate the numerical effectiveness of supermemory quasi-Newton methods, some numerical experience with one such method is reported.The authors are indebted to Dr. H. Y. Huang for his helpful criticism of this paper. 相似文献
14.
Stephen M. Robinson 《Mathematical Programming》1999,86(1):41-50
This paper establishes a linear convergence rate for a class of epsilon-subgradient descent methods for minimizing certain
convex functions on ℝ
n
. Currently prominent methods belonging to this class include the resolvent (proximal point) method and the bundle method
in proximal form (considered as a sequence of serious steps). Other methods, such as a variant of the proximal point method
given by Correa and Lemaréchal, can also fit within this framework, depending on how they are implemented. The convex functions
covered by the analysis are those whose conjugates have subdifferentials that are locally upper Lipschitzian at the origin,
a property generalizing classical regularity conditions.
Received March 29, 1996 / Revised version received March 5, 1999? Published online June 11, 1999 相似文献
15.
Krzysztof C. Kiwiel 《Mathematical Programming》2001,90(1):1-25
We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint
in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not
be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and
to the generalized solution set for classical stepsizes t
k
→0, ∑t
k
=∞, and weak or strong convergence of the iterates to a solution for {t
k
}∈ℓ2∖ℓ1 under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an
efficiency estimate of O(ε-2), thus being optimal in the sense of Nemirovskii.
Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001 相似文献
16.
Received January 5, 1997 / Revised version received November 19, 1997 Published online November 24, 1998 相似文献
17.
A trust region method based on interior point techniques for nonlinear programming 总被引:15,自引:0,他引:15
An algorithm for minimizing a nonlinear function subject to nonlinear inequality constraints is described. It applies sequential
quadratic programming techniques to a sequence of barrier problems, and uses trust regions to ensure the robustness of the
iteration and to allow the direct use of second order derivatives. This framework permits primal and primal-dual steps, but
the paper focuses on the primal version of the new algorithm. An analysis of the convergence properties of this method is
presented.
Received: May 1996 / Accepted: August 18, 2000?Published online October 18, 2000 相似文献
18.
Gongyun Zhao 《Mathematical Programming》2001,90(3):507-536
An algorithm incorporating the logarithmic barrier into the Benders decomposition technique is proposed for solving two-stage
stochastic programs. Basic properties concerning the existence and uniqueness of the solution and the underlying path are
studied. When applied to problems with a finite number of scenarios, the algorithm is shown to converge globally and to run
in polynomial-time.
Received: August 1998 / Accepted: August 2000?Published online April 12, 2001 相似文献
19.
In this paper, we propose a non-interior continuation method for solving generalized linear complementarity problems (GLCP)
introduced by Cottle and Dantzig. The method is based on a smoothing function derived from the exponential penalty function
first introduced by Kort and Bertsekas for constrained minimization. This smoothing function can also be viewed as a natural
extension of Chen-Mangasarian’s neural network smooth function. By using the smoothing function, we approximate GLCP as a
family of parameterized smooth equations. An algorithm is presented to follow the smoothing path. Under suitable assumptions,
it is shown that the algorithm is globally convergent and local Q-quadratically convergent. Few preliminary numerical results
are also reported.
Received September 3, 1997 / Revised version received April 27, 1999?Published online July 19, 1999 相似文献
20.
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 相似文献