共查询到20条相似文献,搜索用时 687 毫秒
1.
Convergence and Application of a Decomposition Method Using Duality Bounds for Nonconvex Global Optimization 总被引:4,自引:0,他引:4
N.V. Thoai 《Journal of Optimization Theory and Applications》2002,113(1):165-193
The subject of this article is a class of global optimization problems, in which the variables can be divided into two groups such that, in each group, the functions involved have the same structure (e.g. linear, convex or concave, etc.). Based on the decomposition idea of Benders (Ref. 1), a corresponding master problem is defined on the space of one of the two groups of variables. The objective function of this master problem is in fact the optimal value function of a nonlinear parametric optimization problem. To solve the resulting master problem, a branch-and-bound scheme is proposed, in which the estimation of the lower bounds is performed by applying the well-known weak duality theorem in Lagrange duality. The results of this article concentrate on two subjects: investigating the convergence of the general algorithm and solving dual problems of some special classes of nonconvex optimization problems. Based on results in sensitivity and stability theory and in parametric optimization, conditions for the convergence are established by investigating the so-called dual properness property and the upper semicontinuity of the objective function of the master problem. The general algorithm is then discussed in detail for some nonconvex problems including concave minimization problems with a special structure, general quadratic problems, optimization problems on the efficient set, and linear multiplicative programming problems. 相似文献
2.
3.
边界约束非凸二次规划问题的分枝定界方法 总被引:2,自引:0,他引:2
本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。 相似文献
4.
In this paper, we will develop an algorithm for solving a quadratic fractional programming problem which was recently introduced by Lo and MacKinlay to construct a maximal predictability portfolio, a new approach in portfolio analysis. The objective function of this problem is defined by the ratio of two convex quadratic functions, which is a typical global optimization problem with multiple local optima. We will show that a well-designed branch-and-bound algorithm using (i) Dinkelbach's parametric strategy, (ii) linear overestimating function and (iii) -subdivision strategy can solve problems of practical size in an efficient way. This algorithm is particularly efficient for Lo-MacKinlay's problem where the associated nonconvex quadratic programming problem has low rank nonconcave property. 相似文献
5.
A global optimization method, QBB, for twice-differentiable NLPs (Non-Linear Programming) is developed to operate within a
branch-and-bound framework and require the construction of a relaxed convex problem on the basis of the quadratic lower bounding
functions for the generic nonconvex structures. Within an exhaustive simplicial division of the constrained region, the rigorous
quadratic underestimation function is constructed for the generic nonconvex function structure by virtue of the maximal eigenvalue
analysis of the interval Hessian matrix. Each valid lower bound of the NLP problem with the division progress is computed
by the convex programming of the relaxed optimization problem obtained by preserving the convex or linear terms, replacing
the concave term with linear convex envelope, underestimating the special terms and the generic terms by using their customized
tight convex lower bounding functions or the valid quadratic lower bounding functions, respectively. The standard convergence
properties of the QBB algorithm for nonconvex global optimization problems are guaranteed. The preliminary computation studies
are presented in order to evaluate the algorithmic efficiency of the proposed QBB approach. 相似文献
6.
Ravi P Agarwal 《Journal of Mathematical Analysis and Applications》1982,89(2):628-638
This paper presents a method for obtaining closed form solutions to serial and nonserial dynamic programming problems with quadratic stage returns and linear transitions. Global parametric optimum solutions can be obtained regardless of the convexity of the stage returns. The closed form solutions are developed for linear, convex, and nonconvex quadratic returns, as well as the procedure for recursively solving each stage of the problem. Dynamic programming is a mathematical optimization technique which is especially powerful for certain types of problems. This paper presents a procedure for obtaining analytical solutions to a class of dynamic programming problems. In addition, the procedure has been programmed on the computer to facilitate the solution of large problems. 相似文献
7.
In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with ℓ1 and ℓ2 norms. These inverse optimization problems are either linear programming when ℓ1 norm is used in the formulation, or convex quadratic separable programming when ℓ2 norm is used. 相似文献
8.
We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S. Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of quadratic objective functions and diagonal coefficient matrices of quadratic constraint functions. A new SOCP relaxation is proposed for the class of nonconvex quadratic optimization problems by extracting valid quadratic inequalities for positive semidefinite cones. Its effectiveness to obtain optimal values is shown to be the same as the SDP relaxation theoretically. Numerical results are presented to demonstrate that the SOCP relaxation is much more efficient than the SDP relaxation. 相似文献
9.
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. 相似文献
10.
We consider the problem of minimizing an indefinite quadratic objective function subject to twosided indefinite quadratic
constraints. Under a suitable simultaneous diagonalization assumption (which trivially holds for trust region type problems),
we prove that the original problem is equivalent to a convex minimization problem with simple linear constraints. We then
consider a special problem of minimizing a concave quadratic function subject to finitely many convex quadratic constraints,
which is also shown to be equivalent to a minimax convex problem. In both cases we derive the explicit nonlinear transformations
which allow for recovering the optimal solution of the nonconvex problems via their equivalent convex counterparts. Special
cases and applications are also discussed. We outline interior-point polynomial-time algorithms for the solution of the equivalent
convex programs.
This author's work was partially supported by GIF, the German-Israeli Foundation for Scientific Research and Development and
by the Binational Science Foundation.
This author's work was partially supported by National Science Foundation Grants DMS-9201297 and DMS-9401871. 相似文献
11.
R. Y. Rubinstein G. Samorodnitsky 《Journal of Optimization Theory and Applications》1986,51(2):321-343
The problem of the coverage of convex regions with polygons and quadratic configurations of minimal volume is considered. The regions are presented as inequality constraints of a linear or nonlinear programming problem. It is shown that the problem of the optimal coverage with an arbitrary polygon can be reduced to a convex one of coverage with a multidimensional rectangle. If, however, rotation of the coordinate system is allowed, an additional nonconvex problem must be solved. It is also shown that, to find the minimal covering hypersphere or hyperellipsoid, one has to solve two convex programming problems. Algorithms and examples illustrating the feasibility of the proposed methods are presented.This work was supported by funds for the promotion of research at the Technion under Contract No. 190-515.The authors would like to express their indebtedness to Prof. Aharon Ben-Tal from Technion and to Prof. L. C. W. Dixon of the Hatfield Polytechnic for several valuable suggestions on an earlier draft of this paper. 相似文献
12.
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. 相似文献
13.
The aim of this paper is to propose an algorithm, based on the optimal level solutions method, which solves a particular class
of box constrained quadratic problems. The objective function is given by the sum of a quadratic strictly convex separable
function and the square of an affine function multiplied by a real parameter. The convexity and the nonconvexity of the problem
can be characterized by means of the value of the real parameter. Within the algorithm, some global optimality conditions
are used as stopping criteria, even in the case of a nonconvex objective function. The results of a deep computational test
of the algorithm are also provided.
This paper has been partially supported by M.I.U.R. 相似文献
14.
We describe a general scheme for solving nonconvex optimization problems, where in each iteration the nonconvex feasible set
is approximated by an inner convex approximation. The latter is defined using an upper bound on the nonconvex constraint functions.
Under appropriate conditions, a monotone convergence to a KKT point is established. The scheme is applied to truss topology
design (TTD) problems, where the nonconvex constraints are associated with bounds on displacements and stresses. It is shown
that the approximate convex problem solved at each inner iteration can be cast as a conic quadratic programming problem, hence
large scale TTD problems can be efficiently solved by the proposed method. 相似文献
15.
Anthony V. Fiacco 《Annals of Operations Research》1990,27(1):381-395
In this tutorial, a strategy is described for calculating parametric piecewise-linear optimal value bounds for nonconvex separable programs containing several parameters restricted to a specified convex set. The methodology is based on first fixing the value of the parameters, then constructing sequences of underestimating and overestimating convex programs whose optimal values respectively increase or decrease to the global optimal value of the original problem. Existing procedures are used for calculating parametric lower bounds on the optimal value of each underestimating problem and parametric upper bounds on the optimal value of each overestimating problem in the sequence, over the given set of parameters. Appropriate updating of the bounds leads to a nondecreasing sequence of lower bounds and a nonincreasing sequence of upper bounds, on the optimal value of the original problem, continuing until the bounds satisfy a specified tolerance at the value of the parameter that was fixed at the outset. If the bounds are also sufficiently tight over the entire set of parameters, according to criteria specified by the user, then the calculation is complete. Otherwise, another parameter value is selected and the procedure is repeated, until the specified criteria are satisfied over the entire set of parameters. A parametric piecewise-linear solution vector approximation is also obtained. Results are expected in the theory, computations, and practical applications. The general idea of developing results for general problems that are limits of results that hold for a sequence of well-behaved (e.g., convex) problems should be quite fruitful. 相似文献
16.
By using conjugate directions a method for solving convex quadratic programming problems is developed. The algorithm generates a sequence of feasible solutions and terminates after a finite number of iterations. Extensions of the algorithm for nonconvex and large structured quadratic programming problems are discussed.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041 and in part by the Natural Sciences and Engineering Research Council of Canada under Grant Nos. A 8189 and E 5582. 相似文献
17.
The object of this paper is to prove duality theorems for quasiconvex programming problems. The principal tool used is the transformation introduced by Manas for reducing a nonconvex programming problem to a convex programming problem. Duality in the case of linear, quadratic, and linear-fractional programming is a particular case of this general case.The authors are grateful to the referees for their kind suggestions. 相似文献
18.
We present a general active set algorithm for the solution of a convex quadratic programming problem having a parametrized Hessian matrix. The parametric Hessian matrix is a positive semidefinite Hessian matrix plus a real parameter multiplying a symmetric matrix of rank one or two. The algorithm solves the problem for all parameter values in the open interval upon which the parametric Hessian is positive semidefinite. The algorithm is general in that any of several existing quadratic programming algorithms can be extended in a straightforward manner for the solution of the parametric Hessian problem.This research was supported by the Natural Sciences and Engineering Research Council under Grant No. A8189 and under a Postgraduate Scholarship, by an Ontario Graduate Scholarship, and by the University of Windsor Research Board under Grant No. 9432. 相似文献
19.
We present a general active set algorithm for the solution of a convex quadratic programming problem having a parametrized
Hessian matrix. The parametric Hessian matrix is a positive semidefinite Hessian matrix plus a real parameter multiplying
a symmetric matrix of rank one or two. The algorithm solves the problem for all parameter values in the open interval upon
which the parametric Hessian is positive semidefinite. The algorithm is general in that any of several existing quadratic
programming algorithms can be extended in a straightforward manner for the solution of the parametric Hessian problem.
This research was supported by the Natural Sciences and Engineering Research Council under Grant No. A8189 and under a Postgraduate
Scholarship, by an Ontario Graduate Scholarship, and by the University of Windsor Research Board under Grant No. 9432. 相似文献