Certificates of infeasibility via nonsmooth optimization

DOI10.1007/S10898-016-0473-XzbMATH Open1380.90223DBLPjournals/jgo/FendlNS17arXiv1506.08338OpenAlexW2256161684WikidataQ59607654 ScholiaQ59607654MaRDI QIDQ1675645FDOQ1675645

Authors: Hannes Fendl, Arnold Neumaier, Hermann Schichl 

Publication date: 2 November 2017

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: An important aspect in the solution process of constraint satisfaction problems is to identify exclusion boxes which are boxes that do not contain feasible points. This paper presents a certificate of infeasibility for finding such boxes by solving a linearly constrained nonsmooth optimization problem. Furthermore, the constructed certificate can be used to enlarge an exclusion box by solving a nonlinearly constrained nonsmooth optimization problem.

Full work available at URL: https://arxiv.org/abs/1506.08338

Recommendations

• An infeasibility certificate for nonlinear programming based on Pareto criticality condition
• Certificates of linear mixed integer infeasibility
• Rigorous verification of feasibility
• Exclusion regions for optimization problems
• Feasibility and infeasibility in optimization. Algorithms and computational methods.

zbMATH Keywords

global optimizationnonsmooth optimizationcertificate of infeasibility

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26) Derivative-free methods and methods using generalized derivatives (90C56)

Cites Work

• BARON: A general purpose global optimization software package
• Rigorous global search: continuous problems
• An implementation of Shor's \(r\)-algorithm
• G<scp>LOPT</scp>L<scp>AB</scp>: a configurable framework for the rigorous global solution of quadratic constraint satisfaction problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• A bundle-Newton method for nonsmooth unconstrained minimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the implementation and usage of SDPT3 -- a Matlab software package for semidefinite-quadratic-linear programming, version 4.0
• Interval Methods for Systems of Equations
• Title not available (Why is that?)
• On implementing a primal-dual interior-point method for conic quadratic optimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complete search in continuous global optimization and constraint satisfaction
• Interval arithmetic: from principles to implementation
• Numerical Software with Result Verification
• Certificates of infeasibility via nonsmooth optimization

Cited In (5)

• Certificates of linear mixed integer infeasibility
• An infeasibility certificate for nonlinear programming based on Pareto criticality condition
• Certificates of infeasibility via nonsmooth optimization
• On primal and dual infeasibility certificates in a homogeneous model for convex optimization
• Rigorous verification of feasibility

Uses Software

• BARON
• GLOPTLAB
• SOCP
• SeDuMi
• INTLAB
• lp_solve
• SDPT3
• SolvOpt
• LINDO
• INTOPT_90
• COCONUT
• LINGO
• PBNCGC
• PNEW
• MPBNGC

This page was built for publication: Certificates of infeasibility via nonsmooth optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1675645)