• 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

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.

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.

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

Research Article

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

Research Article

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.