Solving structured nonlinear least-squares and nonlinear feasibility problems with expensive functions

Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , , , , , , ,

We present an algorithm for nonlinear least-squares and nonlinear feasibility problems, i.e. for systems of nonlinear equations and nonlinear inequalities, which depend on the outcome of expensive functions for which derivatives are assumed to be unavailable. Our algorithm combines derivative-free techniques with filter trust-region methods to keep the number of expensive function evaluations low and … Read more

Global Routing in VLSI Design: Algorithms, Theory, and Computational Practice

Categories Integer Programming, VLSI layout Tags , ,

Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial time algorithm for the global routing problem based on integer programming formulation with a theoretical approximation bound. The algorithm ensures that all routing demands are … Read more

A note on the MIR closure and basic relaxations of polyhedra

Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

Anderson, Cornuejols and Li (2005) show that for a polyhedral mixed integer set defined by a constraint system Ax >= b, where x is n-dimensional, along with integrality restrictions on some of the variables, any split cut is in fact a split cut for a “basic relaxation”, i.e., one defined by a subset of linearly … Read more

An Exact Penalty Global Optimization Approach for Mixed-Integer Programming Problems

Categories (Mixed) Integer Nonlinear Programming Tags , ,

In this work, we propose a global optimization approach for mixed-integer programming problems. To this aim, we preliminarily de ne an exact penalty algorithm model for globally solving general problems and we show its convergence properties. Then, we describe a particular version of the algorithm that solves mixed integer problems. CitationDIS Technical Report n. 17, 2010.ArticleDownload … Read more

NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems

Categories Convex Optimization, Global Optimization Theory Tags , , ,

We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic … Read more

Convex Graph Invariants

Categories Convex Optimization, Graphs and Matroids, Robust Optimization

The structural properties of graphs are usually characterized in terms of invariants, which are functions of graphs that do not depend on the labeling of the nodes. In this paper we study convex graph invariants, which are graph invariants that are convex functions of the adjacency matrix of a graph. Some examples include functions of … Read more

The Convex Geometry of Linear Inverse Problems

Categories Applications - Science and Engineering, Convex Optimization, Semi-definite Programming

In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smaller than the dimension of the model to be estimated. However in many practical situations of interest, models are constrained structurally so that they only have a few degrees … Read more

New approximations for the cone of copositive matrices and its dual

Categories Linear, Cone and Semidefinite Programming

We provide convergent hierarchies for the cone C of copositive matrices and its dual, the cone of completely positive matrices. In both cases the corresponding hierarchy consists of nested spectrahedra and provide outer (resp. inner) approximations for C (resp. for its dual), thus complementing previous inner (resp. outer) approximations for C (for its dual). In … Read more

On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming

The well-known result stating that any non-convex quadratic problem over the nonnegative orthant with some additional linear and binary constraints can be rewritten as linear problem over the cone of completely positive matrices (Burer, 2009) is generalized by replacing the nonnegative orthant with an arbitrary closed convex cone. This set-semidefinite representation result implies new semidefinite … Read more