Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1137/16M1080082 | SIAM JOURNAL ON OPTIMIZATION |
Keywords | Field | DocType |
quadratically constrained quadratic programming,CDT problem,second-order cone,global solutions,SDP relaxation | Discrete mathematics,Duality gap,Perturbation function,Mathematical optimization,Weak duality,Duality (optimization),Strong duality,Wolfe duality,Hyperplane,Linear function,Mathematics | Journal |
Volume | Issue | ISSN |
27 | 2 | 1052-6234 |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
jianhua yuan | 1 | 6 | 1.43 |
meiling wang | 2 | 8 | 4.54 |
wenbao ai | 3 | 6 | 1.09 |
tianping shuai | 4 | 6 | 1.09 |