Henry Wolkowicz – Optimization Online

Optimal Nonergodic Primal-Dual Complexity of Efficient Inexact Parameter-Free Augmented Lagrangian Methods

Published: 2026/08/04, Updated: 2026/08/10

Augmented Lagrangian (AL) methods are a classical framework for constrained optimization, but for directly verifiable approximate KKT points, known first-order complexity bounds for standard inexact AL methods are suboptimal, while the best known proximal augmented Lagrangian (PAL) bounds retain an additional logarithmic factor. We consider linearly constrained convex composite problems with a smooth convex term … Read more

Optimal diagonal preconditioning beyond worst-case conditioning: theory and practice of omega scaling

Published: 2025/09/27, Updated: 2026/05/14

Convex and Nonsmooth Optimization, Nonsmooth Optimization, Optimization in Data Science nonconvex nonsmooth optimization, optimal diagonal preconditioner, preconditioning, pseudoconvex function, subgradient method

Preconditioning is essential in many areas of mathematics, and in particular is a fundamental tool for accelerating iterative methods for solving linear systems. In this work, we study optimal diagonal preconditioning under two distinct notions of conditioning: the classical worst-case \(\kappa\)-condition number and the averaging-based \(\omega\)-condition number. We observe that \(\omega\)-optimal preconditioning generally outperforms \(\kappa\)-optimal … Read more

A necessary condition for the guarantee of the superiorization method

Published: 2025/02/06

Biomedical Applications, Constrained Nonlinear Optimization, Convex Optimization bounded perturbations resilience, dynamic string-averaging, feasibility-seeking, guarantee question of superiorization, strict Fejér monotonicity, superiorization

We study a method that involves principally convex feasibility-seeking and makes secondary efforts of objective function value reduction. This is the well-known superiorization method (SM), where the iterates of an asymptotically convergent iterative feasibility-seeking algorithm are perturbed by objective function nonascent steps. We investigate the question under what conditions a sequence generated by an SM … Read more

Exact Solutions for the NP-hard Wasserstein Barycenter Problem using a Doubly Nonnegative Relaxation and a Splitting Method

Published: 2023/11/06, Updated: 2024/08/26

Combinatorial Optimization, Meta Heuristics, Semi-definite Programming

The simplified Wasserstein barycenter problem, also known as the cheapest hub problem, consists in selecting one point from each of \(k\) given sets, each set consisting of \(n\) points, with the aim of minimizing the sum of distances to the barycenter of the \(k\) chosen points. This problem is also known as the cheapest hub … Read more

Preconditioning for Generelized Jacobians with the ω-Condition Number

Published: 2023/09/29

Nonsmooth Optimization, Other Topics generalized jacobian, iterative methods, preconditioning, ω-condition number

Preconditioning is essential in iterative methods for solving linear systems of equations. We study a nonclassic matrix condition number, the ω-condition number, in the context of optimal conditioning for low rank updating of positive definite matrices. For a positive definite matrix, this condition measure is the ratio of the arithmetic and geometric means of the … Read more

Singularity degree of non-facially exposed faces

Published: 2022/12/28

Linear, Cone and Semidefinite Programming, Semi-definite Programming

In this paper, we study the facial structure of the linear image of a cone. We define the singularity degree of a face of a cone to be the minimum number of steps it takes to expose it using exposing vectors from the dual cone. We show that the singularity degree of the linear image … Read more

Regularized Nonsmooth Newton Algorithms for Best Approximation

Published: 2022/12/20

Convex Optimization, Linear Programming, Nonsmooth Optimization best approximation, constrained linear least squares., Halperin-Lions-Wittmann-Bauschke algorithm, nonsmooth and semismooth methods, projection methods, sparse large-scale linear programming

We consider the problem of finding the best approximation point from a polyhedral set, and its applications, in particular to solving large-scale linear programs. The classical projection problem has many various and many applications. We study a regularized nonsmooth Newton type solution method where the Jacobian is singular; and we compare the computational performance to … Read more

Revisiting Degeneracy, Strict Feasibility, Stability, in Linear Programming

Published: 2022/03/04, Updated: 2023/01/09

Applications - OR and Management Sciences, Linear Programming degeneracy, facial reduction, implicit problem singularity, linear programming, max-singularity degree, preprocessing, singularity degree

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 … Read more

A Semismooth Newton-Type Method for the Nearest Doubly Stochastic Matrix Problem

Published: 2021/07/19

Convex and Nonsmooth Optimization, Nonsmooth Optimization equivalence class, nearest doubly stochastic matrix, quadratic convergence, semismooth newton method, strongly semismooth

We study a semismooth Newton-type method for the nearest doubly stochastic matrix problem where both differentiability and nonsingularity of the Jacobian can fail. The optimality conditions for this problem are formulated as a system of strongly semismooth functions. We show that the so-called local error bound condition does not hold for this system. Thus the … Read more

A Strengthened Barvinok-Pataki Bound on SDP Rank

Published: 2021/04/19

Semi-definite Programming barvinok-pataki bound, facial reduction, rank, semidefinite programming, singularity degree

The Barvinok-Pataki bound provides an upper bound on the rank of extreme points of a spectrahedron. This bound depends solely on the number of affine constraints of the problem, i.e., on the algebra of the problem. Specifically, the triangular number of the rank r is upper bounded by the number of affine constraints. We revisit … Read more