1,721,028 research outputs found
New classes of globally convexized filled functions for global optimization.
No full textWe propose new classes of globally convexized filled functions. Unlike the globally convexized filled functions previously proposed in literature, the ones proposed in this paper are continuously differentiable and, under suitable assumptions, their unconstrained minimization allows to escape from any local minima of the original objective function. Moreover we show that the properties of the proposed functions can be extended to the case of box constrained minimization problems. We also report the results of a preliminary numerical experience
Fix and bound: an efficient approach for solving large-scale quadratic programming problems with box constraints
No full textIn this paper, we propose a branch-and-bound algorithm for solving non convex quadratic programming problems with box constraints (BoxQP). Our approach combines existing tools, such as semidefinite programming (SDP) bounds strengthened through valid inequalities, with a new class of optimality-based linear cuts which leadsto variable fixing. The most important effect of fixing the value of some variables isthe size reduction along the branch-and-bound tree, allowing to compute bounds by solving SDPs of smaller dimension. Extensive computational experiments over large dimensional (up to n = 200) test instances show that our method is the state-of-the-art solver on large-scale BoxQPs. Furthermore, we test the proposed approach on the class of binary QP problems, where it exhibits competitive performance with state-of-the-art solvers
An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem
No full textIn this paper we consider low-rank semidefinite programming (LRSDP) relaxations of combinatorial quadratic problems that are equivalent to the maxcut problem. Using the Gramian representation of a positive semidefinite matrix, the LRSDP problem can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function with quadratic equality constraints. For the solution of this problem we propose a continuously differentiable exact merit function that exploits the special structure of the constraints and we use this function to define an efficient and globally convergent algorithm. Finally, we test our code on an extended set of instances of the maxcut problem and we report comparisons with other existing codes. © 2009 Springer and Mathematical Programming Society
Optimization meets machine learning: an exact algorithm for semi-supervised support vector machines
No full textSupport vector machines (SVMs) are well-studied supervised learning models for binary classification. Large amounts of samples can be cheaply and easily obtained in many applications. What is often a costly and error-prone process is to label these data points manually. Semi-supervised support vector machines (S3VMs) extend the well-known SVM classifiers to the semi-supervised approach, aiming to maximize the margin between samples in the presence of unlabeled data. By leveraging both labeled and unlabeled data, S3VMs attempt to achieve better accuracy and robustness than traditional SVMs. Unfortunately, the resulting optimization problem is non-convex and hence difficult to solve exactly. This paper presents a new branch-and-cut approach for S3VMs using semidefinite programming (SDP) relaxations. We apply optimality-based bound tightening to bound the feasible set. Box constraints allow us to include valid inequalities, strengthening the lower bound. The resulting SDP relaxation provides bounds that are significantly stronger than the ones available in the literature. For the upper bound, instead, we define a local search heuristic exploiting the solution of the SDP relaxation. Computational results highlight the algorithm’s efficiency, showing its capability to solve instances with ten times more data points than the ones solved in the literature
Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems
No full textIn this paper we consider the standard linear SDP problem, and its low rank nonlinear programming reformulation, based on a Gramian representation of a positive semidefinite matrix. For this nonconvex quadratic problem with quadratic equality constraints, we give necessary and sufficient conditions of global optimality expressed in terms of the Lagrangian function
Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming
Full text linkThe minimum sum-of-squares clustering (MSSC), or k-means type clustering, has
been recently extended to exploit prior knowledge on the cardinality of each
cluster. Such knowledge is used to increase performance as well as solution
quality. In this paper, we propose a global optimization approach based on the
branch-and-cut technique to solve the cardinality-constrained MSSC. For the
lower bound routine, we use the semidefinite programming (SDP) relaxation
recently proposed by Rujeerapaiboon et al. [SIAM J. Optim. 29(2), 1211-1239,
(2019)]. However, this relaxation can be used in a branch-and-cut method only
for small-size instances. Therefore, we derive a new SDP relaxation that scales
better with the instance size and the number of clusters. In both cases, we
strengthen the bound by adding polyhedral cuts. Benefiting from a tailored
branching strategy which enforces pairwise constraints, we reduce the
complexity of the problems arising in the children nodes. For the upper bound,
instead, we present a local search procedure that exploits the solution of the
SDP relaxation solved at each node. Computational results show that the
proposed algorithm globally solves, for the first time, real-world instances of
size 10 times larger than those solved by state-of-the-art exact methods
SpeeDP: an algorithm to compute SDP bounds for very large Max-Cut instances
No full textWe consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the non-convex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an efficient and globally convergent algorithm, called SpeeDP, for finding critical points of the LRSDP problem. We provide evidence of the effectiveness of SpeeDP by comparing it with other existing codes on an extended set of instances of the Max-Cut problem. We further include SpeeDP within a simply modified version of the Goemans-Williamson algorithm and we show that the corresponding heuristic SpeeDP-MC can generate high-quality cuts for very large, sparse graphs of size up to a million nodes in a few hours
Courier assignment in meal delivery via integer programming: A case study in Rome
Full text linkpeer reviewe
Supervised Feature Compression based on Counterfactual Analysis
Full text linkCounterfactual Explanations are becoming a de-facto standard in post-hoc
interpretable machine learning. For a given classifier and an instance
classified in an undesired class, its counterfactual explanation corresponds to
small perturbations of that instance that allows changing the classification
outcome. This work aims to leverage Counterfactual Explanations to detect the
important decision boundaries of a pre-trained black-box model. This
information is used to build a supervised discretization of the features in the
dataset with a tunable granularity. Using the discretized dataset, an optimal
Decision Tree can be trained that resembles the black-box model, but that is
interpretable and compact. Numerical results on real-world datasets show the
effectiveness of the approach in terms of accuracy and sparsity.Comment: 30 pages, 45figure
A partition-based global optimization algorithm
No full textGlobal optimization, Partition-based algorithm, DIRECT-type algorithm,
- …
