A polynomial-based QCQP solver for encrypted optimization
作者: Sebastian Schlor, Andrea Iannelli, Junsoo Kim, Hyungbo Shim, Frank Allgöwer
分类: math.OC, cs.CR, eess.SY
发布日期: 2025-10-20
备注: Accepted for presentation at the 64th IEEE Conference on Decision and Control (CDC2025)
💡 一句话要点
提出一种基于多项式的QCQP求解器，用于加密优化场景
🎯 匹配领域: 支柱五：交互与反应 (Interaction & Reaction)
关键词: 二次约束二次规划 同态加密 隐私保护优化 多项式优化 梯度下降
📋 核心要点
- 现有约束优化方法在处理私有数据时面临挑战，因为许多优化算法与同态加密不兼容。
- 该论文提出一种基于多项式惩罚函数的序列无约束优化方法，利用梯度下降求解，适用于同态加密。
- 该方法在密码学问题（寻找两个数中的较小值）上进行了验证，并讨论了加密实现的可能性。
📝 摘要（中文）
本文提出了一种仅使用加法和乘法运算来解决一类二次约束二次优化问题的新方法。由于所涉及的运算与同态加密方案的能力兼容，因此该方法能够在私有数据上解决约束优化问题。为了解决约束优化问题，引入了一系列阶数递增的多项式惩罚函数，这些函数在可行集的边界处足够陡峭。将惩罚函数添加到原始成本函数中，创建了一系列无约束优化问题，这些问题的极小值始终位于容许集中，并收敛于约束问题的极小值。使用梯度下降法生成与这些问题相关联的迭代序列。对于该算法，证明了迭代收敛于原始问题的极小值，并且可行集在迭代下是正不变的。最后，该方法在一个说明性的密码学问题上得到了演示，即找到两个数中的较小值，并讨论了加密的可实现性。
🔬 方法详解
问题定义：论文旨在解决二次约束二次规划（Quadratically Constrained Quadratic Programming, QCQP）问题，尤其是在数据需要加密保护的场景下。传统的优化算法可能涉及除法、开方等操作，这些操作与同态加密不兼容，限制了其在隐私保护场景下的应用。因此，需要一种仅使用加法和乘法运算的QCQP求解方法。
核心思路：论文的核心思路是将约束优化问题转化为一系列无约束优化问题，通过引入多项式惩罚函数，使得在可行集边界处产生陡峭的惩罚。随着惩罚函数阶数的增加，无约束优化问题的解逐渐逼近原始约束优化问题的解。这种方法的关键在于，多项式函数仅涉及加法和乘法运算，与同态加密兼容。
技术框架：该方法主要包含以下几个阶段： 1. 问题转化：将原始的二次约束二次规划问题转化为带有惩罚项的无约束优化问题。 2. 惩罚函数设计：设计一系列阶数递增的多项式惩罚函数，这些函数在可行集边界处具有陡峭的梯度。 3. 迭代优化：使用梯度下降法求解一系列无约束优化问题，生成迭代序列。 4. 收敛性分析：证明迭代序列收敛于原始约束优化问题的极小值，并验证可行集的正不变性。
关键创新：该方法最重要的技术创新在于，它提供了一种完全基于多项式运算的QCQP求解方案，避免了与同态加密不兼容的操作。通过巧妙地设计多项式惩罚函数，将约束优化问题转化为一系列易于加密计算的无约束优化问题。
关键设计： 1. 惩罚函数形式：选择合适的多项式形式，保证在可行集外部产生足够大的惩罚，同时保证计算复杂度较低。 2. 惩罚系数调整：随着迭代的进行，逐步增加惩罚函数的阶数和惩罚系数，以保证解的收敛性。 3. 梯度下降步长：选择合适的梯度下降步长，以保证迭代的稳定性和收敛速度。 4. 收敛判据：设计合理的收敛判据，判断迭代何时停止，以获得满足精度要求的解。
🖼️ 关键图片
📊 实验亮点
论文通过一个简单的密码学问题（寻找两个数中的较小值）验证了该方法的可行性。虽然论文没有提供具体的性能数据，但讨论了加密实现的可能性，表明该方法具有实际应用潜力。未来的工作可以进一步研究该方法在大规模问题上的性能表现，并与其他隐私保护优化算法进行比较。
🎯 应用场景
该研究成果可应用于隐私保护机器学习、安全多方计算等领域。例如，在联邦学习中，参与者可以在本地加密数据后，利用该方法进行模型训练，从而保护用户数据的隐私。此外，该方法还可以应用于智能合约、安全控制等对数据隐私有严格要求的场景。
📄 摘要（原文）
In this paper, we present a novel method for solving a class of quadratically constrained quadratic optimization problems using only additions and multiplications. This approach enables solving constrained optimization problems on private data since the operations involved are compatible with the capabilities of homomorphic encryption schemes. To solve the constrained optimization problem, a sequence of polynomial penalty functions of increasing degree is introduced, which are sufficiently steep at the boundary of the feasible set. Adding the penalty function to the original cost function creates a sequence of unconstrained optimization problems whose minimizer always lies in the admissible set and converges to the minimizer of the constrained problem. A gradient descent method is used to generate a sequence of iterates associated with these problems. For the algorithm, it is shown that the iterate converges to a minimizer of the original problem, and the feasible set is positively invariant under the iteration. Finally, the method is demonstrated on an illustrative cryptographic problem, finding the smaller value of two numbers, and the encrypted implementability is discussed.