共查询到20条相似文献,搜索用时 656 毫秒
1.
In this paper, we first establish some sufficient and some necessary global optimality conditions for quadratic integer programming
problems. Then we present a new local optimization method for quadratic integer programming problems according to its necessary
global optimality conditions. A new global optimization method is proposed by combining its sufficient global optimality conditions,
local optimization method and an auxiliary function. The numerical examples are also presented to show that the proposed optimization
methods for quadratic integer programming problems are very efficient and stable. 相似文献
2.
Zhiyou Wu Yongjian Yang Fusheng Bai Jing Tian 《Applied mathematics and computation》2012,218(11):6214-6231
In this paper some global optimality conditions for general quadratic {0, 1} programming problems with linear equality constraints are discussed and then some global optimality conditions for quadratic assignment problems (QAP) are presented. A local optimization method for (QAP) is derived according to the necessary global optimality conditions. A global optimization method for (QAP) is presented by combining the sufficient global optimality conditions, the local optimization method and some auxiliary functions. Some numerical examples are given to illustrate the efficiency of the given optimization methods. 相似文献
3.
In this paper, we present Lagrange multiplier necessary conditions for global optimality that apply to non-convex optimization
problems beyond quadratic optimization problems subject to a single quadratic constraint. In particular, we show that our
optimality conditions apply to problems where the objective function is the difference of quadratic and convex functions over
a quadratic constraint, and to certain class of fractional programming problems. Our necessary conditions become necessary
and sufficient conditions for global optimality for quadratic minimization subject to quadratic constraint. As an application,
we also obtain global optimality conditions for a class of trust-region problems. Our approach makes use of outer-estimators,
and the powerful S-lemma which has played key role in control theory and semidefinite optimization. We discuss numerical examples
to illustrate the significance of our optimality conditions.
The authors are grateful to the referees for their useful comments which have contributed to the final preparation of the
paper. 相似文献
4.
本文给出了混合整数二次规划问题的全局最优性条件,包括全局最优充分性条件和全局最优必要性条件.我们还给出了一个数值实例用以说明如何利用本文所给出的全局最优性条件来判定一个给定点是否是全局最优解. 相似文献
5.
Guoyin Li 《Journal of Optimization Theory and Applications》2012,152(3):710-726
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. 相似文献
6.
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. 相似文献
7.
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. 相似文献
8.
《Optimization》2012,61(6):627-639
Abstract: In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by [Dür, M., Horst, R. and Locatelli, M., 1998, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications, 217, 637–649] and [Hiriart-Urruty, J.B. and Ledyav, J.S., 1996, A note in the characterization of the global maxima of a convex function over a convex set, Journal of Convex Analysis, 3, 55–61], we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples. 相似文献
9.
In this paper we present necessary conditions for global optimality for polynomial problems with box or bivalent constraints using separable polynomial relaxations. We achieve this by first deriving a numerically checkable characterization of global optimality for separable polynomial problems with box as well as bivalent constraints. Our necessary optimality conditions can be numerically checked by solving semi-definite programming problems. Then, by employing separable polynomial under-estimators, we establish sufficient conditions for global optimality for classes of polynomial optimization problems with box or bivalent constraints. We construct underestimators using the sum of squares convex (SOS-convex) polynomials of real algebraic geometry. An important feature of SOS-convexity that is generally not shared by the standard convexity is that whether a polynomial is SOS-convex or not can be checked by solving a semidefinite programming problem. We illustrate the versatility of our optimality conditions by simple numerical examples. 相似文献
10.
V. Jeyakumar S. Srisatkunrajah 《Journal of Mathematical Analysis and Applications》2007,335(2):779-788
The Kuhn-Tucker Sufficiency Theorem states that a feasible point that satisfies the Kuhn-Tucker conditions is a global minimizer for a convex programming problem for which a local minimizer is global. In this paper, we present new Kuhn-Tucker sufficiency conditions for possibly multi-extremal nonconvex mathematical programming problems which may have many local minimizers that are not global. We derive the sufficiency conditions by first constructing weighted sum of square underestimators of the objective function and then by characterizing the global optimality of the underestimators. As a consequence, we derive easily verifiable Kuhn-Tucker sufficient conditions for general quadratic programming problems with equality and inequality constraints. Numerical examples are given to illustrate the significance of our criteria for multi-extremal problems. 相似文献
11.
In this paper we consider the standard linear SDP problem, and its low rank nonlinear programming reformulation, based on
a Gramian representation of a positive semidefinite matrix. For this nonconvex quadratic problem with quadratic equality constraints,
we give necessary and sufficient conditions of global optimality expressed in terms of the Lagrangian function. 相似文献
12.
In this paper, a new variable reduction technique is presented for general integer quadratic programming problem (GP), under which some variables of (GP) can be fixed at zero without sacrificing optimality. A sufficient condition and a necessary condition for the identification of dominated terms are provided. By comparing the given data of the problem and the upper bound of the variables, if they meet certain conditions, some variables can be fixed at zero. We report a computational study to demonstrate the efficacy of the proposed technique in solving general integer quadratic programming problems. Furthermore, we discuss separable integer quadratic programming problems in a simpler and clearer form. 相似文献
13.
We explore in this paper certain rich geometric properties hidden behind quadratic 0–1 programming. Especially, we derive
new lower bounding methods and variable fixation techniques for quadratic 0–1 optimization problems by investigating geometric
features of the ellipse contour of a (perturbed) convex quadratic function. These findings further lead to some new optimality
conditions for quadratic 0–1 programming. Integrating these novel solution schemes into a proposed solution algorithm of a
branch-and-bound type, we obtain promising preliminary computational results. 相似文献
14.
We establish new necessary and sufficient optimality conditions for global optimization problems. In particular, we establish
tractable optimality conditions for the problems of minimizing a weakly convex or concave function subject to standard constraints,
such as box constraints, binary constraints, and simplex constraints. We also derive some new necessary and sufficient optimality
conditions for quadratic optimization. Our main theoretical tool for establishing these optimality conditions is abstract
convexity. 相似文献
15.
In this paper, we present necessary as well as sufficient conditions for a given feasible point to be a global minimizer of
the difference of quadratic and convex functions subject to bounds on the variables. We show that the necessary conditions
become necessary and sufficient for global minimizers in the case of a weighted sum of squares minimization problems. We obtain
sufficient conditions for global optimality by first constructing quadratic underestimators and then by characterizing global
minimizers of the underestimators. We also derive global optimality conditions for the minimization of the difference of quadratic
and convex functions over binary constraints. We discuss several numerical examples to illustrate the significance of the
optimality conditions.
The authors are grateful to the referees for their helpful comments and valuable suggestions which have contributed to the
final preparation of the paper. 相似文献
16.
Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions 总被引:3,自引:0,他引:3
In this paper, we first examine how global optimality of non-convex constrained optimization problems is related to Lagrange
multiplier conditions. We then establish Lagrange multiplier conditions for global optimality of general quadratic minimization
problems with quadratic constraints. We also obtain necessary global optimality conditions, which are different from the Lagrange
multiplier conditions for special classes of quadratic optimization problems. These classes include weighted least squares
with ellipsoidal constraints, and quadratic minimization with binary constraints. We discuss examples which demonstrate that
our optimality conditions can effectively be used for identifying global minimizers of certain multi-extremal non-convex quadratic
optimization problems.
The work of Z. Y. Wu was carried out while the author was at the Department of Applied Mathematics, University of New South
Wales, Sydney, Australia. 相似文献
17.
18.
In this paper, we develop necessary conditions for global optimality that apply to non-linear programming problems with polynomial
constraints which cover a broad range of optimization problems that arise in applications of continuous as well as discrete
optimization. In particular, we show that our optimality conditions readily apply to problems where the objective function
is the difference of polynomial and convex functions over polynomial constraints, and to classes of fractional programming
problems. Our necessary conditions become also sufficient for global optimality for polynomial programming problems. Our approach
makes use of polynomial over-estimators and, a polynomial version of a theorem of the alternative which is a variant of the
Positivstellensatz in semi-algebraic geometry. We discuss numerical examples to illustrate the significance of our optimality
conditions. 相似文献
19.
Patrick Mehlitz 《Optimization》2017,66(10):1533-1562
We consider a bilevel programming problem in Banach spaces whose lower level solution is unique for any choice of the upper level variable. A condition is presented which ensures that the lower level solution mapping is directionally differentiable, and a formula is constructed which can be used to compute this directional derivative. Afterwards, we apply these results in order to obtain first-order necessary optimality conditions for the bilevel programming problem. It is shown that these optimality conditions imply that a certain mathematical program with complementarity constraints in Banach spaces has the optimal solution zero. We state the weak and strong stationarity conditions of this problem as well as corresponding constraint qualifications in order to derive applicable necessary optimality conditions for the original bilevel programming problem. Finally, we use the theory to state new necessary optimality conditions for certain classes of semidefinite bilevel programming problems and present an example in terms of bilevel optimal control. 相似文献
20.
本文主要讨论了二次整数规划问题的线性化方法.在目标函数为二次函数的情况下,我们讨论了带有二次约束的整数规划问题的线性化方法,并将文献中对二次0-1问题的研究拓展为对带有盒约束的二次整数规划问题的研究.最终将带有盒约束的二次整数规划问题转化为线性混合本文主要讨论了二次整数规划问题的线性化方法.在目标函数为二次函数的情况下,我们讨论了带有二次约束的整数规划问题的线性化方法,并将文献中对二次0-1问题的研究拓展为对带有盒约束的二次整数规划问题的研究.最终将带有盒约束的二次整数规划问题转化为线性混合0-1整数规划问题,然后利用Ilog-cplex或Excel软件中的规划求解工具进行求解,从而解决原二次整数规划. 相似文献