BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Henry Wolkowicz

Henry Wolkowicz appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCmath.COData Structures and Algorithmsmath.AGmath.NAquant-phSystems and Control

Catalog footprint

What is connected

13works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2023arXiv

Revisiting Degeneracy, Strict Feasibility, Stability, in Linear Programming

Currently, the simplex method and the interior point method are indisputably the most popular algorithms for solving linear programs, LPs. Unlike general conic programs, LPs with a finite optimal value do not require strict feasibility in order to establish strong duality. Hence strict feasibility is seldom a concern, even though strict feasibility is equivalent to stability and a compact dual optimal set. This lack of concern is also true for other types of degeneracy of basic feasible solutions in LP. In this paper we discuss that the specific degeneracy that arises from lack of strict feasibility necessarily causes difficulties in both simplex and interior point methods. In particular, we show that the lack of strict feasibility implies that every basic feasible solution, BFS, is degenerate; thus conversely, the existence of a nondegenerate BFS implies that strict feasibility (regularity) holds. We prove the results using facial reduction and simple linear algebra. In particular, the facially reduced system reveals the implicit non-surjectivity of the linear map of the equality constraint system. As a consequence, we emphasize that facial reduction involves two steps where, the first guarantees strict feasibility, and the second recovers full row rank of the constraint matrix. This illustrates the implicit singularity of problems where strict feasibility fails, and also helps in obtaining new efficient techniques for preproccessing. We include an efficient preprocessing method that can be performed as an extension of phase-I of the two-phase simplex method. We show that this can be used to avoid the loss of precision for many well known problem sets in the literature, e.g., the NETLIB problem set.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Facial Reduction for Symmetry Reduced Semidefinite Doubly Nonnegative Programs

We consider both facial reduction, \FRp, and symmetry reduction, \SRp, techniques for semidefinite programming, \SDPp. We show that the two together fit surprisingly well in an alternating direction method of multipliers, \ADMMp, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, \DNN, relaxation of many classes of hard combinatorial problems. We also show that the singularity degree remains the same after \SRp, and that the \DNN relaxations considered here have singularity degree one, that is reduced to zero after \FRp. The combination of \FR and \SR leads to a significant improvement in both numerical stability and running time for both the \ADMM and interior point approaches. We test our method on various \DNN relaxations of hard combinatorial problems including quadratic assignment problems with sizes of more than $n=500$. This translates to a semidefinite constraint of order $250,000$ and $625\times 10^8$ nonnegative constrained variables, before applying the reduction techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Computing the generators of the truncated real radical ideal by moment matrices and SDP facial reduction

Recent breakthroughs have been made in the use of semidefinite programming and its application to real polynomial solving. For example, the real radical of a zero dimensional ideal, can be determined by such approaches as shown by Lasserre and collaborators. Some progress has been made on the determination of the real radical in positive dimension by Ma, Wang and Zhi. Such work involves the determination of maximal rank semidefinite moment matrices. Existing methods are computationally expensive and have poorer accuracy on larger examples. This paper is motivated by problems in the numerical computation of the real radical ideal in the general positive case. In this paper we give a method to compute the generators of the real radical for any given degree $d$. We combine the use of moment matrices and techniques from SDP optimization: facial reduction first developed by Borwein and Wolkowicz. In use of the semidefinite moment matrices to compute the real radical, the maximum rank property is very key, and with facial reduction, it can be guaranteed with very high accuracy. Our algorithm can be used to test the real radical membership of a given polynomial. In a special situation, we can determine the real radical ideal in the positive dimensional case.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Low-Rank Matrix Completion using Nuclear Norm with Facial Reduction

Minimization of the nuclear norm is often used as a surrogate, convex relaxation, for finding the minimum rank completion (recovery) of a partial matrix. The minimum nuclear norm problem can be solved as a trace minimization semidefinite programming problem, (SDP). The SDP and its dual are regular in the sense that they both satisfy strict feasibility. Interior point algorithms are the current methods of choice for these problems. This means that it is difficult to solve large scale problems and difficult to get high accuracy solutions. In this paper we take advantage of the structure at optimality for the minimum nuclear norm problem. We show that even though strict feasibility holds, the facial reduction framework can be successfully applied to obtain a proper face that contains the optimal set, and thus can dramatically reduce the size of the final nuclear norm problem while guaranteeing a low-rank solution. We include numerical tests for both exact and noisy cases. In all cases we assume that knowledge of a target rank is available.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Facial Reduction and SDP Methods for Systems of Polynomial Equations

The real radical ideal of a system of polynomials with finitely many complex roots is generated by a system of real polynomials having only real roots and free of multiplicities. It is a central object in computational real algebraic geometry and important as a preconditioner for numerical solvers. Lasserre and co-workers have shown that the real radical ideal of real polynomial systems with finitely many real solutions can be determined by a combination of semi-definite programming (SDP) and geometric involution techniques. A conjectured extension of such methods to positive dimensional polynomial systems has been given recently by Ma, Wang and Zhi. We show that regularity in the form of the Slater constraint qualification (strict feasibility) fails for the resulting SDP feasibility problems. Facial reduction is then a popular technique whereby SDP problems that fail strict feasibility can be regularized by projecting onto a face of the convex cone of semi-definite problems. In this paper we introduce a framework for combining facial reduction with such SDP methods for analyzing $0$ and positive dimensional real ideals of real polynomial systems. The SDP methods are implemented in MATLAB and our geometric involutive form is implemented in Maple. We use two approaches to find a feasible moment matrix. We use an interior point method within the CVX package for MATLAB and also the Douglas-Rachford (DR) projection-reflection method. Illustrative examples show the advantages of the DR approach for some problems over standard interior point methods. We also see the advantage of facial reduction both in regularizing the problem and also in reducing the dimension of the moment matrices. Problems requiring more than one facial reduction are also presented.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Noisy Euclidean distance realization: robust facial reduction and the Pareto frontier

We present two algorithms for large-scale low-rank Euclidean distance matrix completion problems, based on semidefinite optimization. Our first method works by relating cliques in the graph of the known distances to faces of the positive semidefinite cone, yielding a combinatorial procedure that is provably robust and parallelizable. Our second algorithm is a first order method for maximizing the trace---a popular low-rank inducing regularizer---in the formulation of the problem with a constrained misfit. Both of the methods output a point configuration that can serve as a high-quality initialization for local optimization techniques. Numerical experiments on large-scale sensor localization problems illustrate the two approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Eigenvalue, Quadratic Programming, and Semidefinite Programming Bounds for a Cut Minimization Problem

We consider the problem of partitioning the node set of a graph into $k$ sets of given sizes in order to \emph{minimize the cut} obtained using (removing) the $k$-th set. If the resulting cut has value $0$, then we have obtained a vertex separator. This problem is closely related to the graph partitioning problem. In fact, the model we use is the same as that for the graph partitioning problem except for a different \emph{quadratic} objective function. We look at known and new bounds obtained from various relaxations for this NP-hard problem. This includes: the standard eigenvalue bound, projected eigenvalue bounds using both the adjacency matrix and the Laplacian, quadratic programming (QP) bounds based on recent successful QP bounds for the quadratic assignment problems, and semidefinite programming bounds. We include numerical tests for large and \emph{huge} problems that illustrate the efficiency of the bounds in terms of strength and time.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Projection methods in quantum information science

We consider the problem of constructing quantum operations or channels, if they exist, that transform a given set of quantum states $\{ρ_1, \dots, ρ_k\}$ to another such set $\{\hatρ_1, \dots, \hatρ_k\}$. In other words, we must find a {\em completely positive linear map}, if it exists, that maps a given set of density matrices to another given set of density matrices. This problem, in turn, is an instance of a positive semi-definite feasibility problem, but with highly structured constraints. The nature of the constraints makes projection based algorithms very appealing when the number of variables is huge and standard interior point-methods for semi-definite programming are not applicable. We provide emperical evidence to this effect. We moreover present heuristics for finding both high rank and low rank solutions. Our experiments are based on the \emph{method of alternating projections} and the \emph{Douglas-Rachford} reflection method.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions

The sensor network localization, SNL, problem in embedding dimension r, consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming, SDP, completion problem, by using the linear mapping between Euclidean distance matrices, EDM, and semidefinite matrices. The resulting SDP is solved using primal-dual interior point solvers, yielding an expensive and inexact solution. This relaxation is highly degenerate in the sense that the feasible set is restricted to a low dimensional face of the SDP cone, implying that the Slater constraint qualification fails. Cliques in the graph of the SNL problem give rise to this degeneracy in the SDP relaxation. In this paper, we take advantage of the absence of the Slater constraint qualification and derive a technique for the SNL problem, with exact data, that explicitly solves the corresponding rank restricted SDP problem. No SDP solvers are used. For randomly generated instances, we are able to efficiently solve many huge instances of this NP-hard problem to high accuracy, by finding a representation of the minimal face of the SDP cone that contains the SDP matrix representation of the EDM. The main work of our algorithm consists in repeatedly finding the intersection of subspaces that represent the faces of the SDP cone that correspond to cliques of the SNL problem.

0 citations0 reviewsNo code linkedOpen access