• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 6
Sort:
by name
by year
Article
Nesterov Y., Tuncel I. SIAM Journal on Optimization. 2016.

Article 2016

Added: Jul 11, 2016
Article
Shitov Y. SIAM Journal on Optimization. 2018. Vol. 28. No. 3. P. 2067-2072.

Gouveia, Parrilo, and Thomas gave a description of certain rank functions of matrices in geometric terms, generalizing a celebrated result of Yannakakis on the nonnegative rank. We analyze the algorithmic complexity of their description using the results of Renegar on the first-order theory of the reals. This gives a proof that matrices whose positive semidefinite rank is equal to an integer fixed in advance can be detected in polynomial time.

Added: Sep 26, 2018
Article
Shpirko S., Нестеров Ю. SIAM Journal on Optimization. 2014. No. 24. P. 1444-1457.

In this paper we develop a primal-dual subgradient method for solving huge-scale Linear Conic Optimization Problems. Our main assumption is that the primal cone is formed as a direct product of many small-dimensional convex cones, and that the matrix A of corresponding linear operator is uniformly sparse. In this case, our method can approximate the primal-dual optimal solution with accuracy ϵ in O(1/ϵ^2)iterations. At the same time, complexity of each iteration of this scheme does not exceed O(rq log_2 n) operations, where r and q are the maximal numbers of nonzero elements in the rows and columns of matrix A, and n is the number variables.

Added: Mar 24, 2015
Article
Nesterov Y., Shpirko S. SIAM Journal on Optimization. 2014. Vol. 24. No. 3. P. 1444-1457.

Research Article

Added: Jan 28, 2016
Article
Grapiglia G., Nesterov Y. SIAM Journal on Optimization. 2017. Vol. 27. No. 1. P. 478-506.

Research Article

Added: Sep 18, 2017
Article
Shitov Y. SIAM Journal on Optimization. 2017. Vol. 27. No. 3. P. 1898-1909.

Let $A$ be an $m\times n$ matrix with nonnegative real entries. The PSD rank of $A$ is the smallest integer $k$ for which there exist $k\times k$ real PSD matrices $B_1,\ldots,B_m$, $C_1,\ldots,C_n$ satisfying $A(i|j)=\operatorname{tr}(B_iC_j)$ for all $i,j$. This paper determines the computational complexity status of the PSD rank. Namely, we show that the problem of computing this function is polynomial-time equivalent to the existential theory of the reals.

 

Added: Oct 24, 2017