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

Optimality Conditions for Minimizers at Infinity in polynomial programming

MATHEMATICS OF OPERATIONS RESEARCH 2019年第4期44卷 1381-1395页

作者： Tien-Son Pham Ton Duc Thang Univ Inst Computat Sci Div Computat Math & Engn Ho Chi Minh City 700000 Vietnam Ton Duc Thang Univ Fac Math & Stat Ho Chi Minh City 700000 Vietnam

In this paper we study necessary optimality conditions for the problem of minimizing a polynomial function over a set defined by polynomial inequalities. Assume that the problem is bounded below and has the Mangasarian-Fromovitz property at infinity. We first show that if the problem does not have an optimal solution, then a version at infinity of the Fritz John optimality conditions holds. From this we derive a version at infinity of the Karush-Kuhn-Tucker optimality conditions. As applications, we obtain a Frank-Wolfe type theorem which states that the optimal solution set of the problem is nonempty provided the objective function is "convenient." Finally, in the unconstrained case, we show that the optimal value of the problem is the smallest critical value of some polynomial. All the results are presented in terms of the Newton polyhedra of the polynomials defining the problem.

关键词： existence of minimizers Fermat theorem Frank-Wolfe theorem Fritz John optimality conditions Karush-Kuhn-Tucker optimality conditions Mangasarian-Fromovitz constraint qualification Newton polyhedron polynomial programming

来源：评论

学校读者我要写书评

暂无评论

A dynamic inequality generation scheme for polynomial programming

引用

MATHEMATICAL programming 2016年第1-2期156卷 21-57页

作者： Ghaddar, Bissan Vera, Juan C. Anjos, Miguel F. IBM Res Corp Dublin Technol CampusDamastown Ind PkMulhuddart Dublin Ireland Tilburg Univ Tilburg Sch Econ & Management NL-5000 LE Tilburg Netherlands Gerad Discrete Nonlinear Optimizat Engn Montreal PQ H3C 3A7 Canada Ecole Polytech Montreal PQ H3C 3A7 Canada

Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. As a result, the proposed scheme is in principle scalable to large general polynomial programming problems. When all the variables of the problem are non-negative or when all the variables are binary, the general algorithm is specialized to a more efficient algorithm. In the case of binary polynomial programs, we show special cases for which the proposed scheme converges to the global optimal solution. We also present several examples illustrating the computational behavior of the scheme and provide comparisons with Lasserre's approach and, for the binary linear case, with the lift-and-project method of Balas, Ceria, and Cornu,jols.

关键词： polynomial programming Binary polynomial programming Semidefinite programming Inequality generation

来源：评论

学校读者我要写书评

暂无评论

RLT-POS: Reformulation-Linearization Technique-based optimization software for solving polynomial programming problems

引用

MATHEMATICAL programming COMPUTATION 2016年第3期8卷 337-375页

作者： Dalkiran, Evrim Sherali, Hanif D. Wayne State Univ Dept Ind & Syst Engn Detroit MI 48202 USA Virginia Tech Grado Dept Ind & Syst Engn Blacksburg VA 24061 USA

In this paper, we introduce a Reformulation-Linearization Technique-based open-source optimization software for solving polynomial programming problems (RLT-POS). We present algorithms and mechanisms that form the backbone of RLT-POS, including constraint filtering techniques, reduced RLT representations, and semidefinite cuts. When implemented individually, each model enhancement has been shown in previous papers to significantly improve the performance of the standard RLT procedure. However, the coordination between different model enhancement techniques becomes critical for an improved overall performance since special structures in the original formulation that work in favor of a particular technique might be lost after implementing some other model enhancement. More specifically, we discuss the coordination between (1) constraint elimination via filtering techniques and reduced RLT representations, and (2) semidefinite cuts for sparse problems. We present computational results using instances from the literature as well as randomly generated problems to demonstrate the improvement over a standard RLT implementation and to compare the performances of the software packages BARON, COUENNE, and SparsePOP with RLT-POS.

关键词： Reformulation-Linearization Technique (RLT) Open-source code Constraint filtering strategies Valid inequalities Reduced RLT representations polynomial programming

来源：评论

学校读者我要写书评

暂无评论

Mixed integer polynomial programming

引用

COMPUTERS & CHEMICAL ENGINEERING 2015年 72卷 387-394页

作者： Dua, Vivek UCL Ctr Proc Syst Engn Dept Chem Engn London WC1E 7JE England

The mixed integer polynomial programming problem is reformulated as a multi-parametric programming problem by relaxing integer variables as continuous variables and then treating them as parameters. The optimality conditions for the resulting parametric programming problem are given by a set of simultaneous parametric polynomial equations which are solved analytically to give the parametric optimal solution as a function of the relaxed integer variables. Evaluation of the parametric optimal solution for integer variables fixed at their integer values followed by screening of the evaluated solutions gives the optimal solutions. (C) 2014 The Author. Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license

关键词： Mixed integer programming polynomial programming Nonlinear inversion Multi parametric programming

来源：评论

学校读者我要写书评

暂无评论

Degree reduction techniques for polynomial optimization problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2025年第2期322卷 401-413页

作者： Gonzalez-Rodriguez, Brais Naoum-Sawaya, Joe Western Univ Ivey Business Sch 1255 Western Rd London ON N6G 4W1 Canada

This paper presents anew approach to quadrify a polynomial programming problem, i.e. reduce the polynomial program to a quadratic program, before solving it. The proposed approach, QUAD-RLT, exploits the Reformulation-Linearization Technique (RLT) structure to obtain smaller relaxations that can be solved faster and still provide high quality bounds. QUAD-RLT is compared to other quadrification techniques that have been previously discussed in the literature. The paper presents theoretical as well as computational results showing the advantage of QUAD-RLT compared to other quadrification techniques. Furthermore, rather than quadrifying a polynomial program, QUAD-RLT is generalized to reduce the degree of the polynomial to any degree. Computational results show that reducing the degree of the polynomial to a degree that is higher than two provides computational advantages in certain cases compared to fully quadrifying the problem. Finally, QUAD-RLT along with other quadrification/degree reduction schemes are implemented and made available in the freely available software RAPOSa.

关键词： Nonlinear programming Quadrification Degree reduction Reformulation-linearization technique polynomial programming

来源：评论

学校读者我要写书评

暂无评论

polynomial Optimization: Tightening RLT-Based Branch-and-Bound Schemes with Conic Constraints

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2025年第1期204卷 1-34页

作者： Gonzalez-Rodriguez, Brais Alvite-Pazo, Raul Alvite-Pazo, Samuel Ghaddar, Bissan Gonzalez-Diaz, Julio Univ Vigo Ourense Dept Stat & Operat Res Orense Galicia Spain CITMAga Galician Ctr Math Res & Technol Santiago De Compostela Galicia Spain Western Univ London Ivey Business Sch London ON Canada Univ Santiago De Compostela Dept Stat Math Anal & Optimizat Santiago De Compostela Galicia Spain Univ Santiago de Compostela MODESTYA Res Grp Santiago De Compostela Galicia Spain

This paper explores the potential of (nonlinear) conic constraints to tighten the relaxations of spatial branch-and-bound algorithms. More precisely, we contribute to the literature on the use of conic optimization for the efficient solution, to global optimality, of nonconvex polynomial optimization problems. Taking as baseline an RLT-based algorithm, we present different families of well-known conic-driven constraints: linear SDP-cuts, second-order cone constraints, and SDP constraints. We integrate these constraints in the baseline algorithm and present a thorough computational study to assess their performance, both with respect to each other and with respect to the standard RLT relaxations for polynomial optimization problems. Our main finding is that the different variants of nonlinear constraints (second-order cone and semidefinite) are the best performing ones in around 50%\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$50\%$$\end{document} of the instances in widely used test sets. Additionally, we discuss how one can benefit from the use of machine learning to decide on the most suitable constraints to add to a given instance. The computational results show that the machine learning approach significantly outperforms each of the individual approaches.

关键词： Global optimization Reformulation-linearization technique polynomial programming Conic optimization Machine learning

来源：评论

学校读者我要写书评

暂无评论

A new technique to derive tight convex underestimators (sometimes envelopes)

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2024年第2期87卷 475-499页

作者： Locatelli, M. Univ Parma Dipartimento Ingn & Architettura 181-A Parco Area Sci I-43124 Parma Italy

The convex envelope value for a given function f over a region X at some point x is an element of X can be derived by searching for the largest value at that point among affine underestimators of f over X. This can be computed by solving a maximin problem, whose exact computation, however, may be a hard task. In this paper we show that by relaxation of the inner minimization problem, duality, and, in particular, by an enlargement of the class of underestimators (thus, not only affine ones) an easier derivation of good convex understimating functions, which can also be proved to be convex envelopes in some cases, is possible. The proposed approach is mainly applied to the derivation of convex underestimators (in fact, in some cases, convex envelopes) in the quadratic case. However, some results are also presented for polynomial, ratio of polynomials, and some other separable functions over regions defined by similarly defined separable functions.

关键词： Convex underestimators Convex envelopes Quadratic programming polynomial programming Separable functions

来源：评论

学校读者我要写书评

暂无评论

Computational advances in polynomial optimization: RAPOSa, a freely available global solver

引用

JOURNAL OF GLOBAL OPTIMIZATION 2023年第3期85卷 541-568页

作者： Gonzalez-Rodriguez, Brais Ossorio-Castillo, Joaquin Gonzalez-Diaz, Julio Gonzalez-Rueda, Angel M. Penas, David R. Rodriguez-Martinez, Diego Univ Santiago de Compostela Dept Stat Math Anal & Optimizat MODESTYA Res Grp Santiago Spain Univ A Coruna Dept Math MODES Res Grp La Coruna Spain Univ A Coruna CITIC La Coruna Spain CITMAga Galician Ctr Math Res & Technol Santiago De Compostela Spain

In this paper we introduce RAPOSa, a global optimization solver specifically designed for (continuous) polynomial programming problems with box-constrained variables. Written entirely in C++, RAPOSa is based on the Reformulation-Linearization (Sherali and Tuncbilek in J Glob Optim 103:225-249, 1992). We present a description of the main characteristics of RAPOSa along with a thorough analysis of the impact on its performance of various enhancements discussed in the literature, such as bound tightening and SDP cuts. We also present a comparative study with three of the main state-of-the-art global optimization solvers: BARON, Couenne and SCIP.

关键词： Global optimization polynomial programming Reformulation-Linearization Technique (RLT )

来源：评论

学校读者我要写书评

暂无评论

An Automated Approach to Causal Inference in Discrete Settings

引用

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION 2023年第547期119卷 1778-1793页

作者： Duarte, Guilherme Finkelstein, Noam Knox, Dean Mummolo, Jonathan Shpitser, Ilya Univ Penn Wharton Sch Operat Informat & Decis Dept Philadelphia PA 19104 USA Johns Hopkins Univ Whiting Sch Engn Dept Comp Sci Baltimore MD USA Princeton Univ Dept Polit Princeton NJ USA Princeton Univ Sch Publ & Int Affairs Princeton NJ USA

Applied research conditions often make it impossible to point-identify causal estimands without untenable assumptions. Partial identification-bounds on the range of possible solutions-is a principled alternative, but the difficulty of deriving bounds in idiosyncratic settings has restricted its application. We present a general, automated numerical approach to causal inference in discrete settings. We show causal questions with discrete data reduce to polynomial programming problems, then present an algorithm to automatically bound causal effects using efficient dual relaxation and spatial branch-and-bound techniques. The user declares an estimand, states assumptions, and provides data-however incomplete or mismeasured. The algorithm then searches over admissible data-generating processes and outputs the most precise possible range consistent with available information-that is, sharp bounds-including a point-identified solution if one exists. Because this search can be computationally intensive, our procedure reports and continually refines non-sharp ranges guaranteed to contain the truth at all times, even when the algorithm is not run to completion. Moreover, it offers an e-sharpness guarantee, characterizing the worst-case looseness of the incomplete bounds. These techniques are implemented in our Python package, autobounds. Analytically validated simulations show the method accommodates classic obstacles-including confounding, selection, measurement error, noncompliance, and nonresponse. Supplementary materials for this article are available online.

关键词： Causal inference Constrained optimization Partial identification Linear programming polynomial programming

来源：评论

学校读者我要写书评

暂无评论

Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality

引用

JOURNAL OF GLOBAL OPTIMIZATION 2013年第4期57卷 1147-1172页

作者： Dalkiran, Evrim Sherali, Hanif D. Wayne State Univ Dept Ind & Syst Engn Detroit MI 48202 USA Virginia Tech Grado Dept Ind & Syst Engn Blacksburg VA 24061 USA

In this paper, we propose two sets of theoretically filtered bound-factor constraints for constructing reformulation-linearization technique (RLT)-based linear programming (LP) relaxations for solving polynomial programming problems. We establish related theoretical results for convergence to a global optimum for these reduced sized relaxations, and provide insights into their relative sizes and tightness. Extensive computational results are provided to demonstrate the relative effectiveness of the proposed theoretical filtering strategies in comparison to the standard RLT and a prior heuristic filtering technique using problems from the literature as well as randomly generated test cases.

关键词： Reformulation-linearization technique (RLT) Filtering strategies polynomial programming Branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：