With every real valued function, of a real argument, can be associated a matrix function mapping a linear space of symmetric matrices into itself. In this paper we study directional differentiability properties of such matrix functions associated with directionally differentiable real valued functions. In particular, we show that matrix valued functions inherit semismooth properties of … Read more
We study the problem of designing at minimum cost a two-connected network such that each edge belongs to a cycle using at most K edges. This problem is a particular case of the two-connected networks with bounded meshes problem studied by Fortz, Labbé and Maffioli. In this paper, we compute a lower bound on the … Read more
Given an undirected graph with edge weights, the MAX-CUT problem consists in finding a partition of the nodes into two subsets, such that the sum of the weights of the edges having endpoints in different subsets is maximized. It is a well-known NP-hard problem with applications in several fields, including VLSI design and statistical physics. … Read more
We present a multigrid approach to the optimization of systems governed by differential equations. Such optimization problems have many applications, and are a broader class of problems than systems of equations. Using several model problems we give evidence (both theoretical and numerical) that a multigrid approach can often be successful in the setting of optimization. … Read more
For constrained smooth or nonsmooth optimization problems, new continuously differentiable penalty functions are derived. They are proved exact in the sense that under some nondegeneracy assumption, local optimizers of a nonlinear program are precisely the optimizers of the associated penalty function. This is achieved by augmenting the dimension of the program by a variable that … Read more
Given a graph with nonnegative capacities on its edges, it is well known that the weight of a minimum T-cut is equal to the value of a maximum packing of T-joins. Padberg-Rao’s algorithm finds a minimum weight T-cut but it does not produce a T-join packing, we present a polynomial combinatorial algorithm for finding an … Read more
Current mixed-integer linear programming solvers are based on linear programming routines that use floating point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. It is shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in … Read more
The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that … Read more
It was recently shown that, unlike in linear optimization, the central path in semidefinite optimization (SDO) does not converge to the analytic center of the optimal set in general. In this paper we analyze the limiting behavior of the central path to explain this unexpected phenomenon. This is done by deriving a new necessary and … Read more
A standard stochastic global optimization method is applied to the challenging problem of finding the minimum energy conformation of cluster of identical atoms interacting through the Lennard-Jones potential. The method proposed is based on the use of a two-phase local search procedure which is capable of significantly enlarge the basin of attraction of the global … Read more