The aim of this paper is to introduce a new code for the solution of large-and-sparse linear semidefinite programs (SDPs) with low-rank solutions or solutions with few outlying eigenvalues, and/or problems with low-ra...
详细信息
The aim of this paper is to introduce a new code for the solution of large-and-sparse linear semidefinite programs (SDPs) with low-rank solutions or solutions with few outlying eigenvalues, and/or problems with low-rank data. We propose to use a preconditioned conjugate gradient method within an interior-point SDP algorithm and an efficient preconditioner fully utilizing the low-rank information. The efficiency is demonstrated by numerical experiments using the truss topology optimization problems, Lasserre relaxations of the MAXCUT problems and the sensor network localization problems.
Quantum relative entropy (QRE) programming is a recently popular and challenging class of convex optimization problems with significant applications in quantum computing and quantum information theory. We are interest...
详细信息
Quantum relative entropy (QRE) programming is a recently popular and challenging class of convex optimization problems with significant applications in quantum computing and quantum information theory. We are interested in modern interior-point (IP) methods based on optimal self-concordant barriers for the QRE cone. A range of theoretical and numerical challenges associated with such barrier functions and the QRE cones have hindered the scalability of IP methods. To address these challenges, we propose a series of numerical and linear algebraic techniques and heuristics aimed at enhancing the efficiency of gradient and Hessian computations for the self-concordant barrier function, solving linear systems, and performing matrix-vector products. We also introduce and deliberate about some interesting concepts related to QRE such as symmetric quantum relative entropy. We design a two-phase method for performing facial reduction that can significantly improve the performance of QRE programming. Our new techniques have been implemented in the latest version (DDS 2.2) of the software package Domain-Driven Solver (DDS). In addition to handling QRE constraints, DDS accepts any combination of several other conic and nonconic convex constraints. Our comprehensive numerical experiments encompass several parts, including (1) a comparison of DDS 2.2 with Hypatia for the nearest correlation matrix problem, (2) using DDS 2.2 for combining QRE constraints with various other constraint types, and (3) calculating the key rate for quantum key distribution (QKD) channels and presenting results for several QKD protocols.
In this paper, we investigate a new primal-dual long-step interiorpoint algorithm for linear optimization. Based on the step size, interiorpoint algorithms can be divided into two main groups, short-step, and long-s...
详细信息
In this paper, we investigate a new primal-dual long-step interiorpoint algorithm for linear optimization. Based on the step size, interiorpoint algorithms can be divided into two main groups, short-step, and long-step methods. In practice, long-step variants perform better, but usually, a better theoretical complexity can be achieved for the short-step methods. One of the exceptions is the large-update algorithm of Ai and Zhang. The new wide neighborhood and the main characteristics of the presented algorithm are based on their approach. In addition, we use the algebraic equivalent transformation technique of Darvay to determine new modified search directions for our method. We show that the new long-step algorithm is convergent and has the best known iteration complexity of short-step variants. We present our numerical results and compare the performance of our algorithm with two previously introduced Ai-Zhang type interiorpoint algorithms on a set of linearprogramming test problems from the Netlib library.
In this paper, we propose a new long-step interiorpoint method for solving sufficient linear complementarity problems. The new algorithm combines two important approaches from the literature: the main ideas of the lo...
详细信息
In this paper, we propose a new long-step interiorpoint method for solving sufficient linear complementarity problems. The new algorithm combines two important approaches from the literature: the main ideas of the long-step interiorpoint algorithm introduced by Ai and Zhang and the algebraic equivalent transformation technique proposed by Darvay. Similar to the method of Ai and Zhang, our algorithm also works in a wide neighborhood of the central path and has the best known iteration complexity of short-step variants. However, due to the properties of the applied transforming function in Darvay's technique, the wide neighborhood definition in the analysis depends on the value of the handicap. We implemented not only the theoretical algorithm but a greedy variant of the new method (working in a neighborhood independent of the handicap) in MATLAB and tested its efficiency on both sufficient and non-sufficient problem instances. In addition to presenting our numerical results, we also make some interesting observations regarding the analysis of Ai-Zhang type methods.
In this work, in the context of linear and convex Quadratic programming, we consider Primal Dual Regularized interiorpointmethods (PDR-IPMs) in the framework of the Proximal point Method. The resulting Proximal Stab...
详细信息
In this work, in the context of linear and convex Quadratic programming, we consider Primal Dual Regularized interiorpointmethods (PDR-IPMs) in the framework of the Proximal point Method. The resulting Proximal Stabilized IPM (PS-IPM) is strongly supported by theoretical results concerning convergence and the rate of convergence, and can handle degenerate problems. Moreover, in the second part of this work, we analyse the interactions between the regularization parameters and the computational footprint of the linear algebra routines used to solve the Newton linear systems. In particular, when these systems are solved using an iterative Krylov method, we are able to show-using a new rearrangement of the Schur complement which exploits regularization-that general purposes preconditioners remain attractive for a series of subsequent IPM iterations. Indeed, if on the one hand a series of theoretical results underpin the fact that the approach here presented allows a better re-use of such computed preconditioners, on the other, we show experimentally that such (re)computations are needed only in a fraction of the total IPM iterations. The resulting regularized second order methods, for which low-frequency-update of the preconditioners are allowed, pave the path for an alternative class of second order methods characterized by reduced computational effort.
linearprogramming (LP) is an extremely useful tool which has been successfully applied to solve various problems in a wide range of areas, including operations research, engineer-ing, economics, or even more abstract...
详细信息
linearprogramming (LP) is an extremely useful tool which has been successfully applied to solve various problems in a wide range of areas, including operations research, engineer-ing, economics, or even more abstract mathematical areas such as combinatorics. It is also used in many machine learning applications, such as L1-regularized SVMs, basis pursuit, nonnegative matrix factorization, etc. interiorpointmethods (IPMs) are one of the most popular methods to solve LPs both in theory and in practice. Their underlying complexity is dominated by the cost of solving a system of linear equations at each iteration. In this paper, we consider both feasible and infeasible IPMs for the special case where the number of variables is much larger than the number of constraints. Using tools from Randomized linear Algebra, we present a preconditioning technique that, when combined with the it-erative solvers such as Conjugate Gradient or Chebyshev Iteration, provably guarantees that IPM algorithms (suitably modified to account for the error incurred by the approx-imate solver), converge to a feasible, approximately optimal solution, without increasing their iteration complexity. Our empirical evaluations verify our theoretical results on both real-world and synthetic data.
The interior-point method (IPM) has become the workhorse method for nonlinearprogramming. The performance of IPM is directly related to the linear solver employed to factorize the Karush-Kuhn-Tucker (KKT) system at e...
详细信息
The interior-point method (IPM) has become the workhorse method for nonlinearprogramming. The performance of IPM is directly related to the linear solver employed to factorize the Karush-Kuhn-Tucker (KKT) system at each iteration of the algorithm. When solving large-scale nonlinear problems, state-of-the art IPM solvers rely on efficient sparse linear solvers to solve the KKT system. Instead, we propose a novel reduced-space IPM algorithm that condenses the KKT system into a dense matrix whose size is proportional to the number of degrees of freedom in the problem. Depending on where the reduction occurs, we derive two variants of the reduced-space method: linearize-then-reduce and reduce-then-linearize. We adapt their workflow so that the vast majority of computations are accelerated on GPUs. We provide extensive numerical results on the optimal power flow problem, comparing our GPU-accelerated reduced-space IPM with Knitro and a hybrid full-space IPM algorithm. By evaluating the derivatives on the GPU and solving the KKT system on the CPU, the hybrid solution is already significantly faster than the CPU-only solutions. The two reduced-space algorithms go one step further by solving the KKT system entirely on the GPU. As expected, the performance of the two reduction algorithms depends critically on the number of available degrees of freedom: They underperform the full-space method when the problem has many degrees of freedom, but the two algorithms are up to three times faster than Knitro as soon as the relative number of degrees of freedom becomes smaller.
Domain-Driven Solver (DDS) is a MATLAB-based software package for convex optimization. The current version of DDS accepts every combination of the following function/set constraints: (1) symmetric cones (LP, SOCP, and...
详细信息
Domain-Driven Solver (DDS) is a MATLAB-based software package for convex optimization. The current version of DDS accepts every combination of the following function/set constraints: (1) symmetric cones (LP, SOCP, and SDP);(2) quadratic constraints that are SOCP representable;(3) direct sums of an arbitrary collection of 2-dimensional convex sets defined as the epigraphs of univariate convex functions (including as special cases geometric programming and entropy programming);(4) generalized Koecher (power) cone;(5) epigraphs of matrix norms (including as a special case minimization of nuclear norm over a linear subspace);(6) vector relative entropy;(7) epigraphs of quantum entropy and quantum relative entropy;and (8) constraints involving hyperbolic polynomials. The infeasible-start primal-dual algorithms used for DDS rely heavily on duality theory and properties of Legendre-Fenchel conjugate functions, and are designed to rigorously determine the status of a given problem. We discuss some important implementation details and techniques we used to improve the robustness and efficiency of the software. The appendix contains many examples.
In this paper we generalize the interiorpoint-Proximal Method of Multipliers (IP-PMM) presented in Pougkakiotis and Gondzio (Comput Optim Appl 78:307-351, 2021. https://***/10.1007/s10589-020-00240-9) for the solutio...
详细信息
In this paper we generalize the interiorpoint-Proximal Method of Multipliers (IP-PMM) presented in Pougkakiotis and Gondzio (Comput Optim Appl 78:307-351, 2021. https://***/10.1007/s10589-020-00240-9) for the solution of linear positive Semi-Definite programming (SDP) problems, allowing inexactness in the solution of the associated Newton systems. In particular, we combine an infeasible interiorpoint Method (IPM) with the Proximal Method of Multipliers (PMM) and interpret the algorithm (IP-PMM) as a primal-dual regularized IPM, suitable for solving SDP problems. We apply some iterations of an IPM to each sub-problem of the PMM until a satisfactory solution is found. We then update the PMM parameters, form a new IPM neighbourhood, and repeat this process. Given this framework, we prove polynomial complexity of the algorithm, under mild assumptions, and without requiring exact computations for the Newton directions. We furthermore provide a necessary condition for lack of strong duality, which can be used as a basis for constructing detection mechanisms for identifying pathological cases within IP-PMM.
We propose a new approach to solving linear programs which combines the advantages of interiorpointmethods and active set methods. methods of the first type, in particular the Nesterov-Todd interior-point metho...
详细信息
暂无评论