共查询到20条相似文献,搜索用时 31 毫秒
1.
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 相似文献
2.
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 相似文献
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.
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 相似文献
5.
6.
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 相似文献
7.
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 相似文献
8.
This paper presents a polynomial-time dual simplex algorithm for the generalized circulation problem. An efficient implementation
of this algorithm is given that has a worst-case running time of O(m
2(m+nlogn)logB), where n is the number of nodes, m is the number of arcs and B is the largest integer used to represent the rational gain factors and integral capacities in the network. This running time
is as fast as the running time of any combinatorial algorithm that has been proposed thus far for solving the generalized
circulation problem.
Received: June 1998 / Accepted: June 27, 2001?Published online September 17, 2001 相似文献
9.
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 相似文献
10.
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 相似文献
11.
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 相似文献
12.
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 相似文献
13.
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 相似文献
14.
We present a polynomial time algorithm to find the maximum weight of an edge-cut in graphs embeddable on an arbitrary orientable
surface, with integral weights bounded in the absolute value by a polynomial of the size of the graph.</
The algorithm has been implemented for toroidal grids using modular arithmetics and the generalized nested dissection method.
The applications in statistical physics are discussed.
Received: June 1999 / Accepted: December 2000?Published online March 22, 2001 相似文献
15.
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 相似文献
16.
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 相似文献
17.
18.
Yinyu Ye 《Mathematical Programming》2001,90(1):101-111
We present a .699-approximation algorithm for Max-Bisection, i.e., partitioning the nodes of a weighted graph into two blocks
of equal cardinality so as to maximize the weights of crossing edges. This is an improved result from the .651-approximation
algorithm of Frieze and Jerrum and the semidefinite programming relaxation of Goemans and Williamson.
Received: October 1999 / Accepted: July 2000?Published online January 17, 2001 相似文献
19.
Malcolm C. Pullan 《Mathematical Programming》2002,93(3):415-451
Separated continuous linear programs (SCLP) are a class of continuous linear programs which, among other things, can serve
as a useful model for dynamic network problems where storage is permitted at the nodes. Recent work on SCLP has produced a
detailed duality theory, conditions under which an optimal solution exists with a finite number of breakpoints, a purification
algorithm, as well as a convergent algorithm for solving SCLP under certain assumptions on the problem data. This paper combines
much of this work to develop a possible approach for solving a wider range of SCLP problems, namely those with fairly general
costs. The techniques required to implement the algorithm are no more than standard (finite-dimensional) linear programming
and line searching, and the resulting algorithm is simplex-like in nature. We conclude the paper with the numerical results
obtained by using a simple implementation of the algorithm to solve a small problem.
Received: May 1994 / Accepted: March 2002?Published online June 25, 2002 相似文献
20.
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 相似文献