ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

17. Control Theory and Optimization

1991 MS Classification: 49 Shor Naum, V. M. Glushkov Institute of Cybernetics, Kiev, Ukraine: Methods of improving dual bounds with the use of functionally superfluous constraints in polynomial and boolean problems One of the approaches to improve bounds for objective function in multiextremal or combinatorial optimization problems is using of Lagrangian bounds for the problems designed from initial one by adding new (superfluous) constraints which do not change the optimal solution. In many cases such bounds are essentially better than usual Lagrangian bounds, and sometimes become equal to the optimal value of objective function. To compute these bounds one has to solve the dual problems with greater number of variables. Such problems are convex, but nonsmooth as a rule. Report contains the description of algorithms based on subgradient methods with space transformation for obtaining improved bounds in such problems as nonconvex quagratic ones, extremal graph problems and parametric matrix optimization.