Henry Wolkowicz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Henry Wolkowicz has a total of 52 co-authors. Here are the top co-authors by number of shared publications:
- Dmitriy Drusvyatskiy
Department of Mathematics, U. Washington, Seattle, USA
4 shared publications - Ting Kei Pong
Department of Applied Mathematics The Hong Kong Polytechnic University Hong Kong China
4 shared publications - Levent Tunçel
Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
3 shared publications Danilo Elias Oliveira
University of Waterloo
2 shared publications- Ningchuan Wang
University of Waterloo
2 shared publications - Stephen A. Vavasis
Department of Combinatorics and Optimization Waterloo University of Waterloo N2L 3G1 Ontario Canada
2 shared publications
Latest Publications
- 8 March 2025
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 91 (1) , 235-282
The $\omega $-condition number: applications to preconditioning and low rank generalized Jacobian updating- 8 March 2025
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 91 (1) , 235-282
The $\omega $-condition number: applications to preconditioning and low rank generalized Jacobian updating- Open Access
- 8 September 2022
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 6, 792
Robust Interior Point Method for Quantum Key Distribution Rate Computation
Security proof methods for quantum key distribution, QKD, that are based on the numerical key rate calculation problem, are powerful in principle. However, the practicality of the methods are limited by computational resources and the efficiency and accuracy of the underlying algorithms for convex optimization. We derive a stable reformulation of the convex nonlinear semidefinite programming, SDP, model for the key rate calculation problems. We use this to develop an efficient, accurate algorithm. The stable reformulation is based on novel forms of facial reduction, FR, for both the linear constraints and nonlinear quantum relative entropy objective function. This allows for a Gauss-Newton type interior-point approach that avoids the need for perturbations to obtain strict feasibility, a technique currently used in the literature. The result is high accuracy solutions with theoretically proven lower bounds for the original QKD from the FR stable reformulation. This provides novel contributions for FR for general SDP. We report on empirical results that dramatically improve on speed and accuracy, as well as solving previously intractable problems.
- 8 September 2022
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 6, 792
Open AccessRobust Interior Point Method for Quantum Key Distribution Rate Computation
Security proof methods for quantum key distribution, QKD, that are based on the numerical key rate calculation problem, are powerful in principle. However, the practicality of the methods are limited by computational resources and the efficiency and accuracy of the underlying algorithms for convex optimization. We derive a stable reformulation of the convex nonlinear semidefinite programming, SDP, model for the key rate calculation problems. We use this to develop an efficient, accurate algorithm. The stable reformulation is based on novel forms of facial reduction, FR, for both the linear constraints and nonlinear quantum relative entropy objective function. This allows for a Gauss-Newton type interior-point approach that avoids the need for perturbations to obtain strict feasibility, a technique currently used in the literature. The result is high accuracy solutions with theoretically proven lower bounds for the original QKD from the FR stable reformulation. This provides novel contributions for FR for general SDP. We report on empirical results that dramatically improve on speed and accuracy, as well as solving previously intractable problems.
- 22 January 2021
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 78 (3) , 853-891
A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem
- 22 January 2021
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 78 (3) , 853-891
A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem
- Open Access
Parametric Convex Quadratic Relaxation of the Quadratic Knapsac Problem
We consider a parametric convex quadratic programming, CQP, relaxation for the quadratic knapsack problem, QKP. This relaxation maintains partial quadratic information from the original QKP by perturbing the objective function to obtain a concave quadratic term. The nonconcave part generated by the perturbation is then linearized by a standard approach that lifts the problem to the matrix space. We present a primal-dual interior point method to optimize the perturbation of the quadratic function, in a search for the tightest upper bound for the \QKPp. We prove that the same perturbation approach, when applied in the context of semidefinite programming, SDP, relaxations of the QKP, cannot improve the upper bound given by the corresponding linear \SDP relaxation. The result also applies to more general integer quadratic problems. Finally, we propose new valid inequalities on the lifted matrix variable, derived from cover and knapsack inequalities for the QKP, and present the separation problems to generate cuts for the current solution of the CQP relaxation. Our best bounds are obtained from alternating between optimizing the parametric quadratic relaxation over the perturbation and adding cutting planes generated by the valid inequalities proposed.
Open AccessParametric Convex Quadratic Relaxation of the Quadratic Knapsac Problem
We consider a parametric convex quadratic programming, CQP, relaxation for the quadratic knapsack problem, QKP. This relaxation maintains partial quadratic information from the original QKP by perturbing the objective function to obtain a concave quadratic term. The nonconcave part generated by the perturbation is then linearized by a standard approach that lifts the problem to the matrix space. We present a primal-dual interior point method to optimize the perturbation of the quadratic function, in a search for the tightest upper bound for the \QKPp. We prove that the same perturbation approach, when applied in the context of semidefinite programming, SDP, relaxations of the QKP, cannot improve the upper bound given by the corresponding linear \SDP relaxation. The result also applies to more general integer quadratic problems. Finally, we propose new valid inequalities on the lifted matrix variable, derived from cover and knapsack inequalities for the QKP, and present the separation problems to generate cuts for the current solution of the CQP relaxation. Our best bounds are obtained from alternating between optimizing the parametric quadratic relaxation over the perturbation and adding cutting planes generated by the valid inequalities proposed.
- 20 September 2018
- Published by Springer Nature in Mathematical Programming Computation
- Vol. 10 (4) , 631-658
ADMM for the SDP relaxation of the QAP
- 20 September 2018
- Published by Springer Nature in Mathematical Programming Computation
- Vol. 10 (4) , 631-658
ADMM for the SDP relaxation of the QAP
- 20 December 2017
- Published by Emerald Publishing in Foundations and Trends® in Optimization
- Vol. 3 (2) , 77-170
The Many Faces of Degeneracy in Conic Optimization
Slater’s condition – existence of a “strictly feasible solution” – is a common assumption in conic optimization. Without strict feasibility, first-order optimality conditions may be meaningless, the dual problem may yield little information about the primal, and small changes in the data may render the problem infeasible. Hence, failure of strict feasibility can negatively impact off-the-shelf numerical methods, such as primal-dual interior point methods, in particular. New optimization modeling techniques and convex relaxations for hard nonconvex problems have shown that the loss of strict feasibility is a more pronounced phenomenon than has previously been realized. In this text, we describe various reasons for the loss of strict feasibility, whether due to poor modeling choices or (more interestingly) rich underlying structure, and discuss ways to cope with it and, in many pronounced cases, how to use it as an advantage. In large part, we emphasize the facial reduction preprocessing technique due to its mathematical elegance, geometric transparency, and computational potential.
- 20 December 2017
- Published by Emerald Publishing in Foundations and Trends® in Optimization
- Vol. 3 (2) , 77-170
The Many Faces of Degeneracy in Conic Optimization
Slater’s condition – existence of a “strictly feasible solution” – is a common assumption in conic optimization. Without strict feasibility, first-order optimality conditions may be meaningless, the dual problem may yield little information about the primal, and small changes in the data may render the problem infeasible. Hence, failure of strict feasibility can negatively impact off-the-shelf numerical methods, such as primal-dual interior point methods, in particular. New optimization modeling techniques and convex relaxations for hard nonconvex problems have shown that the loss of strict feasibility is a more pronounced phenomenon than has previously been realized. In this text, we describe various reasons for the loss of strict feasibility, whether due to poor modeling choices or (more interestingly) rich underlying structure, and discuss ways to cope with it and, in many pronounced cases, how to use it as an advantage. In large part, we emphasize the facial reduction preprocessing technique due to its mathematical elegance, geometric transparency, and computational potential.
- 27 November 2017
- Published by Springer Nature in Journal of Global Optimization
- Vol. 72 (1) , 5-26
Low-rank matrix completion using nuclear norm minimization and facial reduction
- 27 November 2017
- Published by Springer Nature in Journal of Global Optimization
- Vol. 72 (1) , 5-26
Low-rank matrix completion using nuclear norm minimization and facial reduction
- Open Access
- 14 April 2017
- Published by Brazilian Society for Computational and Applied Mathematics (SBMAC) in Proceeding Series of the Brazilian Society of Computational and Applied Mathematics
- Vol. 5 (1)
MMDA na resolução da relaxação por Programação Semidefinida do Problema Quadrático de Alocação
A relaxação por Programação Semidefinida (PSD) já demonstrou ser extrema- mente útil para muitos problemas difı́ceis da Otimização Discreta. Em especial, para o problema quadrático de alocação (PQA), conhecido por ser um dos problemas mais difı́ceis da classe NP-hard da Otimização Combinatória. Várias são as dificuldades encontradas ao se resolver a relaxação por PSD através dos métodos atuais. Neste trabalho, propomos a utilização do método do multiplicadores com direção alternada (MMDA) para resolver a relaxação por PSD do PQA. Obtemos, assim, iterações mais rápidas; um método rápido para se obter soluções com posto deficiente; e, também, uma forma simples de se adicionar desigualdades de planos de corte. Em nossos experimentos numéricos, obtivemos resultados mais robustos, eficientes e melhores aproximações para as soluções do PQA.
- 14 April 2017
- Published by Brazilian Society for Computational and Applied Mathematics (SBMAC) in Proceeding Series of the Brazilian Society of Computational and Applied Mathematics
- Vol. 5 (1)
Open AccessMMDA na resolução da relaxação por Programação Semidefinida do Problema Quadrático de Alocação
A relaxação por Programação Semidefinida (PSD) já demonstrou ser extrema- mente útil para muitos problemas difı́ceis da Otimização Discreta. Em especial, para o problema quadrático de alocação (PQA), conhecido por ser um dos problemas mais difı́ceis da classe NP-hard da Otimização Combinatória. Várias são as dificuldades encontradas ao se resolver a relaxação por PSD através dos métodos atuais. Neste trabalho, propomos a utilização do método do multiplicadores com direção alternada (MMDA) para resolver a relaxação por PSD do PQA. Obtemos, assim, iterações mais rápidas; um método rápido para se obter soluções com posto deficiente; e, também, uma forma simples de se adicionar desigualdades de planos de corte. Em nossos experimentos numéricos, obtivemos resultados mais robustos, eficientes e melhores aproximações para as soluções do PQA.
- 1 January 2016
- Published by Emerald Publishing in Foundations and Trends® in Optimization
- Vol. 3 (2) , 77-170
The Many Faces of Degeneracy in Conic Optimization
Publishers of Foundations and Trends, making research accessible
- 1 January 2016
- Published by Emerald Publishing in Foundations and Trends® in Optimization
- Vol. 3 (2) , 77-170
The Many Faces of Degeneracy in Conic Optimization
Publishers of Foundations and Trends, making research accessible
- Open Access
ADMM for the SDP relaxation of the QAP
The semidefinite programming (SDP) relaxation has proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem (QAP), arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g.,~increased dimension; inefficiency of the current primal-dual interior point solvers in terms of both time and accuracy; and difficulty and high expense in adding cutting plane constraints. We propose using the alternating direction method of multipliers (ADMM) to solve the SDP relaxation. This first order approach allows for inexpensive iterations, a method of cheaply obtaining low rank solutions, as well a trivial way of adding cutting plane inequalities. When compared to current approaches and current best available bounds we obtain remarkable robustness, efficiency and improved bounds.
Open AccessADMM for the SDP relaxation of the QAP
The semidefinite programming (SDP) relaxation has proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem (QAP), arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g.,~increased dimension; inefficiency of the current primal-dual interior point solvers in terms of both time and accuracy; and difficulty and high expense in adding cutting plane constraints. We propose using the alternating direction method of multipliers (ADMM) to solve the SDP relaxation. This first order approach allows for inexpensive iterations, a method of cheaply obtaining low rank solutions, as well a trivial way of adding cutting plane inequalities. When compared to current approaches and current best available bounds we obtain remarkable robustness, efficiency and improved bounds.