A linearly convergent derivative-free descent method for the second-order cone complementarity problem

Shaohua Pan, Jein-Shan Chen

Research output: Contribution to journalArticle

8 Citations (Scopus)

Abstract

We consider a class of derivative-free descent methods for solving the second-order cone complementarity problem (SOCCP). The algorithm is based on the Fischer-Burmeister (FB) unconstrained minimization reformulation of the SOCCP, and utilizes a convex combination of the negative partial gradients of the FB merit function FB as the search direction. We establish the global convergence results of the algorithm under monotonicity and the uniform Jordan P-property, and show that under strong monotonicity the merit function value sequence generated converges at a linear rate to zero. Particularly, the rate of convergence is dependent on the structure of second-order cones. Numerical comparisons are also made with the limited BFGS method used by Chen and Tseng (An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104(2005), pp. 293-327), which confirm the theoretical results and the effectiveness of the algorithm.

Original languageEnglish
Pages (from-to)1173-1197
Number of pages25
JournalOptimization
Volume59
Issue number8
DOIs
Publication statusPublished - 2010 Oct 29

Fingerprint

Derivative-free Methods
Second-order Cone
Descent Method
Complementarity Problem
Cones
Linearly
Derivatives
Merit Function
Reformulation
Monotonicity
BFGS Method
Unconstrained Minimization
Convex Combination
Numerical Comparisons
Global Convergence
Convergence Results
Rate of Convergence
Gradient
Converge
Partial

Keywords

  • Derivative-free methods
  • Descent algorithms
  • Fischer- burmeister function
  • Linear convergence
  • Second-order cone complementarity problem

ASJC Scopus subject areas

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

Cite this

A linearly convergent derivative-free descent method for the second-order cone complementarity problem. / Pan, Shaohua; Chen, Jein-Shan.

In: Optimization, Vol. 59, No. 8, 29.10.2010, p. 1173-1197.

Research output: Contribution to journalArticle

@article{c6344349108a45f09db07caee18faf3a,
title = "A linearly convergent derivative-free descent method for the second-order cone complementarity problem",
abstract = "We consider a class of derivative-free descent methods for solving the second-order cone complementarity problem (SOCCP). The algorithm is based on the Fischer-Burmeister (FB) unconstrained minimization reformulation of the SOCCP, and utilizes a convex combination of the negative partial gradients of the FB merit function FB as the search direction. We establish the global convergence results of the algorithm under monotonicity and the uniform Jordan P-property, and show that under strong monotonicity the merit function value sequence generated converges at a linear rate to zero. Particularly, the rate of convergence is dependent on the structure of second-order cones. Numerical comparisons are also made with the limited BFGS method used by Chen and Tseng (An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104(2005), pp. 293-327), which confirm the theoretical results and the effectiveness of the algorithm.",
keywords = "Derivative-free methods, Descent algorithms, Fischer- burmeister function, Linear convergence, Second-order cone complementarity problem",
author = "Shaohua Pan and Jein-Shan Chen",
year = "2010",
month = "10",
day = "29",
doi = "10.1080/02331930903085359",
language = "English",
volume = "59",
pages = "1173--1197",
journal = "Optimization",
issn = "0233-1934",
publisher = "Taylor and Francis Ltd.",
number = "8",

}

TY - JOUR

T1 - A linearly convergent derivative-free descent method for the second-order cone complementarity problem

AU - Pan, Shaohua

AU - Chen, Jein-Shan

PY - 2010/10/29

Y1 - 2010/10/29

N2 - We consider a class of derivative-free descent methods for solving the second-order cone complementarity problem (SOCCP). The algorithm is based on the Fischer-Burmeister (FB) unconstrained minimization reformulation of the SOCCP, and utilizes a convex combination of the negative partial gradients of the FB merit function FB as the search direction. We establish the global convergence results of the algorithm under monotonicity and the uniform Jordan P-property, and show that under strong monotonicity the merit function value sequence generated converges at a linear rate to zero. Particularly, the rate of convergence is dependent on the structure of second-order cones. Numerical comparisons are also made with the limited BFGS method used by Chen and Tseng (An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104(2005), pp. 293-327), which confirm the theoretical results and the effectiveness of the algorithm.

AB - We consider a class of derivative-free descent methods for solving the second-order cone complementarity problem (SOCCP). The algorithm is based on the Fischer-Burmeister (FB) unconstrained minimization reformulation of the SOCCP, and utilizes a convex combination of the negative partial gradients of the FB merit function FB as the search direction. We establish the global convergence results of the algorithm under monotonicity and the uniform Jordan P-property, and show that under strong monotonicity the merit function value sequence generated converges at a linear rate to zero. Particularly, the rate of convergence is dependent on the structure of second-order cones. Numerical comparisons are also made with the limited BFGS method used by Chen and Tseng (An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104(2005), pp. 293-327), which confirm the theoretical results and the effectiveness of the algorithm.

KW - Derivative-free methods

KW - Descent algorithms

KW - Fischer- burmeister function

KW - Linear convergence

KW - Second-order cone complementarity problem

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

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

U2 - 10.1080/02331930903085359

DO - 10.1080/02331930903085359

M3 - Article

VL - 59

SP - 1173

EP - 1197

JO - Optimization

JF - Optimization

SN - 0233-1934

IS - 8

ER -