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

<p><s>This is my reasoning nuclear norm is convex and algebraic and therefore there has to be a semialgebraic convex representation. Then by Heinz <a href="https://core.ac.uk/download/pdf/81196255.pdf" rel="nofollow noreferrer">https://core.ac.uk/download/pdf/81196255.pdf</a> it should be fixed parameter polynomial time</s>.</p>

<p>The precise problem is as follows:</p>

<ol>
<li><p>We have <span class="math-container">$n$</span> integer variables</p></li>
<li><p>We have <span class="math-container">$r$</span> real variables</p></li>
<li><p>We have <span class="math-container">$m$</span> convex semi algebraic constraints with only integer variables</p></li>
<li><p>We have <span class="math-container">$t$</span> polyhedral constraints with real and integer variables</p></li>
<li><p>We have a linear or semi algebraic convex objective function that depends only on integer variables</p></li>
<li><p>We have a nuclear norm minimization objective function that depends only on real variables</p></li>
</ol>

<p>Is it possible to find a feasible solution in <span class="math-container">$O(n^{poly(n)}poly(rmt))$</span> time or at least in time <span class="math-container">$O((rn)^{poly(rn)}poly(mt))$</span>?</p>

<p>At least without <span class="math-container">$5$</span> (no integer objective but only nuclear norm objective) can we do this in the time mentioned?</p>

CC BY-SA 4.0
2018-11-05T16:20:36.297Z
Why do  you say that the nuclear norm is algebraic?
Sasho Nikolov
CC BY-SA 4.0
2018-11-05T17:49:38.367Z
Singular values are algebraic correct?
Turbo
CC BY-SA 4.0
2018-11-06T03:19:52.693Z
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
CC BY-SA 4.0
2018-11-06T03:41:25.473Z
@SashoNikolov sum of algebraic should be algebraic and hence the hypothesis I made.
Turbo
CC BY-SA 4.0
2018-11-06T05:05:09.850Z
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
CC BY-SA 4.0
2018-11-13T17:38:37.097Z
@SashoNikolov After thinking I think what I said might not work. However it seems that we can copy integer variables to reals and do nuclear norm minimization on real part in mixed linear integer programming. Is it possible to do this in poly time if number of integer variables and hence number of real variables is fixed? The objective is nuclear norm minimization but on real variables.
Turbo
<integer-programming><norms>
Convex mixed linear integer programming with real nuclear norm objective and linear integer objective
Turbo
# Convex mixed linear integer programming with real nuclear norm objective and linear integer objective

(Asked by: username_0 on 2018-10-30)

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?

**Tags:** integer-programming, norms

> **Comments:**
> **username_1**: Why do  you say that the nuclear norm is algebraic?  
> **username_0**: Singular values are algebraic correct?  
> **username_1**: 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?  
> **username_0**: @SashoNikolov sum of algebraic should be algebraic and hence the hypothesis I made.  
> **username_1**: 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?  
> **username_0**: @SashoNikolov After thinking I think what I said might not work. However it seems that we can copy integer variables to reals and do nuclear norm minimization on real part in mixed linear integer programming. Is it possible to do this in poly time if number of integer variables and hence number of real variables is fixed? The objective is nuclear norm minimization but on real variables.  

---

## 0 answers

