Let f be a lower semi-continuous convex function in a Euclidean space, finite or infinite dimensional. The gradient differential inclusion is a generalized differential equation which requires that -x'(t) be in the subgradient of f at x. It is the continuous versions of the gradient descent method for minimizing f in case f is differentiable, … Read more
We present results on global and polynomial-time convergence of infeasible-interior-point methods for self-scaled conic programming, which includes linear and semidefinite programming. First, we establish global convergence for an algorithm using a wide neighborhood. Next, we prove polynomial complexity for the algorithm with a slightly narrower neighborhood. Both neighborhoods are related to the wide (minus infinity) … Read more
Recently, tools from algebraic geometry have been successfully applied to develop solution schemes for new classes of optimization problems. A central idea in these constructions is to express a polynomial that is positive on a given domain in terms of polynomials of higher degree so that its positivity is readily revealed. This resembles the “lifting” … Read more
The variational approach for electronic structure based on the two-body reduced density matrix is studied, incorporating two representability conditions beyond the previously used $P$, $Q$ and $G$ conditions. The additional conditions (called $T1$ and $T2$ here) are implicit in work of R.~M.~Erdahl [Int.\ J.\ Quantum Chem.\ {\bf13}, 697–718 (1978)] and extend the well-known three-index diagonal … Read more
We propose a pivotting procedure for a class of Second-Order Cone Programming (SOCP) having one second-order cone. We introduce a dictionary, basic variables, nonbasic variables, and other necessary notions to define a pivot for the class of SOCP. In a pivot, two-dimensional SOCP subproblems are solved to decide which variables should be entering to or … Read more
An important measure of conditioning of a conic linear system is the size of the smallest structured perturbation making the system ill-posed. We show that this measure is unchanged if we restrict to perturbations of low rank. We thereby derive a broad generalization of the classical Eckart-Young result characterizing the distance to ill-posedness for a … Read more
We show that the block-structured distance to non-surjectivity of a set-valued sublinear mapping equals the reciprocal of a suitable block-structured norm of its inverse. This gives a natural generalization of the classical Eckart and Young identity for square invertible matrices. CitationMathematical Programming 103 (2005) pp. 561–573.
We consider the variational inequality problem formed by a general set-valued maximal monotone operator and a possibly unbounded “box” in $R^n$, and study its solution by proximal methods whose distance regularizations are coercive over the box. We prove convergence for a class of double regularizations generalizing a previously-proposed class of Auslender et al. We apply … Read more
We study iterative projection algorithms for the convex feasibility problem of finding a point in the intersection of finitely many nonempty, closed and convex subsets in the Euclidean space. We propose (without proof) an algorithmic scheme which generalizes both the string-averaging algorithm and the block-iterative projections (BIP) method with fixed blocks and prove convergence of … Read more
Primal-dual interior-point (p-d i-p) methods for Semidefinite Programming (SDP) are generally based on solving a system of matrix equations for a Newton type search direction for a symmetrization of the optimality conditions. These search directions followed the derivation of similar p-d i-p methods for linear programming (LP). Among these, a computationally interesting search direction is … Read more