Exploiting Structure and Hidden Convexity in Hard, Large Scale Numerical Optimization
在困难的大规模数值优化中利用结构和隐藏凸性
基本信息
- 批准号:RGPIN-2018-04028
- 负责人:
- 金额:$ 4.01万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2020
- 资助国家:加拿大
- 起止时间:2020-01-01 至 2021-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
My research aims to apply continuous optimization relaxations and to exploit structure in order to derive practical algorithms that efficiently and accurately solve large scale hard numerical problems. These problems arise in data science and are generally non-convex and intractable. One well known application is the low-rank matrix completion (LRMC) problem, such as the netflix movie ratings problem, i.e., one can fill missing entries in order to make good recommendations to customers. Other applications include: hard discrete optimization problems that model scheduling and location problems such as the quadratic assignment problem; robust principal component analysis that includes recovery of measurements from highly corrupted surveillance data; molecular conformation and protein folding sensor network localization and real solutions of polynomial equations. Throughout I emphasize specific applications with extensive numerical tests.
Many current optimization modelling and convex relaxations for hard non-convex problems typically result in loss of strict feasibility, interior, of the feasible set. This can result in both theoretical and numerical difficulties. Rather than being a disadvantage, we turn this loss of regularity to a great advantage using a technique called facial reduction (FR). In particular, this has resulted in extremely efficient algorithms for many intractable problems. The result is that we can solve huge problems often without the need of a numerical optimization solver. For matrix completion type problems, in the noiseless case one gets extremely high accuracy. In the noisy case, one can use the notion of exposing vectors of the faces to avoid build up of round-off error and obtain solutions within the order of the noise. In addition, the FR technique appears to fit perfectly with first order methods as one can maintain two sets of variables and alternate projections between them.
The work I am doing has many applications to the data science and machine learning areas in computer science and to operations research. In particular, the loss of regularity, strict feasibility, appears in surprisingly many applications as mentioned above. The FR techniques allow for more accurate solutions of larger problems than have currently been handled. The novelty of our approach is we can exploit the structures of problems to identify loss of regularity and then use this loss to our advantage to obtain a reformulation that is both stable and reduces the size. We emphasize FR as a preprocessing technique and display its mathematical elegance, geometric transparency and computational potential.
我的研究旨在应用连续优化松弛和利用结构,以获得有效和准确地解决大规模困难的数值问题的实用算法。这些问题出现在数据科学中,通常是非凸和棘手的。一个众所周知的应用是低秩矩阵完成(LRMC)问题,例如网络电影评级问题,即,可以填充缺失的条目以便向客户做出好的推荐。其他应用包括:模拟调度和定位问题的硬离散优化问题,例如二次分配问题;鲁棒主成分分析,包括从高度损坏的监视数据中恢复测量值;分子构象和蛋白质折叠传感器网络定位以及多项式方程的真实的解。 在整个过程中,我强调具体应用广泛的数值测试。
目前许多优化建模和凸松弛硬非凸问题通常会导致严格可行性,内部的可行集的损失。这可能导致理论和数值上的困难。而不是一个缺点,我们把这种规律性的损失变成一个很大的优势,使用一种技术称为面部缩小(FR)。特别是,这导致了非常有效的算法,许多棘手的问题。其结果是,我们可以解决巨大的问题,往往不需要一个数值优化求解器。对于矩阵完成类型的问题,在无噪声的情况下,得到非常高的精度。在有噪声的情况下,可以使用暴露面向量的概念来避免舍入误差的积累,并获得噪声量级内的解。此外,FR技术似乎完全适合一阶方法,因为可以保持两组变量并在它们之间交替投影。
我所做的工作在计算机科学中的数据科学和机器学习领域以及运筹学中有许多应用。特别地,规律性、严格可行性的丧失出现在如上所述的令人惊讶的许多应用中。FR技术允许比目前处理的更大问题的更精确的解决方案。我们的方法的新奇在于,我们可以利用问题的结构来识别规律性的损失,然后利用这种损失来获得一个既稳定又减小大小的重新表述。我们强调FR作为一种预处理技术,并显示其数学优雅,几何透明性和计算潜力。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Wolkowicz, Henry其他文献
On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming
二次矩阵规划半定松弛的等价
- DOI:
10.1287/moor.1100.0473 - 发表时间:
2011-02 - 期刊:
- 影响因子:1.7
- 作者:
Ding, Yichuan;Ge, Dongdong;Wolkowicz, Henry - 通讯作者:
Wolkowicz, Henry
Low-rank matrix completion using nuclear norm minimization and facial reduction
- DOI:
10.1007/s10898-017-0590-1 - 发表时间:
2018-09-01 - 期刊:
- 影响因子:1.8
- 作者:
Huang, Shimeng;Wolkowicz, Henry - 通讯作者:
Wolkowicz, Henry
Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs.
- DOI:
10.1007/s10107-022-01890-9 - 发表时间:
2023 - 期刊:
- 影响因子:2.7
- 作者:
Hu, Hao;Sotirov, Renata;Wolkowicz, Henry - 通讯作者:
Wolkowicz, Henry
Robust Interior Point Method for Quantum Key Distribution Rate Computation
- DOI:
10.22331/q-2022-09-08-792 - 发表时间:
2022-09-01 - 期刊:
- 影响因子:6.4
- 作者:
Hu, Hao;Im, Jiyoung;Wolkowicz, Henry - 通讯作者:
Wolkowicz, Henry
Sensor Network Localization, Euclidean Distance Matrix completions, and graph realization
- DOI:
10.1007/s11081-008-9072-0 - 发表时间:
2010-02-01 - 期刊:
- 影响因子:2.1
- 作者:
Ding, Yichuan;Krislock, Nathan;Wolkowicz, Henry - 通讯作者:
Wolkowicz, Henry
Wolkowicz, Henry的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Wolkowicz, Henry', 18)}}的其他基金
Exploiting Structure and Hidden Convexity in Hard, Large Scale Numerical Optimization
在困难的大规模数值优化中利用结构和隐藏凸性
- 批准号:
RGPIN-2018-04028 - 财政年份:2022
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Exploiting Structure and Hidden Convexity in Hard, Large Scale Numerical Optimization
在困难的大规模数值优化中利用结构和隐藏凸性
- 批准号:
RGPIN-2018-04028 - 财政年份:2021
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Exploiting Structure and Hidden Convexity in Hard, Large Scale Numerical Optimization
在困难的大规模数值优化中利用结构和隐藏凸性
- 批准号:
RGPIN-2018-04028 - 财政年份:2019
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Exploiting Structure and Hidden Convexity in Hard, Large Scale Numerical Optimization
在困难的大规模数值优化中利用结构和隐藏凸性
- 批准号:
RGPIN-2018-04028 - 财政年份:2018
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Theory and Efficient Algorithms for Hard, Large Scale, Numerical Optimization
大规模硬数值优化的理论和高效算法
- 批准号:
9161-2013 - 财政年份:2017
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Theory and Efficient Algorithms for Hard, Large Scale, Numerical Optimization
大规模硬数值优化的理论和高效算法
- 批准号:
9161-2013 - 财政年份:2016
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Theory and Efficient Algorithms for Hard, Large Scale, Numerical Optimization
大规模硬数值优化的理论和高效算法
- 批准号:
9161-2013 - 财政年份:2015
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Workshop on Nonlinear Optimization Algorithms and Industrial Applications
非线性优化算法及工业应用研讨会
- 批准号:
491740-2015 - 财政年份:2015
- 资助金额:
$ 4.01万 - 项目类别:
Regional Office Discretionary Funds
Theory and Efficient Algorithms for Hard, Large Scale, Numerical Optimization
大规模硬数值优化的理论和高效算法
- 批准号:
9161-2013 - 财政年份:2014
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Theory and Efficient Algorithms for Hard, Large Scale, Numerical Optimization
大规模硬数值优化的理论和高效算法
- 批准号:
9161-2013 - 财政年份:2013
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
相似海外基金
Acquiring cognitive maps: how brains learn hidden structure
获取认知图:大脑如何学习隐藏结构
- 批准号:
10739622 - 财政年份:2023
- 资助金额:
$ 4.01万 - 项目类别:
Exploiting Structure and Hidden Convexity in Hard, Large Scale Numerical Optimization
在困难的大规模数值优化中利用结构和隐藏凸性
- 批准号:
RGPIN-2018-04028 - 财政年份:2022
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
Exploiting Structure and Hidden Convexity in Hard, Large Scale Numerical Optimization
在困难的大规模数值优化中利用结构和隐藏凸性
- 批准号:
RGPIN-2018-04028 - 财政年份:2021
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
CAREER: Neural circuit mechanisms of inference: how brains learn and use hidden structure
职业:推理的神经回路机制:大脑如何学习和使用隐藏结构
- 批准号:
2042796 - 财政年份:2021
- 资助金额:
$ 4.01万 - 项目类别:
Continuing Grant
Extracting the hidden structure of glass from particle vibrations
从粒子振动中提取玻璃的隐藏结构
- 批准号:
DE210100256 - 财政年份:2021
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Early Career Researcher Award
Exploiting Structure and Hidden Convexity in Hard, Large Scale Numerical Optimization
在困难的大规模数值优化中利用结构和隐藏凸性
- 批准号:
RGPIN-2018-04028 - 财政年份:2019
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual
RAISE-TAQS: The Hidden Structure of the Disorder in Quantum Systems
RAISE-TAQS:量子系统中无序的隐藏结构
- 批准号:
1839077 - 财政年份:2018
- 资助金额:
$ 4.01万 - 项目类别:
Standard Grant
Elucudation of the significance of hidden break structure in insect ribosome
阐明昆虫核糖体中隐藏断裂结构的重要性
- 批准号:
18K14474 - 财政年份:2018
- 资助金额:
$ 4.01万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
Workshop: Learning Hidden Linguistic Structure; January 3-7, 2019, New York New York
工作坊:学习隐藏的语言结构;
- 批准号:
1832737 - 财政年份:2018
- 资助金额:
$ 4.01万 - 项目类别:
Standard Grant
Exploiting Structure and Hidden Convexity in Hard, Large Scale Numerical Optimization
在困难的大规模数值优化中利用结构和隐藏凸性
- 批准号:
RGPIN-2018-04028 - 财政年份:2018
- 资助金额:
$ 4.01万 - 项目类别:
Discovery Grants Program - Individual