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?

  • $\begingroup$ Why do you say that the nuclear norm is algebraic? $\endgroup$ Nov 5, 2018 at 16:20
  • $\begingroup$ Singular values are algebraic correct? $\endgroup$
    – Turbo
    Nov 5, 2018 at 17:49
  • $\begingroup$ 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? $\endgroup$ Nov 6, 2018 at 3:19
  • $\begingroup$ @SashoNikolov sum of algebraic should be algebraic and hence the hypothesis I made. $\endgroup$
    – Turbo
    Nov 6, 2018 at 3:41
  • $\begingroup$ 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? $\endgroup$ Nov 6, 2018 at 5:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.