## View abstract

### Session II.2 - Continuous Optimization

Saturday, June 17, 17:00 ~ 17:30

## How do exponential size solutions arise in semidefinite programming?

### Gabor Pataki

#### University of North Carolina at Chapel Hill, USA   -   This email address is being protected from spambots. You need JavaScript enabled to view it. document.getElementById('cloak19e6c6726f41211ced8dd4bcd957a997').innerHTML = ''; var prefix = '&#109;a' + 'i&#108;' + '&#116;o'; var path = 'hr' + 'ef' + '='; var addy19e6c6726f41211ced8dd4bcd957a997 = 'g&#97;b&#111;r' + '&#64;'; addy19e6c6726f41211ced8dd4bcd957a997 = addy19e6c6726f41211ced8dd4bcd957a997 + '&#117;nc' + '&#46;' + '&#101;d&#117;'; var addy_text19e6c6726f41211ced8dd4bcd957a997 = 'g&#97;b&#111;r' + '&#64;' + '&#117;nc' + '&#46;' + '&#101;d&#117;';document.getElementById('cloak19e6c6726f41211ced8dd4bcd957a997').innerHTML += '<a ' + path + '\'' + prefix + ':' + addy19e6c6726f41211ced8dd4bcd957a997 + '\'>'+addy_text19e6c6726f41211ced8dd4bcd957a997+'<\/a>';

A striking pathology of semidefinite programs (SDPs) is illustrated by a classical example of Khachiyan: feasible solutions in SDPs may need exponential space even to write down. Such exponential size solutions are the main obstacle to solve a long standing, fundamental open problem: can we decide feasibility of SDPs in polynomial time?

The consensus seems that SDPs with large size solutions are rare. However, here we prove that they are actually quite common: a linear change of variables transforms every strictly feasible SDP into a Khachiyan type SDP, in which the leading variables are large. As to how large", that depends on the singularity degree of a dual problem. Further, we present some SDPs in which large solutions appear naturally, without any change of variables. We also partially answer the question: how do we represent such large solutions in polynomial space?

Joint work with Alex Touzov (UNC Chapel Hill).