撰稿人(alphabetical order) :
- Huang，KuoLing
- Li，Qiuwei
1 引言
优化问题在现实生活中的应用无所不在，如：线性回归 (Linear regression)、最新二乘问题 (Least squares problem)、最大割度问题 (Max-Cut problem)、深度学习 (Deep learning) 中的神经网络训练问题等。Optimization优化模型也由简单到复杂，经历着线性Optimization规划 (Linear programming，LP)、二次规划 (Quadratic programming，QP)、锥规划如半定规划 (Semidefinite programming，SDP)，以及到非凸优化 (Nonconvex optimization，NVX) 的演变；从其定义出发，它们之间又是逐层包含的关系，如下图。
非凸优化当前虽日渐盛行，但其全局优化理论尚不完备，通常求解非凸问题的全局最优解的算法复杂度是指数级的 (NP难)。虽然学术界最近几年在一些特殊的非凸问题上取得了一些全局优化理论的突破 [Chi2019]，但这些理论很难推广到一般问题。
另一方面，半定规划虽然作为一类特殊的凸优化问题，但是凭借着极强的建模能力、完备的最优收敛性理论保障，以及拥有日益完善的优化算法和求解器，在学术界备受青睐，尤其体现在以下三个方面：
- 半定规划作为非常多凸优化问题的一站式求解法，是著名凸优化工具CVX背后的无名英雄。CVX工具箱本身并不解决任何优化问题，它将问题重新表述为锥规划如半定规划，再调用求解器，这个过程中要用到disciplined convex programming (DCP) 进行模型转化，因半定规划出色的建模能力，在整个过程中扮演着重要的角色。
- 半定规划可以逼近很多不同类型的组合优化 [Alizadeh1995]、多项式优化问题 [Waki2006]，尤其还带有逼近效果的理论保证 [Anjos2011]。
- 许多矩阵类问题，特别是数据科学和机器学习相关的问题最终都会建模为半定规划问题，比如矩阵补全(在协同滤波中有很多应用比如著名的 Netflix Prize) [Candès2012]、子空间搜索 [Vaswani2018] 等。
接下来我们主要从数学模型、经典应用、及求解方法来介绍半定规划。
2 从线性规划到半定规划
为便于不同领域的读者了解和学习，我们将从最基础的线性规划讲起，慢慢推广到半定规划。对于线性规划，相信读者并不陌生；它是一个在线性等式和不等式约束下的最小化 (有时或最大化) 线性目标函数的优化问题。其数学标准形式为：
其中
是优化变量，
是目标函数向量，
是线性等式约束矩阵，
是线性等式约束的常数项。最后，不等式
表示
。即，
处于坐标的非负象限。简单地说，我们要从所有非负向量与线性等式解的交集中找到具有最小值
的最优解
。
半定规划是线性规划的推广；两种具有非常相似的数学标准形式：
其中，
为优化变量；这里
表示所有的
对称矩阵的集合。是线性等式约束的常数项，
是线性等式约束中的算子，其定义为：
这里
是给定的系数矩。因此线性等式约束
即为
。最后，不等式
表示
是半正定 (Positive semidefinite，PSD) 对称矩阵，即
；这里
表示所有半正定对称矩阵的集合。具体来说给定
若满足下面任意条件则
1) 所有的特征值皆为非负; 2) 所有的二次式皆为非负:
3)
。 同理，半定规划是从与线性等式解的交集中找到具有最小值
的最优解
。
3 半定规划的应用场景与求解
半定规划作为作为重要的优化建模工具被广泛应用于机器学习、信号处理、计算机视觉、以及量子计算等领域。我们接下来介绍两个经典应用：
- 最大割度问题
- 二次无约束二元优化 (Quadatic unconstrained binary optimization，QUBO)
3.1 最大割度问题
最大割度问题是经典的NP-难的组合优化问题，而Goemans和Williamson在1995年巧妙地提出求解最大割度的半定规划松弛化 (SDP relaxation) 近似算法 [Goemans1995]，就此拉开了半定规划在各领域进行广泛运用的帷幕。
问题描述. 给定无向图
其节点集为
以及边集为
。对于给定的某条边
其权重为
。那么最大割度问题就是找到节点子集
使得从它到它的补集
之间的所有连边的权重和最大化。令
，那么最大割度问题的数学形式给定如下：
令
为全1矩阵，则最大割度问题的数学形式可简化成
求解思路. 虽然上述优化问题是非凸的 (Nonconvex) (其非凸性来自于二元化约束和矩阵秩约束)，但我们可以将这些非凸约束凸松弛化 (Convex Relaxation) 后得到如下半定规划：
其中
为全1向量. 这类技巧被称为半定规划松弛化 (SDP relaxation)，被广泛用于各个工程领域。虽然这是一种近似算法，但在最大割度问题上，这种近似算法具有0.87856精度保障 [Goemans1995]；即
这里
分别代表原问题和半定规划松弛化后的最优值 (附注: 这里为了方便叙述，我们省略了原文中的随机取整的细节)。因此通过半定规划求解这类NP-难的组合优化可以获得88%的精度保障，这是组合优化领域革命性的结果。
3.2 二次无约束二元优化
QUBO 已被广泛用于建模和解决各种优化问题，包括网络流问题 [Neukart2017]、调度问题 [Ikeda2019]、量子优化问题 [Bian2014] 等。
问题描述. QUBO的数学形式一般为：
这里
为给定的模型参数。量子计算领域的一个非常重要的成果是量子线性系统算法 (Quantum linear system algorithm，QLSA) [Harrow2009]，该算法为量子支持向量机 (Quantum support vector machine，QSVM) 提供重要理论基础。其算法核心是考虑求解线性系统
的二元近似解问题。该问题可以自然地写成一个QUBO：
求解思路. 根据
，可将QUBO的一次项表示为
。 故上述QUBO可等价为
上述优化问题的非凸性来自于
，将其凸松弛化为
。根据舒尔引理 (Schur’s Lemma)， 其又可等价为一个线性矩阵不等式 (Linear matrix inequality，LMI)
。因此，最终我们可得到如下的半定规划：
附注: 上述形式可转换为半定规划的标准形式。
除了以上两个经典应用，我们也罗列一些其他的经典应用，感兴趣的读者可通过提供的文献了解更多细节。
- 稀疏主成分分析 (Sparse PCA) [d'Aspremont2004]
- 特征筛选 (Feature selections) [Naghibi2014]
- 量子网络拓扑 (Quantum network topologies) [Åberg2020]
- 最优能流问题 (Optimal power flow problems) [Andersen2013]
- 协同定位映射 (Simultaneous localization and mapping，SLAM) [Carlone2016]
3.3 半定规划求解方法
实际中遇到的半定规划问题往往比较复杂，我们需要借助半定规划的优化算法或相应的求解器来找最优解。另一方面，虽然我们看到SDP是LP的拓展且两者具有相似的数学形式，但是由Dantzig开创的单纯形法 [Dantzig1963] 不能够从LP拓广到求解SDP，这是因为半定规划不同于LP，其约束集合不是多面体。因此求解SDP的算法主要以内点法 [Helmberg1996] 为主。除此之外，学界最近将交替方向乘子法 (Alternating direction method of multipliers, ADMM) [Wen2010] 也成功用于求解SDP，并取得显著成果。使得类似ADMM的一阶优化算法在SDP领域日渐盛行。
相比于一阶优化算法，作为二阶优化算法的内点法虽然具有高精度求解的优势，但因其密切依赖于矩阵分解或矩阵求逆，当遇到稍大一点规模问题的时候，矩阵分解容易耗完内存，这一点在矩阵非稀疏的情况下尤为突出；另外矩阵分解容易为算法的并行花和分布式计算带来更多挑战。因此，我们在实际中面对不同的SDP问题需要选择不同的求解算法，选择最适合的求解算法往往会事半功倍。一个优秀的半定规划求解器需具备面对不同SDP问题选择最适合优化算法的能力。
4. MindOpt优化求解器
MindOpt是阿里巴巴达摩院决策智能实验室研发的高性能求解器套件，目前能用于快速稳定地求解大规模优化问题。MindOpt目前能求解线性规划、网路流问题、二次规划、和混合整数规划问题。最新版的MindOpt (V0.23)也提供了半定规划问题的求解。
MindOpt已经被广泛应用于云计算、零售、金融、制造、交通、能源等领域。每年在弹性计算资源调度优化场景里为阿里云节省数亿成本。
MindOpt目前既支持命令行直接调用，也支持 C、C++、Python、JAVA 四种语言的API调用，提供超过500个API接口。丰富的 API 设计便于用户灵活地应用求解器来建立优化模型，以及对模型进行增、删、改、查等，并对解做各种分析。
以下我们将以Python语言做示例。我们首先给予一SDP的问题描述，接着我们会示范如何用建立模型并求解SDP模型，并对其做逐步解说。
4.1 MindOpt求解半定规划
下面给出Python的示例，C/C++的开发者可看用户文档中代码示例：https://solver.damo.alibaba-inc.com/doc/html/model/sdp/sdp%20problem.html
4.1.1 SDP示例1
其中， 
。
Python代码示例.
frommindoptpyimport*if__name__=="__main__": MDO_INFINITY=MdoModel.get_infinity() # Step 1. Create a model and change the parameters.model=MdoModel() try: # Step 2. Input model.# Change to maximization problem.model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 0) # Add matrix variable. model.add_sym_mat(3, "X") # Input objective coefficients. model.replace_sym_mat_objs(0, [ 0, 0, 1, 2 ], [ 0, 2, 1, 2], [ -3.0, 1.0, -2.0, -3.0]) # Input first constraint. model.add_cons(1.0, 1.0, name="c0") model.replace_sym_mat_elements(0, 0, [ 0, 2, 1, 2 ], [ 0, 0, 1, 2 ], [ 3.0, 1.0, 4.0, 5.0 ]) # Step 3. Solve the problem and populate the result.model.solve_prob() model.display_results() status_code, status_msg=model.get_status() ifstatus_msg=="OPTIMAL": print("Optimizer terminated with an OPTIMAL status (code {0}).".format(status_code)) print(" - Primal objective : {:8.6f}".format(model.get_real_attr(MDO_REAL_ATTR.PRIMAL_OBJ_VAL))) soln=model.get_real_attr_sym_mat(MDO_REAL_ATTR.SYM_MAT_PRIMAL_SOLN, 0, [i*3+jforiinrange(3) forjinrange(3)], [j*3+iforiinrange(3) forjinrange(3)]) print("X = ") foriinrange(3): print(" (", end="") forjinrange(3): print(" {0:8.6f}".format(soln[i*3+j]), end=""), print(" )") else: print("Optimizer terminated with a(n) {0} status (code {1}).".format(status_msg, status_code)) exceptMdoErrorase: print("Received Mindopt exception.") print(" - Code : {}".format(e.code)) print(" - Reason : {}".format(e.message)) exceptExceptionase: print("Received exception.") print(" - Reason : {}".format(e)) finally: # Step 4. Free the model.model.free_mdl()
代码详细解释如下：
第一步：创建MindOpt模型
首先，我们必须先建立一空的MindOpt模型。
# Step 1. Create a model and change the parameters.model=MdoModel()
第二步：SDP模型输入
接着，我们将目标函数改为maximization，并新增
对称矩阵变量。
# Step 2. Input model.# Change to maximization problem.model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 0) # Add matrix variable. model.add_sym_mat(3, "X")
我们利用Python API replace_sym_mat_objs() 来输入目标函数中的
的非零元素。其中，第一个参数为矩阵的索引值(此处为0)，第二和第三个参数分别代表矩阵中非零元素其对应的行和列之索引，而最后一个参数则为非零元的数值。
# Input objective coefficients. model.replace_sym_mat_objs(0, [ 0, 0, 1, 2 ], [ 0, 2, 1, 2], [ -3.0, 1.0, -2.0, -3.0])
接着，我们输入第一个约束。我们首先输一空約束；接着再利用replace_sym_mat_elements()输入约束中的
的非零元素。其中，第一和第二个参数分别为：约束的索引值(此处为0)以及矩阵的索引值(此处为0)，第三第和第四个参数矩阵中非零元素其对应的行和列之索引，而最后一个参数则为非零元的数值。
# Input first constraint. model.add_cons(1.0, 1.0, name="c0") model.replace_sym_mat_elements(0, 0, [ 0, 2, 1, 2 ], [ 0, 0, 1, 2 ], [ 3.0, 1.0, 4.0, 5.0 ])
第三步：求解SDP模型
模型输入后，我们接着用solve_prob()来求解问题，并用display_results()呈现求解结果。
# Step 3. Solve the problem and populate the result.model.solve_prob() model.display_results()
第四步: 取得SDP模型的解
我们利用泛用函数model.get_real_attr(MDO_REAL_ATTR.PRIMAL_OBJ_VAL)来取得最优的的目标函数值。
print(" - Primal objective : {:8.6f}".format(model.get_real_attr(MDO_REAL_ATTR.PRIMAL_OBJ_VAL)))
最后，我们利用get_real_attr_sym_mat()来取得的变量值。其中，第一个参数定义属性值 (附注: get_real_attr_sym_mat为泛用函数，因此必须配合属性值来定义函数的使用目的；MDO_REAL_ATTR.SYM_MAT_PRIMAL_SOLN定义目的为获取(对称矩阵)变量的数值)，第二个参数为：矩阵的索引值 (此处为0)，第三第和第四个参数为矩阵中需要回传的元素其对应的行和列之索引。返回值soln则为矩阵中对应的元素数值。
soln=model.get_real_attr_sym_mat(MDO_REAL_ATTR.SYM_MAT_PRIMAL_SOLN, 0, [i*3+jforiinrange(3) forjinrange(3)], [j*3+iforiinrange(3) forjinrange(3)])
4.1.2 SDP示例2
其中， 
。
Python代码示例.
frommindoptpyimport*if__name__=="__main__": MDO_INFINITY=MdoModel.get_infinity() # Step 1. Create a model and change the parameters.model=MdoModel() try: # Step 2. Input model.# Change to maximization problem.model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 0) # Add variables.x= [] x.append(model.add_var(0.0, MDO_INFINITY, 0.0, None, "x0", False)) x.append(model.add_var(0.0, MDO_INFINITY, 0.0, None, "x1", False)) # Add matrix variables. model.add_sym_mats([ 2, 3 ], [ "X0", "X1" ]); # Input objective coefficients. model.replace_sym_mat_objs(0, [ 0, 1, 1 ], [ 0, 0, 1 ], [ 2.0, 1.0, 2.0 ]); model.replace_sym_mat_objs(1, [ 0, 0, 1, 2 ], [ 0, 2, 1, 2], [ 3.0, 1.0, 2.0, 3.0]); # Input first constraint. model.add_cons(1.0*x[0] ==1.0, "c0"); model.replace_sym_mat_elements(0, 0, [ 0, 1, 1 ], [ 0, 0, 1 ], [ 3.0, 1.0, 3.0 ]); # Input second constraint. model.add_cons(1.0*x[1] ==2.0, "c1"); model.replace_sym_mat_elements(1, 1, [ 0, 2, 1, 2 ], [ 0, 0, 1, 2 ], [ 3.0, 1.0, 4.0, 5.0 ]); # Step 3. Solve the problem and populate the result.model.solve_prob() model.display_results() status_code, status_msg=model.get_status() ifstatus_msg=="OPTIMAL": print("Optimizer terminated with an OPTIMAL status (code {0}).".format(status_code)) print(" - Primal objective : {:8.6f}".format(model.get_real_attr(MDO_REAL_ATTR.PRIMAL_OBJ_VAL))) soln=model.get_real_attr_array(MDO_REAL_ATTR.PRIMAL_SOLN, 0, 2) forindex, valueinenumerate(soln): print("x[{0}]={1:8.6f}".format(index, value)) soln=model.get_real_attr_sym_mat(MDO_REAL_ATTR.SYM_MAT_PRIMAL_SOLN, 0, [i*2+jforiinrange(2) forjinrange(2)], [j*2+iforiinrange(2) forjinrange(2)]) print("X[0] = ") foriinrange(2): print(" (", end="") forjinrange(2): print(" {0:8.6f}".format(soln[i*2+j]), end=""), print(" )") soln=model.get_real_attr_sym_mat(MDO_REAL_ATTR.SYM_MAT_PRIMAL_SOLN, 1, [i*3+jforiinrange(3) forjinrange(3)], [j*3+iforiinrange(3) forjinrange(3)]) print("X[1] = ") foriinrange(3): print(" (", end=""), forjinrange(3): print(" {0:8.6f}".format(soln[i*3+j]), end=""), print(" )") else: print("Optimizer terminated with a(n) {0} status (code {1}).".format(status_msg, status_code)) exceptMdoErrorase: print("Received Mindopt exception.") print(" - Code : {}".format(e.code)) print(" - Reason : {}".format(e.message)) exceptExceptionase: print("Received exception.") print(" - Reason : {}".format(e)) finally: # Step 4. Free the model.model.free_mdl()
代码详细解释如下：
第一步：创建MindOpt模型
首先，我们必须先建立一空的MindOpt模型。
# Step 1. Create a model and change the parameters.model=MdoModel()
第二步：SDP模型输入
接着，我们将目标函数改为maximization，并新增
和
两个变量，以及
和
两个对称矩阵变量。
# Step 2. Input model.# Change to maximization problem.model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 0) # Add variables.x= [] x.append(model.add_var(0.0, MDO_INFINITY, 0.0, None, "x0", False)) x.append(model.add_var(0.0, MDO_INFINITY, 0.0, None, "x1", False)) # Add matrix variables. model.add_sym_mats([ 2, 3 ], [ "X0", "X1" ]);
我们利用Python API replace_sym_mat_objs() 来输入目标函数中的
的非零元素。其中，第一个参数为矩阵的索引值(此处为0)，第二和第三个参数分别代表矩阵中非零元素其对应的行和列之索引，而最后一个参数则为非零元的数值。
# Input objective coefficients. model.replace_sym_mat_objs(0, [ 0, 1, 1 ], [ 0, 0, 1 ], [ 2.0, 1.0, 2.0 ]);
同理，我们再接着输入目标函数中的
的非零元素。
model.replace_sym_mat_objs(1, [ 0, 0, 1, 2 ], [ 0, 2, 1, 2], [ 3.0, 1.0, 2.0, 3.0]);
接着，我们输入第一个约束。我们首先输入
接着再利用replace_sym_mat_elements()输入约束中的
的非零元素。其中，第一和第二个参数分别为：约束的索引值(此处为0)以及矩阵的索引值(此处为0)，第三第和第四个参数矩阵中非零元素其对应的行和列之索引，而最后一个参数则为非零元的数值。
# Input first constraint. model.add_cons(1.0*x[0] ==1.0, "c0"); model.replace_sym_mat_elements(0, 0, [ 0, 1, 1 ], [ 0, 0, 1 ], [ 3.0, 1.0, 3.0 ]);
同理，我们再接着输入第二个约束。
# Input second constraint. model.add_cons(1.0*x[1] ==2.0, "c1"); model.replace_sym_mat_elements(1, 1, [ 0, 2, 1, 2 ], [ 0, 0, 1, 2 ], [ 3.0, 1.0, 4.0, 5.0 ]);
第三步：求解SDP模型
模型输入后，我们接着用solve_prob()来求解问题，并用display_results()呈现求解结果。
# Step 3. Solve the problem and populate the result.model.solve_prob() model.display_results()
第四步: 取得SDP模型的解
我们利用泛用函数model.get_real_attr(MDO_REAL_ATTR.PRIMAL_OBJ_VAL)来取得最优的的目标函数值，并用泛用函数get_real_attr_array(MDO_REAL_ATTR.PRIMAL_SOLN, 0, 2)来取得和两个变量值；此处第一个参数定义了属性值 (附注: get_real_attr_array为泛用函数，因此必须配合属性值来定义函数的使用目的；MDO_REAL_ATTR.PRIMAL_SOLN定义目的为获取(线性)变量的数值)，第二和第三个参数分别代表第一个索引和最后一个索引加上1，也就是
print(" - Primal objective : {:8.6f}".format(model.get_real_attr(MDO_REAL_ATTR.PRIMAL_OBJ_VAL))) soln=model.get_real_attr_array(MDO_REAL_ATTR.PRIMAL_SOLN, 0, 2)
最后，我们利用get_real_attr_sym_mat()来取得的变量值。其中，第一个参数定义属性值 (附注: get_real_attr_sym_mat为泛用函数，因此必须配合属性值来定义函数的使用目的；MDO_REAL_ATTR.SYM_MAT_PRIMAL_SOLN定义目的为获取(对称矩阵)变量的数值)，第二个参数为：矩阵的索引值 (此处为0)，第三第和第四个参数为矩阵中需要回传的元素其对应的行和列之索引。返回值soln则为矩阵中对应的元素数值。
soln=model.get_real_attr_sym_mat(MDO_REAL_ATTR.SYM_MAT_PRIMAL_SOLN, 0, [i*2+jforiinrange(2) forjinrange(2)], [j*2+iforiinrange(2) forjinrange(2)])
4.2 如何取得MindOpt求解器
求解器安装包的发布渠道。请大家:
- 前往 https://www.aliyun.com/product/ai/opt 来下载求解器软件。
- 在阿里云上获取免费授权码:
关于求解器的使用文档，请参考：https://help.aliyun.com/document_detail/298219.htm
4.3 首次发布的公开评测成绩，国际第二
业界最权威的Mittelmann求解器榜单由美国亚利桑那州立大学Hans Mittelmann教授维护，榜单从数万个实际问题中精心挑出最难的优化问题作为评测数据集，吸引众多商业级求解器软件来参与评测。MindOpt新的半定求解器在首次发布的公开评测中取得国际第二的成绩，其性能大幅超过了该领域知名求解器Mosek，而且与第一的距离只有不到20%的性能区别。
参考文献
- Åberg, Johan, Ranieri Nery, Cristhiano Duarte, and Rafael Chaves. "Semidefinite tests for quantum network topologies." Physical Review Letters 125, no. 11 (2020): 110505.
- Alizadeh, Farid. "Interior point methods in semidefinite programming with applications to combinatorial optimization." SIAM Journal on Optimization 5, no. 1 (1995): 13-51.
- Andersen, Martin S., Anders Hansson, and Lieven Vandenberghe. "Reduced-complexity semidefinite relaxations of optimal power flow problems." IEEE Transactions on Power Systems 29, no. 4 (2013): 1855-1863.
- Anjos, Miguel F., and Jean B. Lasserre, eds. Handbook on semidefinite, conic and polynomial optimization. Vol. 166. Springer Science & Business Media, 2011.
- Bian, Zhengbing, Fabian Chudak, Robert Israel, Brad Lackey, William G. Macready, and Aidan Roy. "Discrete optimization using quantum annealing on sparse Ising models." Frontiers in Physics 2 (2014): 56.
- Candès, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55, no. 6 (2012): 111-119.
- Carlone, Luca, Giuseppe C. Calafiore, Carlo Tommolillo, and Frank Dellaert. "Planar pose graph optimization: Duality, optimal solutions, and verification." IEEE Transactions on Robotics 32, no. 3 (2016): 545-565.
- Chi, Yuejie, Yue M. Lu, and Yuxin Chen. "Nonconvex optimization meets low-rank matrix factorization: An overview." IEEE Transactions on Signal Processing 67, no. 20 (2019): 5239-5269.
- Dantzig, George B. "Linear Programming and Extensions." (1963).
- d'Aspremont, Alexandre, Laurent Ghaoui, Michael Jordan, and Gert Lanckriet. "A direct formulation for sparse PCA using semidefinite programming." Advances in neural information processing systems 17 (2004).
- Goemans, Michel X., and David P. Williamson. "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming." Journal of the ACM (JACM) 42, no. 6 (1995): 1115-1145.
- Harrow, Aram W., Avinatan Hassidim, and Seth Lloyd. "Quantum algorithm for linear systems of equations." Physical review letters 103, no. 15 (2009): 150502.
- Helmberg, Christoph, Franz Rendl, Robert J. Vanderbei, and Henry Wolkowicz. "An interior-point method for semidefinite programming." SIAM Journal on Optimization 6, no. 2 (1996): 342-361.
- Ikeda, Kazuki, Yuma Nakamura, and Travis S. Humble. "Application of quantum annealing to nurse scheduling problem." Scientific reports 9, no. 1 (2019): 1-10.
- Naghibi, Tofigh, Sarah Hoffmann, and Beat Pfister. "A semidefinite programming based search strategy for feature selection with mutual information measure." IEEE transactions on pattern analysis and machine intelligence 37, no. 8 (2014): 1529-1541.
- Neukart, Florian, Gabriele Compostella, Christian Seidel, David Von Dollen, Sheir Yarkoni, and Bob Parney. "Traffic flow optimization using a quantum annealer." Frontiers in ICT 4 (2017): 29.
- Waki, Hayato, Sunyoung Kim, Masakazu Kojima, and Masakazu Muramatsu. "Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity." SIAM Journal on Optimization 17, no. 1 (2006): 218-242.
- Wen, Zaiwen, Donald Goldfarb, and Wotao Yin. "Alternating direction augmented Lagrangian methods for semidefinite programming." Mathematical Programming Computation 2, no. 3 (2010): 203-230.
- Vaswani, Namrata, Thierry Bouwmans, Sajid Javed, and Praneeth Narayanamurthy. "Robust subspace learning: Robust PCA, robust subspace tracking, and robust subspace recovery." IEEE signal processing magazine 35, no. 4 (2018): 32-55.
- Xu, Zi, Mingyi Hong, and Zhi-Quan Luo. "Semidefinite approximation for mixed binary quadratically constrained quadratic programs." SIAM Journal on Optimization 24, no. 3 (2014): 1265-1293.
