TY - JOUR
T1 - A continuation approach for the capacitated multi-facility weber problem based on nonlinear SOCP reformulation
AU - Chen, Jein Shan
AU - Pan, Shaohua
AU - Ko, Chun Hsu
N1 - Funding Information:
J.-S. Chen—Member of Mathematics Division, National Center for Theoretical Sciences, Taipei Office. The author’s work is partially supported by National Science Council of Taiwan. S. Pan—The author’s work is supported by the Fundamental Research Funds for the Central Universities (SCUT), Guangdong Natural Science Foundation (No. 9251802902000001) and National Young Natural Science Foundation (No. 10901058).
PY - 2011/8
Y1 - 2011/8
N2 - We propose a primal-dual continuation approach for the capacitated multi-facility Weber problem (CMFWP) based on its nonlinear second-order cone program (SOCP) reformulation. The main idea of the approach is to reformulate the CMFWP as a nonlinear SOCP with a nonconvex objective function, and then introduce a logarithmic barrier term and a quadratic proximal term into the objective to construct a sequence of convexified subproblems. By this, this class of nondifferentiable and nonconvex optimization problems is converted into the solution of a sequence of nonlinear convex SOCPs. In this paper, we employ the semismooth Newton method proposed in Kanzow et al. (SIAM Journal of Optimization 20:297-320, 2009) to solve the KKT system of the resulting convex SOCPs. Preliminary numerical results are reported for eighteen test instances, which indicate that the continuation approach is promising to find a satisfying suboptimal solution, even a global optimal solution for some test problems.
AB - We propose a primal-dual continuation approach for the capacitated multi-facility Weber problem (CMFWP) based on its nonlinear second-order cone program (SOCP) reformulation. The main idea of the approach is to reformulate the CMFWP as a nonlinear SOCP with a nonconvex objective function, and then introduce a logarithmic barrier term and a quadratic proximal term into the objective to construct a sequence of convexified subproblems. By this, this class of nondifferentiable and nonconvex optimization problems is converted into the solution of a sequence of nonlinear convex SOCPs. In this paper, we employ the semismooth Newton method proposed in Kanzow et al. (SIAM Journal of Optimization 20:297-320, 2009) to solve the KKT system of the resulting convex SOCPs. Preliminary numerical results are reported for eighteen test instances, which indicate that the continuation approach is promising to find a satisfying suboptimal solution, even a global optimal solution for some test problems.
KW - Capacitated multi-facility Weber problem
KW - Nonconvex
KW - Nondifferentiable
KW - Second-order cone program
KW - Semismooth Newton method
UR - http://www.scopus.com/inward/record.url?scp=80051591990&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80051591990&partnerID=8YFLogxK
U2 - 10.1007/s10898-010-9632-7
DO - 10.1007/s10898-010-9632-7
M3 - Article
AN - SCOPUS:80051591990
SN - 0925-5001
VL - 50
SP - 713
EP - 728
JO - Journal of Global Optimization
JF - Journal of Global Optimization
IS - 4
ER -