共查询到20条相似文献,搜索用时 46 毫秒
1.
2.
《Optimization》2012,61(6):605-625
A class of convexification and concavification methods are proposed for solving some classes of non-monotone optimization problems. It is shown that some classes of non-monotone optimization problems can be converted into better structured optimization problems, such as, concave minimization problems, reverse convex programming problems, and canonical D.C. programming problems by the proposed convexification and concavification methods. The equivalence between the original problem and the converted better structured optimization problem is established. 相似文献
3.
We show in this paper that via certain convexification, concavification and monotonization schemes a nonconvex optimization problem over a simplex can be always converted into an equivalent better-structured nonconvex optimization problem, e.g., a concave optimization problem or a D.C. programming problem, thus facilitating the search of a global optimum by using the existing methods in concave minimization and D.C. programming. We first prove that a monotone optimization problem (with a monotone objective function and monotone constraints) can be transformed into a concave minimization problem over a convex set or a D.C. programming problem via pth power transformation. We then prove that a class of nonconvex minimization problems can be always reduced to a monotone optimization problem, thus a concave minimization problem or a D.C. programming problem. 相似文献
4.
A convexification method for a class of global optimization problems with applications to reliability optimization 总被引:1,自引:0,他引:1
A convexification method is proposed for solving a class of global optimization problems with certain monotone properties. It is shown that this class of problems can be transformed into equivalent concave minimization problems using the proposed convexification schemes. An outer approximation method can then be used to find the global solution of the transformed problem. Applications to mixed-integer nonlinear programming problems arising in reliability optimization of complex systems are discussed and satisfactory numerical results are presented. 相似文献
5.
首先将一个具有多个约束的规划问题转化为一个只有一个约束的规划问题,然后通过利用这个单约束的规划问题,对原来的多约束规划问题提出了一些凸化、凹化的方法,这样这些多约束的规划问题可以被转化为一些凹规划、反凸规划问题.最后,还证明了得到的凹规划和反凸规划的全局最优解就是原问题的近似全局最优解. 相似文献
6.
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. 相似文献
7.
Mixed-integer nonlinear programming (MINLP) problems involving general constraints and objective functions with continuous
and integer variables occur frequently in engineering design, chemical process industry and management. Although many optimization
approaches have been developed for MINLP problems, these methods can only handle signomial terms with positive variables or
find a local solution. Therefore, this study proposes a novel method for solving a signomial MINLP problem with free variables
to obtain a global optimal solution. The signomial MINLP problem is first transformed into another one containing only positive
variables. Then the transformed problem is reformulated as a convex mixed-integer program by the convexification strategies
and piecewise linearization techniques. A global optimum of the signomial MINLP problem can finally be found within the tolerable
error. Numerical examples are also presented to demonstrate the effectiveness of the proposed method. 相似文献
8.
本文提出了一个指数型凸化,凹化变换,并证明了单调非线性规划总能变换成相应的凹规划或凸规划.还证明了带某种类型线性或非线性约束的非线性规划在适当条件下能变换成单调非线性规划. 相似文献
9.
单调优化是指目标函数与约束函数均为单调函数的全局优化问题.本文提出一种新的凸化变换方法把单调函数化为凸函数,进而把单调优化问题化为等价的凸极大或凹极小问题,然后采用Hoffman的外逼近方法来求得问题的全局最优解.我们把这种凸化方法同Tuy的Polyblock外逼近方法作了比较,通过数值比较可以看出本文提出的凸化的方法在收敛速度上明显优于Polyblock方法. 相似文献
10.
Parametric global optimisation for bilevel programming 总被引:2,自引:2,他引:0
Nuno P. Faísca Vivek Dua Berç Rustem Pedro M. Saraiva Efstratios N. Pistikopoulos 《Journal of Global Optimization》2007,38(4):609-623
We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based
on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s)
problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables
of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem
is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved
to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without
right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global
optimisation strategy. 相似文献
11.
12.
1.IntroductionAlthoughthegenerallinearintegerprogrammingproblemisNP-hard,muchworkhasbeendevotedtoit(SeeNumhauserandWolsey[1988],Schrijver[1986]).Thesolutionmethodsincludethecuttingplane,theBranch-and-Bound,thedynamicprogrammingmethodsetc..However,thegeneralnonlinearintegerprogrammingproblemisdifficulttosolve.GareyandJohnson[1979]pointedoutthattheintegerprogrammingoverRewithalinearobjectivefunctionandquadraticconstraintsisundecidable.Soifanonlinearintegerprogrammingproblemishandled,itisalw… 相似文献
13.
Ming-Hua LinJung-Fa Tsai 《European Journal of Operational Research》2012,216(1):17-25
Many global optimization approaches for solving signomial geometric programming problems are based on transformation techniques and piecewise linear approximations of the inverse transformations. Since using numerous break points in the linearization process leads to a significant increase in the computational burden for solving the reformulated problem, this study integrates the range reduction techniques in a global optimization algorithm for signomial geometric programming to improve computational efficiency. In the proposed algorithm, the non-convex geometric programming problem is first converted into a convex mixed-integer nonlinear programming problem by convexification and piecewise linearization techniques. Then, an optimization-based approach is used to reduce the range of each variable. Tightening variable bounds iteratively allows the proposed method to reach an approximate solution within an acceptable error by using fewer break points in the linearization process, therefore decreasing the required CPU time. Several numerical experiments are presented to demonstrate the advantages of the proposed method in terms of both computational efficiency and solution quality. 相似文献
14.
A general monotonization method is proposed for converting a constrained programming problem with non-monotone objective function and monotone constraint functions into a monotone programming problem. An equivalent monotone programming problem with only inequality constraints is obtained via this monotonization method. Then the existing convexification and concavefication methods can be used to convert the monotone programming problem into an equivalent better-structured optimization problem. 相似文献
15.
K. Moshirvaziri 《Journal of Optimization Theory and Applications》1998,98(1):83-108
This paper presents a method for constructing test problems with known global solutions for concave minimization under linear constraints with an additional convex constraint and for reverse convex programs with an additional convex constraint. The importance of such a construction can be realized from the fact that the well known d.c. programming problem can be formulated in this form. Then, the method is further extended to generate test problems with more than one convex constraint, tight or untight at the global solution. 相似文献
16.
Convex integer quadratic programming involves minimization of a convex quadratic objective function with affine constraints and is a well-known NP-hard problem with a wide range of applications. We proposed a new variable reduction technique for convex integer quadratic programs (IQP). Based on the optimal values to the continuous relaxation of IQP and a feasible solution to IQP, the proposed technique can be applied to fix some decision variables of an IQP simultaneously at zero without sacrificing optimality. Using this technique, computational effort needed to solve IQP can be greatly reduced. Since a general convex bounded IQP (BIQP) can be transformed to a convex IQP, the proposed technique is also applicable for the convex BIQP. We report a computational study to demonstrate the efficacy of the proposed technique in solving quadratic knapsack problems. 相似文献
17.
This paper considers several probability maximization models for multi-scenario portfolio selection problems in the case that
future returns in possible scenarios are multi-dimensional random variables. In order to consider occurrence probabilities
and decision makers’ predictions with respect to all scenarios, a portfolio selection problem setting a weight with flexibility
to each scenario is proposed. Furthermore, by introducing aspiration levels to occurrence probabilities or future target profit
and maximizing the minimum aspiration level, a robust portfolio selection problem is considered. Since these problems are
formulated as stochastic programming problems due to the inclusion of random variables, they are transformed into deterministic
equivalent problems introducing chance constraints based on the stochastic programming approach. Then, using a relation between
the variance and absolute deviation of random variables, our proposed models are transformed into linear programming problems
and efficient solution methods are developed to obtain the global optimal solution. Furthermore, a numerical example of a
portfolio selection problem is provided to compare our proposed models with the basic model. 相似文献
18.
Generalized geometric programming (GGP) problems occur frequently in engineering design and management. Some exponential-based decomposition methods have been developed for solving global optimization of GGP problems. However, the use of logarithmic/exponential transformations restricts these methods to handle the problems with strictly positive variables. This paper proposes a technique for treating non-positive variables with integer powers in GGP problems. By means of variable transformation, the GGP problem with non-positive variables can be equivalently solved with another one having positive variables. In addition, we present some computationally efficient convexification rules for signomial terms to enhance the efficiency of the optimization approach. Numerical examples are presented to demonstrate the usefulness of the proposed method in GGP problems with non-positive variables. 相似文献
19.
In this paper, we propose a new continuous approach for the unconstrained binary quadratic programming (BQP) problems based
on the Fischer-Burmeister NCP function. Unlike existing relaxation methods, the approach reformulates a BQP problem as an
equivalent continuous optimization problem, and then seeks its global minimizer via a global continuation algorithm which
is developed by a sequence of unconstrained minimization for a global smoothing function. This smoothing function is shown
to be strictly convex in the whole domain or in a subset of its domain if the involved barrier or penalty parameter is set
to be sufficiently large, and consequently a global optimal solution can be expected. Numerical results are reported for 0-1
quadratic programming problems from the OR-Library, and the optimal values generated are made comparisons with those given
by the well-known SBB and BARON solvers. The comparison results indicate that the continuous approach is extremely promising
by the quality of the optimal values generated and the computational work involved, if the initial barrier parameter is chosen
appropriately.
This work is partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province. 相似文献
20.
In this paper, we consider the box constrained nonlinear integer programming problem. We present an auxiliary function, which has the same discrete global minimizers as the problem. The minimization of the function using a discrete local search method can escape successfully from previously converged discrete local minimizers by taking increasing values of a parameter. We propose an algorithm to find a global minimizer of the box constrained nonlinear integer programming problem. The algorithm minimizes the auxiliary function from random initial points. We prove that the algorithm can converge asymptotically with probability one. Numerical experiments on a set of test problems show that the algorithm is efficient and robust. 相似文献