Конструирование гладких выпуклых продолжений булевых функций

Системы булевых уравнений широко используются в математике, компьютерных и прикладных науках. В связи с этим, с одной стороны, для таких систем разрабатываются новые методы и алгоритмы исследования, а с другой — совершенствуются существующие методы и алгоритмы решения таких систем. Один из методов заключается в том, что, во-первых, система булевых уравнений, заданная над кольцом булевых полиномов, трансформируется в систему уравнений над полем действительных чисел, а во-вторых, трансформированная система сводится либо к задаче численной минимизации соответствующей целевой функции, либо к задаче MILP или QUBO, либо к системе полиномиальных уравнений, решаемой на множестве целых чисел, либо к эквивалентной системе полиномиальных уравнений, решаемой символьными методами. Имеется много способов, позволяющих трансформировать систему булевых уравнений в задачу непрерывной минимизации, поскольку принципиальное отличие таких методов от «переборных» алгоритмов локального поиска — на каждой итерации алгоритма сдвиг по антиградиенту производится по всем переменным одновременно. Но одна из основных проблем, возникающая при применении этих способов, состоит в том, что минимизируемая целевая функция в искомой области может иметь множество локальных минимумов, что значительно усложняет их практическое использование. В работе строится неотрицательное выпуклое и непрерывно дифференцируемое продолжение произвольной булевой функции, которое применяется к решению произвольной системы булевых уравнений. Утверждается, что задача решения произвольной системы булевых уравнений может быть конструктивно сведена к задаче минимизации функции, любой локальный минимум которой в искомой области является глобальным минимумом.