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

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

一类反凸规划的全局新算法

§1.引言 到目前为止,大多数非线性规划的有效算法都是寻求它的局部最优解,由于很难判断一个局部解是否就是一个全局解,全局规划的研究是个困难问题,反凸规划由于其可行域的非凸性甚至非连通性,目前有效算法更少。 [1]已经指出很容易把D.C.规划(即目标函数和约束函数均为二个凸函数之差)转化成为一个目标函数为线性的反凸规划:     

单调全局最优化问题的凸化外逼近算法

单调优化是指目标函数与约束函数均为单调函数的全局优化问题．本文提出一种新的凸化变换方法把单调函数化为凸函数，进而把单调优化问题化为等价的凸极大或凹极小问题，然后采用Hoffman的外逼近方法来求得问题的全局最优解．我们把这种凸化方法同Tuy的Polyblock外逼近方法作了比较，通过数值比较可以看出本文提出的凸化的方法在收敛速度上明显优于Polyblock方法．     

用罚函数求解二层凸规划的方法

用罚函数法将二层凸规划化为约束区域为凸集的凹规划,然后用渐进外逼算法求其全局最优解。     

非线性规划的凸化,凹化和单调化

本文提出了一个指数型凸化,凹化变换,并证明了单调非线性规划总能变换成相应的凹规划或凸规划.还证明了带某种类型线性或非线性约束的非线性规划在适当条件下能变换成单调非线性规划.     

非线性规划的凸化,凹化和单调化

本文提出了一个指数型凸化,凹化变换,并证明了单调非线性规划总能变换成相应的凹规划或凸规划.还证明了带某种类型线性或非线性约束的非线性规划在适当条件下能变换成单调非线性规划.     

基于凹性割的线性双层规划全局优化算法

通过对线性双层规划下层问题对偶间隙的讨论,定义了一种凹性割,利用该凹性割的性质,给出了一个求解线性双层规划的割平面算法。由于线性双层规划全局最优解可在其约束域的极点上达到,提出的算法能求得问题的全局最优解,并通过一个算例说明了算法的有效性。     

一类带反凸约束的非线性比式和问题的全局优化算法

本文针对一类带有反凸约束的非线性比式和分式规划问题,提出一种求其全局最优解的单纯形分支和对偶定界算法.该算法利用Lagrange对偶理论将其中关键的定界问题转化为一系列易于求解的线性规划问题.收敛性分析和数值算例均表明提出的算法是可行的.     

凸多乘积问题的完全多项式时间近似算法

针对凸多乘积问题,提出一种求其全局最优解的近似算法.首先,通过引入参量获得一个等价问题,然后估计问题中每一乘积项的上下界,进而借助网格结点,获得一些凸规划问题,通过求解这些凸规划问题获得原问题的近似最优解.最后,给出了该算法的收敛性证明和计算复杂性分析.     

带有不等式约束的非线性规划问题的一个精确增广Lagrange函数

对求解带有不等式约束的非线性非凸规划问题的一个精确增广Lagrange函数进行了研究．在适当的假设下,给出了原约束问题的局部极小点与增广Lagrange函数,在原问题变量空间上的无约束局部极小点之间的对应关系．进一步地,在对全局解的一定假设下,还提供了原约束问题的全局最优解与增广Lagrange函数,在原问题变量空间的一个紧子集上的全局最优解之间的一些对应关系．因此,从理论上讲,采用该文给出的增广Lagrange函数作为辅助函数的乘子法,可以求得不等式约束非线性规划问题的最优解和对应的Lagrange乘子．     

Construction of Test Problems for Concave Minimization Under Linear and Nonlinear Constraints

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.     

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.     

Convexification, Concavification and Monotonization in Global Optimization

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.     

On Optimization over the Efficient Set in Linear Multicriteria Programming

The efficient set of a linear multicriteria programming problem can be represented by a reverse convex constraint of the form g(z)≤0, where g is a concave function. Consequently, the problem of optimizing some real function over the efficient set belongs to an important problem class of global optimization called reverse convex programming. Since the concave function used in the literature is only defined on some set containing the feasible set of the underlying multicriteria programming problem, most global optimization techniques for handling this kind of reverse convex constraint cannot be applied. The main purpose of our article is to present a method for overcoming this disadvantage. We construct a concave function which is finitely defined on the whole space and can be considered as an extension of the existing function. Different forms of the linear multicriteria programming problem are discussed, including the minimum maximal flow problem as an example. The research was partly done while the third author was visiting the Department of Mathematics, University of Trier with the support by the Alexander von Humboldt Foundation. He thanks the university as well as the foundation.     

Convex optimization approach to a single quadratically constrained quadratic minimization problem

In this paper, first we show that for rank deficient matrices, the optimal solution of a single equality constrained quadratic minimization problem can be found by relaxing the equality constraint to the inequality one, which makes the problem a convex problem. Then we show that for full rank matrices, an optimal solution can be obtained using semidefinite optimization framework.     

On the global optimality of generalized trust region subproblems

Quadratically constrained quadratic programming is an important class of optimization problems. We consider the case with one quadratic constraint. Since both the objective function and its constraint can be neither convex nor concave, it is also known as the ‘generalized trust region subproblem.’ The theory and algorithms for this problem have been well studied under the Slater condition. In this article, we analyse the duality property between the primal problem and its Lagrangian dual problem, and discuss the attainability of the optimal primal solution without the Slater condition. The relations between the Lagrangian dual and semidefinite programming dual is also given.     

Inscribed ball and enclosing box methods for the convex maximization problem

Many important classes of decision models give rise to the problem of finding a global maximum of a convex function over a convex set. This problem is known also as concave minimization, concave programming or convex maximization. Such problems can have many local maxima, therefore finding the global maximum is a computationally difficult problem, since standard nonlinear programming procedures fail. In this article, we provide a very simple and practical approach to find the global solution of quadratic convex maximization problems over a polytope. A convex function achieves its global maximum at extreme points of the feasible domain. Since an inscribed ball does not contain any extreme points of the domain, we use the largest inscribed ball for an inner approximation while a minimal enclosing box is exploited for an outer approximation of the domain. The approach is based on the use of these approximations along with the standard local search algorithm and cutting plane techniques.     

Solving Sum of Ratios Fractional Programs via Concave Minimization

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.