For a linear complementarity problem with inconsistent system of constraints a notion of quasi-solution of Tschebyshev type is introduced. It’s shown that this solution can be obtained automatically by Lemke’s method if the constraint matrix of the original problem is copositive plus or belongs to the intersection of matrix classes P 0 and Q 0.
We consider the non-convex quadratic maximization problem subject to the l1 unit ball constraint. The nature of the l1 norm structure makes this problem extremely hard to analyze, and as a consequence, the same difficulties are encountered when trying to build suitable approximations for this problem by some tractable convex counterpart formulations. We explore some properties of this problem, derive SDP-like relaxations and raise open questions.
In this paper, we have studied the problem of minimizing the ratio of two indefinite quadratic functions subject to a strictly convex quadratic constraint. First utilizing the relationship between fractional and parametric programming problems due to Dinkelbach, we reformulate the fractional problem as a univariate equation. To find the root of the univariate equation, the generalized Newton method is utilized that requires solving a nonconvex quadratic optimization problem at each iteration. A...
We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel...
We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel...