# Convex mixed linear integer programming with real nuclear norm objective and linear integer objective

Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $$O(ld^{ O(k^4)})$$ algorithm to minimize a degree $$d$$ form with integer coefficients of binary length at most $$l$$ over integer points in a convex set in $$\Bbb R^k$$. Is similar parametrization possible with nuclear norm?

This is my reasoning nuclear norm is convex and algebraic and therefore there has to be a semialgebraic convex representation. Then by Heinz https://core.ac.uk/download/pdf/81196255.pdf it should be fixed parameter polynomial time.

The precise problem is as follows:

1. We have $$n$$ integer variables

2. We have $$r$$ real variables

3. We have $$m$$ convex semi algebraic constraints with only integer variables

4. We have $$t$$ polyhedral constraints with real and integer variables

5. We have a linear or semi algebraic convex objective function that depends only on integer variables

6. We have a nuclear norm minimization objective function that depends only on real variables

Is it possible to find a feasible solution in $$O(n^{poly(n)}poly(rmt))$$ time or at least in time $$O((rn)^{poly(rn)}poly(mt))$$?

At least without $$5$$ (no integer objective but only nuclear norm objective) can we do this in the time mentioned?

• Why do you say that the nuclear norm is algebraic? – Sasho Nikolov Nov 5 '18 at 16:20
• Singular values are algebraic correct? – Turbo Nov 5 '18 at 17:49
• The eigenvalues of a matrix are because they are the roots of the characteristic polynomial. But singular values are defined as square roots of eigenvalues so I don't know how to show they are algebraic. Also isn't that different from showing that the unit ball of the nuclear norm is semi-algebraic? Isn't the latter what you need? – Sasho Nikolov Nov 6 '18 at 3:19
• @SashoNikolov sum of algebraic should be algebraic and hence the hypothesis I made. – Turbo Nov 6 '18 at 3:41
• I don't follow, can you be more precise? I can see that you can write the set $\{\pm \sigma_1(A), \ldots, \pm\sigma_n(A)\}$ as the roots of $\det(AA^\top - t^2 I)$. How do you get that the unit ball of the nuclear norm is semi-algebraic? Or that the unit sphere $\{A: \sigma_1(A) + \ldots + \sigma_n(A) = 1\}$ is algebraic? Also "sum of algebraic should be algebraic" makes no sense to me. Can you state more precisely what proposition you are making here? – Sasho Nikolov Nov 6 '18 at 5:05