共查询到20条相似文献,搜索用时 781 毫秒
1.
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 相似文献
2.
Basis- and partition identification for quadratic programming and linear complementarity problems 总被引:1,自引:0,他引:1
Arjan B. Berkelaar Benjamin Jansen Kees Roos Tamás Terlaky 《Mathematical Programming》1999,86(2):261-282
Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide
maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other
hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification
algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification
algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from
any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski
and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity
problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality
property of basis tableaus.
Received April 9, 1996 / Revised version received April 27, 1998?
Published online May 12, 1999 相似文献
3.
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 相似文献
4.
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 相似文献
5.
A class of affine-scaling interior-point methods for bound constrained optimization problems is introduced which are locally
q–superlinear or q–quadratic convergent. It is assumed that the strong second order sufficient optimality conditions at the
solution are satisfied, but strict complementarity is not required. The methods are modifications of the affine-scaling interior-point
Newton methods introduced by T. F. Coleman and Y. Li (Math. Programming, 67, 189–224, 1994). There are two modifications. One is a modification of the scaling matrix, the other one is the use of a
projection of the step to maintain strict feasibility rather than a simple scaling of the step. A comprehensive local convergence
analysis is given. A simple example is presented to illustrate the pitfalls of the original approach by Coleman and Li in
the degenerate case and to demonstrate the performance of the fast converging modifications developed in this paper.
Received October 2, 1998 / Revised version received April 7, 1999?Published online July 19, 1999 相似文献
6.
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 相似文献
7.
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 相似文献
8.
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 相似文献
9.
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 相似文献
10.
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 相似文献
11.
The 0-1 Knapsack problem with a single continuous variable 总被引:5,自引:0,他引:5
Specifically we investigate the polyhedral structure of the knapsack problem with a single continuous variable, called the
mixed 0-1 knapsack problem. First different classes of facet-defining inequalities are derived based on restriction and lifting. The order of
lifting, particularly of the continuous variable, plays an important role. Secondly we show that the flow cover inequalities
derived for the single node flow set, consisting of arc flows into and out of a single node with binary variable lower and
upper bounds on each arc, can be obtained from valid inequalities for the mixed 0-1 knapsack problem. Thus the separation
heuristic we derive for mixed knapsack sets can also be used to derive cuts for more general mixed 0-1 constraints. Initial
computational results on a variety of problems are presented.
Received May 22, 1997 / Revised version received December 22, 1997 Published online November 24, 1998 相似文献
12.
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 相似文献
13.
Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods 总被引:6,自引:0,他引:6
The paper extends prior work by the authors on loqo, an interior point algorithm for nonconvex nonlinear programming. The
specific topics covered include primal versus dual orderings and higher order methods, which attempt to use each factorization
of the Hessian matrix more than once to improve computational efficiency. Results show that unlike linear and convex quadratic
programming, higher order corrections to the central trajectory are not useful for nonconvex nonlinear programming, but that
a variant of Mehrotra’s predictor-corrector algorithm can definitely improve performance.
Received: May 3, 1999 / Accepted: January 24, 2000?Published online March 15, 2000 相似文献
14.
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 相似文献
15.
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]. 相似文献
16.
An improved rounding method and semidefinite programming relaxation for graph partition 总被引:8,自引:0,他引:8
Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming
(SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance
ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP
relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut,
and Max-Vertex-Cover.
Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002 相似文献
17.
We investigate certain combinatorial properties of the central curve associated with interior point methods for linear optimization.
We define a measure of complexity for the curve in terms of the number of turns, or changes of direction, that it makes in
a geometric sense, and then perform an average case analysis of this measure for P-matrix linear complementarity problems. We show that the expected number of nondegenerate turns taken by the central curve
is bounded by n
2-n, where the expectation is taken with respect to a sign-invariant probability distribution on the problem data. As an alternative
measure of complexity, we also consider the number of times the central curve intersects with a wide class of algebraic hypersurfaces,
including such objects as spheres and boxes. As an example of the results obtained, we show that the primal and dual variables
in each coordinate of the central curve cross each other at most once, on average. As a further example, we show that the
central curve intersects any sphere centered at the origin at most twice, on average.
Received May 28, 1998 / Revised version received October 12, 1999?Published online December 15, 1999 相似文献
18.
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 相似文献
19.
Oktay Günlük 《Mathematical Programming》1999,86(1):17-39
We present a branch-and-cut algorithm to solve capacitated network design problems. Given a capacitated network and point-to-point
traffic demands, the objective is to install more capacity on the edges of the network and route traffic simultaneously, so
that the overall cost is minimized. We study a mixed-integer programming formulation of the problem and identify some new
facet defining inequalities. These inequalities, together with other known combinatorial and mixed-integer rounding inequalities,
are used as cutting planes. To choose the branching variable, we use a new rule called “knapsack branching”. We also report
on our computational experience using real-life data.
Received April 29, 1997 / Revised version received January 9, 1999? Published online June 28, 1999 相似文献
20.
Pierre Hansen 《Discrete Applied Mathematics》2009,157(6):1267-1290
We present and compare three new compact linearizations for the quadratic 0-1 minimization problem, two of which achieve the same lower bound as does the “standard linearization”. Two of the linearizations require the same number of constraints with respect to Glover’s one, while the last one requires n additional constraints where n is the number of variables in the quadratic 0-1 problem. All three linearizations require the same number of additional variables as does Glover’s linearization. This is an improvement on the linearization of Adams, Forrester and Glover (2004) which requires n additional variables and 2n additional constraints to reach the same lower bound as does the standard linearization. Computational results show however that linearizations achieving a weaker lower bound at the root node have better global performances than stronger linearizations when solved by Cplex. 相似文献