-

 

 

 




Optimization Online





 

On the identification of optimal partition for semidefinite optimization

Ali Mohammad-Nezhad (alm413***at***lehigh.edu)
Tamas Terlaky (terlaky***at***lehigh.edu)

Abstract: The concept of the optimal partition was originally introduced for linear optimization and linear complementarity problems and subsequently extended to semidefinite optimization. For linear optimization and sufficient linear complementarity problems, the optimal partition and a maximally complementary optimal solution can be identified in strongly polynomial time. In this paper, under no assumption on strict complementarity, we consider the identification of the optimal partition of semidefinite optimization for solutions on, or in a neighborhood of the central path. In contrast to linear optimization and linear complementarity problem, the optimal partition for semidefinite optimization cannot be identified exactly from an interior solution. Instead, we identify the sets of eigenvectors converging to an orthonormal bases for the optimal partition using the bounds for the magnitude of the eigenvalues. The magnitude of the eigenvalues of an interior solution is quantified using a condition number and an upper bound for the distance of an interior solution to the optimal set. We provide iteration complexity bound for the identification of the above sets of eigenvectors.

Keywords: Conic programming and interior point methods, Semidefinite optimization, Optimal partition, Maximally complementary optimal solution, Degree of singularity

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Report No. 17T-008, Industrial and Systems Engineering Department, Lehigh University, June 2017.

Download: [PDF]

Entry Submitted: 09/09/2016
Entry Accepted: 09/12/2016
Entry Last Modified: 06/15/2017

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society