共查询到20条相似文献,搜索用时 31 毫秒
1.
In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions. 相似文献
2.
This paper presents a multiplier-type method for nonlinear programming problems with both equality and inequality constraints. Slack variables are used for the inequalities. The penalty coefficient is adjusted automatically, and the method converges quadratically to points satisfying second-order conditions.The work of the first author was supported by NSF RANN and JSEP Contract No. F44620-71-C-0087; the work of the second author was supported by the National Science Foundation Grant No. ENG73-08214A01 and US Army Research Office Durham Contract No. DAHC04-73-C-0025. 相似文献
3.
On the mixed integer signomial programming problems 总被引:1,自引:0,他引:1
Ching-Ter Chang 《Applied mathematics and computation》2005,170(2):1436-1451
This paper proposes an approximate method to solve the mixed integer signomial programming problem, for which the objective function and the constraints may contain product terms with exponents and decision variables, which could be continuous or integral. A linear programming relaxation is derived for the problem based on piecewise linearization techniques, which first convert a signomial term into the sum of absolute terms; these absolute terms are then linearized by linearization strategies. In addition, a novel approach is included for solving integer and undefined problems in the logarithmic piecewise technique, which leads to more usefulness of the proposed method. The proposed method could reach a solution as close as possible to the global optimum. 相似文献
4.
5.
This paper treats a class of posynomial-like functions whose variables may appear also as exponents or in logarithms. It is shown that the resulting programs, called transcendental geometric programs, retain many useful properties of ordinary geometric programs, although the new class of problems need not have unique minima and cannot, in general, be transformed into convex programs. A duality theory, analogous to geometric programming duality, is formulated under somewhat more restrictive conditions. The dual constraints are not all linear, but the notion ofdegrees of difficulty is maintained in its geometric programming sense. One formulation of the dual program is shown to be a generalization of the chemical equilibrium problem where correction factors are added to account for nonideality. Some of the computational difficulties in solving transcendental programs are discussed briefly.This research was partially supported by the National Institute of Health Grant No. GM-14789; Office of Naval Research under Contract No. N00014-75-C-0276; National Science Foundation Grant No. MPS-71-03341 A03; and the US Atomic Energy Commission Contract No. AT(04-3)-326 PA #18. 相似文献
6.
R. T. Rockafellar 《Mathematical Programming》1990,48(1-3):447-474
Numerical approaches are developed for solving large-scale problems of extended linear-quadratic programming that exhibit Lagrangian separability in both primal and dual variables simultaneously. Such problems are kin to large-scale linear complementarity models as derived from applications of variational inequalities, and they arise from general models in multistage stochastic programming and discrete-time optimal control. Because their objective functions are merely piecewise linear-quadratic, due to the presence of penalty terms, they do not fit a conventional quadratic programming framework. They have potentially advantageous features, however, which so far have not been exploited in solution procedures. These features are laid out and analyzed for their computational potential. In particular, a new class of algorithms, called finite-envelope methods, is described that does take advantage of the structure. Such methods reduce the solution of a high-dimensional extended linear-quadratic program to that of a sequence of low-dimensional ordinary quadratic programs.This work was supported in part by grants AFOSR 87-0821 and AFOSR 89-0081 from the Air Force Office of Scientific Research. 相似文献
7.
Douglas J. White 《Mathematical Programming》1985,31(2):192-205
The Lagrangean function for scalar constrained optimisation problems is extended in a directly analogous manner to constrained
vector optimisation problems. Some simple saddle point results are presented for vector maxima sets. Conditions are given
for the characterisation of the vector maximum set of the original vector problem in terms of the vector maximum sets with
respect to the vector Lagrangeans.
Finally some attention is given to Lagrangean relaxation for vector optimisation problems as an extension of a result of Everett. 相似文献
8.
We present a framework for sequential decision making in problems described by graphical models. The setting is given by dependent discrete random variables with associated costs or revenues. In our examples, the dependent variables are the potential outcomes (oil, gas or dry) when drilling a petroleum well. The goal is to develop an optimal selection strategy of wells that incorporates a chosen utility function within an approximated dynamic programming scheme. We propose and compare different approximations, from naive and myopic heuristics to more complex look-ahead schemes, and we discuss their computational properties. We apply these strategies to oil exploration over multiple prospects modeled by a directed acyclic graph, and to a reservoir drilling decision problem modeled by a Markov random field. The results show that the suggested strategies clearly improve the naive or myopic constructions used in petroleum industry today. This is useful for decision makers planning petroleum exploration policies. 相似文献
9.
We present a new method for computing bounds on parametric solutions of convex problems. The approach is based on a uniform quadratic underestimation of the objective function and a simple technique for the calculation of bounds on the optimal value function.Research supported by Grant ECS-8619859, National Science Foundation and Contract N00017-86-K-0052, Office of Naval Research. 相似文献
10.
Dimitri P. Bertsekas 《Mathematical Programming》1985,32(2):125-145
We introduce a broad class of algorithms for finding a minimum cost flow in a capacitated network. The algorithms are of the primal-dual type. They maintain primal feasibility with respect to capacity constraints, while trying to satisfy the conservation of flow equation at each node by means of a wide variety of procedures based on flow augmentation, price adjustment, and ascent of a dual functional. The manner in which these procedures are combined is flexible thereby allowing the construction of algorithms that can be tailored to the problem at hand for maximum effectiveness. Particular attention is given to methods that incorporate features from classical relaxation procedures. Experimental codes based on these methods outperform by a substantial margin the fastest available primal-dual and primal simplex codes on standard benchmark problems.This work was supported by the National Science Foundation under Contract NSF/ECS 8217668. 相似文献
11.
12.
On multilevel iterative methods for optimization problems 总被引:2,自引:0,他引:2
This paper is concerned with multilevel iterative methods which combine a descent scheme with a hierarchy of auxiliary problems in lower dimensional subspaces. The construction of auxiliary problems as well as applications to elasto-plastic model and linear programming are described. The auxiliary problem for the dual of a perturbed linear program is interpreted as a dual of perturbed aggregated linear program. Coercivity of the objective function over the feasible set is sufficient for the boundedness of the iterates. Equivalents of this condition are presented in special cases.Supported by NSF under grant DMS-8704169, AFOSR under grant 86-0126, and ONR under Contract N00014-83-K-0104. Consulting for American Airlines Decision Technologies, MD 2C55, P.O. Box 619616, DFW, TX 75261-9616, USA.Supported by NSF under grant DMS-8704169 and AFOSR under grant 86-0126. 相似文献
13.
Philip E. Gill Walter Murray Michael A. Saunders J. A. Tomlin Margaret H. Wright 《Mathematical Programming》1986,36(2):183-209
Interest in linear programming has been intensified recently by Karmarkar’s publication in 1984 of an algorithm that is claimed
to be much faster than the simplex method for practical problems. We review classical barrier-function methods for nonlinear
programming based on applying a logarithmic transformation to inequality constraints. For the special case of linear programming,
the transformed problem can be solved by a “projected Newton barrier” method. This method is shown to be equivalent to Karmarkar’s
projective method for a particular choice of the barrier parameter. We then present details of a specific barrier algorithm
and its practical implementation. Numerical results are given for several non-trivial test problems, and the implications
for future developments in linear programming are discussed.
The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AA03-76SF00326, PA No. DE-AS03-76ER72018;
National Science Foundation Grants DCR-8413211 and ECS-8312142; the Office of Naval Research Contract N00014-85-K-0343; and
the U.S. Army Research Office Contract DAAG29-84-K-0156.
The research of J.A. Tomlin was supported by Ketron, Inc. and the Office of Naval Research Contract N00014-85-C-0338. 相似文献
14.
Michael J. Todd 《Mathematical Programming》1992,55(1-3):1-15
Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better search directions and a more useful algorithm. Much of the analysis depends on a two-constraint linear programming problem that is a relaxation of the scaled original problem.Research supported in part by NSF Grant ECS-8602534 and ONR Contract N00014-87-K-0212. 相似文献
15.
Resolution method for mixed integer bi-level linear problems based on decomposition technique 总被引:2,自引:0,他引:2
In this article, we propose a new algorithm for the resolution of mixed integer bi-level linear problem (MIBLP). The algorithm
is based on the decomposition of the initial problem into the restricted master problem (RMP) and a series of problems named
slave problems (SP). The proposed approach is based on Benders decomposition method where in each iteration a set of variables
are fixed which are controlled by the upper level optimization problem. The RMP is a relaxation of the MIBLP and the SP represents
a restriction of the MIBLP. The RMP interacts in each iteration with the current SP by the addition of cuts produced using
Lagrangian information from the current SP. The lower and upper bound provided from the RMP and SP are updated in each iteration.
The algorithm converges when the difference between the upper and lower bound is within a small difference ε. In the case of MIBLP Karush–Kuhn–Tucker (KKT) optimality conditions could not be used directly to the inner problem in order
to transform the bi-level problem into a single level problem. The proposed decomposition technique, however, allows the use
of KKT conditions and transforms the MIBLP into two single level problems. The algorithm, which is a new method for the resolution
of MIBLP, is illustrated through a modified numerical example from the literature. Additional examples from the literature
are presented to highlight the algorithm convergence properties. 相似文献
16.
This paper presents a secant method, based on R. B. Wilson's formula for the solution of optimization problems with inequality constraints. Global convergence properties are ensured by grafting the secant method onto a phase I - phase II feasible directions method, using a rate of convergence test for crossover control.This research was sponsored by the National Science Foundation, Grant No. ENG-73-08214 and Grant No. (RANN)-ENV-76-04264, and by the Joint Services Electronics Program. Contract No. F44620-76-C-0100. 相似文献
17.
We describe an implementation of the tabu search metaheuristic that effectively finds a low-cost topology for a communications network to provide a centralized new service. Our results are compared to those of a greedy algorithm which applies corresponding decision rules, but without the guidance of the tabu search framework. These problems are difficult computationally, representing integer programs that can involve as many as 10,000 integer variables and 2000 constraints in practical applications. The tabu search results approach succeeded in obtaining significant improvements over the greedy approach, yielding optimal solutions to problems small enough to allow independent verification of optimality status and, more generally, yielding both absolute and percentage cost improvements that did not deteriorate with increasing problem size.This research was partially supported by the Air Force Office of Scientific Research and the Office of Naval Research Contract No. F49629-90-C-0033. 相似文献
18.
Semidefinite programming in combinatorial optimization 总被引:7,自引:0,他引:7
Michel X. Goemans 《Mathematical Programming》1997,79(1-3):143-161
We discuss the use of semidefinite programming for combinatorial optimization problems. The main topics covered include (i)
the Lovász theta function and its applications to stable sets, perfect graphs, and coding theory, (ii) the automatic generation
of strong valid inequalities, (iii) the maximum cut problem and related problems, and (iv) the embedding of finite metric
spaces and its relationship to the sparsest cut problem.
Part of this work is supported by NSF contract 9623859-CCR, a Sloan Foundation Fellowship, and ARPA Contract N00014-95-1-1246. 相似文献
19.
Summary We present an algorithm which combines standard active set strategies with the gradient projection method for the solution of quadratic programming problems subject to bounds. We show, in particular, that if the quadratic is bounded below on the feasible set then termination occurs at a stationary point in a finite number of iterations. Moreover, if all stationary points are nondegenerate, termination occurs at a local minimizer. A numerical comparison of the algorithm based on the gradient projection algorithm with a standard active set strategy shows that on mildly degenerate problems the gradient projection algorithm requires considerable less iterations and time than the active set strategy. On nondegenerate problems the number of iterations typically decreases by at least a factor of 10. For strongly degenerate problems, the performance of the gradient projection algorithm deteriorates, but it still performs better than the active set method.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38 相似文献
20.
In this paper, we analyze some properties of the discrete linear bilevel program for different discretizations of the set of variables. We study the geometry of the feasible set and discuss the existence of an optimal solution. We also establish equivalences between different classes of discrete linear bilevel programs and particular linear multilevel programming problems. These equivalences are based on concave penalty functions and can be used to design penalty function methods for the solution of discrete linear bilevel programs.Support of this work has been provided by the INIC (Portugal) under Contract 89/EXA/5, by INVOTAN, FLAD, and CCLA (Portugal), and by FCAR (Québec), NSERC, and DND-ARP (Canada). 相似文献