A continuation approach for the capacitated multi-facility weber problem based on nonlinear SOCP reformulation

Jein-Shan Chen, Shaohua Pan, Chun Hsu Ko

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)713-728
Number of pages16
JournalJournal of Global Optimization
Volume50
Issue number4
DOIs
Publication statusPublished - 2011 Aug 1

Fingerprint

Weber Problem
Second-order Cone
Reformulation
Continuation
Cones
Newton-Raphson method
KKT System
Nondifferentiable Optimization
Semismooth Newton Method
Nonconvex Optimization
Nonconvex Problems
Primal-dual
Term
Test Problems
Logarithmic
Objective function
Optimal Solution
Optimization Problem
Numerical Results
Optimization

Keywords

  • Capacitated multi-facility Weber problem
  • Nonconvex
  • Nondifferentiable
  • Second-order cone program
  • Semismooth Newton method

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Cite this

A continuation approach for the capacitated multi-facility weber problem based on nonlinear SOCP reformulation. / Chen, Jein-Shan; Pan, Shaohua; Ko, Chun Hsu.

In: Journal of Global Optimization, Vol. 50, No. 4, 01.08.2011, p. 713-728.

Research output: Contribution to journalArticle

@article{4da2d23e3ade4f788653b720b01b7b59,
title = "A continuation approach for the capacitated multi-facility weber problem based on nonlinear SOCP reformulation",
abstract = "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.",
keywords = "Capacitated multi-facility Weber problem, Nonconvex, Nondifferentiable, Second-order cone program, Semismooth Newton method",
author = "Jein-Shan Chen and Shaohua Pan and Ko, {Chun Hsu}",
year = "2011",
month = "8",
day = "1",
doi = "10.1007/s10898-010-9632-7",
language = "English",
volume = "50",
pages = "713--728",
journal = "Journal of Global Optimization",
issn = "0925-5001",
publisher = "Springer Netherlands",
number = "4",

}

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

PY - 2011/8/1

Y1 - 2011/8/1

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

VL - 50

SP - 713

EP - 728

JO - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 4

ER -