A primal-dual interior-point method for semidefinite optimization based on a class of trigonometric barrier functions

被引：19

作者：

Peyghami, M. Reza ^{[1
,2
]}

Fathi-Hafshejani, S. ^{[3
]}

Chen, S. ^{[4
]}

机构：

[1] KN Toosi Univ Tech, Fac Math, POB 16315-1618, Tehran, Iran

[2] KN Toosi Univ Tech, Sci Computat Optimizat & Syst Engn SCOPE, Tehran, Iran

[3] Shiraz Univ Tech, Fac Math, POB 71555-313, Shiraz, Iran

[4] York Univ, Dept Math & Stat, Toronto, ON M3J 2R7, Canada

来源：

OPERATIONS RESEARCH LETTERS | 2016年 / 44卷 / 03期

关键词：

Proximity function; Semidefinite optimization; Interior-point methods; Large-update methods; KERNEL FUNCTION; ALGORITHM; COMPLEXITY;

D O I：

10.1016/j.orl.2016.02.013

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

A primal-dual interior-point method (IPM) based on a new class of proximity functions is proposed for solving Semidefinite Optimization (SDO) problems. The proposed functions are induced from the kernel functions with trigonometric barrier terms. We derive iteration complexity of large-update IPMs for SDO as O(root n log n log n/epsilon). This improves the result obtained in Li and Zhang (2015) for linear optimization and matches to the bound for the so-called self-regular kernel functions. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：319 / 323

页数：5

共 17 条

[1] A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization [J].

Bai, YQ ;

El Ghami, M ;

Roos, C .

SIAM JOURNAL ON OPTIMIZATION, 2004, 15 (01) :101-128

[2] Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term [J].

El Ghami, M. ;

Guennoun, Z. A. ;

Bouali, S. ;

Steihaug, T. .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2012, 236 (15) :3613-3623

[3]

ELGHAMI M, 2013, OPTIM THEORY DECIS M, V31, P331

[4] A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].

KARMARKAR, N .

COMBINATORICA, 1984, 4 (04) :373-395

[5] Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term [J].

Kheirfam, Behrouz .

NUMERICAL ALGORITHMS, 2012, 61 (04) :659-680

[6] Interior-point algorithm for linear optimization based on a new trigonometric kernel function [J].

Li, Xin ;

Zhang, Mingwang .

OPERATIONS RESEARCH LETTERS, 2015, 43 (05) :471-475

[7]

Megiddo N., 1989, PROGR MATH PROGRAMMI, P131, DOI 10.1007/978-1-4613-9617-8_8

[8]

Nesterov Y., 1994, SIAM STUDIES APPL MA, V13

[9]

Peng Jiming., 2002, PRIN SER APPL MATH

[10] Complexity analysis of an interior-point algorithm for linear optimization based on a new proximity function [J].

Peyghami, M. Reza ;

Hafshejani, S. Fathi .

NUMERICAL ALGORITHMS, 2014, 67 (01) :33-48

← 1 2 →