共查询到20条相似文献,搜索用时 140 毫秒
1.
A method is presented for computing convex and concave relaxations of the parametric solutions of nonlinear, semi-explicit, index-one differential-algebraic equations (DAEs). These relaxations are central to the development of a deterministic global optimization algorithm for problems with DAEs embedded. The proposed method uses relaxations of the DAE equations to derive an auxiliary system of DAEs, the solutions of which are proven to provide the desired relaxations. The entire procedure is fully automatable. 相似文献
2.
A new method is described for computing nonlinear convex and concave relaxations of the solutions of parametric ordinary differential equations (ODEs). Such relaxations enable deterministic global optimization algorithms to be applied to problems with ODEs embedded, which arise in a wide variety of engineering applications. The proposed method computes relaxations as the solutions of an auxiliary system of ODEs, and a method for automatically constructing and numerically solving appropriate auxiliary ODEs is presented. This approach is similar to two existing methods, which are analyzed and shown to have undesirable properties that are avoided by the new method. Two numerical examples demonstrate that these improvements lead to significantly tighter relaxations than previous methods. 相似文献
3.
McCormick’s classical relaxation technique constructs closed-form convex and concave relaxations of compositions of simple intrinsic functions. These relaxations have several properties which make them useful for lower bounding problems in global optimization: they can be evaluated automatically, accurately, and computationally inexpensively, and they converge rapidly to the relaxed function as the underlying domain is reduced in size. They may also be adapted to yield relaxations of certain implicit functions and differential equation solutions. However, McCormick’s relaxations may be nonsmooth, and this nonsmoothness can create theoretical and computational obstacles when relaxations are to be deployed. This article presents a continuously differentiable variant of McCormick’s original relaxations in the multivariate McCormick framework of Tsoukalas and Mitsos. Gradients of the new differentiable relaxations may be computed efficiently using the standard forward or reverse modes of automatic differentiation. Extensions to differentiable relaxations of implicit functions and solutions of parametric ordinary differential equations are discussed. A C++ implementation based on the library MC++ is described and applied to a case study in nonsmooth nonconvex optimization. 相似文献
4.
A new approach is proposed for finding all real solutions of systems of nonlinear equations with bound constraints. The zero
finding problem is converted to a global optimization problem whose global minima with zero objective value, if any, correspond
to all solutions of the original problem. A branch-and-bound algorithm is used with McCormick’s nonsmooth convex relaxations
to generate lower bounds. An inclusion relation between the solution set of the relaxed problem and that of the original nonconvex
problem is established which motivates a method to generate automatically, starting points for a local Newton-type method.
A damped-Newton method with natural level functions employing the restrictive monotonicity test is employed to find solutions robustly and rapidly. Due to the special structure of the objective function, the solution
of the convex lower bounding problem yields a nonsmooth root exclusion test which is found to perform better than earlier
interval-analysis based exclusion tests. Both the componentwise Krawczyk operator and interval-Newton operator with Gauss-Seidel
based root inclusion and exclusion tests are also embedded in the proposed algorithm to refine the variable bounds for efficient
fathoming of the search space. The performance of the algorithm on a variety of test problems from the literature is presented,
and for most of them, the first solution is found at the first iteration of the algorithm due to the good starting point generation. 相似文献
5.
This paper examines global optimization of an integral objective function subject to nonlinear ordinary differential equations.
Theory is developed for deriving a convex relaxation for an integral by utilizing the composition result defined by McCormick
(Mathematical Programming 10, 147–175, 1976) in conjunction with a technique for constructing convex and concave relaxations
for the solution of a system of nonquasimonotone ordinary differential equations defined by Singer and Barton (SIAM Journal
on Scientific Computing, Submitted). A fully automated implementation of the theory is briefly discussed, and several literature
case study problems are examined illustrating the utility of the branch-and-bound algorithm based on these relaxations. 相似文献
6.
Yurii Nesterov 《Mathematical Programming》2011,127(1):31-56
In this paper we develop a new affine-invariant primal–dual subgradient method for nonsmooth convex optimization problems.
This scheme is based on a self-concordant barrier for the basic feasible set. It is suitable for finding approximate solutions
with certain relative accuracy. We discuss some applications of this technique including fractional covering problem, maximal concurrent flow problem, semidefinite
relaxations and nonlinear online optimization. For all these problems, the rate of convergence of our method does not depend
on the problem’s data. 相似文献
7.
This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer
constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and
discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without
duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual
solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is
equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique.
Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm
is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite
programming method is revealed. 相似文献
8.
César Gutiérrez Bienvenido Jiménez Vicente Novo 《Computational Optimization and Applications》2006,35(3):305-324
This work deals with approximate solutions in vector optimization problems. These solutions frequently appear when an iterative
algorithm is used to solve a vector optimization problem. We consider a concept of approximate efficiency introduced by Kutateladze
and widely used in the literature to study this kind of solutions. Necessary and sufficient conditions for Kutateladze’s approximate
solutions are given through scalarization, in such a way that these points are approximate solutions for a scalar optimization
problem. Necessary conditions are obtained by using gauge functionals while monotone functionals are considered to attain
sufficient conditions. Two properties are then introduced to describe the idea of parametric representation of the approximate
efficient set. Finally, through scalarization, characterizations and parametric representations for the set of approximate
solutions in convex and nonconvex vector optimization problems are proved and the obtained results are applied to Pareto problems.
AMS Classification:90C29, 49M37
This research was partially supported by Ministerio de Ciencia y Tecnología (Spain), project BFM2003-02194. 相似文献
9.
M. Köppe M. Queyranne C. T. Ryan 《Journal of Optimization Theory and Applications》2010,146(1):137-150
We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables.
Using recent results in parametric integer programming, we present polynomial time algorithms for pure and mixed integer bilevel
problems. For the mixed integer case where the leader’s variables are continuous, our algorithm also detects whether the infimum
cost fails to be attained, a difficulty that has been identified but not directly addressed in the literature. In this case,
it yields a “better than fully polynomial time” approximation scheme with running time polynomial in the logarithm of the
absolute precision. For the pure integer case where the leader’s variables are integer, and hence optimal solutions are guaranteed
to exist, we present an algorithm which runs in polynomial time when the total number of variables is fixed. 相似文献
10.
We study approaches for obtaining convex relaxations of global optimization problems containing multilinear functions. Specifically, we compare the concave and convex envelopes of these functions with the relaxations that are obtained with a standard relaxation approach, due to McCormick. The standard approach reformulates the problem to contain only bilinear terms and then relaxes each term independently. We show that for a multilinear function having a single product term, this approach yields the convex and concave envelopes if the bounds on all variables are symmetric around zero. We then review and extend some results on conditions when the concave envelope of a multilinear function can be written as a sum of concave envelopes of its individual terms. Finally, for bilinear functions we prove that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is always within a constant of the difference between the concave and convex envelopes. These results, along with numerical examples we provide, give insight into how to construct strong relaxations of multilinear functions. 相似文献
11.
We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MILP only. We propose a technique to obtain valid inequalities that are based on both the MILP constraints and the concave constraints. We begin by characterizing the convex hull of a four-dimensional set consisting of a single binary indicator variable, a single concave constraint, and two linear inequalities. Using this analysis, we demonstrate how valid inequalities for the single node flow set and for the lot-sizing polyhedron can be “tilted” to give valid inequalities that also account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities for nonlinear transportation problems and for lot-sizing problems with concave costs. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed-integer nonlinear programs. 相似文献
12.
Jing Ping YANG Shi Hong CHENG Xiao Qian WANG 《数学学报(英文版)》2007,23(3):467-478
This paper investigates bivariate recursive equations on excess-of-loss reinsurance. For an insurance portfolio, under the assumptions that the individual claim severity distribution has bounded continuous density and the number of claims belongs to R1 (a, b) family, bivariate recursive equations for the joint distribution of the cedent's aggregate claims and the reinsurer's aggregate claims are obtained. 相似文献
13.
This article considers the non-linear mixed 0–1 optimization problems that appear in topology optimization of load carrying
structures. The main objective is to present a Generalized Benders’ Decomposition (GBD) method for solving single and multiple
load minimum compliance (maximum stiffness) problems with discrete design variables to global optimality. We present the theoretical
aspects of the method, including a proof of finite convergence and conditions for obtaining global optimal solutions. The
method is also linked to, and compared with, an Outer-Approximation approach and a mixed 0–1 semi definite programming formulation
of the considered problem. Several ways to accelerate the method are suggested and an implementation is described. Finally,
a set of truss topology optimization problems are numerically solved to global optimality. 相似文献
14.
María C. Maciel Sandra A. Santos Graciela N. Sottosanto 《Journal of Optimization Theory and Applications》2011,149(2):332-351
In this article, two second-order constraint qualifications for the vector optimization problem are introduced, that come
from first-order constraint qualifications, originally devised for the scalar case. The first is based on the classical feasible
arc constraint qualification, proposed by Kuhn and Tucker (Proceedings of the Second Berkeley Symposium on Mathematical Statistics
and Probability, vol. 1, pp. 481–492, University of California Press, California, 1951) together with a slight modification of McCormick’s second-order constraint qualification. The second—the constant rank constraint
qualification—was introduced by Janin (Math. Program. Stud. 21:110–126, 1984). They are used to establish two second-order necessary conditions for the vector optimization problem, with general nonlinear
constraints, without any convexity assumption. 相似文献
15.
Yuri A. Melnikov 《Central European Journal of Mathematics》2010,8(1):53-72
Convenient for immediate computer implementation equivalents of Green’s functions are obtained for boundary-contact value
problems posed for two-dimensional Laplace and Klein-Gordon equations on some regions filled in with piecewise homogeneous
isotropic conductive materials. Dirichlet, Neumann and Robin conditions are allowed on the outer boundary of a simply-connected
region, while conditions of ideal contact are assumed on interface lines. The objective in this study is to widen the range
of effective applicability for the Green’s function version of the boundary integral equation method making the latter usable
for equations with piecewise-constant coefficients. 相似文献
16.
Polyhedral relaxations have been incorporated in a variety of solvers for the global optimization of mixed-integer nonlinear programs. Currently, these relaxations constitute the dominant approach in global optimization practice. In this paper, we introduce a new relaxation paradigm for global optimization. The proposed framework combines polyhedral and convex nonlinear relaxations, along with fail-safe techniques, convexity identification at each node of the branch-and-bound tree, and learning strategies for automatically selecting and switching between polyhedral and nonlinear relaxations and among different local search algorithms in different parts of the search tree. We report computational experiments with the proposed methodology on widely-used test problem collections from the literature, including 369 problems from GlobalLib, 250 problems from MINLPLib, 980 problems from PrincetonLib, and 142 problems from IBMLib. Results show that incorporating the proposed techniques in the BARON software leads to significant reductions in execution time, and increases by 30% the number of problems that are solvable to global optimality within 500 s on a standard workstation. 相似文献
17.
David Yang Gao 《Journal of Global Optimization》2006,35(1):131-143
This paper presents a set of complete solutions to a class of polynomial optimization problems. By using the so-called sequential canonical dual transformation developed in the author’s recent book [Gao, D.Y. (2000), Duality Principles in Nonconvex Systems: Theory, Method and Applications,
Kluwer Academic Publishers, Dordrecht/Boston/London, xviii + 454 pp], the nonconvex polynomials in
can be converted into an one-dimensional canonical dual optimization problem, which can be solved completely. Therefore,
a set of complete solutions to the original problem is obtained. Both global minimizer and local extrema of certain special
polynomials can be indentified by Gao-Strang’s gap function and triality theory. For general nonconvex polynomial minimization
problems, a sufficient condition is proposed to identify global minimizer. Applications are illustrated by several examples. 相似文献
18.
In this article we investigate a new variant of Variable Neighborhood Search (VNS): Relaxation Guided Variable Neighborhood
Search. It is based on the general VNS scheme and a new Variable Neighborhood Descent (VND) algorithm. The ordering of the
neighborhood structures in this VND is determined dynamically by solving relaxations of them. The objective values of these
relaxations are used as indicators for the potential gains of searching the corresponding neighborhoods. We tested this new
approach on the well-studied multidimensional knapsack problem. Computational experiments show that our approach is beneficial
to the search, improving the obtained results. The concept is, in principle, more generally applicable and seems to be promising
for many other combinatorial optimization problems approached by VNS.
NICTA is funded by the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research
Council.The Institute of Computer Graphics and Algorithms is supported by the European RTN ADONET under grant 504438. 相似文献
19.
JIANJINBAO 《高校应用数学学报(英文版)》1997,12(3):343-354
In this paper, a new superlinearly convergent algorithm is presented for optimization problems with general nonlineer equality and inequality Constraints, Comparing with other methods for these problems, the algorithm has two main advantages. First, it doesn‘t solve anyquadratic programming (QP), and its search directions are determined by the generalized projection technique and the solutions of two systems of linear equations. Second, the sequential points generated by the algoritbh satisfy all inequity constraints and its step-length is computed by the straight line search,The algorithm is proved to possesa global and auperlinear convergence. 相似文献
20.
《Operations Research Letters》2023,51(2):146-152
Recursive McCormick relaxations are among the most popular convexification techniques for binary polynomial optimization. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal sequence amounts to solving a difficult combinatorial optimization problem. We prove that any recursive McCormick relaxation is implied by the extended flower relaxation, a linear programming relaxation, which for binary polynomial optimization problems with fixed degree can be solved in strongly polynomial time. 相似文献