共查询到20条相似文献,搜索用时 375 毫秒
1.
G. Still 《Mathematical Programming》2001,91(1):53-69
The discretization approach for solving semi-infinite optimization problems is considered. We are interested in the convergence
rate of the error between the solution of the semi-infinite problem and the solution of the discretized program depending
on the discretization mesh-size. It will be shown how this rate depends on whether the minimizer is strict of order one or
two and on whether the discretization includes boundary points of the index set in a specific way. This is done for ordinary
and for generalized semi-infinite problems.
Received: November 21, 2000 / Accepted: May 2001?Published online September 17, 2001 相似文献
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.
Mirjam Dür 《Mathematical Programming》2001,91(1):117-125
Branch–and–Bound methods with dual bounding procedures have recently been used to solve several continuous global optimization
problems. We improve results on their convergence theory and give a condition that enables us to detect infeasible partition
sets from the dual optimal value.
Received: May 5, 1999 / Accepted: April 19, 2001?Published online September 17, 2001 相似文献
4.
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 相似文献
5.
Bernd Kummer 《Mathematical Programming》2000,88(2):313-339
We show that, even for monotone directionally differentiable Lipschitz functionals on Hilbert spaces, basic concepts of generalized
derivatives identify only particular pseudo regular (or metrically regular) situations. Thus, pseudo regularity of (multi-)
functions will be investigated by other means, namely in terms of the possible inverse functions. In this way, we show how
pseudo regularity for the intersection of multifunctions can be directly characterized and estimated under general settings
and how contingent and coderivatives may be modified to obtain sharper regularity conditions. Consequences for a concept of
stationary points as limits of Ekeland points in nonsmooth optimization will be studied, too.
Received: May 20, 1999 / Accepted: February 15, 2000?Published online July 20, 2000 相似文献
6.
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 相似文献
7.
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 相似文献
8.
We prove that strict complementarity, primal and dual nondegeneracy of optimal solutions of convex optimization problems in
conic form are generic properties. In this paper, we say generic to mean that the set of data possessing the desired property
(or properties) has strictly larger Hausdorff dimension than the set of data that does not. Our proof is elementary and it
employs an important result due to Larman [7] on the boundary structure of convex bodies.
Received: September 1997 / Accepted: May 2000?Published online November 17, 2000 相似文献
9.
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 相似文献
10.
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 相似文献
11.
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 相似文献
12.
Robust Optimization (RO) is a modeling methodology, combined with computational tools, to process optimization problems in
which the data are uncertain and is only known to belong to some uncertainty set. The paper surveys the main results of RO
as applied to uncertain linear, conic quadratic and semidefinite programming. For these cases, computationally tractable robust
counterparts of uncertain problems are explicitly obtained, or good approximations of these counterparts are proposed, making
RO a useful tool for real-world applications. We discuss some of these applications, specifically: antenna design, truss topology
design and stability analysis/synthesis in uncertain dynamic systems. We also describe a case study of 90 LPs from the NETLIB
collection. The study reveals that the feasibility properties of the usual solutions of real world LPs can be severely affected
by small perturbations of the data and that the RO methodology can be successfully used to overcome this phenomenon.
Received: May 24, 2000 / Accepted: September 12, 2001?Published online February 14, 2002 相似文献
13.
Martin Gugat 《Mathematical Programming》1999,85(3):643-653
The growth of the multipliers, when the parameter approaches such a critical parameter, is characterized by a parametric constraint
qualification which is introduced here. It is equivalent to a bound on the growth of the multipliers.
Received May 8, 1995 / Revised version received February 12, 1998
Published online February 25, 1999 相似文献
14.
Optimality conditions for nonconvex semidefinite programming 总被引:9,自引:0,他引:9
Anders Forsgren 《Mathematical Programming》2000,88(1):105-128
This paper concerns nonlinear semidefinite programming problems for which no convexity assumptions can be made. We derive
first- and second-order optimality conditions analogous to those for nonlinear programming. Using techniques similar to those
used in nonlinear programming, we extend existing theory to cover situations where the constraint matrix is structurally sparse.
The discussion covers the case when strict complementarity does not hold. The regularity conditions used are consistent with
those of nonlinear programming in the sense that the conventional optimality conditions for nonlinear programming are obtained
when the constraint matrix is diagonal.
Received: May 15, 1998 / Accepted: April 12, 2000?Published online May 12, 2000 相似文献
15.
In this paper necessary, and sufficient optimality conditions are established without Lipschitz continuity for convex composite
continuous optimization model problems subject to inequality constraints. Necessary conditions for the special case of the
optimization model involving max-min constraints, which frequently arise in many engineering applications, are also given. Optimality conditions in the presence
of Lipschitz continuity are routinely obtained using chain rule formulas of the Clarke generalized Jacobian which is a bounded
set of matrices. However, the lack of derivative of a continuous map in the absence of Lipschitz continuity is often replaced
by a locally unbounded generalized Jacobian map for which the standard form of the chain rule formulas fails to hold. In this
paper we overcome this situation by constructing approximate Jacobians for the convex composite function involved in the model
problem using ε-perturbations of the subdifferential of the convex function and the flexible generalized calculus of unbounded
approximate Jacobians. Examples are discussed to illustrate the nature of the optimality conditions.
Received: February 2001 / Accepted: September 2001?Published online February 14, 2002 相似文献
16.
Benchmarking optimization software with performance profiles 总被引:9,自引:6,他引:3
We propose performance profiles — distribution functions for a performance metric — as a tool for benchmarking and comparing
optimization software. We show that performance profiles combine the best features of other tools for performance evaluation.
Received: February 2001 / Accepted: May 2001?Published online October 2, 2001 相似文献
17.
Received August 29, 1996 / Revised version received May 1, 1998 Published online October 21, 1998 相似文献
18.
Received May 28, 1996 / Revised version received May 1, 1998 Published online October 9, 1998 相似文献
19.
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 相似文献
20.
The bin packing problem is one of the classical NP-hard optimization problems. In this paper, we present a simple generic
approach for obtaining new fast lower bounds, based on dual feasible functions. Worst-case analysis as well as computational
results show that one of our classes clearly outperforms the previous best “economical” lower bound for the bin packing problem
by Martello and Toth, which can be understood as a special case. In particular, we prove an asymptotic worst-case performance
of 3/4 for a bound that can be computed in linear time for items sorted by size. In addition, our approach provides a general
framework for establishing new bounds.
Received: August 11, 1998 / Accepted: February 1, 2001?Published online September 17, 2001 相似文献