Role of redundant constraints for improving dual bounds in polynomial optimization problems (Q1288665)

The author considers some extremum quadratic and Boolean combinatorial problem of infimum and their dual Lagrangian problems of supremum. The used techniques introduce functionally redundant constraints that reduce the duality gap. (1) The problem of finding the maximum weighted set of graph nodes is a linear programming problem that is reducible to the minimization of a nonsmooth convex function by the method of nonsmooth penalty functions in the form of a maximum function. (2) The maximum cut problem is written as a quadratic nonlinear programming problem and for its solution the Lagrange multiplier method is used. This problem is also written as a linear programming problem, but with a number of constraints, excessively large. This inconvenience is raised by the utilization of a special shortest path problem for an auxiliary graph. (3) Bounds for the global minimum of polynomial functions. The polynomial are represented as quadratic functions, using some linear transformations. For minimization the Lagrange multiplier method is used.