Abstract: Abstract This paper addresses an optimal impulsive control problem whose trajectories are functions of bounded variation and impulsive controls are regular vector measures. This problem is characterized by two main features. First, the dynamical control system to be considered may not possess the so-called well-posedness property. Second, the constraints on the one-sided limits of states are presented. Such constraints are interpreted as multipoint state constraints. For this problem, we derive global optimality conditions based on using of compound Lyapunov type functions which possess strongly monotone properties with respect to the control system. As a motivating case, a model of advertising expenses optimization for mutually complementary products is considered. For this model, we propose four variants of resolving sets of Lyapunov type functions and explain the technique of applying the optimality conditions. PubDate: 2020-01-16

Abstract: Abstract The quartet method is a novel hierarchical clustering approach where, given a set of n data objects and their pairwise dissimilarities, the aim is to construct an optimal tree from the total number of possible combinations of quartet topologies on n, where optimality means that the sum of the dissimilarities of the embedded (or consistent) quartet topologies is minimal. This corresponds to an NP-hard combinatorial optimization problem, also referred to as minimum quartet tree cost (MQTC) problem. We provide details and formulation of this challenging problem, and propose a basic greedy heuristic that is characterized by some appealing insights and findings for speeding up and simplifying the processes of solution generation and evaluation, such as the use of adjacency-like matrices to represent the topology structures of candidate solutions; fast calculation of coefficients and weights of the solution matrices; shortcuts in the enumeration of all solution permutations for a given configuration; and an iterative distance matrix reduction procedure, which greedily merges together highly connected objects which may bring lower values of the quartet cost function in a given partial solution. It will be shown that this basic greedy heuristic is able to improve consistently the performance of popular quartet clustering algorithms in the literature, namely a reduced variable neighbourhood search and a simulated annealing metaheuristic, producing novel efficient solution approaches to the MQTC problem. PubDate: 2020-01-13

Abstract: Abstract We study the behavior of the Douglas–Rachford algorithm on the graph vertex-coloring problem. Given a graph and a number of colors, the goal is to find a coloring of the vertices so that all adjacent vertex pairs have different colors. In spite of the combinatorial nature of this problem, the Douglas–Rachford algorithm was recently shown to be a successful heuristic for solving a wide variety of graph coloring instances, when the problem was cast as a feasibility problem on binary indicator variables. In this work we consider a different formulation, based on semidefinite programming. The much improved performance of the Douglas–Rachford algorithm, with this new approach, is demonstrated through various numerical experiments. PubDate: 2020-01-13

Abstract: Abstract The present paper first provides sufficient conditions and characterizations for linearly conditioned bifunction associated with an equilibrium problem. It then introduces the notion of weak sharp solution for equilibrium problems which is analogous to the linear conditioning notion. This new notion generalizes and unifies the notion of weak sharp minima for optimization problems as well as the notion of weak sharp solutions for variational inequality problems. Some sufficient conditions and characterizations of weak sharpness are also presented. Finally, we study the finite convergence property of sequences generated by some algorithms for solving equilibrium problems under linear conditioning and weak shapness assumptions. An upper bound of the number of iterations by which the sequence generated by proximal point algorithm converges to a solution of equilibrium problems is also given. PubDate: 2020-01-10

Abstract: Abstract Motivated by the fact that pay-per-use rentals require firms to be responsible for the the operational costs of products and service support network, we establish a pay-per-use rental model where a firm strategically sets the availability of products for rentals to achieve the trade-off between production quantity and operational costs. Furthermore, based on the traditional sale model, we also propose a combined model of sale and pay-per-use rental. The objective is to maximize firm’s profits under three models: the sale model, the pay-per-use rental model, and the hybrid model of sale and rental. The approach of backward induction is adopted to obtain the firm’s optimal decisions on pricing and production volume. Through comparative analysis, we provide the firm’s global optimal strategic solution, and the corresponding solutions in different market environments are developed, respectively, due to the variance of polling effects and costs. The results show that under the no-pooling case where customers’ requests overlap completely, the hybrid model always show higher profitability than the pay-per-use rental model, and it performs better than the sales model only when the per-unit operational and production costs are low. Under the perfect-pooling case where customers’ requests do not overlap, the hybrid model is always the optimal strategy. Numerical experiments are also conducted to illustrate the results under the general pooling case. PubDate: 2020-01-10

Abstract: Abstract In this paper, we consider a class of structured nonsmooth optimization problem in which the first component of the objective is a smooth function while the second component is the sum of one-dimensional nonsmooth functions. We first verify that every minimizer of this problem is a solution of an equation \(h(x)=0\), where h is continuous but not differentiable, and moreover \(-h(x)\) is a descent direction of the objective at \(x\in \mathbb {R}^n\) if \(h(x)\ne 0\). Then by using \(-h(x)\) as a search direction, we propose a residual-based algorithm for solving this problem. Under proper conditions, we verify that any accumulation point of the sequence of iterates generated by our algorithm is a first-order stationary point of the problem. Additionally, we prove that the worst-case iteration-complexity for finding an \(\epsilon \) first-order stationary point is \(O(\epsilon ^{-2})\). Numerical results have shown the efficiency of this algorithm. PubDate: 2020-01-01

Abstract: Abstract In this paper, we study the strong duality for an optimization problem to minimize a homogeneous quadratic function subject to two homogeneous quadratic constraints over the unit sphere, called Problem (P) in this paper. When a feasible (P) fails to have a Slater point, we show that (P) always adopts the strong duality. When (P) has a Slater point, we propose a set of conditions, called “Property J”, on an SDP relaxation of (P) and its conical dual. We show that (P) has the strong duality if and only if there exists at least one optimal solution to the SDP relaxation of (P) which fails Property J. Our techniques are based on various extensions of S-lemma as well as the matrix rank-one decomposition procedure introduced by Ai and Zhang. Many nontrivial examples are constructed to help understand the mechanism. PubDate: 2020-01-01

Abstract: Abstract It is known that the analysis to tackle with non-symmetric cone optimization is quite different from the way to deal with symmetric cone optimization due to the discrepancy between these types of cones. However, there are still common concepts for both optimization problems, for example, the decomposition with respect to the given cone, smooth and nonsmooth analysis for the associated conic function, conic-convexity, conic-monotonicity and etc. In this paper, motivated by Chares’s thesis (Cones and interior-point algorithms for structured convex optimization involving powers and exponentials, 2009), we consider the decomposition issue of two core non-symmetric cones, in which two types of decomposition formulae will be proposed, one is adapted from the well-known Moreau decomposition theorem and the other follows from geometry properties of the given cones. As a byproduct, we also establish the conic functions of these cones and generalize the power cone case to its high-dimensional counterpart. PubDate: 2020-01-01

Abstract: Abstract In this article we propose a new approach to an analysis of DC optimization problems. This approach was largely inspired by codifferential calculus and the method of codifferential descent and is based on the use of a so-called affine support set of a convex function instead of the Frenchel conjugate function. With the use of affine support sets we define a global codifferential mapping of a DC function and derive new necessary and sufficient global optimality conditions for DC optimization problems. We also provide new simple necessary and sufficient conditions for the global exactness of the \(\ell _1\) penalty function for DC optimization problems with equality and inequality constraints and present a series of simple examples demonstrating a constructive nature of the new global optimality conditions. These examples show that when the optimality conditions are not satisfied, they can be easily utilised in order to find “global descent” directions of both constrained and unconstrained problems. As an interesting theoretical example, we apply our approach to the analysis of a nonsmooth problem of Bolza. PubDate: 2020-01-01

Abstract: Abstract The challenge of taking many variables into account in optimization problems may be overcome under the hypothesis of low effective dimensionality. Then, the search of solutions can be reduced to the random embedding of a low dimensional space into the original one, resulting in a more manageable optimization problem. Specifically, in the case of time consuming black-box functions and when the budget of evaluations is severely limited, global optimization with random embeddings appears as a sound alternative to random search. Yet, in the case of box constraints on the native variables, defining suitable bounds on a low dimensional domain appears to be complex. Indeed, a small search domain does not guarantee to find a solution even under restrictive hypotheses about the function, while a larger one may slow down convergence dramatically. Here we tackle the issue of low-dimensional domain selection based on a detailed study of the properties of the random embedding, giving insight on the aforementioned difficulties. In particular, we describe a minimal low-dimensional set in correspondence with the embedded search space. We additionally show that an alternative equivalent embedding procedure yields simultaneously a simpler definition of the low-dimensional minimal set and better properties in practice. Finally, the performance and robustness gains of the proposed enhancements for Bayesian optimization are illustrated on numerical examples. PubDate: 2020-01-01

Abstract: Abstract In recent years many papers have derived polyhedral and non-polyhedral convex envelopes for different classes of functions. Except for the univariate cases, all these classes of functions share the property that the generating set of their convex envelope is a subset of the border of the region over which the envelope is computed. In this paper we derive the convex envelope over a rectangular region for a class of functions which does not have this property, namely the class of bivariate cubic functions without univariate third-degree terms. PubDate: 2020-01-01

Abstract: Abstract The continuous k-center problem aims at finding k balls with the smallest radius to cover a finite number of given points in \(\mathbb {R}^n\). In this paper, we propose and study the following generalized version of the k-center problem: Given a finite number of nonempty closed convex sets in \(\mathbb {R}^n\), find k balls with the smallest radius such that their union intersects all of the sets. Because of its nonsmoothness and nonconvexity, this problem is very challenging. Based on nonsmooth optimization techniques, we first derive some qualitative properties of the problem and then propose new algorithms to solve the problem. Numerical experiments are also provided to show the effectiveness of the proposed algorithms. PubDate: 2020-01-01

Abstract: Abstract We introduce a new regularization technique, using what we refer to as the Steklov regularization function, and apply this technique to devise an algorithm that computes a global minimizer of univariate coercive functions. First, we show that the Steklov regularization convexifies a given univariate coercive function. Then, by using the regularization parameter as the independent variable, a trajectory is constructed on the surface generated by the Steklov function. For monic quartic polynomials, we prove that this trajectory does generate a global minimizer. In the process, we derive some properties of quartic polynomials. Comparisons are made with a previous approach which uses a quadratic regularization function. We carry out numerical experiments to illustrate the working of the new method on polynomials of various degree as well as a non-polynomial function. PubDate: 2020-01-01

Abstract: Abstract Flexible agile and extreme project management methods have become increasingly popular among practitioners, particularly in the IT and R&D sectors. In contrast to the theoretically and algorithmically well-established and developed trade-off and multimode methods applied in traditional project management methods, flexible project scheduling methods, which are applied in agile, hybrid, and especially extreme project management, lack a principled foundation and algorithmic handling. The aim of this paper is to fill this gap. We propose a matrix-based method that provides scores for alternative project plans that host flexible task dependencies and undecided, supplementary task completion while also handling the new but unplanned tasks. In addition, traditional multimode resource-constrained project scheduling problems are also covered. The proposed method can bridge the flexible and traditional approaches. PubDate: 2020-01-01

Abstract: Abstract In this paper we prove necessary and sufficient criteria for a cancellation of a bounded convex set in the inclusion of Minkowski sums of sets. We also prove an order cancellation law in semigroups of not closed, bounded and convex sets. PubDate: 2019-12-19

Abstract: Abstract The capacitated vehicle routing problem (CVRP) is a well-known NP-hard combinatorial optimization problem with numerous real-world applications in logistics. In this work, we present a literature review with recent successful parallel implementations of variable neighborhood search regarding different variants of vehicle routing problems. We conduct an experimental study for the CVRP using well-known benchmark instances, and we present and investigate three parallelization strategies that coordinate the communication of the multiple processors. We experimentally evaluate a non-cooperative and two novel cooperation models, the managed cooperative and the parameterized cooperative strategies. Our results constitute a first proof-of-concept for the benefits of this new self-adaptive parameterized cooperative approach, especially in computationally hard instances. PubDate: 2019-12-12

Abstract: Abstract This paper presents a first continuous, linear, conic formulation for the discrete ordered median problem (DOMP). Starting from a binary, quadratic formulation in the original space of location and allocation variables that are common in location analysis (L.A.), we prove that there exists a transformation of that formulation, using the same space of variables, that allows us to cast DOMP as a continuous, linear programming problem in the space of completely positive matrices. This is the first positive result that states equivalence between the family of continuous, convex problems and some hard combinatorial problems in L.A. The result is of theoretical interest because it allows us to share the tools from continuous optimization to shed new light into the difficult combinatorial structure of the class of ordered median problems that combines elements of the p-median, quadratic assignment and permutation polytopes. PubDate: 2019-12-09

Abstract: Abstract This paper deals with a convex vector optimization problem with set-valued maps. In the absence of constraint qualifications, it provides, by the scalarization theorem, sequential Lagrange multiplier conditions characterizing approximate weak Pareto optimal solutions for the problem in terms of the approximate subdifferentials of the marginal function associated with corresponding set-valued maps. The paper shows also that this result yields the approximate Lagrange multiplier condition for the problem under a new constraint qualification which is weaker than the Slater-type constraint qualification. Illustrative examples are also provided to discuss the significance of the sequential conditions. PubDate: 2019-12-07

Abstract: Abstract Exhausters are families of convex compact sets that allow one to represent directional derivative of the studied function at a point in the form of InfMax or SupMin of linear functions. Functions for which such a representation is valid we call exhausterable. This class of functions is quite wide and contains many nonsmooth ones. The set of exhausterable function is also called exhausterable. In the present paper we describe optimality conditions for an exhausterable function on an exhausterable set. These conditions can be used for solving many nondifferentiable optimization problems. An example that illustrate obtained results is provided. PubDate: 2019-11-21