An unconstrained smooth minimization reformulation of the second-order cone complementarity problem

Jein-Shan Chen, Paul Tseng

Research output: Contribution to journalArticle

120 Citations (Scopus)

Abstract

A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over ℝ n . A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over ℝ n and, for monotone NCP, each stationary point is a solution of the NCP. This merit function and its analysis were subsequently extended to the semidefinite complementarity problem (SDCP), although only differentiability, not continuous differentiability, was established. In this paper, we extend this merit function and its analysis, including continuous differentiability, to the second-order cone complementarity problem (SOCCP). Although SOCCP is reducible to a SDCP, the reduction does not allow for easy translation of the analysis from SDCP to SOCCP. Instead, our analysis exploits properties of the Jordan product and spectral factorization associated with the second-order cone. We also report preliminary numerical experience with solving DIMACS second-order cone programs using a limited-memory BFGS method to minimize the merit function.

Original languageEnglish
Pages (from-to)293-327
Number of pages35
JournalMathematical Programming
Volume104
Issue number2-3
DOIs
Publication statusPublished - 2005 Nov 1

Fingerprint

Second-order Cone
Complementarity Problem
Merit Function
Reformulation
Cones
Nonlinear Complementarity Problem
Differentiability
Limited Memory Method
BFGS Method
Spectral Factorization
Global Minimization
Stationary point
Factorization
Monotone
Minimise
Norm
Data storage equipment

Keywords

  • Complementarity
  • Error bound
  • Jordan product
  • Level set
  • Merit function
  • Second-order cone
  • Spectral factorization

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

An unconstrained smooth minimization reformulation of the second-order cone complementarity problem. / Chen, Jein-Shan; Tseng, Paul.

In: Mathematical Programming, Vol. 104, No. 2-3, 01.11.2005, p. 293-327.

Research output: Contribution to journalArticle

@article{3d0771bf66f749b0ba68a78ba650107a,
title = "An unconstrained smooth minimization reformulation of the second-order cone complementarity problem",
abstract = "A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over ℝ n . A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over ℝ n and, for monotone NCP, each stationary point is a solution of the NCP. This merit function and its analysis were subsequently extended to the semidefinite complementarity problem (SDCP), although only differentiability, not continuous differentiability, was established. In this paper, we extend this merit function and its analysis, including continuous differentiability, to the second-order cone complementarity problem (SOCCP). Although SOCCP is reducible to a SDCP, the reduction does not allow for easy translation of the analysis from SDCP to SOCCP. Instead, our analysis exploits properties of the Jordan product and spectral factorization associated with the second-order cone. We also report preliminary numerical experience with solving DIMACS second-order cone programs using a limited-memory BFGS method to minimize the merit function.",
keywords = "Complementarity, Error bound, Jordan product, Level set, Merit function, Second-order cone, Spectral factorization",
author = "Jein-Shan Chen and Paul Tseng",
year = "2005",
month = "11",
day = "1",
doi = "10.1007/s10107-005-0617-0",
language = "English",
volume = "104",
pages = "293--327",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "2-3",

}

TY - JOUR

T1 - An unconstrained smooth minimization reformulation of the second-order cone complementarity problem

AU - Chen, Jein-Shan

AU - Tseng, Paul

PY - 2005/11/1

Y1 - 2005/11/1

N2 - A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over ℝ n . A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over ℝ n and, for monotone NCP, each stationary point is a solution of the NCP. This merit function and its analysis were subsequently extended to the semidefinite complementarity problem (SDCP), although only differentiability, not continuous differentiability, was established. In this paper, we extend this merit function and its analysis, including continuous differentiability, to the second-order cone complementarity problem (SOCCP). Although SOCCP is reducible to a SDCP, the reduction does not allow for easy translation of the analysis from SDCP to SOCCP. Instead, our analysis exploits properties of the Jordan product and spectral factorization associated with the second-order cone. We also report preliminary numerical experience with solving DIMACS second-order cone programs using a limited-memory BFGS method to minimize the merit function.

AB - A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over ℝ n . A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over ℝ n and, for monotone NCP, each stationary point is a solution of the NCP. This merit function and its analysis were subsequently extended to the semidefinite complementarity problem (SDCP), although only differentiability, not continuous differentiability, was established. In this paper, we extend this merit function and its analysis, including continuous differentiability, to the second-order cone complementarity problem (SOCCP). Although SOCCP is reducible to a SDCP, the reduction does not allow for easy translation of the analysis from SDCP to SOCCP. Instead, our analysis exploits properties of the Jordan product and spectral factorization associated with the second-order cone. We also report preliminary numerical experience with solving DIMACS second-order cone programs using a limited-memory BFGS method to minimize the merit function.

KW - Complementarity

KW - Error bound

KW - Jordan product

KW - Level set

KW - Merit function

KW - Second-order cone

KW - Spectral factorization

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

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

U2 - 10.1007/s10107-005-0617-0

DO - 10.1007/s10107-005-0617-0

M3 - Article

VL - 104

SP - 293

EP - 327

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2-3

ER -