检索结果-内蒙古大学图书馆

Probabilistic subproblem selection in branch-and-bound algorithms

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2005年第1期182卷 67-80页

作者： Dür, M Stix, V Tech Univ Darmstadt Dept Math D-64289 Darmstadt Germany Vienna Univ Econ & Business Adm Dept Informat Business A-1090 Vienna Austria

We investigate the branch-and-bound method for solving nonconvex optimization problems. Traditionally, much effort has been invested in improving the quality of the bounds and in the development of branching strategies, whereas little is known about good selection rules. After summarizing several known selection methods, we propose to introduce a probabilistic element into the selection process. We describe conditions which guarantee that a branch-and-bound algorithm using our probabilistic selection rule converges with probability 1. This new method is a generalization of the well-known best-bound selection rule. Furthermore, we relate the corresponding probability measure to the distribution of the optimal solution in the bounding interval. We also show how information on the quality of the upper and lower bounds influences the choice of the subset selection rule and conclude with numerical experiments on the Maximum Clique Problem which show that probabilistic selection can speed up an algorithm in many cases. (c) 2004 Elsevier B.V. All rights reserved.

关键词： nonconvex programming subset selection in branch-and-bound algorithms convergence of branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

NECESSARY CONDITIONS FOR NONLINEAR SUBOPTIMIZATION OVER THE WEAKLY-EFFICIENT SET

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1993年第3期78卷 579-598页

作者： BOLINTINEANU, S 1. Université de Perpignan Perpignan France

The optimization problem of a nonlinear real function over the weakly-efficient set associated to a nonlinear multi-objective program is examined. Necessary first-order conditions for a suboptimal solution are proposed, assuming the convexity of the multi-objective program. Estimations of the optimal value are established and an algorithm for finding suboptimal solutions is proposed. The optimal value is approximated to any prescribed degree of accuracy using a weakly-efficient suboptimal solution.

关键词： MULTIOBJECTIVE OPTIMIZATION GLOBAL OPTIMIZATION NONLINEAR programming nonconvex programming STABILITY SENSITIVITY ANALYSIS

来源：评论

学校读者我要写书评

暂无评论

Abstract convexity and augmented Lagrangians

引用

SIAM JOURNAL ON OPTIMIZATION 2007年第2期18卷 413-436页

作者： Burachik, Regina Sandra Rubinov, Alex Univ Ballarat Ctr Informat & Appl Optimizat Ballarat Vic Australia Univ S Australia Sch Math & Stat Mawson Lakes SA 5095 Australia

The ultimate goal of this paper is to demonstrate that abstract convexity provides a natural language and a suitable framework for the examination of zero duality gap properties and exact multipliers of augmented Lagrangians. We study augmented Lagrangians in a very general setting and formulate the main definitions and facts describing the augmented Lagrangian theory in terms of abstract convexity tools. We illustrate our duality scheme with an application to stochastic semi- infinite optimization.

关键词： abstract convexity nonconvex programming Lagrange-type functions augmented Lagrangians exact penalty representation stochastic semi-infinite programming

来源：评论

学校读者我要写书评

暂无评论

A method for approximating pairwise comparison matrices by consistent matrices

引用

JOURNAL OF GLOBAL OPTIMIZATION 2008年第3期42卷 423-442页

作者： Fulop, Janos Hungarian Acad Sci Lab Operat Res & Decis Syst Comp & Automat Res Inst H-1111 Budapest Hungary

In several methods of multiattribute decision making, pairwise comparison matrices are applied to derive implicit weights for a given set of decision alternatives. A class of the approaches is based on the approximation of the pairwise comparison matrix by a consistent matrix. In the paper this approximation problem is considered in the least-squares sense. In general, the problem is nonconvex and difficult to solve, since it may have several local optima. In the paper the classic logarithmic transformation is applied and the problem is transcribed into the form of a separable programming problem based on a univariate function with special properties. We give sufficient conditions of the convexity of the objective function over the feasible set. If such a sufficient condition holds, the global optimum of the original problem can be obtained by local search, as well. For the general case, we propose a branch-and-bound method. Computational experiments are also presented.

关键词： pairwise comparison matrix consistent matrix nonconvex programming branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

An Evolutionary Algorithm for Solving Bilevel programming Problems Using Duality Conditions

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2012年第1期2012卷 1-14页

作者： Li, Hecheng Fang, Lei Nankai Univ Sch Business Tianjin 300071 Peoples R China Qinghai Normal Univ Minist Educ Key Lab Tibetan Informat Proc Dept Math Xining 810008 Peoples R China Chinese Acad Sci Acad Math & Syst Sci Beijing 100190 Peoples R China

Bilevel programming is characterized by two optimization problems located at different levels, in which the constraint region of the upper level problem is implicitly determined by the lower level problem. This paper is focused on a class of bilevel programming with a linear lower level problem and presents a new algorithm for solving this kind of problems by combining an evolutionary algorithm with the duality principle. First, by using the prime-dual conditions of the lower level problem, the original problem is transformed into a single-level nonlinear programming problem. In addition, for the dual problem of the lower level, the feasible bases are taken as individuals in population. For each individual, the values of dual variables can be obtained by taking the dual problem into account, thus simplifying the single-level problem. Finally, the simplified problem is solved, and the objective value is taken as the fitness of the individual. Besides, when nonconvex functions are involved in the upper level, a coevolutionary scheme is incorporated to obtain global optima. In the computational experiment, 10 problems, smaller or larger-scale, are solved, and the results show that the proposed algorithm is efficient and robust.

关键词： ALGORITHMS BILEVEL programming WAVE-particle duality nonconvex programming ROBUST control

来源：评论

学校读者我要写书评

暂无评论

Branching and bounding improvements for global optimization algorithms with Lipschitz continuity properties

引用

JOURNAL OF GLOBAL OPTIMIZATION 2015年第3期61卷 429-457页

作者： Cartis, Coralia Fowkes, Jaroslav M. Gould, Nicholas I. M. Univ Edinburgh Sch Math Kings Bldg Edinburgh EH9 3JZ Midlothian Scotland Rutherford Appleton Lab Computat Sci & Engn Dept Chilton OX11 0QX Oxon England

We present improvements to branch and bound techniques for globally optimizing functions with Lipschitz continuity properties by developing novel bounding procedures and parallelisation strategies. The bounding procedures involve nonconvex quadratic or cubic lower bounds on the objective and use estimates of the spectrum of the Hessian or derivative tensor, respectively. As the nonconvex lower bounds are only tractable if solved over Euclidean balls, we implement them in the context of a recent branch and bound algorithm (Fowkes et al. in J Glob Optim 56:1791-1815, 2013) that uses overlapping balls. Compared to the rectangular tessellations of traditional branch and bound, overlapping ball coverings result in an increased number of subproblems that need to be solved and hence makes the need for their parallelization even more stringent and challenging. We develop parallel variants based on both data- and task-parallel paradigms, which we test on an HPC cluster on standard test problems with promising results.

关键词： Global optimization Lipschitzian optimization Parallel branch and bound nonconvex programming

来源：评论

学校读者我要写书评

暂无评论

DELETION-BY-INFEASIBILITY RULE FOR DC-CONSTRAINED GLOBAL OPTIMIZATION

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1995年第2期84卷 443-455页

作者： FULOP, J HUNGARIAN ACAD SCI INST COMP & AUTOMATOPERAT RES & DECIS SYST LABBUDAPESTHUNGARY

In Ref. 1, a general class of branch-and-bound methods was proposed by Horst for solving global optimization problems. One of the main contributions of Ref. 1 was the opportunity of handling partition elements whose feasibility is not known. Deletion-by-infeasibility rules were presented for problems where the feasible set is convex, is defined by finitely many convex and reverse convex constraints, or is defined by Lipschitzian inequalities. In this note, we propose a new deletion-by-infeasibility rule for problems whose feasible set is defined by functions representable as differences of convex functions.

关键词： GLOBAL OPTIMIZATION nonconvex programming MATHEMATICAL programming DC-programming BRANCH-AND-BOUND METHODS

来源：评论

学校读者我要写书评

暂无评论

CONVERGENCE AND RESTART IN BRANCH-AND-BOUND ALGORITHMS FOR GLOBAL OPTIMIZATION - APPLICATION TO CONCAVE MINIMIZATION AND DC OPTIMIZATION PROBLEMS

引用

MATHEMATICAL programming 1988年第2期41卷 161-183页

作者： TUY, H HORST, R UNIV TRIER D-5500 TRIERFED REP GER

A general branch-and-bound conceptual scheme for global optimization is presented that includes along with previous branch-and-bound approaches also grid-search techniques. The corresponding convergence theory, as well as the question of restart capability for branch-and-bound algorithms used in decomposition or outer approximation schemes are discussed. As an illustration of this conceptual scheme, a finite branch-and-bound algorithm for concave minimization is described and a convergent branch-and-bound algorithm, based on the previous one, is developed for the minimization of a difference of two convex functions.

关键词： Global optimization nonconvex programming branch-and-bound restart procedure decomposition outer approximation concave minimization d.c. optimization

来源：评论

学校读者我要写书评

暂无评论

Improved Convex and Concave Relaxations of Composite Bilinear Forms

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2023年第1期197卷 174-204页

作者： Wilhelm, Matthew E. Stuber, Matthew D. Univ Connecticut Dept Chem & Biomol Engn Proc Syst & Operat Res Lab 191 Auditorium Rd Unit 3222 Storrs 0626 CT USA

Deterministic nonconvex optimization solvers generate convex relaxations of noncon-vex functions by making use of underlying factorable representations. One approach introduces auxiliary variables assigned to each factor that lifts the problem into a higher-dimensional decision space. In contrast, a generalized McCormick relaxation approach offers the significant advantage of constructing relaxations in the lower dimensionality space of the original problem without introducing auxiliary variables, often referred to as a "reduced-space" approach. Recent contributions illustrated how additional nontrivial inequality constraints may be used in factorable programming to tighten relaxations of the ubiquitous bilinear term. In this work, we exploit an analogous representation of McCormick relaxations and factorable programming to formulate tighter relaxations in the original decision space. We develop the under-lying theory to generate necessarily tighter reduced-space McCormick relaxations when a priori convex/concave relaxations are known for intermediate bilinear terms. We then show how these rules can be generalized within a McCormick relaxation scheme via three different approaches: the use of a McCormick relaxations coupled to affine arithmetic, the propagation of affine relaxations implied by subgradients, and an enumerative approach that directly uses relaxations of each factor. The developed approaches are benchmarked on a library of optimization problems using the *** optimizer. Two case studies are also considered to demonstrate the developments: an application in advanced manufacturing to optimize supply chain quality metrics and a global dynamic optimization application for rigorous model validation of a kinetic mechanism. The presented subgradient method leads to an improvement in CPU time required to solve the considered problems to is an element of-global optimality.

关键词： Deterministic global optimization nonconvex programming McCormick relaxations Branch-and-bound Multilinear products

来源：评论

学校读者我要写书评

暂无评论

Two-level primal-dual proximal decomposition technique to solve large scale optimization problems

引用

APPLIED MATHEMATICS AND COMPUTATION 2005年第3期160卷 921-938页

作者： Hamdi, A King Saud Univ Coll Sci Dept Math Riyadh 11451 Saudi Arabia

We describe a primal-dual application of the proximal point algorithm to nonconvex minimization problems. Motivated by the work of Spingarn and more recently by the work of Hamdi et al. about the primal resource-directive decomposition scheme to solve nonlinear separable problems. This paper discusses some local results of a primal-dual regularization approach that leads to a decomposition algorithm. (C) 2004 Elsevier Inc. All rights reserved.

关键词： multiplier methods proximal regularization decomposition nonconvex programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：