共查询到20条相似文献,搜索用时 31 毫秒
1.
We present a construction which gives deterministic upper bounds for stochastic programs in which the randomness appears on
the right–hand–side and has a multivariate Gaussian distribution. Computation of these bounds requires the solution of only
as many linear programs as the problem has variables.
Received December 2, 1997 / Revised version received January 5, 1999? Published online May 12, 1999 相似文献
2.
Solving large quadratic assignment problems on computational grids 总被引:10,自引:0,他引:10
Kurt Anstreicher Nathan Brixius Jean-Pierre Goux Jeff Linderoth 《Mathematical Programming》2002,91(3):563-588
The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming
algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve
QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known
as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is
reported.
Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001 相似文献
3.
theory. This approach also quantifies the size of permissible perturbations. We include a discussion of these results for
block diagonal semidefinite programs, of which linear programming is a special case.
Received November 26, 1995 / Revised version received November 1, 1998
Published online February 25, 1999 相似文献
4.
Martin Skutella 《Mathematical Programming》2002,91(3):493-514
In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex
to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed
along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed
a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various
areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing.
Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results
of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques
do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation
results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally,
we provide results on the hardness of approximation for several variants of the problem.
Received: August 23, 2000 / Accepted: April 20, 2001?Published online October 2, 2001 相似文献
5.
A conic linear system is a system of the form?P(d): find x that solves b - Ax∈C
Y
, x∈C
X
,? where C
X
and C
Y
are closed convex cones, and the data for the system is d=(A,b). This system is“well-posed” to the extent that (small) changes in the data (A,b) do not alter the status of the system (the system remains solvable or not). Renegar defined the “distance to ill-posedness”,
ρ(d), to be the smallest change in the data Δd=(ΔA,Δb) for which the system P(d+Δd) is “ill-posed”, i.e., d+Δd is in the intersection of the closure of feasible and infeasible instances d’=(A’,b’) of P(·). Renegar also defined the “condition measure” of the data instance d as C(d):=∥d∥/ρ(d), and showed that this measure is a natural extension of the familiar condition measure associated with systems of linear
equations. This study presents two categories of results related to ρ(d), the distance to ill-posedness, and C(d), the condition measure of d. The first category of results involves the approximation of ρ(d) as the optimal value of certain mathematical programs. We present ten different mathematical programs each of whose optimal
values provides an approximation of ρ(d) to within certain constants, depending on whether P(d) is feasible or not, and where the constants depend on properties of the cones and the norms used. The second category of
results involves the existence of certain inscribed and intersecting balls involving the feasible region of P(d) or the feasible region of its alternative system, in the spirit of the ellipsoid algorithm. These results roughly state that
the feasible region of P(d) (or its alternative system when P(d) is not feasible) will contain a ball of radius r that is itself no more than a distance R from the origin, where the ratio R/r satisfies R/r≤c
1
C(d), and such that r≥ and R≤c
3
C(d), where c
1,c
2,c
3 are constants that depend only on properties of the cones and the norms used. Therefore the condition measure C(d) is a relevant tool in proving the existence of an inscribed ball in the feasible region of P(d) that is not too far from the origin and whose radius is not too small.
Received November 2, 1995 / Revised version received June 26, 1998?Published online May 12, 1999 相似文献
6.
Walter Gómez Bofill 《Mathematical Programming》1999,86(3):649-659
The paper presents an interior embedding of nonlinear optimization problems. This embedding satisfies a sufficient condition
for the success of pathfollowing algorithms with jumps being applied to one-parametric optimization problems.?The one-parametric
problem obtained by the embedding is supposed to be regular in the sense of Jongen, Jonker and Twilt. This asumption is analyzed,
and its genericity is proved in the space of the original optimization problems.
Received May 20, 1997 / Revised version received October 6, 1998?Published online May 12, 1999 相似文献
7.
Jan-J. Rückmann 《Mathematical Programming》1999,86(2):387-415
The paper deals with semi-infinite optimization problems which are defined by finitely many equality constraints and infinitely
many inequality constraints. We generalize the concept of strongly stable stationary points which was introduced by Kojima
for finite problems; it refers to the local existence and uniqueness of a stationary point for each sufficiently small perturbed
problem, where perturbations up to second order are allowed. Under the extended Mangasarian-Fromovitz constraint qualification
we present equivalent conditions for the strong stability of a considered stationary point in terms of first and second derivatives
of the involved functions. In particular, we discuss the case where the reduction approach is not satisfied.
Received June 30, 1995 / Revised version received October 9, 1998?
Published online June 11, 1999 相似文献
8.
Error bounds for proximal point subproblems and associated inexact proximal point algorithms 总被引:1,自引:0,他引:1
We study various error measures for approximate solution of proximal point regularizations of the variational inequality problem,
and of the closely related problem of finding a zero of a maximal monotone operator. A new merit function is proposed for
proximal point subproblems associated with the latter. This merit function is based on Burachik-Iusem-Svaiter’s concept of
ε-enlargement of a maximal monotone operator. For variational inequalities, we establish a precise relationship between the
regularized gap function, which is a natural error measure in this context, and our new merit function. Some error bounds
are derived using both merit functions for the corresponding formulations of the proximal subproblem. We further use the regularized
gap function to devise a new inexact proximal point algorithm for solving monotone variational inequalities. This inexact
proximal point method preserves all the desirable global and local convergence properties of the classical exact/inexact method,
while providing a constructive error tolerance criterion, suitable for further practical applications. The use of other tolerance
rules is also discussed.
Received: April 28, 1999 / Accepted: March 24, 2000?Published online July 20, 2000 相似文献
9.
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 相似文献
10.
Received August 29, 1996 / Revised version received May 1, 1998 Published online October 21, 1998 相似文献
11.
M. Locatelli 《Mathematical Programming》1999,85(3):593-616
In this paper the problem of finding the global optimum of a concave function over a polytope is considered. A well-known
class of algorithms for this problem is the class of conical algorithms. In particular, the conical algorithm based on the
so called ω-subdivision strategy is considered. It is proved that, for any given accuracy ε>0, this algorithm stops in a finite
time by returning an ε-optimal solution for the problem, while it is convergent for ε=0.
Received January 24, 1996 / Revised version received December 9, 1998
Published online June 11, 1999 相似文献
12.
A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities 总被引:17,自引:0,他引:17
In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the
box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions,
we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent
nonsmooth equation H(u,x)=0, where H:ℜ
2n
→ℜ
2n
, u∈ℜ
n
is a parameter variable and x∈ℜ
n
is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z
k
=(u
k
,x
k
)} such that the mapping H(·) is continuously differentiable at each z
k
and may be non-differentiable at the limiting point of {z
k
}. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which
play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not
require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if
we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the
proposed methods for particularly chosen smoothing functions are very promising.
Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999 相似文献
13.
Inexact implicit methods for monotone general variational inequalities 总被引:32,自引:0,他引:32
Bingsheng He 《Mathematical Programming》1999,86(1):199-217
Solving a variational inequality problem is equivalent to finding a solution of a system of nonsmooth equations. Recently,
we proposed an implicit method, which solves monotone variational inequality problem via solving a series of systems of nonlinear
smooth (whenever the operator is smooth) equations. It can exploit the facilities of the classical Newton–like methods for
smooth equations. In this paper, we extend the method to solve a class of general variational inequality problems Moreover, we improve the implicit method to allow inexact solutions of the systems of nonlinear equations at each iteration.
The method is shown to preserve the same convergence properties as the original implicit method.
Received July 31, 1995 / Revised version received January 15, 1999? Published online May 28, 1999 相似文献
14.
Linear Programming based lower bounds have been considered both for the general as well as for the symmetric quadratic assignment
problem several times in the recent years. Their quality has turned out to be quite good in practice. Investigations of the
polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadratic
assignment polytope) have been started during the last decade [34, 31, 21, 22]. They have lead to basic knowledge on these
polytopes concerning questions like their dimensions, affine hulls, and trivial facets. However, no large class of (facet-defining)
inequalities that could be used in cutting plane procedures had been found. We present in this paper the first such class
of inequalities, the box inequalities, which have an interesting origin in some well-known hypermetric inequalities for the
cut polytope. Computational experiments with a cutting plane algorithm based on these inequalities show that they are very
useful with respect to the goal of solving quadratic assignment problems to optimality or to compute tight lower bounds. The
most effective ones among the new inequalities turn out to be indeed facet-defining for both the non-symmetric as well as
for the symmetric quadratic assignment polytope.
Received: April 17, 2000 / Accepted: July 3, 2001?Published online September 3, 2001 相似文献
15.
Received June 13, 1995 / Revised version received February 6, 1998 Published online August 18, 1998 相似文献
16.
This paper concerns with convergence properties of the classical proximal point algorithm for finding zeroes of maximal monotone
operators in an infinite-dimensional Hilbert space. It is well known that the proximal point algorithm converges weakly to
a solution under very mild assumptions. However, it was shown by Güler [11] that the iterates may fail to converge strongly
in the infinite-dimensional case. We propose a new proximal-type algorithm which does converge strongly, provided the problem
has a solution. Moreover, our algorithm solves proximal point subproblems inexactly, with a constructive stopping criterion
introduced in [31]. Strong convergence is forced by combining proximal point iterations with simple projection steps onto
intersection of two halfspaces containing the solution set. Additional cost of this extra projection step is essentially negligible
since it amounts, at most, to solving a linear system of two equations in two unknowns.
Received January 6, 1998 / Revised version received August 9, 1999?Published online November 30, 1999 相似文献
17.
An interior Newton method for quadratic programming 总被引:2,自引:0,他引:2
We propose a new (interior) approach for the general quadratic programming problem. We establish that the new method has strong
convergence properties: the generated sequence converges globally to a point satisfying the second-order necessary optimality
conditions, and the rate of convergence is 2-step quadratic if the limit point is a strong local minimizer. Published alternative
interior approaches do not share such strong convergence properties for the nonconvex case. We also report on the results
of preliminary numerical experiments: the results indicate that the proposed method has considerable practical potential.
Received October 11, 1993 / Revised version received February 20, 1996
Published online July 19, 1999 相似文献
18.
Received May 28, 1996 / Revised version received May 1, 1998 Published online October 9, 1998 相似文献
19.
Trade-off information related to Pareto optimal solutions is important in multiobjective optimization problems with conflicting
objectives. Recently, the concept of trade-off directions has been introduced for convex problems. These trade-offs are characterized
with the help of tangent cones. Generalized trade-off directions for nonconvex problems can be defined by replacing convex
tangent cones with nonconvex contingent cones. Here we study how the convex concepts and results can be generalized into a
nonconvex case. Giving up convexity naturally means that we need local instead of global analysis.
Received: December 2000 / Accepted: October 2001?Published online February 14, 2002 相似文献
20.
Global error bounds with fractional exponents 总被引:2,自引:0,他引:2
Using the partial order induced by a proper weakly lower semicontinuous function on a reflexive Banach space X we give a sufficient condition for f to have error bounds with fractional exponents. Application is given to identify the set of such exponents for quadratic
functions.
Received: August 20, 1999 / Accepted: March 20, 2000?Published online July 20, 2000 相似文献