A Semismooth Newton-Type Method for the Nearest Doubly Stochastic Matrix Problem br

被引：0

作者：

Hu, Hao ^{[1
,2
]}

Li, Xinxin ^{[3
]}

Im, Haesol ^{[2
]}

Wolkowicz, Henry ^{[2
]}

机构：

[1] Clemson Univ, Sch Math & Stat Sci, Clemson, SC 29634 USA

[2] Univ Waterloo, Dept Combinator & Optimizat, Fac Math, Waterloo, ON N2L 3G1, Canada

[3] Jilin Univ, Sch Math, Changchun 130012, Peoples R China

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 2024年 / 49卷 / 02期

基金：

中国国家自然科学基金; 加拿大自然科学与工程研究理事会;

关键词：

nearest doubly stochastic matrix; semismooth Newton method; strongly semismooth; quadratic convergence; equivalence class;

D O I：

10.1287/moor.2023.1382

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study a semismooth Newton-type method for the nearest doubly stochastic matrix problem where the nonsingularity of the Jacobian can fail. The optimality conditions for this problem are formulated as a system of strongly semismooth functions. We show that the nonsingularity of the Jacobian does not hold for this system. By exploiting the problem structure, we construct a modified two step semismooth Newton method that guarantees a nonsingular Jacobian matrix at each iteration, and that converges to the nearest doubly stochastic matrix quadratically.

引用

页码：729 / 751

页数：23

共 58 条

[1] Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming [J].

Al-Homidan, S ;

Wolkowicz, H .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 406 :109-141

[2] Computing the nearest doubly stochastic matrix with a prescribed entry [J].

Bai, Zheng-Jian ;

Chu, Delin ;

Tan, Roger C. E. .

SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2007, 29 (02) :635-655

[3] A semi-smooth Newton method for a special piecewise linear system with application to positively constrained convex quadratic programming [J].

Barrios, J. G. ;

Bello Cruz, J. Y. ;

Ferreira, O. P. ;

Nemeth, S. Z. .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2016, 301 :91-100

[4]

BERTSIMAS D, 1997, INTRO LINEAR OPTIMIZ

[5]

Best M. J., 2017, ADV APPL MATH

[6] AN ALGORITHM FOR SOLVING QUADRATIC NETWORK FLOW PROBLEMS [J].

BOLAND, N ;

GOH, CJ ;

MEES, AI .

APPLIED MATHEMATICS LETTERS, 1991, 4 (04) :61-64

[7] A SIMPLE CONSTRAINT QUALIFICATION IN INFINITE DIMENSIONAL PROGRAMMING [J].

BORWEIN, JM ;

WOLKOWICZ, H .

MATHEMATICAL PROGRAMMING, 1986, 35 (01) :83-96

[8] PARTIALLY FINITE CONVEX-PROGRAMMING .1. QUASI RELATIVE INTERIORS AND DUALITY-THEORY [J].

BORWEIN, JM ;

LEWIS, AS .

MATHEMATICAL PROGRAMMING, 1992, 57 (01) :15-48

[9]

Brualdi R.A., 1991, ENCY MATH ITS APPL, V39

[10] SOME APPLICATIONS OF DOUBLY STOCHASTIC MATRICES [J].

BRUALDI, RA .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1988, 107 :77-100

← 1 2 3 4 5 6 →