Abstract We investigate Difference of Convex (DC) constrained optimization problems where both the objective function and the constraints are DC and nonsmooth. The problem has applications in a variety of fields, including quadratic programs with complementarity constraints and classification in Machine Learning. We introduce the Constrained Descent-Ascent DC algorithm (CDADC) which generalizes the standard Descent-Ascent framework to incorporate DC constraints using a piecewise affine approximation strategy. The algorithm utilizes the bundle technique to construct models for both the objective and constraint functions. It solves a sequence of convex quadratic subproblems designed to balance objective improvement, proximity to the current iterate, and constraint fulfilment. CDADC avoids evaluation of the objective function’s concave part and, to minimize computational effort, implements bundle resetting whenever a serious step is achieved. We demonstrate finiteness and convergence of the algorithm to a point that satisfies a criterion associated with the B-stationarity notion. The algorithm’s behaviour is illustrated through a couple of numerical examples

We introduce a bundle method for the unconstrained minimization of nonsmooth difference-of-convex (DC) functions, and it is based on the calculation of a special type of descent direction called descent–ascent direction. The algorithm only requires evaluations of the minuend component function at each iterate, and it can be considered as a parsimonious bundle method as accumulation of information takes place only in case the descent–ascent direction does not provide a sufficient decrease. No line search is performed, and proximity control is pursued independent of whether the decrease in the objective function is achieved. Termination of the algorithm at a point satisfying a weak criticality condition is proved, and numerical results on a set of benchmark DC problems are reported. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms – Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0142 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0142 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract We propose a novel Mixed-Integer Nonlinear Programming (MINLP) model for sparse optimization based on the polyhedral k-norm. We put special emphasis on the application of sparse optimization in Feature Selection for Support Vector Machine (SVM) classification. We address the continuous relaxation of the problem, which comes out in the form of a fractional programming problem (FPP). In particular, we consider a possible way for tackling FPP by reformulating it via a DC (Difference of Convex) decomposition. We also overview the SVM models and the related Feature Selection in terms of multi-objective optimization. The results of some numerical experiments on benchmark classification datasets are reported.

Abstract We present a fast heuristic approach for solving a binary multiple instance learning (MIL) problem, which consists in discriminating between two kinds of item sets: the sets are called bags and the items inside them are called instances. Assuming that only two classes of instances are allowed, a common standard hypothesis states that a bag is positive if it contains at least a positive instance and it is negative when all its instances are negative. Our approach constructs a MIL separating hyperplane by preliminary fixing the normal and reducing the learning phase to a univariate nonsmooth optimization problem, which can be quickly solved by simply exploring the kink points. Numerical results are presented on a set of test problems drawn from the literature.

Abstract We consider the directional sensor network lifetime maximization problem (DSLMP). Given a set of directional sensor and target locations, the problem consists in assigning, at each time unit of a given time horizon, the action radius, the aperture angle, and the orientation direction to all sensors. The objective is to maximize the number of time units when all targets are covered, under certain constraints on sensor available energy. We present a mixed integer nonlinear programming formulation and tackle it by Lagrangean decomposition and subgradient optimization. The algorithm is equipped with a repairing heuristics aimed at finding good‐quality feasible solutions to DSLMP. The results of the application of the proposed approach to a number of problem instances are also reported.

Abstract This article addresses the minimum spanning tree problem with conflicting edge pairs, a variant of the classical minimum spanning tree where, given a list of conflicting edges, the goal is to find the cheapest spanning tree with no edges in conflict. We adopt a Lagrangian relaxation approach together with a dual ascent and a subgradient procedure to find tight lower bounds on the optimal solution. The algorithm is also equipped with a heuristic approach which provides an upper bound by removing the conflicts from possible infeasible solutions met during the calculation of the lower bounds. The computational results, carried out on benchmark instances, show that the proposed algorithm finds the optimal solutions on several instances. Moreover, the lower bounds it provides are much more accurate than ones provided by other Lagrangian approaches available in the literature and they are computed in much less time.

Abstract We consider polyhedral separation of sets as a possible tool in supervised classification. In particular, we focus on the optimization model introduced by Astorino and Gaudioso (J Optim Theory Appl 112(2):265–293, 2002) and adopt its reformulation in difference of convex (DC) form. We tackle the problem by adapting the algorithm for DC programming known as DCA. We present the results of the implementation of DCA on a number of benchmark classification datasets.

Abstract This paper is motivated by the case of a forwarder dealing with inland transportation planning, from a seaport, of inbound containers filled with pallets having different destinations in the land‐side. Although the forwarder is not the owner nor controls any vehicle, he is required to plan both the assignment of containers to intermediate depots, where the pallets are unpacked, and the assignment of pallets to the vehicles used for the distribution from depots to consignees. We present a mathematical model supporting the forwarder in this two‐echelon network to minimize assignment costs, while accounting for a balanced workload among all carriers involved in this distribution scheme. We discuss a tailor‐made implementation of the model in a realistic context and present a heuristic method to solve realistic‐sized instances. Our computational experiments confirm the viability of this method.

In the standard classification problems, the objective is to categorize points into different classes. Multiple instance learning (MIL), instead, is aimed at classifying bags of points, each point being an instance. The main peculiarity of a MIL problem is that, in the learning phase, only the label of each bag is known whereas the labels of the instances are unknown. We discuss an instance-level learning approach for a binary MIL classification problem characterized by two classes of instances, positive and negative, respectively. In such a problem, a negative bag is constituted only by negative instances, while a bag is positive if it contains at least one positive instance. We start from a mixed integer nonlinear optimization model drawn from the literature and the main result we obtain is to prove that a Lagrangian relaxation approach, equipped with a dual ascent scheme, allows us to obtain an optimal solution of the original problem. The relaxed problem is tackled by means of a block coordinate descent (BCD) algorithm. We provide, finally, the results of our implementation on some benchmark data sets.

After a brief survey on well established methods for image classification, we focus on a recently proposed Multiple Istance Learning (MIL) method which is suitable for applications in image processing.

We present an Electronic Nose (ENose) which is aimed both at identifying the type of gas and at estimating its concentration. Our system contains 8 sensors, 5 of them being gas sensors (of the class TGS from FIGARO USA, INC., whose sensing element is a tin dioxide (SnOz) semiconductor), the remaining being a temperature sensor (LM35 from National Semiconductor Corporation), a humidity sensor (HIH-3610 from Honeywell), and a pressure sensor (XFAM from Fujikura Ltd.). Our integrated hardware-software system uses some machine learning principles and least square regression principle to identify at first a new gas sample, and then to estimate its concentration, respectively. In particular we adopt a training model using the Support Vector Machine (SVM) approach to teach the system how discriminate among different gases, then we apply another training model using the least square regression, for each type of gas, to predict its concentration.

In the generalized quadratic assignment problem (GQAP) we are given n weighted facilities, m capacitated sites, a traffic intensity matrix between facilities, a distance matrix between sites, unit traffic costs, and assignment costs of facilities to sites. The aim is to determine an assignment of facilities to sites so that the sum of assignment and traffic costs is minimized and the total weight of all facilities assigned to the same site does not exceed the site capacity. The GQAP is a generalization of the quadratic assignment problem (QAP) in which n = m and exactly one facility must be assigned to each site. The problem has applications in container yard management and in the assignment of equipment to manufacturing sites. This article describes a memetic heuristic for the GQAP, as well as an integer linear programming formulation that can be solved by CPLEX for small instances. For larger instances, feasible solutions can be obtained by a truncated branch-and-bound procedure. Computational experiments show that on small instances the proposed heuristic always yields an optimal solution; on larger instances it always outperforms the truncated branch-and-bound algorithm.