Novel approaches for relaxation and approximation techniques in deterministic global optimization
Project goals
The aim of the project is to improve and develop novel tools for methods in global optimization. These methods are usually based on splitting the feasible set into subsets (called boxes) and checking certain properties on these boxes. For this purpose techniques from the discipline of interval computation are often used. That is why we need to be able to check for various properties of functions on a box and be able to find a tight convex enclosures of nonconvex functions. To this end, we also need to develop new results in interval linear algebra and interval linear programming. From the algorithmic perspective we will investigate novel kinds of approximations (outer and inner, linear and quadratic etc.) and solve special cases. From the theoretical standpoint, we will analyze computational complexity of the problems, characterize the relaxed systems, and investigate objective and constraint function properties from the viewpoint of matrix theory.
Keywords
operations researchoptimizationlinear programmingnonlinear programmingapproximationinterval analysis
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 22 (SGA0201800001)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
18-04735S
Alternative language
Project name in Czech
Nové přístupy pro relaxační a aproximační techniky v deterministické globální optimalizaci
Annotation in Czech
Projekt si klade za cíl vylepšit stávající a také navrhnout nové nástroje pro metody globální optimalizace. Tyto metody jsou převážně založeny na dělení množiny přípustných řešení na menší části (tzv. boxy) a testování určitých vlastností na těchto boxech. Pro toto testování se pak využívají techniky intervalové analýzy. Proto je zapotřebí umět testovat nejrůznější vlastnosti funkcí na boxu a umět najít těsnou konvexní obálku nekonvexních funkcí. K tomu potřebujeme také rozvinout matematický aparát v intervalové lineární algebře a intervalového lineárního programování. Z algoritmického pohledu budeme zkoušet nové druhy aproximací (vnější a vnitřní, lineární a kvadratické), a řešit speciální případy úloh globální optimalizace. Z teoretického hlediska budeme analyzovat výpočetní složitost problémů, charakterizovat relaxované systémy a zkoumat vlastnosti účelových a omezujících funkcí z pohledu teorie matic.
Scientific branches
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The project was focused on the design of new tools of global optimization methods. The project objectives were met and the publication goals were achieved. The project involved both Ph.D. and undergraduate students who were authors or co-authors of particular publications. The project can be evaluated as a successful one.
Solution timeline
Realization period - beginning
Jan 1, 2018
Realization period - end
Dec 31, 2021
Project status
U - Finished project
Latest support payment
Apr 1, 2021
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP22-GA0-GA-U
Data delivery date
Jun 29, 2022
Finance
Total approved costs
6,237 thou. CZK
Public financial support
5,517 thou. CZK
Other public sources
720 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
6 237 CZK thou.
Public support
5 517 CZK thou.
88%
Provider
Czech Science Foundation
OECD FORD
Economic Theory
Solution period
01. 01. 2018 - 31. 12. 2021