共查询到20条相似文献,搜索用时 878 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
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. 相似文献
4.
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. 相似文献
5.
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. 相似文献
6.
Z. Y. Wu Y. J. Yang F. S. Bai M. Mammadov 《Journal of Optimization Theory and Applications》2011,151(2):241-259
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. 相似文献
7.
本文给出了混合整数二次规划问题的全局最优性条件,包括全局最优充分性条件和全局最优必要性条件.我们还给出了一个数值实例用以说明如何利用本文所给出的全局最优性条件来判定一个给定点是否是全局最优解. 相似文献
8.
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. 相似文献
9.
Valeriya Lykina Sabine Pickenhain 《Journal of Mathematical Analysis and Applications》2018,457(2):1591-1612
In this paper a class of infinite horizon optimal control problems with an isoperimetrical constraint, also interpreted as a budget constraint, is considered. Herein a linear both in the state and in the control dynamic is allowed. The problem setting includes a weighted Sobolev space as the state space. For this class of problems, we establish the necessary optimality conditions in form of a Pontryagin Type Maximum Principle including a transversality condition. The proved theoretical result is applied to a linear–quadratic regulator problem. 相似文献
10.
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. 相似文献
11.
12.
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. 相似文献
13.
Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming 总被引:2,自引:0,他引:2
When the follower's optimality conditions are both necessary and sufficient, the nonlinear bilevel program can be solved as a global optimization problem. The complementary slackness condition is usually the complicating constraint in such problems. We show how this constraint can be replaced by an equivalent system of convex and separable quadratic constraints. In this paper, we propose different methods for finding the global minimum of a concave function subject to quadratic separable constraints. The first method is of the branch and bound type, and is based on rectangular partitions to obtain upper and lower bounds. Convergence of the proposed algorithm is also proved. For computational purposes, different procedures that accelerate the convergence of the proposed algorithm are analysed. The second method is based on piecewise linear approximations of the constraint functions. When the constraints are convex, the problem is reduced to global concave minimization subject to linear constraints. In the case of non-convex constraints, we use zero-one integer variables to linearize the constraints. The number of integer variables depends only on the concave parts of the constraint functions.Parts of the present paper were prepared while the second author was visiting Georgia Tech and the University of Florida. 相似文献
14.
Shu-Cherng Fang David Y. Gao Ruey-Lin Sheu Wenxun Xing 《Journal of Global Optimization》2009,45(3):337-353
This paper presents a canonical dual approach to minimizing the sum of a quadratic function and the ratio of two quadratic
functions, which is a type of non-convex optimization problem subject to an elliptic constraint. We first relax the fractional
structure by introducing a family of parametric subproblems. Under proper conditions on the “problem-defining” matrices associated
with the three quadratic functions, we show that the canonical dual of each subproblem becomes a one-dimensional concave maximization
problem that exhibits no duality gap. Since the infimum of the optima of the parameterized subproblems leads to a solution
to the original problem, we then derive some optimality conditions and existence conditions for finding a global minimizer
of the original problem. Some numerical results using the quasi-Newton and line search methods are presented to illustrate
our approach. 相似文献
15.
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. 相似文献
16.
AbstractWe present optimality conditions for a class of nonsmooth and nonconvex constrained optimization problems. To achieve this aim, various well-known constraint qualifications are extended based on the concept of tangential subdifferential and the relations between them are investigated. Moreover, local and global necessary and sufficient optimality conditions are derived in the absence of convexity of the feasible set. In addition to the theoretical results, several examples are provided to illustrate the advantage of our outcomes. 相似文献
17.
In this paper, using the Fréchet subdifferential, we derive several sufficient conditions ensuring an error bound for inequality systems in Asplund spaces. As an application we obtain in the context of Banach spaces a global error bound for quadratic nonconvex inequalities and we derive necessary optimality conditions for optimization problems. 相似文献
18.
In this paper, we investigate a constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. While it is obvious that, for a nonempty constraint set, there exists a global minimum cost, a method to determine if a given local solution yields the global minimum cost has not been established. We develop a necessary and sufficient condition that will guarantee that solutions of the optimization problem yield the global minimum cost. This constrained optimization problem occurs naturally in the computation of the phase margin for multivariable control systems. Our results guarantee that numerical routines can be developed that will converge to the global solution for the phase margin. 相似文献
19.
20.
Linh T. H. Nguyen 《Optimization》2018,67(2):195-216
Motivated by weakly convex optimization and quadratic optimization problems, we first show that there is no duality gap between a difference of convex (DC) program over DC constraints and its associated dual problem. We then provide certificates of global optimality for a class of nonconvex optimization problems. As an application, we derive characterizations of robust solutions for uncertain general nonconvex quadratic optimization problems over nonconvex quadratic constraints. 相似文献