分词(Tokenisation)是当前自然语言处理(NLP)流程中不可或缺的一环。目前主流的分词算法(如字节对编码BPE和Unigram)均属于贪心算法——它们仅在局部范围内做出最优决策,而未将最终生成的整个词表作为一个整体加以通盘考量。我们转而将分词器的构建建模为一个线性规划问题,并借助凸优化工具求解,由此提出一种新算法,命名为ConvexTok。实验表明,ConvexTok在各项内在分词评价指标上均能实现稳定提升,并可降低语言模型所达到的每字节比特数(bits-per-byte, BpB);它对下游任务性能亦有改善作用,但提升效果不如前者稳定。此外,ConvexTok允许用户针对特定优化目标,通过一个理论下界来量化评估其分词器距离全局最优解的差距;我们在实验中发现,在常用词表规模下,该算法所得结果与理论最优值的差距通常不超过1%。