New Results on Narrowing the Duality Gap of the Extended Celis--Dennis--Tapia Problem
研究了扩展CDT问题的正对偶间隙，证明添加适当的二阶锥约束可缩小甚至消除该间隙，并给出充分条件，数值实验验证了方法的有效性。
In this paper, we consider the extended Celis--Dennis--Tapia (CDT) problem that has a positive duality gap. It is presented in theory that this positive duality gap can be narrowed by adding an appropriate second-order-cone (SOC) constraint, which may lead to dividing the problem into two separate subproblems. More concretely, for any extended CDT problem with a positive duality gap, we prove that one SOC constraint is valid to narrow the positive duality gap if and only if the corresponding hyperplane intersects the “open optimal line segment." Especially when the second constraint function consists of the product of two linear functions, we prove that the positive duality gap can be eliminated thoroughly by solving two subproblems with SOC constraints. For any classical CDT problem with a positive duality gap, a new model with two SOC constraints is proposed, and a sufficient condition is presented under which this positive duality gap can be eliminated thoroughly. In particular, based on the sufficient condition, it is proved that the positive duality gaps of any two-dimensional classical CDT problem and a class of three-dimensional classical CDT problems can be eliminated thoroughly. Numerical results of some gap-existing examples coming from other papers show that their positive duality gaps are indeed eliminated by our SOC reformulation technique.