It is shown that a matrix $M$ is a P-matrix if and only if, whatever is the vector $q$, the Newton-min algorithm does not cycle between two points when it is used to solve the linear complementarity problem $0\leq x\perp (Mx+q)\geq0$. Citation Inria research report RR-8004 Article Download View An algorithmic characterization of P-matricity
Sequential quadratic programming (SQP) methods are a popular class of methods for nonlinearly constrained optimization. They are particularly effective for solving a sequence of related problems, such as those arising in mixed-integer nonlinear programming and the optimization of functions subject to differential equation constraints. Recently, there has been considerable interest in the formulation of \emph{stabilized} … Read more
We show that the maximal cp-rank of $n\times n$ completely positive matrices is attained at a positive-definite matrix on the boundary of the cone of $n\times n$ completely positive matrices, thus answering a long standing question. We also show that the maximal cp-rank of $5\times 5$ matrices equals six, which proves the famous Drew-Johnson-Loewy conjecture … Read more
This paper is concerned with the minimization of an objective that is the sum of a convex function $f$ and an $\ell_1$ regularization term. Our interest is in methods that incorporate second-order information about the function $f$ to accelerate convergence. We describe a semi-smooth Newton framework that can be used to generate a variety of … Read more
In this paper, we consider the $l_0$ norm minimization problem with linear equation and nonnegativity constraints. By introducing the concept of generalized $Z$-matrix for a rectangular matrix, we show that this $l_0$ norm minimization with such a kind of measurement matrices and nonnegative observations can be exactly solved via the corresponding $l_p$ ($0
We consider the primal problem of finding the zeros of the sum of a maximally monotone operator with the composition of another maximally monotone operator with a linear continuous operator and a corresponding dual problem formulated by means of the inverse operators. A primal-dual splitting algorithm which simultaneously solves the two problems in finite-dimensional spaces … Read more
Recently, the so-called $\psi$-learning approach, the Support Vector Machine (SVM) classifier obtained with the ramp loss, has attracted attention from the computational point of view. A Mixed Integer Nonlinear Programming (MINLP) formulation has been proposed for $\psi$-learning, but solving this MINLP formulation to optimality is only possible for datasets of small size. For datasets of … Read more
This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after … Read more
A new result in convex analysis on the calculation of proximity operators in certain scaled norms is derived. We describe efficient implementations of the proximity calculation for a useful class of functions; the implementations exploit the piece-wise linear nature of the dual problem. The second part of the paper applies the previous result to acceleration … Read more
In a cross-dock facility, goods are moved by forklift from incoming truck platforms (strip doors) to temporary holding areas and then to outgoing truck platforms (stack doors) or directly from strip doors to stack doors. Costs within the cross-dock may be minimized by appropriate assignment of strip doors to incoming trucks and stack doors to … Read more