Range reduction techniques for improving computational efficiency in global optimization of signomial geometric programming problems

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.     

Global optimization of signomial mixed-integer nonlinear programming problems with free variables

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.     

On generalized geometric programming problems with non-positive variables

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.     

Convexification and Concavification for a General Class of Global Optimization Problems

A kind of general convexification and concavification methods is proposed for solving some classes of global optimization problems with certain monotone properties. It is shown that these minimization problems can be transformed into equivalent concave minimization problem or reverse convex programming problem or canonical D.C. programming problem by using the proposed convexification and concavification schemes. The existing algorithms then can be used to find the global solutions of the transformed problems.     

A convexification method for a class of global optimization problems with applications to reliability optimization

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.     

带自由变量的广义几何规划全局求解的新算法

带自由变量的广义几何规划(FGGP)问题广泛出现在证券投资和工程设计等实际问题中.利用等价转换及对目标函数和约束函数的凸下界估计,提出一种求(FGGP)问题全局解的凸松弛方法.与已有方法相比,方法可处理符号项中含有更多变量的(FGGP)问题,且在最后形成的凸松弛问题中含有更少的变量和约束,从而在计算上更容易实现.最后数值实验表明文中方法是可行和有效的.     

Limit vector variational inequality problems via scalarization

This paper presents a global optimization approach for solving signomial geometric programming (SGP) problems. We employ an accelerated extended cutting plane (ECP) approach integrated with piecewise linear (PWL) approximations to solve the global optimization of SGP problems. In this approach, we separate the feasible regions determined by the constraints into convex and nonconvex ones in the logarithmic domain. In the nonconvex feasible regions, the corresponding constraint functions are converted into mixed integer linear constraints using PWL approximations, while the other constraints with convex feasible regions are handled by the ECP method. We also use pre-processed initial cuts and batched cuts to accelerate the proposed algorithm. Numerical results show that the proposed approach can solve the global optimization of SGP problems efficiently and effectively.     

On the mixed integer signomial programming problems

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.     

一些类型的数学规划问题的全局最优解

本文对严格单调函数给出了几个凸化和凹化的方法，利用这些方法可将一个严格单调的规划问题转化为一个等价的标准D．C．规划或凹极小问题．本文还对只有一个严格单调的约束的非单调规划问题给出了目标函数的一个凸化和凹化方法，利用这些方法可将只有一个严格单调约束的非单调规划问题转化为一个等价的凹极小问题．再利用已有的关于D．C．规划和凹极小的算法，可以求得原问题的全局最优解．     

Global solution of optimization problems with signomial parts

In this paper a new approach for the global solution of nonconvex MINLP (Mixed Integer NonLinear Programming) problems that contain signomial (generalized geometric) expressions is proposed and illustrated. By applying different variable transformation techniques and a discretization scheme a lower bounding convex MINLP problem can be derived. The convexified MINLP problem can be solved with standard methods. The key element in this approach is that all transformations are applied termwise. In this way all convex parts of the problem are left unaffected by the transformations. The method is illustrated by four example problems.     

符号几何规划的一种分解方法

针对符号几何规划提出了一种直接的分解方法,将难于求解的符号几何规划问题等价地转化为一个非线性程度很低的可分离规划,为寻求困难度高且规模较大的符号几何规划问题的求解提供了一种方法,特别是经此方法分解后的每个子问题均易于求解,最后给出了数值实例,验证了此方法的有效性．     

混合约束下广义几何规划的一种全局收敛算法

In this paper, we develop a rapidly convergent algorithm for mixed constrained signomial geometric programming. The algorithm makes use of the characteristics of signomial geometric programming, and establishes a new active-set strategy on the basis of trust region method. The global convergence is proved, and some numerical tests are given to illustrate the effectiveness.     

Global Optimization of Nonconvex Polynomial Programming Problems Having Rational Exponents

This paper considers the solution of nonconvex polynomial programming problems that arise in various engineering design, network distribution, and location-allocation contexts. These problems generally have nonconvex polynomial objective functions and constraints, involving terms of mixed-sign coefficients (as in signomial geometric programs) that have rational exponents on variables. For such problems, we develop an extension of the Reformulation-Linearization Technique (RLT) to generate linear programming relaxations that are embedded within a branch-and-bound algorithm. Suitable branching or partitioning strategies are designed for which convergence to a global optimal solution is established. The procedure is illustrated using a numerical example, and several possible extensions and algorithmic enhancements are discussed.     

Treating Free Variables in Generalized Geometric Global Optimization Programs

Generalized geometric programming (GGP) problems occur frequently in engineering design and management. Recently, some exponential-based decomposition methods [Maranas and Floudas, 1997,Computers and Chemical Engineering 21(4), 351–370; Floudas et al., 1999 , Handbook of Test Problems in Local and Global Optimization, Kluwer Academic Publishers, Boston, pp. 5–105; Floudas, 2000 Deterministic Global Optimizaion: Theory, Methods and Application, Kluwer Academic Publishers, Boston, pp. 257–306] have been developed for GGP problems. These methods can only handle problems with positive variables, and are incapable of solving more general GGP problems. This study proposes a technique for treating free (i.e., positive, zero or negative) variables in GGP problems. Computationally effective convexification rules are also provided for signomial terms with three variables.     

一类具有连续变量的全局最优化问题的凸化方法

本文研究了一类非凸最优化问题的凸化方法与最优性条件的问题.利用构造含有参数的函数变换方法,将具有次正定性质的目标函数凸化,并获得了这一类非凸优化问题全局最优解的充要条件,推广了凸化方法在求解全局最优化问题方面的应用.     

MM algorithms for geometric and signomial programming

This paper derives new algorithms for signomial programming, a generalization of geometric programming. The algorithms are based on a generic principle for optimization called the MM algorithm. In this setting, one can apply the geometric-arithmetic mean inequality and a supporting hyperplane inequality to create a surrogate function with parameters separated. Thus, unconstrained signomial programming reduces to a sequence of one-dimensional minimization problems. Simple examples demonstrate that the MM algorithm derived can converge to a boundary point or to one point of a continuum of minimum points. Conditions under which the minimum point is unique or occurs in the interior of parameter space are proved for geometric programming. Convergence to an interior point occurs at a linear rate. Finally, the MM framework easily accommodates equality and inequality constraints of signomial type. For the most important special case, constrained quadratic programming, the MM algorithm involves very simple updates.     

A class of convexification and concavification methods for non-monotone optimization problems

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.     

一般广义几何规划问题的一种有效数值方法

一般广义几何规划问题的一种有效数值方法张可村，杨波艇（西安交通大学）ＡＮＥＦＦＥＣＴＩＶＥＮＵＭＥＲＩＣＡＬＭＥＴＨＯＤＦＯＲＧＥＮＥＲＡＬＳＩＧＮＯＭＩＡＬＧＥＯＭＥＴＲＩＣＰＲＯＧＲＡＭＭＩＮＧＰＲＯＢＬＥＭＳ￥ＺｈａｎｇＫｅ－ｃｕｎ；ＹａｎｇＢ...     

一些约束规划问题的近似全局最优解

首先将一个具有多个约束的规划问题转化为一个只有一个约束的规划问题,然后通过利用这个单约束的规划问题,对原来的多约束规划问题提出了一些凸化、凹化的方法,这样这些多约束的规划问题可以被转化为一些凹规划、反凸规划问题．最后,还证明了得到的凹规划和反凸规划的全局最优解就是原问题的近似全局最优解．     

Accelerating method of global optimization for signomial geometric programming

Signomial geometric programming (SGP) has been an interesting problem for many authors recently. Many methods have been provided for finding locally optimal solutions of SGP, but little progress has been made for global optimization of SGP. In this paper we propose a new accelerating method for global optimization algorithm of SGP using a suitable deleting technique. This technique offers a possibility to cut away a large part of the currently investigated region in which the globally optimal solution of SGP does not exist, and can be seen as an accelerating device for global optimization algorithm of SGP problem. Compared with the method of Shen and Zhang [Global optimization of signomial geometric programming using linear relaxation, Appl. Math. Comput. 150 (2004) 99–114], numerical results show that the computational efficiency is improved obviously by using this new technique in the number of iterations, the required saving list length and the execution time of the algorithm.