在半监督的基于图的二进制分类器学习中，假设标签信号$ \ mathbf {x} $相对于相似性，则使用已知标签的子集$ \ hat {x} _i $来推断未知标签图形由拉普拉斯矩阵指定。当将标签$ x_i $限制为二进制值时，问题是NP-HARD。虽然可以在多项式时间内使用乘数的交替方向方法（ADMM）在多项式时间内解决常规半准编程放松（SDR），但投射候选矩阵$ \ mathbf {m mathbf {m mathbf {m} $的复杂性-definite（PSD）锥（$ \ Mathbf {M} \ succeq 0 $）每个迭代仍然很高。在本文中，我们利用一种称为Gershgorin Disc Perfect Alignment（GDPA）的最新线性代数理论，我们通过求解一系列线性程序（LP）提出了一种快速投影方法。具体而言，我们首先将SDR重新铸造为二元，其中可行的解决方案$ \ mathbf {h} \ succeq 0 $解释为与平衡签名的图相对应的laplacian矩阵减去最后一个节点。为了达到图表平衡，我们将最后一个节点分为两个，每个节点保留了原始的正 /负边缘，从而导致新的laplacian $ \ bar {\ mathbf {h}} $。我们在解决方案$ \ bar {\ mathbf {h}} $上放置sdr dual，然后替换PSD锥约束$ \ bar {\ Mathbf {h} \ succeq 0 $，具有从GDPA衍生的线性约束 - 可确保足够的条件 - 确保足够的条件$ \ bar {\ mathbf {h}} $是psd-因此，优化成为LP，每次迭代。最后，我们从融合解决方案$ \ bar {\ mathbf {h}} $中提取预测标签。实验表明，我们的算法在下一个最快的方案中享受了$ 28 \ times $速度，同时达到了可比的标签预测性能。

图形信号处理（GSP）中的基本前提是，将目标信号的成对（反）相关性作为边缘权重以用于图形过滤。但是，现有的快速图抽样方案仅针对描述正相关的正图设计和测试。在本文中，我们表明，对于具有强固有抗相关的数据集，合适的图既包含正边缘和负边缘。作为响应，我们提出了一种以平衡签名图的概念为中心的线性时间签名的图形采样方法。具体而言，给定的经验协方差数据矩阵$ \ bar {\ bf {c}} $，我们首先学习一个稀疏的逆矩阵（Graph laplacian）$ \ MATHCAL {l} $对应于签名图$ \ Mathcal $ \ Mathcal {G} $ 。我们为平衡签名的图形$ \ Mathcal {g} _b $ - 近似$ \ Mathcal {g} $通过Edge Exge Exgement Exgmentation -As Graph频率组件定义Laplacian $ \ Mathcal {L} _b $的特征向量。接下来，我们选择样品以将低通滤波器重建误差分为两个步骤最小化。我们首先将Laplacian $ \ Mathcal {L} _b $的所有Gershgorin圆盘左端对齐，最小的EigenValue $ \ lambda _ {\ min}（\ Mathcal {l} _b）$通过相似性转换$ \ MATHCAL $ \ MATHCAL} s \ Mathcal {l} _b \ s^{ - 1} $，利用最新的线性代数定理，称为gershgorin disc perfect perfect对齐（GDPA）。然后，我们使用以前的快速gershgorin盘式对齐采样（GDAS）方案对$ \ Mathcal {L} _p $进行采样。实验结果表明，我们签名的图形采样方法在各种数据集上明显优于现有的快速采样方案。

我们的目标是有效地计算输入图中的节点的低维潜在坐标 - 称为图形嵌入 - 用于后续数据处理，例如群集。专注于在连续歧管上解释为均匀样品的有限图（称为歧管图），我们利用现有的快速极端特征向量计算算法来快速执行。我们首先为稀疏矩阵配对构成普遍的特征值问题，其中$ \ a = \ l - \ mu \ q + \ epsilon \ i $是图表拉普拉斯$ \ l \ l的总和断开双跳差异矩阵$ \ q $。特征向量$ \ v $最小化瑞利商$ \ frac {\ v ^ {\ top} \ top} \ a \ a \ v} $，从而最大限度地降低$ 1 $ -hop邻居距离，同时最大化断开连接2美元之间的距离$ -hop邻居，保留图形结构。矩阵$ \ b = \ text {diag}（\ {\ b_i \}），然后选择定义特征向量正交性，以便采样域中的边界/内部节点具有相同的广义度。 $ k $ -dimensional潜在的$ n $ graph节点是$（\ a，\ b）$的$ k $概括的特征向量，在$ \ co（n）$中使用lobpcg，其中$ k \ ll n $。实验表明，我们的嵌入是文献中最快的，同时为歧管图产生了最佳聚类性能。

我们考虑学习底层多变量数据的稀疏无向图的问题。我们专注于稀疏精度矩阵上的图表拉普拉斯相关的约束，它在与图形节点相关联的随机变量之间编码条件依赖性。在这些约束下，精度矩阵的偏差元素是非正（总阳性），并且精度矩阵可能不是全级。我们调查了对广泛使用惩罚的日志似然方法来强制执行总积极性但不是拉普拉斯结构的修改。然后可以从非对角线精密矩阵中提取图拉普拉斯。乘法器（ADMM）算法的交替方向方法被提出和分析了Laplacian相关约束和套索的约束优化以及自适应套索处罚。基于合成数据的数值结果表明，所提出的约束的自适应套索方法显着优于现有的基于拉普拉斯的方法。我们还评估了我们对实际财务数据的方法。

该博士学位论文的中心对象是在计算机科学和统计力学领域的不同名称中以不同名称而闻名的。在计算机科学中，它被称为“最大切割问题”，这是著名的21个KARP的原始NP硬性问题之一，而物理学的相同物体称为Ising Spin Glass模型。这种丰富的结构的模型通常是减少或重新制定计算机科学，物理和工程学的现实问题。但是，准确地求解此模型（查找最大剪切或基态）可能会留下一个棘手的问题（除非$ \ textit {p} = \ textit {np} $），并且需要为每一个开发临时启发式学特定的实例家庭。离散和连续优化之间的明亮而美丽的连接之一是一种基于半限定编程的圆形方案，以最大程度地切割。此过程使我们能够找到一个近乎最佳的解决方案。此外，该方法被认为是多项式时间中最好的。在本论文的前两章中，我们研究了旨在改善舍入方案的局部非凸照。在本文的最后一章中，我们迈出了一步，并旨在控制我们想要在前几章中解决的问题的解决方案。我们在Ising模型上制定了双层优化问题，在该模型中，我们希望尽可能少地调整交互作用，以使所得ISING模型的基态满足所需的标准。大流行建模出现了这种问题。我们表明，当相互作用是非负的时，我们的双层优化是在多项式时间内使用凸编程来解决的。

最近已扩展了最小方形聚类（MSSC）或K-均值类型聚类的最小总和，以利用每个群集的基数的先验知识。这种知识用于提高性能以及解决方案质量。在本文中，我们提出了一种基于分支和切割技术的精确方法，以解决基数受限的MSSC。对于下边界的例程，我们使用Rujeerapaiboon等人最近提出的半决赛编程（SDP）放松。 [Siam J. Optim。 29（2），1211-1239，（2019）]。但是，这种放松只能用于小型实例中的分支和切割方法。因此，我们得出了一种新的SDP松弛，该松弛随着实例大小和簇的数量更好。在这两种情况下，我们都通过添加多面体切割来增强结合。从量身定制的分支策略中受益，该策略会实施成对的约束，我们减少了儿童节点中出现的问题的复杂性。相反，对于上限，我们提出了一个本地搜索过程，该过程利用在每个节点上求解的SDP松弛的解。计算结果表明，所提出的算法在全球范围内首次求解了大小的现实实例，比通过最新精确方法求解的算法大10倍。

我们开发了快速算法和可靠软件，以凸出具有Relu激活功能的两层神经网络的凸优化。我们的工作利用了标准的重量罚款训练问题作为一组组-YELL_1 $调查的数据本地模型的凸重新印度，其中局部由多面体锥体约束强制执行。在零规范化的特殊情况下，我们表明此问题完全等同于凸“ Gated Relu”网络的不受约束的优化。对于非零正则化的问题，我们表明凸面式relu模型获得了RELU训练问题的数据依赖性近似范围。为了优化凸的重新制定，我们开发了一种加速的近端梯度方法和实用的增强拉格朗日求解器。我们表明，这些方法比针对非凸问题（例如SGD）和超越商业内部点求解器的标准训练启发式方法要快。在实验上，我们验证了我们的理论结果，探索组-ELL_1 $正则化路径，并对神经网络进行比例凸的优化，以在MNIST和CIFAR-10上进行图像分类。

我们提出了一种新的基于同型的条件梯度方法，用于解决大量简单圆锥约束的凸优化问题。该模板的实例自然出现在半决赛编程问题中，这是组合优化问题的凸松弛。我们的方法是一种双环算法，其中通过自我符合屏障处理圆锥约束，并且内环采用条件梯度算法来近似分析中心路径，而外圈则更新了对时间溶液上的精度。和同喻参数。当面对最先进的SDP求解器时，我们的理论迭代复杂性具有竞争力，具有廉价的无投影子例程的决定性优势。提供了初步数值实验，以说明该方法的实际性能。

将离散域上的功能集成到神经网络中是开发其推理离散对象的能力的关键。但是，离散域是（1）自然不适合基于梯度的优化，并且（2）与依赖于高维矢量空间中表示形式的深度学习体系结构不相容。在这项工作中，我们解决了设置功能的两个困难，这些功能捕获了许多重要的离散问题。首先，我们开发了将设置功能扩展到低维连续域的框架，在该域中，许多扩展是自然定义的。我们的框架包含许多众所周知的扩展，作为特殊情况。其次，为避免不良的低维神经网络瓶颈，我们将低维扩展转换为高维空间中的表示形式，从半际计划进行组合优化的成功中获得了灵感。从经验上讲，我们观察到扩展对无监督的神经组合优化的好处，特别是具有高维其表示。

给定数据点之间的一组差异测量值，确定哪种度量表示与输入测量最“一致”或最能捕获数据相关几何特征的度量是许多机器学习算法的关键步骤。现有方法仅限于特定类型的指标或小问题大小，因为在此类问题中有大量的度量约束。在本文中，我们提供了一种活跃的集合算法，即项目和忘记，该算法使用Bregman的预测，以解决许多（可能是指数）不平等约束的度量约束问题。我们提供了\ textsc {project and Hoses}的理论分析，并证明我们的算法会收敛到全局最佳解决方案，并以指数速率渐近地渐近地衰减了当前迭代的$ L_2 $距离。我们证明，使用我们的方法，我们可以解决三种类型的度量约束问题的大型问题实例：一般体重相关聚类，度量近距离和度量学习；在每种情况下，就CPU时间和问题尺寸而言，超越了艺术方法的表现。

人工神经网络（ANN）训练景观的非凸起带来了固有的优化困难。虽然传统的背传播随机梯度下降（SGD）算法及其变体在某些情况下是有效的，但它们可以陷入杂散的局部最小值，并且对初始化和普通公共表敏感。最近的工作表明，随着Relu激活的ANN的培训可以重新重整为凸面计划，使希望能够全局优化可解释的ANN。然而，天真地解决凸训练制剂具有指数复杂性，甚至近似启发式需要立方时间。在这项工作中，我们描述了这种近似的质量，并开发了两个有效的算法，这些算法通过全球收敛保证培训。第一算法基于乘法器（ADMM）的交替方向方法。它解决了精确的凸形配方和近似对应物。实现线性全局收敛，并且初始几次迭代通常会产生具有高预测精度的解决方案。求解近似配方时，每次迭代时间复杂度是二次的。基于“采样凸面”理论的第二种算法更简单地实现。它解决了不受约束的凸形制剂，并收敛到大约全球最佳的分类器。当考虑对抗性培训时，ANN训练景观的非凸起加剧了。我们将稳健的凸优化理论应用于凸训练，开发凸起的凸起制剂，培训Anns对抗对抗投入。我们的分析明确地关注一个隐藏层完全连接的ANN，但可以扩展到更复杂的体系结构。

大图通常出现在社交网络，知识图，推荐系统，生命科学和决策问题中。通过其高级别属性总结大图有助于解决这些设置中的问题。在光谱聚类中，我们旨在确定大多数边缘落在簇内的节点簇，而在簇之间只有很少的边缘。此任务对于许多下游应用和探索性分析很重要。光谱聚类的核心步骤是执行相应图的拉普拉斯矩阵（或等效地，奇异值分解，SVD）的特征分类。迭代奇异值分解方法的收敛取决于给定矩阵的光谱的特征，即连续特征值之间的差异。对于对应于群集图的图形的图形拉普拉斯，特征值将是非负的，但很小（小于$ 1 $）的减慢收敛性。本文引入了一种可行的方法，用于扩张光谱以加速SVD求解器，然后又是光谱群集。这是通过对矩阵操作的多项式近似来实现的，矩阵操作有利地改变矩阵的光谱而不更改其特征向量。实验表明，这种方法显着加速了收敛，我们解释了如何并行化和随机近似于可用的计算。

To rigorously certify the robustness of neural networks to adversarial perturbations, most state-of-the-art techniques rely on a triangle-shaped linear programming (LP) relaxation of the ReLU activation. While the LP relaxation is exact for a single neuron, recent results suggest that it faces an inherent "convex relaxation barrier" as additional activations are added, and as the attack budget is increased. In this paper, we propose a nonconvex relaxation for the ReLU relaxation, based on a low-rank restriction of a semidefinite programming (SDP) relaxation. We show that the nonconvex relaxation has a similar complexity to the LP relaxation, but enjoys improved tightness that is comparable to the much more expensive SDP relaxation. Despite nonconvexity, we prove that the verification problem satisfies constraint qualification, and therefore a Riemannian staircase approach is guaranteed to compute a near-globally optimal solution in polynomial time. Our experiments provide evidence that our nonconvex relaxation almost completely overcome the "convex relaxation barrier" faced by the LP relaxation.

自我监督的学习（SSL）推测，投入和成对的积极关系足以学习有意义的表示。尽管SSL最近达到了一个里程碑：在许多模式下，胜过监督的方法\点，理论基础是有限的，特定于方法的，并且未能向从业者提供原则上的设计指南。在本文中，我们提出了一个统一的框架，这些框架是在光谱歧管学习的掌舵下，以解决这些局限性。通过这项研究的过程，我们将严格证明Vic​​reg，Simclr，Barlowtwins等。对应于诸如Laplacian eigenmaps，多维缩放等方面的同名光谱方法。然后，此统一将使我们能够获得（i）每种方法的闭合形式的最佳表示，（ii）每种方法的线性态度中的封闭形式的最佳网络参数，（iii）在期间使用的成对关系的影响对每个数量和下游任务性能的培训，以及最重要的是，（iv）分别针对全球和局部光谱嵌入方法的对比度和非对抗性方法之间的第一个理论桥梁，暗示了每种方法的益处和限制。例如，（i）如果成对关系与下游任务一致，则可以成功采用任何SSL方法并将恢复监督方法，但是在低数据状态下，Vicreg的不变性超参数应该很高； （ii）如果成对关系与下游任务未对准，则与SIMCLR或BARLOWTWINS相比，具有小型不变性高参数的VICREG。

最小的平方和群集（MSSC）或K-Means型聚类，传统上被认为是无监督的学习任务。近年来，使用背景知识来提高集群质量，促进聚类过程的可解释性已成为数学优化和机器学习研究的热门研究课题。利用数据群集中的背景信息的问题称为半监督或约束群集。在本文中，我们为半监控MSSC提供了一种新的分支和绑定算法，其中背景知识被包含为成对必须 - 链接和无法链接约束。对于较低的界限，我们解决了MSSC离散优化模型的Semidefinite编程宽松，并使用了用于加强界限的纤维平面程序。相反，通过使用整数编程工具，我们提出了将K-Means算法适应受约束的情况。这是第一次，所提出的全局优化算法有效地管理，以解决现实世界的情况，最高可达800个数据点，具有必要的必须 - 链接和无法链接约束以及通用数量的功能。这个问题大小大约比最先进的精确算法解决的实例大约四倍。

我们研究了估计多元高斯分布中的精度矩阵的问题，其中所有部分相关性都是非负面的，也称为多变量完全阳性的顺序阳性（$ \ mathrm {mtp} _2 $）。近年来，这种模型得到了重大关注，主要是由于有趣的性质，例如，无论底层尺寸如何，最大似然估计值都存在于两个观察。我们将此问题作为加权$ \ ell_1 $ -norm正常化高斯的最大似然估计下$ \ mathrm {mtp} _2 $约束。在此方向上，我们提出了一种新颖的预计牛顿样算法，该算法包含精心设计的近似牛顿方向，这导致我们具有与一阶方法相同的计算和内存成本的算法。我们证明提出的预计牛顿样算法会聚到问题的最小值。从理论和实验中，我们进一步展示了我们使用加权$ \ ell_1 $ -norm的制剂的最小化器能够正确地恢复基础精密矩阵的支持，而无需在$ \ ell_1 $ -norm中存在不连贯状态方法。涉及合成和实世界数据的实验表明，我们所提出的算法从计算时间透视比最先进的方法显着更有效。最后，我们在金融时序数据中应用我们的方法，这些数据对于显示积极依赖性，在那里我们在学习金融网络上的模块间值方面观察到显着性能。

我们考虑了提高柱生成效率（CG）方法的方法，以解决车辆路由问题。我们介绍了CG配方中常用的NG-Route松弛度和降低状态空间松弛（DSSR）的替代/补充，我们引入了局部区域（LA）路线。 LA路线是NG路由的子集和基本路线的超级集合。通常，CG的定价阶段必须产生基本路线，这些路线是没有重复客户的路线，使用可能在计算上昂贵的流程。非元素路线至少访问至少一个客户，创建一个周期。 LA路线以允许有效定价的方式放松成为基本途径的约束。从NG-Route放松方面，最好理解LA路线。 NG路由是允许在空间中具有非定位循环的路线。这意味着周期中至少有一个中间客户（称为断路器）必须考虑到周期中的起始客户在空间上远离。使用一组特殊索引来描述LA路线，该特殊索引与从开始到路线尽头的路线上的客户相对应。 LA路线的松弛进一步限制了一组允许的周期，除了强制执行断路器必须位于特殊索引中，该循环均超出了NG路由，其中​​一组特殊索引被递归地定义为如下。该路线中的第一个特殊索引是索引1，这意味着它与路线中的第一个客户关联。 K'th特殊索引对应于K-1第三个特殊索引之后的第一个客户，该索引并非被认为是（在空间上被认为是远离K-1'TEXPATEX的客户）的邻居。我们证明，与标准DSSR相比，LA路线松弛可以显着提高定价的计算速度。

我们研究了p-laplacians和光谱聚类，以融合了边缘依赖性顶点权重（EDVW）的最近提出的超图模型。这些权重可以反映在超边缘内顶点的不同重要性，从而赋予超图模型更高的表达性和灵活性。通过构建基于EDVWS的基于EDVWS的分裂函数，我们将具有EDVW的超图转换为频谱理论更好地开发的谱图。这样，现有的概念和定理，例如P-Laplacians和Subsodular HyperGraph设置下提出的P-Laplacians和Cheeger不平等现象，可以直接扩展到具有EDVW的超图。对于具有基于EDVWS的拆分功能的子管道超图，我们提出了一种有效的算法来计算与1-Laplacian的第二小特征值相关的特征向量。然后，我们利用此特征向量来聚类顶点，比基于2-Laplacian的传统光谱聚类获得更高的聚类精度。从更广泛的角度来看，所提出的算法适用于所有可降低图的亚物种超图。使用现实世界数据的数值实验证明了基于1-Laplacian和EDVW的光谱聚类的有效性。

我们提出了一种凸锥程序，可推断随机点产品图（RDPG）的潜在概率矩阵。优化问题最大化Bernoulli最大似然函数，增加核规范正则化术语。双重问题具有特别良好的形式，与众所周知的SemideFinite程序放松MaxCut问题有关。使用原始双功率条件，我们绑定了原始和双解决方案的条目和等级。此外，我们在轻微的技术假设下绑定了最佳目标值并证明了略微修改模型的概率估计的渐近一致性。我们对合成RDPG的实验不仅恢复了自然集群，而且还揭示了原始数据的下面的低维几何形状。我们还证明该方法在空手道俱乐部图表和合成美国参议图中恢复潜在结构，并且可以扩展到最多几百个节点的图表。

在县粒度上预测每年农作物的产量对于国家粮食生产和价格稳定至关重要。在本文中，为了实现更好的作物产量预测，利用最新的图形信号处理（GSP）工具来利用相邻县之间的空间相关性，我们通过图形光谱滤波来证明相关的特征，这些特征是深度学习预测模型的输入。具体而言，我们首先构建一个具有边缘权重的组合图，该图可以通过公制学习编码土壤和位置特征的县对县的相似性。然后，我们通过最大的后验（MAP）配方使用图形laplacian正常化程序（GLR）来定性特征。我们关注的挑战是估算关键的权重参数$ \ mu $，交易忠诚度和GLR，这是噪声差异的函数，以无监督的方式。我们首先使用发现局部恒定区域的图集集合检测（GCD）过程直接从噪声浪费的图形信号估算噪声方差。然后，我们通过通过偏置变化分析来计算最佳$ \ mu $最大程度地减少近似平方误差函数。收集到的USDA数据的实验结果表明，使用DeNo的特征作为输入，可以明显改善作物产量预测模型的性能。