Russian Universities Reports. Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Russian Universities Reports. Mathematics:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Russian Universities Reports. Mathematics, 2024, Volume 29, Issue 145, Pages 20–28
DOI: https://doi.org/10.20310/2686-9667-2024-29-145-20-28
(Mi vtamu310)
 

Scientific articles

Construction of smooth convex extensions of Boolean functions

D. N. Barotova, R. N. Barotovb

a Financial University under the Government of the Russian Federation
b Khujand State University named after academician Bobojon Gafurov
References:
Abstract: Systems of Boolean equations are widely used in mathematics, computer science, and applied sciences. In this regard, on the one hand, new research methods and algorithms are being developed for such systems, and on the other hand, existing methods and algorithms for solving such systems are being improved. One of these methods is that, firstly, the system of Boolean equations given over the ring of Boolean polynomials is transformed into a system of equations over the field of real numbers, and secondly, the transformed system is reduced either to the problem of numerical minimization of the corresponding objective function, to a MILP or QUBO problem, to a system of polynomial equations solved on the set of integers, or to an equivalent system of polynomial equations solved by symbolic methods. There are many ways to transform a system of Boolean equations into a continuous minimization problem, since the fundamental difference between such methods and “brute force” local search algorithms is that at each iteration of the algorithm, the shift along the antigradient is performed on all variables simultaneously. But one of the main problems that arise when applying these methods is that the objective function to be minimized in the desired area can have many local minima, which greatly complicates their practical use. In this paper, a non-negative convex and continuously differentiable extension of any Boolean function is constructed, which is applied to solving an arbitrary system of Boolean equations. It is argued that the problem of solving an arbitrary system of Boolean equations can be constructively reduced to the problem of minimizing a function, any local minimum of which in the desired domain is a global minimum.
Keywords: global optimization, convex function, Boolean function, extension of a Boolean function, local minimum
Received: 09.07.2023
Accepted: 11.03.2024
Document Type: Article
UDC: 519.85, 517.518.244
MSC: 65K05, 90C25, 46N10
Language: Russian
Citation: D. N. Barotov, R. N. Barotov, “Construction of smooth convex extensions of Boolean functions”, Russian Universities Reports. Mathematics, 29:145 (2024), 20–28
Citation in format AMSBIB
\Bibitem{BarBar24}
\by D.~N.~Barotov, R.~N.~Barotov
\paper Construction of smooth convex extensions of Boolean functions
\jour Russian Universities Reports. Mathematics
\yr 2024
\vol 29
\issue 145
\pages 20--28
\mathnet{http://mi.mathnet.ru/vtamu310}
\crossref{https://doi.org/10.20310/2686-9667-2024-29-145-20-28}
Linking options:
  • https://www.mathnet.ru/eng/vtamu310
  • https://www.mathnet.ru/eng/vtamu/v29/i145/p20
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Russian Universities Reports. Mathematics
    Statistics & downloads:
    Abstract page:65
    Full-text PDF :23
    References:14
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024