Two unconstrained optimization approaches for the Euclidean κ-centrum location problem

Shaohua Pan, Jein-Shan Chen

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Consider the single-facility Euclidean κ-centrum location problem in Rn. This problem is a generalization of the classical Euclidean 1-median problem and 1-center problem. In this paper, we develop two efficient algorithms that are particularly suitable for problems where n is large by using unconstrained optimization techniques. The first algorithm is based on the neural networks smooth approximation for the plus function and reduces the problem to an unconstrained smooth convex minimization problem. The second algorithm is based on the Fischer-Burmeister merit function for the second-order cone complementarity problem and transforms the KKT system of the second-order cone programming reformulation for the problem into an unconstrained smooth minimization problem. Our computational experiments indicate that both methods are extremely efficient for large problems and the first algorithm is able to solve problems of dimension n up to 10,000 efficiently.

Original languageEnglish
Pages (from-to)1368-1383
Number of pages16
JournalApplied Mathematics and Computation
Volume189
Issue number2
DOIs
Publication statusPublished - 2007 Jun 15

Fingerprint

Location Problem
Unconstrained Optimization
Euclidean
Cones
Minimization Problem
KKT System
Second-order Cone Programming
Smooth Approximation
Second-order Cone
Convex Minimization
Center Problem
Merit Function
Complementarity Problem
Neural networks
Reformulation
Computational Experiments
Optimization Techniques
Efficient Algorithms
Neural Networks
Transform

Keywords

  • Merit function
  • Second-order cone programming
  • Smoothing function
  • The Euclidean κ-centrum problem

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Cite this

Two unconstrained optimization approaches for the Euclidean κ-centrum location problem. / Pan, Shaohua; Chen, Jein-Shan.

In: Applied Mathematics and Computation, Vol. 189, No. 2, 15.06.2007, p. 1368-1383.

Research output: Contribution to journalArticle

@article{608f6112ad7f4f2abaf500c2ff691d59,
title = "Two unconstrained optimization approaches for the Euclidean κ-centrum location problem",
abstract = "Consider the single-facility Euclidean κ-centrum location problem in Rn. This problem is a generalization of the classical Euclidean 1-median problem and 1-center problem. In this paper, we develop two efficient algorithms that are particularly suitable for problems where n is large by using unconstrained optimization techniques. The first algorithm is based on the neural networks smooth approximation for the plus function and reduces the problem to an unconstrained smooth convex minimization problem. The second algorithm is based on the Fischer-Burmeister merit function for the second-order cone complementarity problem and transforms the KKT system of the second-order cone programming reformulation for the problem into an unconstrained smooth minimization problem. Our computational experiments indicate that both methods are extremely efficient for large problems and the first algorithm is able to solve problems of dimension n up to 10,000 efficiently.",
keywords = "Merit function, Second-order cone programming, Smoothing function, The Euclidean κ-centrum problem",
author = "Shaohua Pan and Jein-Shan Chen",
year = "2007",
month = "6",
day = "15",
doi = "10.1016/j.amc.2006.12.014",
language = "English",
volume = "189",
pages = "1368--1383",
journal = "Applied Mathematics and Computation",
issn = "0096-3003",
publisher = "Elsevier Inc.",
number = "2",

}

TY - JOUR

T1 - Two unconstrained optimization approaches for the Euclidean κ-centrum location problem

AU - Pan, Shaohua

AU - Chen, Jein-Shan

PY - 2007/6/15

Y1 - 2007/6/15

N2 - Consider the single-facility Euclidean κ-centrum location problem in Rn. This problem is a generalization of the classical Euclidean 1-median problem and 1-center problem. In this paper, we develop two efficient algorithms that are particularly suitable for problems where n is large by using unconstrained optimization techniques. The first algorithm is based on the neural networks smooth approximation for the plus function and reduces the problem to an unconstrained smooth convex minimization problem. The second algorithm is based on the Fischer-Burmeister merit function for the second-order cone complementarity problem and transforms the KKT system of the second-order cone programming reformulation for the problem into an unconstrained smooth minimization problem. Our computational experiments indicate that both methods are extremely efficient for large problems and the first algorithm is able to solve problems of dimension n up to 10,000 efficiently.

AB - Consider the single-facility Euclidean κ-centrum location problem in Rn. This problem is a generalization of the classical Euclidean 1-median problem and 1-center problem. In this paper, we develop two efficient algorithms that are particularly suitable for problems where n is large by using unconstrained optimization techniques. The first algorithm is based on the neural networks smooth approximation for the plus function and reduces the problem to an unconstrained smooth convex minimization problem. The second algorithm is based on the Fischer-Burmeister merit function for the second-order cone complementarity problem and transforms the KKT system of the second-order cone programming reformulation for the problem into an unconstrained smooth minimization problem. Our computational experiments indicate that both methods are extremely efficient for large problems and the first algorithm is able to solve problems of dimension n up to 10,000 efficiently.

KW - Merit function

KW - Second-order cone programming

KW - Smoothing function

KW - The Euclidean κ-centrum problem

UR - http://www.scopus.com/inward/record.url?scp=34249018988&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34249018988&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2006.12.014

DO - 10.1016/j.amc.2006.12.014

M3 - Article

VL - 189

SP - 1368

EP - 1383

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

SN - 0096-3003

IS - 2

ER -