Weighted or reweighted strategies have not been considered for sparsity constrained optimization. In this paper, we reformulate the sparsity constraint as an equivalent weighted l1-norm constraint in the sparsity constrained optimization problem. To solve the reformulated problem, we investigate the problem in the Lagrange dual framework, and prove that the strong duality property holds. Then … Read more
Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection … Read more
We present well known properties related to the topology of Steiner minimal trees and to the geometric position of Steiner points, and investigate their application in the main exact algorithms that have been proposed for the Euclidean Steiner problem. We discuss the difficulty in the application of properties that were very successfully applied to solve … Read more
We consider a direct approach to solve mixed-integer nonlinear optimization problems with constraints depending on initial and terminal conditions of an ordinary differential equation. In order to obtain a finite-dimensional problem, the dynamics are approximated using discretization methods. In the framework of general one-step methods, we provide sufficient conditions for the convergence of this approach … Read more
Concepts of consistency have long played a key role in constraint programming but never developed in integer programming (IP). Consistency nonetheless plays a role in IP as well. For example, cutting planes can reduce backtracking by achieving various forms of consistency as well as by tightening the linear programming (LP) relaxation. We introduce a type … Read more
In this article we introduce an inner parallel cutting plane method (IPCP) to compute good feasible points along with valid cutting planes for mixed-integer convex optimization problems. The method iteratively generates polyhedral outer approximations of an enlarged inner parallel set (EIPS) of the continuously relaxed feasible set. This EIPS possesses the crucial property that any … Read more
Signal estimation problems with smoothness and sparsity priors can be naturally modeled as quadratic optimization with L0-“norm” constraints. Since such problems are non-convex and hard-to-solve, the standard approach is, instead, to tackle their convex surrogates based on L1-norm relaxations. In this paper, we propose new iterative conic quadratic relaxations that exploit not only the L0-“norm” … Read more
Semidefinite programming relaxations complement polyhedral relaxations for quadratic optimization, but global optimization solvers built on polyhedral relaxations cannot fully exploit this advantage. This paper develops linear outer-approximations of semidefinite constraints that can be effectively integrated into global solvers. The difference from previous work is that our proposed cuts are (i) sparser with respect to the … Read more
A need for an optimal solution for a given mathematical model is well known and many solution approaches have been developed to identify efficiently an optimal solution in a given situation. For example, one such class of mathematical models with industrial applications have been classified as mathematical programming models (MPM). The main idea behind these … Read more
Decades of advances in mixed-integer linear programming (MILP) and recent development in mixed-integer second-order-cone programming (MISOCP) have translated very mildly to progresses in global solving nonconvex mixed-integer quadratically constrained programs (MIQCP). In this paper we propose a new approach, namely Compact Disjunctive Approximation (CDA), to approximate nonconvex MIQCP to arbitrary precision by convex MIQCPs, which … Read more