共查询到20条相似文献,搜索用时 0 毫秒
1.
In this paper, we investigate a constrained optimization problem with a quadratic cost functional and two quadratic equality constraints. It is assumed that the cost functional is positive definite and that the constraints are both feasible and regular (but otherwise they are unrestricted quadratic functions). Thus, the existence of a global constrained minimum is assured. We develop a necessary and sufficient condition that completely characterizes the global minimum cost. Such a condition is of essential importance in iterative numerical methods for solving the constrained minimization problem, because it readily distinguishes between local minima and global minima and thus provides a stopping criterion for the computation. The result is similar to one obtained previously by the authors. In the previous result, we gave a characterization of the global minimum of a constrained quadratic minimization problem in which the cost functional was an arbitrary quadratic functional (as opposed to positive-definite here) and the constraints were at least positive-semidefinite quadratic functions (as opposed to essentially unrestricted here). 相似文献
2.
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. 相似文献
3.
In this paper we introduce an augmented Lagrangian type algorithm for strictly convex quadratic programming problems with equality constraints. The new feature of the proposed algorithm is the adaptive precision control of the solution of auxiliary problems in the inner loop of the basic algorithm. Global convergence and boundedness of the penalty parameter are proved and an error estimate is given that does not have any term that accounts for the inexact solution of the auxiliary problems. Numerical experiments illustrate efficiency of the algorithm presented 相似文献
4.
This paper considers the problem of minimizing a quadratic cost subject to purely quadratic equality constraints. This problem
is tackled by first relating it to a standard semidefinite programming problem. The approach taken leads to a dynamical systems
analysis of semidefinite programming and the formulation of a gradient descent flow which can be used to solve semidefinite
programming problems. Though the reformulation of the initial problem as a semidefinite pro- gramming problem does not in
general lead directly to a solution of the original problem, the initial problem is solved by using a modified flow incorporating
a penalty function.
Accepted 10 March 1998 相似文献
5.
Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints 总被引:4,自引:0,他引:4
N. V. Thoai 《Journal of Optimization Theory and Applications》2000,107(2):331-354
The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported. 相似文献
6.
Z. Dostál A. Friedlander S.A. Santos K. Alesawi 《Computational Optimization and Applications》2002,23(1):127-133
In this paper we give corrections to our paper on an augmented Lagrangian type algorithm for strictly convex quadratic programming problems with equality constraints. 相似文献
7.
Global Optimality Conditions in Maximizing a Convex Quadratic Function under Convex Quadratic Constraints 总被引:2,自引:0,他引:2
Jean-Baptiste Hiriart-Urruty 《Journal of Global Optimization》2001,21(4):443-453
For the problem of maximizing a convex quadratic function under convex quadratic constraints, we derive conditions characterizing a globally optimal solution. The method consists in exploiting the global optimality conditions, expressed in terms of -subdifferentials of convex functions and -normal directions, to convex sets. By specializing the problem of maximizing a convex function over a convex set, we find explicit conditions for optimality. 相似文献
8.
Thomas F. Coleman Jianguo Liu Wei Yuan 《Computational Optimization and Applications》2000,15(2):103-123
We present a modified quadratic penalty function method for equality constrained optimization problems. The pivotal feature of our algorithm is that at every iterate we invoke a special change of variables to improve the ability of the algorithm to follow the constraint level sets. This change of variables gives rise to a suitable block diagonal approximation to the Hessian which is then used to construct a quasi-Newton method. We show that the complete algorithm is globally convergent. Preliminary computational results are reported. 相似文献
9.
Yinyu Ye 《Journal of Global Optimization》1999,15(1):1-17
We consider the problem of approximating the global maximum of a quadratic program (QP) subject to convex non-homogeneous quadratic constraints. We prove an approximation quality bound that is related to a condition number of the convex feasible set; and it is the currently best for approximating certain problems, such as quadratic optimization over the assignment polytope, according to the best of our knowledge. 相似文献
10.
11.
12.
S. Rangavajhala A. A. Mullur A. Messac 《Journal of Optimization Theory and Applications》2009,140(2):315-337
Robust design optimization (RDO) problems can generally be formulated by incorporating uncertainty into the corresponding
deterministic problems. In this context, a careful formulation of deterministic equality constraints into the robust domain
is necessary to avoid infeasible designs under uncertain conditions. The challenge of formulating equality constraints is
compounded in multiobjective RDO problems. Modeling the tradeoffs between the mean of the performance and the variation of
the performance for each design objective in a multiobjective RDO problem is itself a complex task. A judicious formulation
of equality constraints adds to this complexity because additional tradeoffs are introduced between constraint satisfaction
under uncertainty and multiobjective performance. Equality constraints under uncertainty in multiobjective problems can therefore
pose a complicated decision making problem. In this paper, we provide a new problem formulation that can be used as an effective
multiobjective decision making tool, with emphasis on equality constraints. We present two numerical examples to illustrate
our theoretical developments. 相似文献
13.
In this paper a particular quadratic minimum program, having a particular d.c. objective function, is studied. Some theoretical properties of the problem are stated and the existence of minimizers is characterized. A solution algorithm, based on the so called optimal level solutions approach, is finally proposed. 相似文献
14.
15.
Thomas F. Coleman Jianguo Liu Wei Yuan 《Computational Optimization and Applications》2002,21(2):177-199
We present a new trust-region algorithm for solving nonlinear equality constrained optimization problems. Quadratic penalty functions are employed to obtain global convergence. At each iteration a local change of variables is performed to improve the ability of the algorithm to follow the constraint level set. Under certain assumptions we prove that this algorithm globally converges to a point satisfying the second-order necessary optimality conditions. Results of preliminary numerical experiments are reported. 相似文献
16.
Z. Y. Wu V. Jeyakumar A. M. Rubinov 《Journal of Optimization Theory and Applications》2007,133(1):123-130
We present sufficient conditions for the global optimality of bivalent nonconvex quadratic programs involving quadratic inequality
constraints as well as equality constraints. By employing the Lagrangian function, we extend the global subdifferential approach,
developed recently in Jeyakumar et al. (J. Glob. Optim., 2007, to appear; Math. Program. Ser. A, 2007, to appear) for studying bivalent quadratic programs without quadratic constraints, and derive global optimality conditions.
The authors are grateful to the referees for constructive comments and suggestions which have contributed to the final preparation
of the paper.
Z.Y. Wu’s current address: School of Information Technology and Mathematical Sciences, University of Ballarat, Ballarat, Victoria,
Australia. The work of this author was completed while at the Department of Applied Mathematics, University of New South Wales,
Sydney, Australia. 相似文献
17.
The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822. 相似文献
18.
We prove a sufficient global optimality condition for the problem of minimizing a quadratic function subject to quadratic equality constraints where the variables are allowed to take values –1 and 1. We extend the condition to quadratic problems with matrix variables and orthonormality constraints, and in particular to the quadratic assignment problem. 相似文献
19.
K. C. Kiwiel 《Journal of Optimization Theory and Applications》2007,134(3):549-554
We give a linear time algorithm for the continuous quadratic knapsack problem which is simpler than existing methods and competitive
in practice. Encouraging computational results are presented for large-scale problems.
The author thanks the Associate Editor and an anonymous referee for their helpful comments. 相似文献
20.
边界约束非凸二次规划问题的分枝定界方法 总被引:2,自引:0,他引:2
本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。 相似文献