Search

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 algorithm asymptotically converges to a feasible point whose objective function value is superior (meaning smaller or equal) to that of a feasible point reached by the corresponding unperturbed one (i.e., the exactly same feasibility-seeking algorithm that the SM algorithm employs.) This question is yet only partially answered in the literature. We present a condition under which an SM algorithm that uses negative gradient descent steps in its perturbations fails to yield such a superior outcome. The significance of the discovery of this negative condition is that it necessitates that the inverse of this condition will have to be assumed to hold in any future guarantee result for the SM. The condition is important for practitioners who use the SM because it is avoidable in experimental work with the SM, thus increasing the success rate of the method in real-world applications., Comment: 17 pages. Accepted for publication in the journal "Optimization Letters". arXiv admin note: text overlap with arXiv:2212.14724

Finding zeros of the sum of two maximally monotoneoperators involving a continuous linear operator is a central problem in optimization and monotone operator theory. We revisit the duality framework proposed by Eckstein, Ferris, Pennanen, and Robinson from a quarter of a century ago. Paramonotonicity is identified as a broad condition ensuring that saddle points coincide with the closed convex rectangle formed by the primal and dual solutions. Additionally, we characterize total duality in the subdifferential setting and derive projection formulas for sets that arise in the analysis of the Chambolle-Pock algorithm within the recent framework developed by Bredies, Chenchene, Lorenz, and Naldi.

The ever-increasing demand for higher data rates in communication systems intensifies the need for advanced non-linear equalizers capable of higher performance. Recently artificial neural networks (ANNs) were introduced as a viable candidate for advanced non-linear equalizers, as they outperform traditional methods. However, they are computationally complex and therefore power hungry. Spiking neural networks (SNNs) started to gain attention as an energy-efficient alternative to ANNs. Recent works proved that they can outperform ANNs at this task. In this work, we explore the design space of an SNN-based decision-feedback equalizer (DFE) to reduce its computational complexity for an efficient implementation on field programmable gate array (FPGA). Our Results prove that it achieves higher communication performance than ANN-based DFE at roughly the same throughput and at 25X higher energy efficiency., Comment: accepted for publication in IEEE Middle East Conference on Communications and Networking (MECOM 2024). November, 2024

Facial reduction, FR, is a regularization technique for convex programs where the strict feasibility constraint qualification, CQ, fails. Though this CQ holds generically, failure is pervasive in applications such as semidefinite relaxations of hard discrete optimization problems. In this paper we relate FR to the analysis of the convergence behaviour of a semi-smooth Newton root finding method for the projection onto a spectrahedron, i.e., onto the intersection of a linear manifold and the semidefinite cone. In the process, we derive and use an elegant formula for the projection onto a face of the semidefinite cone. We show further that the ill-conditioning of the Jacobian of the Newton method near optimality characterizes the degeneracy of the nearest point in the spectrahedron. We apply the results, both theoretically and empirically, to the problem of finding nearest points to the sets of: (i) correlation matrices or the elliptope; and (ii) semidefinite relaxations of permutation matrices or the vontope, i.e., the feasible sets for the semidefinite relaxations of the max-cut and quadratic assignment problems, respectively.

The \emph{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 problem. This problem is known to be NP-hard. We compute the Wasserstein barycenter by exploiting the Euclidean distance matrix structure to obtain a facially reduced doubly nonnegative, \DNNp, relaxation. The facial reduction provides a natural splitting for applying the symmetric alternating directions method of multipliers (\sADMM) to the \DNN relaxation. The \sADMM method exploits structure in the subproblems to find strong upper and lower bounds. In addition, we extend the problem to allow varying $n_j$ points for the $j$-th set. The purpose of this paper is twofold. First we want to illustrate the strength of this \DNN relaxation with a splitting approach. Our numerical tests then illustrate the surprising success on random problems, as we generally, efficiently, find the provable exact solution of this NP-hard problem. Comparisons with current commercial software illustrate this surprising efficiency. However, we demonstrate and prove that there is a duality gap for problems with \emph{enough} multiple optimal solutions, and that this arises from problems with highly symmetrized structure.

The $O(1/k^2)$ convergence rate in function value of accelerated gradient descent is optimal, but there are many modifications that have been used to speed up convergence in practice. Among these modifications are restarts, that is, starting the algorithm with the current iteration being considered as the initial point. We focus on the adaptive restart techniques introduced by O'Donoghue and Cand\`es, specifically their gradient restart strategy. While the gradient restart strategy is a heuristic in general, we prove that applying gradient restarts preserves and in fact improves the $O(1/k^2)$ bound, hence establishing function value convergence, for one-dimensional functions. Applications of our results to separable and nearly separable functions are presented.

Primal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al.\ analyzed the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions. Their analysis hinges on the notion of the infimal displacement vector in the closure of the range of the displacement mapping of the splitting operator that encodes the PDHG algorithm. In this paper, we develop a novel formula for this range using monotone operator theory. The analysis is then specialized to conic programming and further to quadratic programming (QP) and second-order cone programming (SOCP). A consequence of our analysis is that PDHG is able to diagnose infeasible or unbounded instances of QP and of the ellipsoid-separation problem, a subclass of SOCP.

Monotone inclusion problems occur in many areas of optimization and variational analysis. Splitting methods, which utilize resolvents or proximal mappings of the underlying operators, are often applied to solve these problems. In 2022, Bredies, Chenchene, Lorenz, and Naldi introduced a new elegant algorithmic framework that encompasses various well known algorithms including Douglas-Rachford and Chambolle-Pock. They obtained powerful weak and strong convergence results, where the latter type relies on additional strong monotonicity assumptions. In this paper, we complement the analysis by Bredies et al. by relating the projections of the fixed point sets of the underlying operators that generate the (reduced and original) preconditioned proximal point sequences. We also obtain strong convergence results in the case of linear relations. Various examples are provided to illustrate the applicability of our results.

Projection operators are fundamental algorithmic operators in Analysis and Optimization. It is well known that these operators are firmly nonexpansive; however, their composition is generally only averaged and no longer firmly nonexpansive. In this note, we introduce the modulus of averagedness and provide an exact result for the composition of two linear projection operators. As a consequence, we deduce that the Ogura-Yamada bound for the modulus of the composition is sharp.

We explore the relationship between the dual of a weighted minimum-energy control problem, a special case of linear-quadratic optimal control problems, and the Douglas-Rachford (DR) algorithm. We obtain an expression for the fixed point of the DR operator as applied to solving the optimal control problem, which in turn devises a certificate of optimality that can be employed for numerical verification. The fixed point and the optimality check are illustrated in an example optimal control problem.

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 that of the classical projection method of Halperin-Lions-Wittmann-Bauschke (HLWB). We observe empirically that the regularized nonsmooth method significantly outperforms the HLWB method. However, the HLWB has a convergence guarantee while the nonsmooth method is not monotonic and does not guarantee convergence due in part to singularity of the generalized Jacobian. Our application to solving large-scale linear programs uses a parametrized projection problem. This leads to a \emph{stepping stone external path following} algorithm. Other applications are finding triangles from branch and bound methods, and generalized constrained linear least squares. We include scaling methods that improve the efficiency and robustness., Comment: 38 pages, 7 tables, 8 figures

Let $A$ be a closed affine subspace and let $B$ be a hyperplane in a Hilbert space. Suppose we are given their associated nearest point mappings $P_A$ and $P_B$, respectively. We present a formula for the projection onto their intersection $A\cap B$. As a special case, we derive a formula for the projection onto the intersection of two hyperplanes. These formulas provides useful information even if $A\cap B$ is empty. Examples and numerical experiments are also provided.

The Douglas-Rachford algorithm is one of the most prominent splitting algorithms for solving convex optimization problems. Recently, the method has been successful in finding a generalized solution (provided that one exists) for optimization problems in the inconsistent case, i.e., when a solution does not exist. The convergence analysis of the inconsistent case hinges on the study of the range of the displacement operator associated with the Douglas-Rachford splitting operator and the corresponding minimal displacement vector. In this paper, we provide a formula for the range of the Douglas-Rachford splitting operator in (possibly) infinite-dimensional Hilbert space under mild assumptions on the underlying operators. Our new results complement known results in finite-dimensional Hilbert spaces. Several examples illustrate and tighten our conclusions.

The correspondence between the class of nonexpansive mappings and the class of maximally monotone operators via the reflected resolvents of the latter has played an instrumental role in the convergence analysis of the splitting methods. Indeed, the performance of some of these methods, e.g., Douglas-Rachford and Peaceman-Rachford methods hinges on iterating the so-called splitting operator associated with the individual operators. This splitting operator is a function of the composition of the reflected resolvents of the underlying operators. In this paper, we provide a comprehensive study of the class of uniformly monotone operators and their corresponding reflected resolvents. We show that the latter is closely related to the class of the strongly nonexpansive operators introduced by Bruck and Reich. Connections to duality via inverse operators are systematically studied. We provide applications to Douglas-Rachford and Peaceman-Rachford methods. Examples that illustrate and tighten our results are presented.

The Douglas-Rachford and Peaceman-Rachford algorithms have been successfully employed to solve convex optimization problems, or more generally find zeros of monotone inclusions. Recently, the behaviour of these methods in the inconsistent case, i.e., in the absence of solutions has triggered significant consideration. It has been shown that under mild assumptions the shadow sequence of the Douglas-Rachford algorithm converges weakly to a generalized solution when the underlying operators are subdifferentials of proper lower semicontinuous convex functions. However, no convergence behaviour has been proved in the case of Peaceman-Rachford algorithm. In this paper, we prove the convergence of the shadow sequences associated with the Douglas-Rachford algorithm and Peaceman-Rachford algorithm when one of the operators is uniformly monotone and $3^*$ monotone but not necessarily a subdifferential. Several examples illustrate and strengthen our conclusion. We carry out numerical experiments using example instances of optimization problems.