共查询到20条相似文献,搜索用时 15 毫秒
1.
1IntroductionWeconsiderastrictlyconvex(i.e.,positivedefinite)quadraticprogrammingproblemsubjecttoboxconstraints:t-iereA=[aij]isannxnsymmetricpositivedefinitematrix,andb,canddaren-vectors.Letg(x)bethegradient,Ax b,off(x)atx.Withoutlossofgeneralityweassumebothcianddiarefinitenumbers,ci相似文献
2.
To solve a system of nonlinear equations, Wu wen-tsun introduced a new formative elimination method. Based on Wu's method and the theory of nonlinear programming, we here propose a global optimization algorithm for nonlinear programming with rational objective function and rational constraints. The algorithm is already programmed and the test results are satisfactory with respect to precision and reliability. 相似文献
3.
本文提出了一种求解带二次约束和线性约束的二次规划的分支定界算法.在算法中,我们运用Lipschitz条件来确定目标函数和约束函数的在每个n矩形上的上下界,对于n矩形的分割,我们采用选择n矩形最长边的二分法,同时我们采用了一些矩形删除技术,在不大幅增加计算量的前提下,起到了加速算法收敛的效果.从理论上我们证明了算法的收敛性,同时数值实验表明该算法是有效的. 相似文献
4.
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). 相似文献
5.
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. 相似文献
6.
A Global Optimization Method for Solving Convex Quadratic Bilevel Programming Problems 总被引:4,自引:0,他引:4
We use the merit function technique to formulate a linearly constrained bilevel convex quadratic problem as a convex program with an additional convex-d.c. constraint. To solve the latter problem we approximate it by convex programs with an additional convex-concave constraint using an adaptive simplicial subdivision. This approximation leads to a branch-and-bound algorithm for finding a global optimal solution to the bilevel convex quadratic problem. We illustrate our approach with an optimization problem over the equilibrium points of an n-person parametric noncooperative game. 相似文献
7.
S. Cafieri M. D’Apuzzo V. De Simone D. di Serafino G. Toraldo 《Journal of Optimization Theory and Applications》2007,135(3):355-366
We analyze the convergence of an infeasible inexact potential reduction method for quadratic programming problems. We show
that the convergence of this method is achieved if the residual of the KKT system satisfies a bound related to the duality
gap. This result suggests stopping criteria for inner iterations that can be used to adapt the accuracy of the computed direction
to the quality of the potential reduction iterate in order to achieve computational efficiency.
This research was partially supported by the Italian MIUR, Project FIRB—Large Scale Nonlinear Optimization # RBNE01WBBB and
Project PRIN—Innovative Problems and Methods in Nonlinear Optimization # 2005017083. 相似文献
8.
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 相似文献
9.
We present a fully polynomial time approximation scheme (FPTAS) for minimizing an objective (a
T
x + γ)(b
T
x + δ) under linear constraints A
x ≤ d. Examples of such problems are combinatorial minimum weight product problems such as the following: given a graph G = (V,E) and two edge weights find an s − t path P that minimizes a(P)b(P), the product of its edge weights relative to a and b.
相似文献
10.
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. 相似文献
11.
The constrained optimization problem with a quadratic cost functional and two quadratic equality constraints has been studied by Bar-on and Grasse, with positive-definite matrix in the objective. In this note, we shall relax the matrix in the objective to be positive semidefinite. A necessary and sufficient condition to characterize a local optimal solution to be global is established. Also, a perturbation scheme is proposed to solve this generalized problem. 相似文献
12.
13.
We present in this paper a numerical method for solving non-strictly-convex quadratic semi-infinite programming including linear semi-infinite programming. The proposed method transforms the problem into a series of strictly convex quadratic semi-infinite programming problems. Several convergence results and a numerical experiment are given. 相似文献
14.
《Operations Research Letters》2021,49(4):543-547
The quadratic double-ratio minimax optimization (QRM) admits a generalized linear conic fractional reformulation. It leads to two algorithms to globally solve (QRM) from the primal and dual sides, respectively. The hidden convexity of (QRM) remains unknown except for the special case when both denominators are equal. 相似文献
15.
16.
J. Spjøtvold P. Tøndel T. A. Johansen 《Journal of Optimization Theory and Applications》2007,134(2):177-189
A method for obtaining continuous solutions to convex quadratic and linear programs with parameters in the linear part of
the objective function and right-hand side of the constraints is presented. For parameter values for which the problem has
nonunique solutions, the optimizer with the least Euclidean norm is selected. The normal cone optimality condition is utilized
to obtain a unique polyhedral representation of the piecewise affine minimizer function.
This research is part of the Strategic University Program on Computational Methods for Nonlinear Motion Control funded by
the Research Council of Norway. We thank Dr. E.C. Kerrigan at the Department of Electrical Engineering, Imperial College,
London and Dr. Colin Jones at ETH Zürich for their comments. Finally, we thank the anonymous reviewers for their comments. 相似文献
17.
本文针对一类带有反凸约束的非线性比式和分式规划问题,提出一种求其全局最优解的单纯形分支和对偶定界算法.该算法利用Lagrange对偶理论将其中关键的定界问题转化为一系列易于求解的线性规划问题.收敛性分析和数值算例均表明提出的算法是可行的. 相似文献
18.
R. Goldbach 《Applied Mathematics and Optimization》1999,39(1):121-142
We adapt some randomized algorithms of Clarkson [3] for linear programming to the framework of so-called LP-type problems,
which was introduced by Sharir and Welzl [10]. This framework is quite general and allows a unified and elegant presentation
and analysis. We also show that LP-type problems include minimization of a convex quadratic function subject to convex quadratic
constraints as a special case, for which the algorithms can be implemented efficiently, if only linear constraints are present.
We show that the expected running times depend only linearly on the number of constraints, and illustrate this by some numerical
results. Even though the framework of LP-type problems may appear rather abstract at first, application of the methods considered
in this paper to a given problem of that type is easy and efficient. Moreover, our proofs are in fact rather simple, since
many technical details of more explicit problem representations are handled in a uniform manner by our approach. In particular,
we do not assume boundedness of the feasible set as required in related methods.
Accepted 7 May 1997 相似文献
19.
Immanuel M. Bomze 《Journal of Global Optimization》1998,13(4):369-387
A standard quadratic optimization problem (QP) consists of finding (global) maximizers of a quadratic form over the standard simplex. Standard QPs arise quite naturally in copositivity-based procedures which enable an escape from local solutions. Furthermore, several important applications yield optimization problems which can be cast into a standard QP in a straightforward way. As an example, a new continuous reformulation of the maximum weight clique problem in undirected graphs is presented which considerably improves previous attacks both as numerical stability and interpretation of the results are concerned. Apparently also for the first time, an equivalence between standard QPs and QPs on the positive orthant is established. Also, a recently presented global optimization procedure (GENF - genetical engineering via negative fitness) is shortly reviewed. 相似文献
20.
We present a method which when applied to certain non-convex QP will locatethe globalminimum, all isolated local minima and some of the non-isolated localminima. The method proceeds by formulating a (multi) parametric convex QP interms ofthe data of the given non-convex QP. Based on the solution of the parametricQP,an unconstrained minimization problem is formulated. This problem ispiece-wisequadratic. A key result is that the isolated local minimizers (including theglobalminimizer) of the original non-convex problem are in one-to-one correspondencewiththose of the derived unconstrained problem.The theory is illustrated with several numerical examples. A numericalprocedure isdeveloped for a special class of non-convex QP's. It is applied to a problemfrom theliterature and verifies a known global optimum and in addition, locates apreviously unknown local minimum. 相似文献