共查询到20条相似文献,搜索用时 312 毫秒
1.
In this paper, we relate several questions about cutting planes to a fundamental problem in the geometry of numbers, namely,
the closest vector problem. Using this connection we show that the dominance, membership and validity problems are NP-complete
for Chvátal and split cuts.
Received: August 28, 2001 / Accepted: March 2002?Published online May 8, 2002 相似文献
2.
We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with
k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values.
Received: August 2001 / Accepted: January 2002?Published online March 27, 2002 相似文献
3.
Given a linear transformation L:?
n
→?
n
and a matrix Q∈?
n
, where ?
n
is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,?
n
+,Q) over the cone ?
n
+ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R
n×n
, we consider the linear transformation L
A
:?
n
→?
n
defined by L
A
(X):=AX+XA
T
and show that the P- and Q-properties for L
A
are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov.
Received: March 1999 / Accepted: November 1999?Published online April 20, 2000 相似文献
4.
Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation 总被引:2,自引:0,他引:2
Received April 10, 1996 / Revised version received April 30, 1998 Published online August 18, 1998 相似文献
5.
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 相似文献
6.
We propose a class of non-interior point algorithms for solving the complementarity problems(CP): Find a nonnegative pair
(x,y)∈ℝ
2n
satisfying y=f(x) and x
i
y
i
=0 for every i∈{1,2,...,n}, where f is a continuous mapping from ℝ
n
to ℝ
n
. The algorithms are based on the Chen-Harker-Kanzow-Smale smoothing functions for the CP, and have the following features;
(a) it traces a trajectory in ℝ
3n
which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from an arbitrary
(not necessarily positive) point in ℝ
2n
in contrast to most of interior-point methods, and (c) its global convergence is ensured for a class of problems including
(not strongly) monotone complementarity problems having a feasible interior point. To construct the algorithms, we give a
homotopy and show the existence of a trajectory leading to a solution under a relatively mild condition, and propose a class
of algorithms involving suitable neighborhoods of the trajectory. We also give a sufficient condition on the neighborhoods
for global convergence and two examples satisfying it.
Received April 9, 1997 / Revised version received September 2, 1998? Published online May 28, 1999 相似文献
7.
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 相似文献
8.
Josef Haberl 《Mathematical Programming》1999,85(3):617-642
Received February 12, 1993 / Revised version received February 6, 1998
Published online February 25, 1999 相似文献
9.
We obtain local estimates of the distance to a set defined by equality constraints under assumptions which are weaker than
those previously used in the literature. Specifically, we assume that the constraints mapping has a Lipschitzian derivative,
and satisfies a certain 2-regularity condition at the point under consideration. This setting directly subsumes the classical
regular case and the twice differentiable 2-regular case, for which error bounds are known, but it is significantly richer
than either of these two cases. When applied to a certain equation-based reformulation of the nonlinear complementarity problem,
our results yield an error bound under an assumption more general than b-regularity. The latter appears to be the weakest assumption under which a local error bound for complementarity problems
was previously available. We also discuss an application of our results to the convergence rate analysis of the exterior penalty
method for solving irregular problems.
Received: February 2000 / Accepted: November 2000?Published online January 17, 2001 相似文献
10.
Received April 15, 1997 / Revised version received July 22, 1998 Published online November 24, 1998 相似文献
11.
Received January 5, 1997 / Revised version received November 19, 1997 Published online November 24, 1998 相似文献
12.
We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound
uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known
projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and
computational effort.
Received: February 2000 / Accepted: November 2000?Published online January 17, 2001 相似文献
13.
Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation
methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming)
Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems
have a linear objective function c
T
x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,”
into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number
of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of
standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method
which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for
a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method
which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations.
Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000 相似文献
14.
Received March 18, 1996 / Revised version received August 8, 1997 Published online November 24, 1998 相似文献
15.
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 相似文献
16.
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 相似文献
17.
Received May 15, 1995 / Revised version received May 20, 1998 Published online October 21, 1998 相似文献
18.
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 相似文献
19.
We introduce a new NCP-function in order to reformulate the nonlinear complementarity problem as a nonsmooth system of equations.
This new NCP-function turns out to have stronger theoretical properties than the widely used Fischer-Burmeister function and
other NCP-functions suggested previously. Moreover, numerical experience indicates that a semismooth Newton method based on
this new NCP-function performs considerably better than the corresponding method based on the Fischer-Burmeister function.
Received: March 10, 1997 / Accepted: February 15, 2000?Published online May 12, 2000 相似文献
20.
Logarithmic SUMT limits in convex programming 总被引:1,自引:1,他引:0
The limits of a class of primal and dual solution trajectories associated with the Sequential Unconstrained Minimization Technique
(SUMT) are investigated for convex programming problems with non-unique optima. Logarithmic barrier terms are assumed. For
linear programming problems, such limits – of both primal and dual trajectories – are strongly optimal, strictly complementary,
and can be characterized as analytic centers of, loosely speaking, optimality regions. Examples are given, which show that
those results do not hold in general for convex programming problems. If the latter are weakly analytic (Bank et al. [3]),
primal trajectory limits can be characterized in analogy to the linear programming case and without assuming differentiability.
That class of programming problems contains faithfully convex, linear, and convex quadratic programming problems as strict
subsets. In the differential case, dual trajectory limits can be characterized similarly, albeit under different conditions,
one of which suffices for strict complementarity.
Received: November 13, 1997 / Accepted: February 17, 1999?Published online February 22, 2001 相似文献