共查询到20条相似文献,搜索用时 31 毫秒
1.
We consider stochastic programming problems with probabilistic constraints involving integer-valued random variables. The
concept of a p-efficient point of a probability distribution is used to derive various equivalent problem formulations. Next we introduce
the concept of r-concave discrete probability distributions and analyse its relevance for problems under consideration. These notions are
used to derive lower and upper bounds for the optimal value of probabilistically constrained stochastic programming problems
with discrete random variables. The results are illustrated with numerical examples.
Received: October 1998 / Accepted: June 2000?Published online October 18, 2000 相似文献
2.
Diethard Klatte 《Mathematical Programming》2000,88(2):285-311
We analyze the local upper Lipschitz behavior of critical points, stationary solutions and local minimizers to parametric
C
1,1 programs. In particular, we derive a characterization of this property for the stationary solution set map without assuming
the Mangasarian–Fromovitz CQ. Moreover, conditions which also ensure the persistence of solvability are given, and the special
case of linear constraints is handled. The present paper takes pattern from [21] by continuing the approach via contingent
derivatives of the Kojima function associated with the given optimization problem.
Received: June 10, 1999 / Accepted: November 15, 1999?Published online July 20, 2000 相似文献
3.
Martin Gugat 《Mathematical Programming》2000,88(2):255-275
The feasible set of a convex semi–infinite program is described by a possibly infinite system of convex inequality constraints.
We want to obtain an upper bound for the distance of a given point from this set in terms of a constant multiplied by the
value of the maximally violated constraint function in this point. Apart from this Lipschitz case we also consider error bounds
of H?lder type, where the value of the residual of the constraints is raised to a certain power.?We give sufficient conditions
for the validity of such bounds. Our conditions do not require that the Slater condition is valid. For the definition of our
conditions, we consider the projections on enlarged sets corresponding to relaxed constraints. We present a condition in terms
of projection multipliers, a condition in terms of Slater points and a condition in terms of descent directions. For the Lipschitz
case, we give five equivalent characterizations of the validity of a global error bound.?We extend previous results in two
directions: First, we consider infinite systems of inequalities instead of finite systems. The second point is that we do
not assume that the Slater condition holds which has been required in almost all earlier papers.
Received: April 12, 1999 / Accepted: April 5, 2000?Published online July 20, 2000 相似文献
4.
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 相似文献
5.
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 相似文献
6.
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 相似文献
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 generalize the disjunctive approach of Balas, Ceria, and Cornuéjols [2] and devevlop a branch-and-cut method for solving
0-1 convex programming problems. We show that cuts can be generated by solving a single convex program. We show how to construct
regions similar to those of Sherali and Adams [20] and Lovász and Schrijver [12] for the convex case. Finally, we give some
preliminary computational results for our method.
Received January 16, 1996 / Revised version received April 23, 1999?Published online June 28, 1999 相似文献
9.
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 相似文献
10.
The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many
closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization
(constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard
constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull
intersection property. Jameson’s duality for two cones, which relates bounded linear regularity to property (G), is re-derived
and refined. For polyhedral cones, a statement dual to Hoffman’s error bound result is obtained. A sharpening of a result
on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is
quantified by the angle between the subspaces.
Received October 1, 1997 / Revised version received July 21, 1998? Published online June 11, 1999 相似文献
11.
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 相似文献
12.
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 相似文献
13.
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 相似文献
14.
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 相似文献
15.
Stephen M. Robinson 《Mathematical Programming》1999,86(1):41-50
This paper establishes a linear convergence rate for a class of epsilon-subgradient descent methods for minimizing certain
convex functions on ℝ
n
. Currently prominent methods belonging to this class include the resolvent (proximal point) method and the bundle method
in proximal form (considered as a sequence of serious steps). Other methods, such as a variant of the proximal point method
given by Correa and Lemaréchal, can also fit within this framework, depending on how they are implemented. The convex functions
covered by the analysis are those whose conjugates have subdifferentials that are locally upper Lipschitzian at the origin,
a property generalizing classical regularity conditions.
Received March 29, 1996 / Revised version received March 5, 1999? Published online June 11, 1999 相似文献
16.
Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality.
However, solving them by primal-dual interior point methods can take much time even for problems of moderate size. The recent
spectral bundle method of Helmberg and Rendl can solve quite efficiently large structured equality-constrained semidefinite
programs if the trace of the primal matrix variable is fixed, as happens in many applications. We extend the method so that
it can handle inequality constraints without seriously increasing computation time. In addition, we introduce inexact null
steps. This abolishes the need of computing exact eigenvectors for subgradients, which brings along significant advantages
in theory and in practice. Encouraging preliminary computational results are reported.
Received: February 1, 2000 / Accepted: September 26, 2001?Published online August 27, 2002
RID="*"
ID="*"A preliminary version of this paper appeared in the proceedings of IPCO ’98 [12]. 相似文献
17.
Roman A. Polyak 《Mathematical Programming》2002,92(2):197-235
We introduce an alternative to the smoothing technique approach for constrained optimization. As it turns out for any given
smoothing function there exists a modification with particular properties. We use the modification for Nonlinear Rescaling
(NR) the constraints of a given constrained optimization problem into an equivalent set of constraints.?The constraints transformation
is scaled by a vector of positive parameters. The Lagrangian for the equivalent problems is to the correspondent Smoothing
Penalty functions as Augmented Lagrangian to the Classical Penalty function or MBFs to the Barrier Functions. Moreover the
Lagrangians for the equivalent problems combine the best properties of Quadratic and Nonquadratic Augmented Lagrangians and
at the same time are free from their main drawbacks.?Sequential unconstrained minimization of the Lagrangian for the equivalent
problem in primal space followed by both Lagrange multipliers and scaling parameters update leads to a new class of NR multipliers
methods, which are equivalent to the Interior Quadratic Prox methods for the dual problem.?We proved convergence and estimate
the rate of convergence of the NR multipliers method under very mild assumptions on the input data. We also estimate the rate
of convergence under various assumptions on the input data.?In particular, under the standard second order optimality conditions
the NR method converges with Q-linear rate without unbounded increase of the scaling parameters, which correspond to the active
constraints.?We also established global quadratic convergence of the NR methods for Linear Programming with unique dual solution.?We
provide numerical results, which strongly support the theory.
Received: September 2000 / Accepted: October 2001?Published online April 12, 2002 相似文献
18.
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 相似文献
19.
In this paper, we consider a special class of nonconvex programming problems for which the objective function and constraints
are defined in terms of general nonconvex factorable functions. We propose a branch-and-bound approach based on linear programming
relaxations generated through various approximation schemes that utilize, for example, the Mean-Value Theorem and Chebyshev
interpolation polynomials coordinated with a Reformulation-Linearization Technique (RLT). A suitable partitioning process
is proposed that induces convergence to a global optimum. The algorithm has been implemented in C++ and some preliminary computational
results are reported on a set of fifteen engineering process control and design test problems from various sources in the
literature. The results indicate that the proposed procedure generates tight relaxations, even via the initial node linear
program itself. Furthermore, for nine of these fifteen problems, the application of a local search method that is initialized
at the LP relaxation solution produced the actual global optimum at the initial node of the enumeration tree. Moreover, for
two test cases, the global optimum found improves upon the solutions previously reported in the source literature.
Received: January 14, 1998 / Accepted: June 7, 1999?Published online December 15, 2000 相似文献
20.
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 相似文献