全局优化问题的一类积分型最优性条件 (英)

本文通过构造水平集辅助函数对一类积分全局最优性条件进行研究. 所构造的辅助函数仅含有一个参数变量与一个控制变量,该参数变量用以表征对原问题目标函数最优值的估计,而控制变量用以控制积分型全局最优性条件的精度. 对参数变量做极限运算即可得到积分型全局最优性条件.继而给出了用该辅助函数所刻画的全局最优性的充要条件, 从而将原全局优化问题的求解转化为寻找一个非线性方程根的问题.更进一步地,若所取测度为勒贝格测度且积分区域为自然数集合的一个有限子集, 则该积分最优性条件便化为有限极大极小问题中利用凝聚函数对极大值函数进行逼近的近似系统.从而积分型全局最优性条件可以看作是该近似系统从离散到连续的一种推广.     

Global Quadratic Minimization over Bivalent Constraints: Necessary and Sufficient Global Optimality Condition

In this paper, we establish global optimality conditions for quadratic optimization problems with quadratic equality and bivalent constraints. We first present a necessary and sufficient condition for a global minimizer of quadratic optimization problems with quadratic equality and bivalent constraints. Then we examine situations where this optimality condition is equivalent to checking the positive semidefiniteness of a related matrix, and so, can be verified in polynomial time by using elementary eigenvalues decomposition techniques. As a consequence, we also present simple sufficient global optimality conditions, which can be verified by solving a linear matrix inequality problem, extending several known sufficient optimality conditions in the existing literature.     

A sufficient and necessary condition for global optimization

We consider a class of global optimization problems, in which the objective function is Lebesgue integrable. In this paper, we present a sufficient and necessary condition for computing the essential infimum. This optimality condition can be used to design algorithms for solving the global optimization problem.     

Optimality conditions for nonsmooth mathematical programs with equilibrium constraints,using convexificators

In this paper, we deal with constraint qualifications, stationary concepts and optimality conditions for a nonsmooth mathematical program with equilibrium constraints (MPEC). The main tool in our study is the notion of convexificator. Using this notion, standard and MPEC Abadie and several other constraint qualifications are proposed and a comparison between them is presented. We also define nonsmooth stationary conditions based on the convexificators. In particular, we show that GS-stationary is the first-order optimality condition under generalized standard Abadie constraint qualification. Finally, sufficient conditions for global or local optimality are derived under some MPEC generalized convexity assumptions.     

Global optimality conditions for fixed charge quadratic programs

In this note, we establish sufficient and necessary global optimality conditions for fixed charge quadratic programming problem. The main theoretical tool for establishing these global optimality conditions is abstract convexity. The newly obtained sufficient condition extends the existing sufficient conditions. A numerical example is also provided to illustrate our optimality conditions.     

混合整数二次规划问题的全局最优性条件

本文给出了混合整数二次规划问题的全局最优性条件,包括全局最优充分性条件和全局最优必要性条件.我们还给出了一个数值实例用以说明如何利用本文所给出的全局最优性条件来判定一个给定点是否是全局最优解.     

Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems

The quadratic knapsack problem (QKP) maximizes a quadratic objective function subject to a binary and linear capacity constraint. Due to its simple structure and challenging difficulty, it has been studied intensively during the last two decades. This paper first presents some global optimality conditions for (QKP), which include necessary conditions and sufficient conditions. Then a local optimization method for (QKP) is developed using the necessary global optimality condition. Finally a global optimization method for (QKP) is proposed based on the sufficient global optimality condition, the local optimization method and an auxiliary function. Several numerical examples are given to illustrate the efficiency of the presented optimization methods.     

THE OPTIMALITY CONDITIONS OF NONCONVEXSET-VALUED VECTOR OPTIMIZATION

1 IntroductionIt is well known that the most linportant task of nonsmooth is to extend the classicaIderivatives to broaden tl1e scope of dtherentiable function. One of the importallt geuerallzationis the Clarke's generalized directional derivative[1]--[2]…     

A new necessary and sufficient global optimality condition for canonical DC problems

The paper proposes a new necessary and sufficient global optimality condition for canonical DC optimization problems. We analyze the rationale behind Tuy’s standard global optimality condition for canonical DC problems, which relies on the so-called regularity condition and thus can not deal with the widely existing non-regular instances. Then we show how to modify and generalize the standard condition to a new one that does not need regularity assumption, and prove that this new condition is equivalent to other known global optimality conditions. Finally, we show that the cutting plane method, when associated with the new optimality condition, could solve the non-regular canonical DC problems, which significantly enlarges the application of existing cutting plane (outer approximation) algorithms.     

A new local and global optimization method for mixed integer quadratic programming problems

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.     

Characterization of the Darboux point for particular classes of problems

A minimal sufficient condition for global optimality involving the Darboux point, analogous to the minimal sufficient condition of local optimality involving the conjugate point, is presented. The Darboux point is then characterized for optimal control problems with linear dynamics, cost functionals with a general terminal state term and an integrand quadratic in the state and control, and general terminal conditions. The Darboux point is shown to be the supremum of a sequence of conjugate points. If the terminal state term is quadratic, along with a scalar quadratic boundary condition, then the Darboux point is also the time at which the Riccati matrix becomes unbounded, giving a characterization of the unboundedness of the Riccati matrix at points which are not in general conjugate points.This research was supported by the National Science Foundation under Grant No. GK-30115.This is Definition 2.1 of Ref. 1.     

拟可微函数优化的Lagrange乘子与一阶最优性条件

本文给出了拟可微优化的Fritz John必须条件与Shapiro最优性必要条件的等价性质以及两个最优性充分条件.     

指数型增广拉格朗日函数在广义半无限规划中的应用

本文利用指数型增广拉格朗日函数将一类广义半无限极大极小问题在一定条件下转化为标准的半无限极大极小问题,使它们具有相同的局部与全局最优解.我们给出了两个转化条件:一个是充分与必要条件,另一个是在实际中易于验证的充分条件.通过这种转化,我们给出了广义半无限极大极小问题的一个新的一阶最优性条件.     

Higher-Order Optimality Conditions for Set-Valued Optimization

This paper deals with higher-order optimality conditions of set-valued optimization problems. By virtue of the higher-order derivatives introduced in (Aubin and Frankowska, Set-Valued Analysis, Birkhäuser, Boston, [1990]) higher-order necessary and sufficient optimality conditions are obtained for a set-valued optimization problem whose constraint condition is determined by a fixed set. Higher-order Fritz John type necessary and sufficient optimality conditions are also obtained for a set-valued optimization problem whose constraint condition is determined by a set-valued map.     

一个全局优化最优性条件

本文讨论将一个全局优化问题转化为一个非线性方程求根问题，进而讨论全局优化的最优性条件．在文中给出了求解一个全局优化问题的充分必要条件，并证明了所求问题的解为非线性方程的最大根，即为原问题的全局最优解．     

群体多目标决策联合有效解类的不变凸充分条件

对于群体多目标决策问题，文[1]引进它的联合有效解类的概念，并给出这类解的最优性必要条件，在对于问题的目标函数和约束函数附加凸性的条件下，文[2]又给出了联合有效解类的最优性充分条件，本文进一步在目标函数和约束函数具不变凸和不变广义 凸的情况下，分别给出了联合有效解类的若干最优性充分条件。     

Sufficient optimality conditions and duality in vector optimization with invex-convexlike functions

We prove the Kuhn-Tucker sufficient optimality condition, the Wolfe duality, and a modified Mond-Weir duality for vector optimization problems involving various types of invex-convexlike functions. The class of such functins contains many known generalized convex functions. As applications, we demonstrate that, under invex-convexlikeness assumptions, the Pontryagin maximum principle is a sufficient optimality condition for cooperative differential games. The Wolfe duality is established for these games.The author is indebted to the referees and Professor W. Stadler for valuable remarks and comments, which have been used to revise considerably the paper.     

双值约束非凸三次规化问题的全局最优性条件

考虑一类带有双值约束的非凸三次优化问题, 给出了该问题的一个全局最优充分必要条件. 结果改进并推广了一些文献中所给出的全局最优性条件, 同时还通过数值例子来说明所给出的全局最优充要条件是易验证的.     

线性约束三次规划问题的全局最优性必要条件和最优化算法

讨论了带线性不等式约束三次规划问题的最优性条件和最优化算法. 首先, 讨论了带有线性不等式约束三次规划问题的 全局最优性必要条件. 然后, 利用全局最优性必要条件, 设计了解线性约束三次规划问题的一个新的局部最优化算法(强局部最优化算法). 再利用辅助函数和所给出的新的局部最优化算法, 设计了带有线性不等式约束三 规划问题的全局最优化算法. 最后, 数值算例说明给出的最优化算法是可行的、有效的.     

Global optimization and multi knapsack: A percolation algorithm

Since the standard multi knapsack problem, may be rewritten as a reverse convex problem, we present a global optimization approach. It is known from solving high dimensional nonconvex problems that pure cutting plane methods may fail and branch-and-bound is impractical, due to a large duality gap. On the other hand, a strategy based on some sufficient optimality condition does not help much because it requires generating all level set points, an intractable problem. Therefore, we propose to combine both a cutting plane method and a sufficient optimality condition together with a random generation of level set points where the number of points is limited by a tabu list to prevent re-examination of the same level set area. Experiments show that we end up with a small duality gap allowing a subsequent branch-and-bound approach to prove optimality.