共查询到20条相似文献,搜索用时 15 毫秒
1.
Global Optimization of Nonlinear Bilevel Programming Problems 总被引:5,自引:0,他引:5
A novel technique that addresses the solution of the general nonlinear bilevel programming problem to global optimality is presented. Global optimality is guaranteed for problems that involve twice differentiable nonlinear functions as long as the linear independence constraint qualification condition holds for the inner problem constraints. The approach is based on the relaxation of the feasible region by convex underestimation, embedded in a branch and bound framework utilizing the basic principles of the deterministic global optimization algorithm, BB [2, 4, 5, 11]. Epsilon global optimality in a finite number of iterations is theoretically guaranteed. Computational studies on several literature problems are reported. 相似文献
2.
Ivo Nowak 《Journal of Global Optimization》2000,18(4):337-356
A central problem of branch-and-bound methods for global optimization is that often a lower bound do not match with the optimal value of the corresponding subproblem even if the diameter of the partition set shrinks to zero. This can lead to a large number of subdivisions preventing the method from terminating in reasonable time. For the all-quadratic optimization problem with convex constraints we present optimality cuts which cut off a given local minimizer from the feasible set. We propose a branch-and-bound algorithm using optimality cuts which is finite if all global minimizers fulfill a certain second order optimality condition. The optimality cuts are based on the formulation of a dual problem where additional redundant constraints are added. This technique is also used for constructing tight lower bounds. Moreover we present for the box-constrained and the standard quadratic programming problem dual bounds which have under certain conditions a zero duality gap. 相似文献
3.
In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable. 相似文献
4.
This paper presents a global optimization approach for solving signomial geometric programming problems. In most cases nonconvex optimization problems with signomial parts are difficult, NP-hard problems to solve for global optimality. But some transformation and convexification strategies can be used to convert the original signomial geometric programming problem into a series of standard geometric programming problems that can be solved to reach a global solution. The tractability and effectiveness of the proposed successive convexification framework is demonstrated by seven numerical experiments. Some considerations are also presented to investigate the convergence properties of the algorithm and to give a performance comparison of our proposed approach and the current methods in terms of both computational efficiency and solution quality. 相似文献
5.
6.
We study the transit frequency optimization problem, which aims to determine the time interval between subsequent buses for a set of public transportation lines given by their itineraries, i.e., sequences of stops and street sections. The solution should satisfy a given origin–destination demand and a constraint on the available fleet of buses. We propose a new mixed integer linear programming (MILP) formulation for an already existing model, originally formulated as a nonlinear bilevel one. The proposed formulation is able to solve to optimality real small-sized instances of the problem using MILP techniques. For solving larger instances we propose a metaheuristic which accuracy is estimated by comparing against exact results (when possible). Both exact and approximated approaches are tested by using existing cases, including a real one related to a small-city which public transportation system comprises 13 lines. The magnitude of the improvement of that system obtained by applying the proposed methodologies, is comparable with the improvements reported in the literature, related to other real systems. Also, we investigate the applicability of the metaheuristic to a larger-sized real case, comprising more than 130 lines. 相似文献
7.
《European Journal of Operational Research》1999,116(3):640-652
The clusterwise regression model is used to perform cluster analysis within a regression framework. While the traditional regression model assumes the regression coefficient (β) to be identical for all subjects in the sample, the clusterwise regression model allows β to vary with subjects of different clusters. Since the cluster membership is unknown, the estimation of the clusterwise regression is a tough combinatorial optimization problem. In this research, we propose a “Generalized Clusterwise Regression Model” which is formulated as a mathematical programming (MP) problem. A nonlinear programming procedure (with linear constraints) is proposed to solve the combinatorial problem and to estimate the cluster membership and β simultaneously. Moreover, by integrating the cluster analysis with the discriminant analysis, a clusterwise discriminant model is developed to incorporate parameter heterogeneity into the traditional discriminant analysis. The cluster membership and discriminant parameters are estimated simultaneously by another nonlinear programming model. 相似文献
8.
Two approaches that solve the mixed-integer nonlinear bilevel programming problem to global optimality are introduced. The first addresses problems mixed-integer nonlinear in outer variables and C2-nonlinear in inner variables. The second adresses problems with general mixed-integer nonlinear functions in outer level. Inner level functions may be mixed-integer nonlinear in outer variables, linear, polynomial, or multilinear in inner integer variables, and linear in inner continuous variables. This second approach is based on reformulating the mixed-integer inner problem as continuous via its vertex polyheral convex hull representation and solving the resulting nonlinear bilevel optimization problem by a novel deterministic global optimization framework. Computational studies illustrate proposed approaches. 相似文献
9.
Descent approaches for quadratic bilevel programming 总被引:7,自引:0,他引:7
The bilevel programming problem involves two optimization problems where the data of the first one is implicitly determined by the solution of the second. In this paper, we introduce two descent methods for a special instance of bilevel programs where the inner problem is strictly convex quadratic. The first algorithm is based on pivot steps and may not guarantee local optimality. A modified steepest descent algorithm is presented to overcome this drawback. New rules for computing exact stepsizes are introduced and a hybrid approach that combines both strategies is discussed. It is proved that checking local optimality in bilevel programming is a NP-hard problem.Support of this work has been provided by INIC (Portugal) under Contract 89/EXA/5, by FCAR (Québec), and by NSERC and DND-ARP (Canada). 相似文献
10.
Scalarizing vector optimization problems 总被引:5,自引:0,他引:5
A scalarization of vector optimization problems is proposed, where optimality is defined through convex cones. By varying the parameters of the scalar problem, it is possible to find all vector optima from the scalar ones. Moreover, it is shown that, under mild assumptions, the dependence is differentiable for smooth objective maps defined over reflexive Banach spaces. A sufficiency condition of optimality for a general mathematical programming problem is also given in the Appendix. 相似文献
11.
H. Tuy 《Journal of Optimization Theory and Applications》2003,118(1):201-216
We discuss global optimality conditions and cutting plane algorithms for DC optimization. The discussion is motivated by certain incorrect results that have appeared recently in the literature on these topics. Incidentally, we investigate the relation of the Tikhonov reciprocity theorem to the optimality conditions for general nonconvex global optimization problems and show how the outer-approximation scheme developed earlier for DC programming can be used to solve a wider class of problems. 相似文献
12.
In this work we present a global optimization algorithm for solving a class of large-scale nonconvex optimization models that
have a decomposable structure. Such models, which are very expensive to solve to global optimality, are frequently encountered
in two-stage stochastic programming problems, engineering design, and also in planning and scheduling. A generic formulation
and reformulation of the decomposable models is given. We propose a specialized deterministic branch-and-cut algorithm to
solve these models to global optimality, wherein bounds on the global optimum are obtained by solving convex relaxations of
these models with certain cuts added to them in order to tighten the relaxations. These cuts are based on the solutions of
the sub-problems obtained by applying Lagrangean decomposition to the original nonconvex model. Numerical examples are presented
to illustrate the effectiveness of the proposed method compared to available commercial global optimization solvers that are
based on branch and bound methods. 相似文献
13.
This paper is concerned with the study of optimality conditions for disjunctive fractional minmax programming problems in which the decision set can be considered as a union of a family of convex sets. Dinkelbach’s global optimization approach for finding the global maximum of the fractional programming problem is discussed. Using the Lagrangian function definition for this type of problem, the Kuhn–Tucker saddle point and stationary-point problems are established. In addition, via the concepts of Mond–Weir type duality and Schaible type duality, a general dual problem is formulated and some weak, strong and converse duality theorems are proven. 相似文献
14.
15.
We are concerned with concave programming or the convex maximization problem. In this paper, we propose a method and algorithm
for solving the problem which are based on the global optimality conditions first obtained by Strekalovsky (Soviet Mathematical
Doklady, 8(1987)). The method continues approaches given in (Journal of global optimization, 8(1996); Journal of Nolinear
and convex Analyses 4(1)(2003)). Under certain assumptions a convergence property of the proposed method has been established.
Some computational results are reported. Also, it has been shown that the problem of finding the largest eigenvalue can be
found by the proposed method. 相似文献
16.
在本文中,我们提出了双凹规划问题和更一般的广义凹规划问题。我们给出了双凹规划问题的整体最优性条件,并构造了一个有限终止外逼近算法。 相似文献
17.
In goal programming problem, the general equilibrium and optimization are often two conflicting factors. This paper proposes a generalized varying-domain optimization method for fuzzy goal programming (FGP) incorporating multiple priorities. According to the three possible styles of the objective function, the varying-domain optimization method and its generalization are proposed. This method can generate the results consistent with the decision-maker (DM)’s expectation, that the goal with higher priority may have higher level of satisfaction. Using this new method, it is a simple process to balance between the equilibrium and optimization, and the result is the consequence of a synthetic decision between them. In contrast to the previous method, the proposed method can make that the higher priority achieving the higher satisfactory degree. To get the global solution of the nonlinear nonconvex programming problem resulting from the original problem and the varying-domain optimization method, the co-evolutionary genetic algorithms (GAs), called GENOCOPIII, is used instead of the SQP method. In this way the DM can get the optimum of the optimization problem. We demonstrate the power of this proposed method by illustrative examples. 相似文献
18.
The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems 总被引:1,自引:0,他引:1
The DC programming and its DC algorithm (DCA) address the problem of minimizing a function f=g−h (with g,h being lower semicontinuous proper convex functions on R
n
) on the whole space. Based on local optimality conditions and DC duality, DCA was successfully applied to a lot of different
and various nondifferentiable nonconvex optimization problems to which it quite often gave global solutions and proved to
be more robust and more efficient than related standard methods, especially in the large scale setting. The computational
efficiency of DCA suggests to us a deeper and more complete study on DC programming, using the special class of DC programs
(when either g or h is polyhedral convex) called polyhedral DC programs. The DC duality is investigated in an easier way, which is more convenient
to the study of optimality conditions. New practical results on local optimality are presented. We emphasize regularization
techniques in DC programming in order to construct suitable equivalent DC programs to nondifferentiable nonconvex optimization
problems and new significant questions which have to be answered. A deeper insight into DCA is introduced which really sheds
new light on DCA and could partly explain its efficiency. Finally DC models of real world nonconvex optimization are reported. 相似文献
19.
20.
Morteza Pakdaman 《Applied mathematics and computation》2011,217(12):5998
In this comment, we preset a minor mistake in typing which is made in “A new local and global optimization method for mixed integer quadratic programming problems” by G.Q. Li et al. 相似文献