Abstract: The aim of this paper is to develop first-order necessary and sufficient optimality conditions for nonsmooth multiobjective optimization problems with vanishing constraints. First of all, we introduce some data qualifications for the problem, and derive the comparisons between them. Secondly, based on the mentioned qualifications, we demonstrate some necessary optimality conditions, named strongly stationary conditions, at weakly efficient and efficient solutions of considered problem. Then, we show that the strongly stationary conditions are also sufficient for optimality. Finally, using the tightened problems, we establish other classes of qualifications and stationary conditions. PubDate: 2021-05-10

Abstract: Multi-objective optimization of computationally expensive, multimodal problems is very challenging, and is even more difficult for problems with many objectives (more than three). Optimization methods that incorporate surrogates within iterative frameworks, can be effective for solving such problems by reducing the number of expensive objective function evaluations that need to be done to find a good solution. However, only a few surrogate algorithms have been developed that are suitable for solving expensive many-objective problems. We propose a novel and effective optimization algorithm, \(\varepsilon \) -MaSO, that integrates \(\varepsilon \) -dominance with iterative Radial Basis Function surrogate-assisted framework to solve problems with many expensive objectives. \(\varepsilon \) -MaSO also incorporates a new strategy for selecting points for expensive evaluations, that is specially designed for many-objective problems. Moreover, a bi-level restart mechanism is introduced to prevent the algorithm from remaining in a local optimum and hence, increase the probability of finding the global optimum. Effectiveness of \(\varepsilon \) -MaSO is illustrated via application to DTLZ test suite with 2 to 8 objectives and to a simulation model of an environmental application. Results on both test problems and the environmental application indicate that \(\varepsilon \) -MaSO outperforms the other two surrogate-assisted many-objective methods, CSEA and K-RVEA, and an evolutionary many-objective method Borg within limited budget. PubDate: 2021-05-07

Abstract: This work attempts to combine the strengths of two major technologies that have matured over the last three decades: global mixed-integer nonlinear optimization and branch-and-price. We consider a class of generally nonconvex mixed-integer nonlinear programs (MINLPs) with linear complicating constraints and integer linking variables. If the complicating constraints are removed, the problem becomes easy to solve, e.g. due to decomposable structure. Integrality of the linking variables allows us to apply a discretization approach to derive a Dantzig-Wolfe reformulation and solve the problem to global optimality using branch-andprice. It is a remarkably simple idea; but to our surprise, it has barely found any application in the literature. In this work, we show that many relevant problems directly fall or can be reformulated into this class of MINLPs. We present the branch-and-price algorithm and demonstrate its effectiveness (and sometimes ineffectiveness) in an extensive computational study considering multiple large-scale problems of practical relevance, showing that, in many cases, orders-of-magnitude reductions in solution time can be achieved. PubDate: 2021-05-07

Abstract: In this paper, we propose a novel algorithm that is based on quadratic-piecewise-linear approximations of DC functions to solve nonnegative sparsity-constrained optimization. A penalized DC (difference of two convex functions) formulation is proved to be equivalent to the original problem under a suitable penalty parameter. We employ quadratic-piecewise-linear approximations to the two parts of the DC objective function, resulting in a nonconvex subproblem. This is the key ingredient of our main algorithm. This nonconvex subproblem can be solved by a globally convergent alternating variable algorithm. Under some mild conditions, we prove that the proposed main algorithm for the penalized problem is globally convergent. Some preliminary numerical results on the sparse nonnegative least squares and logistic regression problems demonstrate the efficiency of our algorithm. PubDate: 2021-05-05

Abstract: In this paper, we propose a new algorithm for solving bilevel variational inequalities. We consider a dynamical system and prove that the trajectory of this dynamical system converges to a desired solution. PubDate: 2021-05-05

Abstract: A framework is proposed to simultaneously cluster objects and detect anomalies in attributed graph data. Our objective function along with the carefully constructed constraints promotes interpretability of both the clustering and anomaly detection components, as well as scalability of our method. In addition, we developed an algorithm called Outlier detection and Robust Clustering for Attributed graphs (ORCA) within this framework. ORCA is fast and convergent under mild conditions, produces high quality clustering results, and discovers anomalies that can be mapped back naturally to the features of the input data. The efficacy and efficiency of ORCA is demonstrated on real world datasets against multiple state-of-the-art techniques. PubDate: 2021-05-03

Abstract: The 2-sets convex feasibility problem aims at finding a point in the nonempty intersection of two closed convex sets A and B in a Hilbert space H. The method of alternating projections is the simplest iterative procedure for finding a solution and it goes back to von Neumann. In the present paper, we study some stability properties for this method in the following sense: we consider two sequences of closed convex sets \(\{A_n\}\) and \(\{B_n\}\) , each of them converging, with respect to the Attouch-Wets variational convergence, respectively, to A and B. Given a starting point \(a_0\) , we consider the sequences of points obtained by projecting on the “perturbed” sets, i.e., the sequences \(\{a_n\}\) and \(\{b_n\}\) given by \(b_n=P_{B_n}(a_{n-1})\) and \(a_n=P_{A_n}(b_n)\) . Under appropriate geometrical and topological assumptions on the intersection of the limit sets, we ensure that the sequences \(\{a_n\}\) and \(\{b_n\}\) converge in norm to a point in the intersection of A and B. In particular, we consider both when the intersection \(A\cap B\) reduces to a singleton and when the interior of \(A \cap B\) is nonempty. Finally we consider the case in which the limit sets A and B are subspaces. PubDate: 2021-04-23

Abstract: Canonical duality theory (CDT) is presented by its creator DY Gao as a theory which can be used for solving a large class of challenging real-world problems. It is the aim of this paper to study rigorously constrained optimization problems in finite dimensional spaces using the method suggested by CDT and to discuss several results published in the last ten years. PubDate: 2021-04-23

Abstract: When solving large-scale cardinality-constrained Markowitz mean–variance portfolio investment problems, exact solvers may be unable to derive some efficient portfolios, even within a reasonable time limit. In such cases, information on the distance from the best feasible solution, found before the optimization process has stopped, to the true efficient solution is unavailable. In this article, I demonstrate how to provide such information to the decision maker. I aim to use the concept of lower bounds and upper bounds on objective function values of an efficient portfolio, developed in my earlier works. I illustrate the proposed approach on a large-scale data set based upon real data. I address cases where a top-class commercial mixed-integer quadratic programming solver fails to provide efficient portfolios attempted to be derived by Chebyshev scalarization of the bi-objective optimization problem within a given time limit. In this case, I propose to transform purely technical information provided by the solver into information which can be used in navigation over the efficient frontier of the cardinality-constrained Markowitz mean–variance portfolio investment problem. PubDate: 2021-04-23

Abstract: In this paper, we give necessary conditions for the existence of a strict local minimum of order two for multiobjective optimization problems with equality and inequality constraints. We suppose that the objective function and the active inequality constraints are only locally Lipschitz. We consider both regular equality constraints and degenerate equality constraints. This article could be considered as a continuation of [E. Constantin, Necessary Conditions for Weak Efficiency for Nonsmooth Degenerate Multiobjective Optimization Problems, J. Global Optim, 75, 111-129, 2019]. We introduce a constraint qualification and a regularity condition, and we show that under each of them, the dual necessary conditions for a weak local minimum of the aforementioned article become of Kuhn-Tucker type. PubDate: 2021-04-21

Abstract: A standard quadratic program is an optimization problem that consists of minimizing a (nonconvex) quadratic form over the unit simplex. We focus on reformulating a standard quadratic program as a mixed integer linear programming problem. We propose two alternative formulations. Our first formulation is based on casting a standard quadratic program as a linear program with complementarity constraints. We then employ binary variables to linearize the complementarity constraints. For the second formulation, we first derive an overestimating function of the objective function and establish its tightness at any global minimizer. We then linearize the overestimating function using binary variables and obtain our second formulation. For both formulations, we propose a set of valid inequalities. Our extensive computational results illustrate that the proposed mixed integer linear programming reformulations significantly outperform other global solution approaches. On larger instances, we usually observe improvements of several orders of magnitude. PubDate: 2021-04-20

Abstract: The optimization problem with sparsity arises in many areas of science and engineering such as compressed sensing, image processing, statistical learning and data sparse approximation. In this paper, we study the dual-density-based reweighted \(\ell _{1}\) -algorithms for a class of \(\ell _{0}\) -minimization models which can be used to model a wide range of practical problems. This class of algorithms is based on certain convex relaxations of the reformulation of the underlying \(\ell _{0}\) -minimization model. Such a reformulation is a special bilevel optimization problem which, in theory, is equivalent to the underlying \(\ell _{0}\) -minimization problem under the assumption of strict complementarity. Some basic properties of these algorithms are discussed, and numerical experiments have been carried out to demonstrate the efficiency of the proposed algorithms. Comparison of numerical performances of the proposed methods and the classic reweighted \(\ell _1\) -algorithms has also been made in this paper. PubDate: 2021-04-19

Abstract: We address the problem of covering a rectangle with six identical circles, whose radius is to be minimized. We focus on open cases from Melissen and Schuur (Discrete Appl Math 99:149–156, 2000). Depending on the rectangle side lengths, different configurations of the circles, corresponding to the different ways they are placed, yield the optimal covering. We prove the optimality of the two configurations corresponding to open cases. For the first one, we propose a mathematical mixed-integer nonlinear optimization formulation, that allows one to compute global optimal solutions. For the second one, we provide an analytical expression of the optimal radius as a function of one of the rectangle side lengths. All open cases are thus closed for the optimal covering of a rectangle with six circles. PubDate: 2021-04-17

Abstract: This paper presents a novel partially distributed outer approximation algorithm, named PaDOA, for solving a class of structured mixed integer convex programming problems to global optimality. The proposed scheme uses an iterative outer approximation method for coupled mixed integer optimization problems with separable convex objective functions, affine coupling constraints, and compact domain. PaDOA proceeds by alternating between solving large-scale structured mixed-integer linear programming problems and partially decoupled mixed-integer nonlinear programming subproblems that comprise much fewer integer variables. We establish conditions under which PaDOA converges to global minimizers after a finite number of iterations and verify these properties with an application to thermostatically controlled loads and to mixed-integer regression. PubDate: 2021-04-17

Abstract: 3D protein structures and nanostructures can be obtained by exploiting distance information provided by experimental techniques, such as nuclear magnetic resonance and the pair distribution function method. These are examples of instances of the unassigned distance geometry problem (uDGP), where the aim is to calculate the position of some points using a list of associated distance values not previoulsy assigned to the pair of points. We propose new mathematical programming formulations and a new heuristic to solve the uDGP related to molecular structure calculations. In addition to theoretical results, computational experiments are also provided. PubDate: 2021-04-15

Abstract: Let \(\mathcal {O}\) be a set of k orientations in the plane, and let P be a simple polygon in the plane. Given two points p, q inside P, we say that p \(\mathcal {O}\) -sees q if there is an \(\mathcal {O}\) -staircase contained in P that connects p and q. The \(\mathcal {O}\) -Kernel of the polygon P, denoted by \(\mathcal {O}\) - \(\mathrm{Kernel }(P)\) , is the subset of points of P which \(\mathcal {O}\) -see all the other points in P. This work initiates the study of the computation and maintenance of \(\mathcal {O}\) - \(\mathrm{Kernel }(P)\) as we rotate the set \(\mathcal {O}\) by an angle \(\theta \) , denoted by \(\mathcal {O}\) - \(\mathrm{Kernel }_{\theta }(P)\) . In particular, we consider the case when the set \(\mathcal {O}\) is formed by either one or two orthogonal orientations, \(\mathcal {O}=\{0^\circ \}\) or \(\mathcal {O}=\{0^\circ ,90^\circ \}\) . For these cases and P being a simple polygon, we design efficient algorithms for computing the \(\mathcal {O}\) - \(\mathrm{Kernel }_{\theta }(P)\) while \(\theta \) varies in \([-\frac{\pi }{2},\frac{\pi }{2})\) , obtaining: (i) the intervals of angle \(\theta \) where \(\mathcal {O}\) - \(\mathrm{Kernel }_{\theta }(P)\) is not empty, (ii) a value of angle \(\theta \) where \(\mathcal {O}\) - \(\mathrm{Kernel }_{\theta }(P)\) optimizes area or perimeter. Further, we show how the algorithms can be improved when PubDate: 2021-04-09

Abstract: In this paper, duality relations in nonconvex vector optimization are studied. An augmented Lagrangian function associated with the primal problem is introduced and efficient solutions to the given vector optimization problem, are characterized in terms of saddle points of this Lagrangian. The dual problem to the given primal one, is constructed with the help of the augmented Lagrangian introduced and weak and strong duality theorems are proved. Illustrative examples for duality relations are provided. PubDate: 2021-04-03

Abstract: We consider a real-time emergency medical service (EMS) vehicle patient transportation problem in which vehicles are assigned to patients so they can be transported to hospitals during an emergency. The objective is to minimize the total travel time of all vehicles while satisfying two types of time window constraints. The first requires each EMS vehicle to arrive at a patient’s location within a specified time window. The second requires the vehicle to arrive at the designated hospital within another time window. We allow an EMS vehicle to serve up to two patients instead of just one. The problem is shown to be NP-complete. We, therefore, develop a simulated annealing (SA) heuristic for efficient solution in real-time. A column generation algorithm is developed for determining a tight lower bound. Numerical results show that the proposed SA heuristic provides high-quality solutions in much less CPU time, when compared to the general-purpose solver. Therefore, it is suitable for implementation in a real-time decision support system, which is available via a web portal (www.rtdss.org). PubDate: 2021-04-01