共查询到20条相似文献,搜索用时 31 毫秒
1.
Received June 6, 1995 / Revised version received May 26, 1998 Published online October 9, 1998 相似文献
2.
Received February 10, 1997 / Revised version received June 6, 1998 Published online October 9, 1998 相似文献
3.
Sample-path solution of stochastic variational inequalities 总被引:2,自引:0,他引:2
Received July 30, 1997 / Revised version received June 4, 1998 Published online October 21, 1998 相似文献
4.
Lagrangean dualization and subgradient optimization techniques are frequently used within the field of computational optimization
for finding approximate solutions to large, structured optimization problems. The dual subgradient scheme does not automatically
produce primal feasible solutions; there is an abundance of techniques for computing such solutions (via penalty functions,
tangential approximation schemes, or the solution of auxiliary primal programs), all of which require a fair amount of computational
effort.
We consider a subgradient optimization scheme applied to a Lagrangean dual formulation of a convex program, and construct,
at minor cost, an ergodic sequence of subproblem solutions which converges to the primal solution set. Numerical experiments
performed on a traffic equilibrium assignment problem under road pricing show that the computation of the ergodic sequence
results in a considerable improvement in the quality of the primal solutions obtained, compared to those generated in the
basic subgradient scheme.
Received February 11, 1997 / Revised version received June 19, 1998?Published online June 28, 1999 相似文献
5.
Received June 10, 1996 / Revised version received May 20, 1997 Published online October 21, 1998 相似文献
6.
The many facets of linear programming 总被引:1,自引:0,他引:1
Michael J. Todd 《Mathematical Programming》2002,91(3):417-436
We examine the history of linear programming from computational, geometric, and complexity points of view, looking at simplex,
ellipsoid, interior-point, and other methods.
Received: June 22, 2000 / Accepted: April 4, 2001?Published online October 2, 2001 相似文献
7.
The stable admissions polytope– the convex hull of the stable assignments of the university admissions problem – is described by a set of linear inequalities.
It depends on a new characterization of stability and arguments that exploit and extend a graphical approach that has been
fruitful in the analysis of the stable marriage problem.
Received: April 10, 1998 / Accepted: June 3, 1999?Published online January 27, 2000 相似文献
8.
Stephen M. Robinson 《Mathematical Programming》1999,85(1):1-13
* TL, where T is maximal monotone and L is linear and continuous with adjoint L*.
Received September 9, 1997 / Revised version received June 30, 1998 Published online January 20, 1999 相似文献
9.
Andrzej Cegielski 《Mathematical Programming》1999,85(3):469-490
Received November 11, 1995 / Revised version received June 2, 1998
Published online March 16, 1999 相似文献
10.
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 相似文献
11.
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 相似文献
12.
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 相似文献
13.
Charles Audet Pierre Hansen Brigitte Jaumard Gilles Savard 《Mathematical Programming》1999,85(3):573-592
Received June 24, 1996 / Revised version received May 22, 1997
Published online February 25, 1999 相似文献
14.
This paper is about set packing relaxations of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and set
packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines
carry over to the problems under investigation.
Received: September 1997 / Accepted: November 1999?Published online June 8, 2000 相似文献
15.
A polyhedral approach to single-machine scheduling problems 总被引:2,自引:0,他引:2
J.M. van den Akker C.P.M. van Hoesel M.W.P. Savelsbergh 《Mathematical Programming》1999,85(3):541-572
We report new results for a time-indexed formulation of nonpreemptive single-machine scheduling problems. We give complete
characterizations of all facet inducing inequalities with integral coefficients and right-hand side 1 or 2 for the convex
hull of the set of feasible partial schedules, i.e., schedules in which not all jobs have to be started. Furthermore, we identify
conditions under which these facet inducing inequalities are also facet inducing for the original polytope, which is the convex
hull of the set of feasible complete schedules, i.e., schedules in which all jobs have to be started. To obtain insight in
the effectiveness of these classes of facet-inducing inequalities, we develop a branch-and-cut algorithm based on them. We
evaluate its performance on the strongly NP-hard single machine scheduling problem of minimizing the weighted sum of the job
completion times subject to release dates.
Received March 24, 1994 / Revised version received February 13, 1997
Published online June 28, 1999 相似文献
16.
Lagrangian relaxation is often an efficient tool to solve (large-scale) optimization problems, even nonconvex. However it
introduces a duality gap, which should be small for the method to be really efficient. Here we make a geometric study of the
duality gap. Given a nonconvex problem, we formulate in a first part a convex problem having the same dual. This formulation
involves a convexification in the product of the three spaces containing respectively the variables, the objective and the
constraints. We apply our results to several relaxation schemes, especially one called “Lagrangean decomposition” in the combinatorial-optimization
community, or “operator splitting” elsewhere. We also study a specific application, highly nonlinear: the unit-commitment
problem.
Received: June 1997 / Accepted: December 2000?Published online April 12, 2001 相似文献
17.
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 相似文献
18.
It is shown that: (1) any action of a Moscow group G on a first countable, Dieudonné complete (in particular, on a metrizable) space X can uniquely be extended to an action of the Dieudonné completion γG on X, (2) any action of a locally pseudocompact topological group G on a b
f
-space (in particular, on a first countable space) X can uniquely be extended to an action of the Weil completion on the Dieudonné completion γX of X. As a consequence, we obtain that, for each locally pseudocompact topological group G, every G-space with the b
f
-property admits an equivariant embedding into a compact Hausdorff G-space. Furthermore, for each pseudocompact group G, every metrizable G-space has a G-invariant metric compatible with its topology. We also give a direct construction of such an invariant metric.
Received: June 22, 2000; in final form: May 22, 2001?Published online: June 11, 2002 相似文献
19.
T (Mx+q)=0, Mx+q≥0, x≥0 has a solution. We explain how one can use the polyhedral structure of the set of all triangulations
of a finite point set to determine if an n×n matrix M is a Q-matrix. Our implementation of the algorithm is practical for
deciding the Q-nature for all M with n≤8.
Received May 30, 1997 / Revised version received June 12, 1998
Published online November 24, 1998 相似文献
20.
Alan J. King 《Mathematical Programming》2002,91(3):543-562
The hedging of contingent claims in the discrete time, discrete state case is analyzed from the perspective of modeling the
hedging problem as a stochastic program. Application of conjugate duality leads to the arbitrage pricing theorems of financial
mathematics, namely the equivalence of absence of arbitrage and the existence of a probability measure that makes the price
process into a martingale. The model easily extends to the analysis of options pricing when modeling risk management concerns
and the impact of spreads and margin requirements for writers of contingent claims. However, we find that arbitrage pricing
in incomplete markets fails to model incentives to buy or sell options. An extension of the model to incorporate pre-existing
liabilities and endowments reveals the reasons why buyers and sellers trade in options. The model also indicates the importance
of financial equilibrium analysis for the understanding of options prices in incomplete markets.
Received: June 5, 2000 / Accepted: July 12, 2001?Published online December 6, 2001 相似文献