This paper presents a branch-and-bound algorithm for nonconvex quadratic programming, which is based on solving semidefinite relaxations at each node of the enumeration tree. The method is motivated by a recent branch-and-cut approach for the box-constrained case that employs linear relaxations of the first-order KKT conditions. We discuss certain limitations of linear relaxations when handling … Read more
For a locally optimal solution to the nonlinear semidefinite programming problem, under Robinson’s constraint qualification, the following conditions are proved to be equivalent: the strong second order sufficient condition and constraint nondegeneracy; the nonsingularity of Clarke’s Jacobian of the Karush-Kuhn-Tucker system; the strong regularity of the Karush-Kuhn-Tucker point; and others. CitationTechnical Report, Department of Mathematics, … Read more
The inverse quadratic eigenvalue problem (IQEP) arises in the field of structural dynamics. It aims to find three symmetric matrices, known as the mass, the damping and the stiffness matrices, respectively such that they are closest to the given analytical matrices and satisfy the measured data. The difficulty of this problem lies in the fact … Read more
In our reports on GAMM-04 and ECCOMAS-04 there has been presented a new conjugate directions method for large scale unconstrained minimization problems. High efficiency of this method is ensured by employing an orthogonalization procedure: when constructing the next conjugate vector the component of the gradient is used that is orthogonal to the subspace of preceding … Read more
We propose two line search primal-dual interior-point methods that approximately solve a equence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an $\ell_2$-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, … Read more
We present a new method for regularization of ill-conditioned problems, such as those that arise in image restoration or mathematical processing of medical data. The method extends the traditional {\em trust-region subproblem}, \TRS, approach that makes use of the {\em L-curve} maximum curvature criterion, a strategy recently proposed to find a good regularization parameter. We … Read more
This paper presents a convergence rate for the sequence generated by the Cauchy algorithm. The method is applied to a convex quadratic function with exact line search. Instead of using the norm induced by the hessian matrix, the q-linear convergence is shown for the l2 (or Euclidean) norm. CitationTecnhical Report, Dep. Mathematics, Federal University of … Read more
New theorems of the alternative for polynomial constraints (based on the Positivstellensatz from real algebraic geometry) and for linear constraints (generalizing the transposition theorems of Motzkin and Tucker) are proved. Based on these, two Karush-John optimality conditions — holding without any constraint qualification — are proved for single- or multi-objective constrained optimization problems. The first … Read more
We present a compact linearization for a broad class of bilinear 0-1 mixed-integer problems subject to assignment constraints. We apply the linearization to three classes of problems: quadratic assignment, multiprocessor scheduling with communication delays, and graph partitioning, and show that it yields faster solution times. CitationDEI, Politecnico di Milano, Working paper, April 2005.ArticleDownload View PDF
Multi-leader-follower games arise when modeling competition between two or more dominant firms and lead in a natural way to equilibrium problems with equilibrium constraints (EPECs). We examine a variety of nonlinear optimization and nonlinear complementarity formulations of EPECs. We distinguish two broad cases: problems where the leaders can cost-differentiate and problems with price-consistent followers. We … Read more