Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Relevance and diversity are two desirable properties in data retrieval applications, an important field in data science and machine learning. In this paper, we consider three maximization problems to balance these two factors. The objective function in each problem is the sum of a monotone submodular function f and a supermodular function g, where f and g capture the relevance and diversity of any feasible solution, respectively. In the first problem, we consider a special supermodular diversity function g of a sum-sum format satisfying the relaxed triangle inequality, for which we propose a greedy-type approximation algorithm with an \(\left( 1-1/e,1/(2\alpha )\right) \) -bifactor approximation ratio, improving the previous \(\left( 1/(2\alpha ),1/(2\alpha )\right) \) -bifactor approximation ratio. In the second problem, we consider an arbitrary supermodular diversity function g, for which we propose a distorted greedy method to give a \(\min \left\{ 1-k_{f}e^{-1},1-k^{g}e^{-(1-k^{g})}\right\} \) -approximation algorithm, improving the previous \(k_f^{-1}\left( 1-e^{-k_f(1-k^{g})}\right) \) -approximation ratio, where \(k_f\) and \(k^g\) are the curvatures of the submodular function f and the supermodular funciton g, respectively. In the third problem, we generalize the uniform matroid constraint to the p matroid constraints, for which we present a local search algorithm to improve the previous \(\frac{1-k^g}{(1-k^g)k^f+p}\) -approximation ratio to \(\min \left\{ \frac{p+1-k_f}{p(p+1)},\left( \frac{1-k^g}{p}+\frac{k^g(1-k^g)^2}{p+(1-k^g)^2}\right) \right\} \) . PubDate: 2021-08-02

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: This paper investigates a mathematical programming based methodology for solving the minimum sum-of-squares clustering problem, also known as the “k-means problem”, in the presence of side constraints. We propose several exact and approximate mixed-integer linear and nonlinear formulations. The approximations are based on norm inequalities and random projections, the approximation guarantees of which are based on an additive version of the Johnson–Lindenstrauss lemma. We perform computational testing (with fixed CPU time) on a range of randomly generated and real data instances of medium size, but with high dimensionality. We show that when side constraints make k-means inapplicable, our proposed methodology—which is easy and fast to implement and deploy—can obtain good solutions in limited amounts of time. PubDate: 2021-08-02

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We develop a stochastic optimization model for scheduling a hybrid solar-battery storage system. Solar power in excess of the promise can be used to charge the battery, while power short of the promise is met by discharging the battery. We ensure reliable operations by using a joint chance constraint. Models with a few hundred scenarios are relatively tractable; for larger models, we demonstrate how a Lagrangian relaxation scheme provides improved results. To further accelerate the Lagrangian scheme, we embed the progressive hedging algorithm within the subgradient iterations of the Lagrangian relaxation. We investigate several enhancements of the progressive hedging algorithm, and find bundling of scenarios results in the best bounds. Finally, we provide a generalization for how our analysis extends to a microgrid with multiple batteries and photovoltaic generators. PubDate: 2021-08-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

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 P is a simple orthogonal polygon. In addition, our results are extended to the case of a set \(\mathcal {O}=\{\alpha _1,\dots ,\... PubDate: 2021-08-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: The computation of lower bounds via the solution of convex lower bounding problems depicts current state-of-the-art in deterministic global optimization. Typically, the nonlinear convex relaxations are further underestimated through linearizations of the convex underestimators at one or several points resulting in a lower bounding linear optimization problem. The selection of linearization points substantially affects the tightness of the lower bounding linear problem. Established methods for the computation of such linearization points, e.g., the sandwich algorithm, are already available for the auxiliary variable method used in state-of-the-art deterministic global optimization solvers. In contrast, no such methods have been proposed for the (multivariate) McCormick relaxations. The difficulty of determining a good set of linearization points for the McCormick technique lies in the fact that no auxiliary variables are introduced and thus, the linearization points have to be determined in the space of original optimization variables. We propose algorithms for the computation of linearization points for convex relaxations constructed via the (multivariate) McCormick theorems. We discuss alternative approaches based on an adaptation of Kelley’s algorithm; computation of all vertices of an n-simplex; a combination of the two; and random selection. All algorithms provide substantial speed ups when compared to the single point strategy used in our previous works. Moreover, we provide first results on the hybridization of the auxiliary variable method with the McCormick technique benefiting from the presented linearization strategies resulting in additional computational advantages. PubDate: 2021-08-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We focus on a special nonconvex and nonsmooth composite function, which is the sum of the smooth weakly convex component functions and a proper lower semi-continuous weakly convex function. An algorithm called the proximal-like incremental aggregated gradient (PLIAG) method proposed in Zhang et al. (Math Oper Res 46(1): 61–81, 2021) is proved to be convergent and highly efficient to solve convex minimization problems. This algorithm can not only avoid evaluating the exact full gradient which can be expensive in big data models but also weaken the stringent global Lipschitz gradient continuity assumption on the smooth part of the problem. However, under the nonconvex case, there is few analysis on the convergence of the PLIAG method. In this paper, we prove that the limit point of the sequence generated by the PLIAG method is the critical point of the weakly convex problems. Under further assumption that the objective function satisfies the Kurdyka–Łojasiewicz (KL) property, we prove that the generated sequence converges globally to a critical point of the problem. Additionally, we give the convergence rate when the Łojasiewicz exponent is known. PubDate: 2021-08-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: This work starts a new level of research in the area of conflict graphs and hypergraphs. We introduce a new term “mixed conflict hypergraphs”, which comes from merging and generalizing 0-1 conflict hypergraphs and mixed conflict graphs. Two structured mixed integer problems (referred to as convexification of posynomial and signomial functions, CoPF and CoSF, respectively) are solved efficiently with applying new strong cutting planes, outperforming modern commercial software. PubDate: 2021-08-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: An interesting observation is that most pairs of weakly homogeneous mappings do not possess strongly monotonic property, which is one of the key conditions to ensure the unique solvability of the generalized variational inequality. This paper focuses on studying the uniqueness and solvability of the generalized variational inequality with a pair of weakly homogeneous mappings. By using a weaker condition than the strong monotonicity and some additional conditions, we achieve several results on the unique solvability to the underlying problem, which are exported by making use of the exceptional family of elements. As an adjunct, we also obtain the nonemptiness and compactness of the solution sets to the weakly homogeneous generalized variational inequality under some appropriate conditions. The conclusions presented in this paper are new or supplements to the existing ones even when the problem comes down to its important subclasses studied in recent years. PubDate: 2021-08-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

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-08-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We study a conical extension of averaged nonexpansive operators and the role it plays in convergence analysis of fixed point algorithms. Various properties of conically averaged operators are systematically investigated, in particular, the stability under relaxations, convex combinations and compositions. We derive conical averagedness properties of resolvents of generalized monotone operators. These properties are then utilized in order to analyze the convergence of the proximal point algorithm, the forward–backward algorithm, and the adaptive Douglas–Rachford algorithm. Our study unifies, improves and casts new light on recent studies of these topics. PubDate: 2021-07-30

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: In this study, we consider a health network that faces uncertain supply disruptions in the form of regional, nationwide, or worldwide drug shortages. Each hospital observes stochastic demand and if the drug is unavailable, patients leave and receive care in another network. As these instances of unavailability diminish the brand value, health networks look for inventory sharing mechanisms among hospitals to mitigate the effect of uncertain supply disruptions. In line with this expectation, we propose a proactive inventory sharing approach for critical drugs to investigate the effect of the inventory-related parameters on service levels. PubDate: 2021-07-30

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family implicitly induces a convex underestimator of the objective function on the feasible region of the quadratic program. This alternative perspective on convex relaxations enables us to establish several useful properties of the corresponding convex underestimators. In particular, if the recession cone of the feasible region of the quadratic program does not contain any directions of negative curvature, we show that the convex underestimator arising from the copositive relaxation is precisely the convex envelope of the objective function of the quadratic program, strengthening Burer’s well-known result on the exactness of the copositive relaxation in the case of nonconvex quadratic programs. We also present an algorithmic recipe for constructing instances of quadratic programs with a finite optimal value but an unbounded relaxation for a rather large family of convex relaxations including the doubly nonnegative relaxation. PubDate: 2021-07-29

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: We study directional strict efficiency in vector optimization and equilibrium problems with set-valued map objectives. We devise several possibilities to define a meaningful concept of strict efficiency in a directional sense for these kinds of problems and then we present necessary optimality conditions from several perspectives by means of generalized differentiation calculus. A concept of generalized convexity for multimappings is employed as well and its role in getting equivalence between some classes of solutions is emphasized. PubDate: 2021-07-29

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: In this research, stochastic geometric programming with joint chance constraints is investigated with elliptically distributed random parameters. The constraint’s random coefficient vectors are considered dependent, and the dependence of the random vectors is handled through copulas. Moreover, Archimedean copulas are used to derive the random rows distribution. A convex approximation optimization problem is proposed for this class of stochastic geometric programming problems using a standard variable transformation. Furthermore, a piecewise tangent approximation and sequential convex approximation are employed to obtain the lower and upper bounds for the convex optimization model, respectively. Finally, an illustrative optimization example on randomly generated data is presented to demonstrate the efficiency of the methods and algorithms. PubDate: 2021-07-28

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: In this paper, we consider a class of fourth degree polynomial problems, which are NP-hard. First, we are concerned with the bi-quadratic optimization problem (Bi-QOP) over compact sets, which is proven to be equivalent to a multi-linear optimization problem (MOP) when the objective function of Bi-QOP is concave. Then, we introduce an augmented Bi-QOP (which can also be regarded as a regularized Bi-QOP) for the purpose to guarantee the concavity of the underlying objective function. Theoretically, both the augmented Bi-QOP and the original problem share the same optimal solutions when the compact sets are specified as unit spheres. By exploiting the multi-block structure of the resulting MOP, we accordingly propose a proximal alternating minimization algorithm to get an approximate optimal value of the problem under consideration. Convergence of the proposed algorithm is established under mild conditions. Finally, some preliminary computational results on synthetic datasets are reported to show the efficiency of the proposed algorithm. PubDate: 2021-07-27

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: The aim of this paper is to establish new results on the error bounds for a class of vector equilibrium problems with partial order provided by a polyhedral cone generated by some matrix. We first propose some regularized gap functions of this problem using the concept of \(\mathcal {G}_{A}\) -convexity of a vector-valued function. Then, we derive error bounds for vector equilibrium problems with partial order given by a polyhedral cone in terms of regularized gap functions under some suitable conditions. Finally, a real-world application to a vector network equilibrium problem is given to illustrate the derived theoretical results. PubDate: 2021-07-24

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Branch and Bound (B&B) algorithms in Global Optimization are used to perform an exhaustive search over the feasible area. One choice is to use simplicial partition sets. Obtaining sharp and cheap bounds of the objective function over a simplex is very important in the construction of efficient Global Optimization B&B algorithms. Although enclosing a simplex in a box implies an overestimation, boxes are more natural when dealing with individual coordinate bounds, and bounding ranges with Interval Arithmetic (IA) is computationally cheap. This paper introduces several linear relaxations using gradient information and Affine Arithmetic and experimentally studies their efficiency compared to traditional lower bounds obtained by natural and centered IA forms and their adaption to simplices. A Global Optimization B&B algorithm with monotonicity test over a simplex is used to compare their efficiency over a set of low dimensional test problems with instances that either have a box constrained search region or where the feasible set is a simplex. Numerical results show that it is possible to obtain tight lower bounds over simplicial subsets. PubDate: 2021-07-10

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: In many real-world problems there is often the requirement to optimise multiple conflicting objectives in an efficient manner. In such problems there can be the requirement to optimise a mixture of continuous and discrete variables. Herein, we propose a new multi-objective algorithm capable of optimising both continuous and discrete bounded variables in an efficient manner. The algorithm utilises Gaussian processes as surrogates in combination with a novel distance metric based upon Gower similarity. The MVMOO algorithm was compared to an existing mixed variable implementation of NSGA-II and random sampling for three test problems. MVMOO shows competitive performance on all proposed problems with efficient data acquisition and approximation of the Pareto fronts for the selected test problems. PubDate: 2021-07-09

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: It is well known that the convex hull of \(\{{(x,y,xy)}\}\) , where (x, y) is constrained to lie in a box, is given by the reformulation-linearization technique (RLT) constraints. Belotti et al. (Electron Notes Discrete Math 36:805–812, 2010) and Miller et al. (SIAG/OPT Views News 22(1):1–8, 2011) showed that if there are additional upper and/or lower bounds on the product \(z=xy\) , then the convex hull can be represented by adding an infinite family of inequalities, requiring a separation algorithm to implement. Nguyen et al. (Math Progr 169(2):377–415, 2018) derived convex hulls for \(\{(x,y,z)\}\) with bounds on \(z=xy^b\) , \(b\ge 1\) . We focus on the case where \(b=1\) and show that the convex hull with either an upper bound or lower bound on the product is given by RLT constraints, the bound on z and a single second-order cone (SOC) constraint. With both upper and lower bounds on the product, the convex hull can be represented using no more than three SOC constraints, each applicable on a subset of (x, y) values. In addition to the convex hull characterizations, volumes of the convex hulls with either an upper or lower bound on z are calculated and compared to the relaxation that imposes only the RLT constraints. As an application of these volume results, we show how spatial branching can be applied to the product variable so as to minimize the sum of the volumes for the two resulting subproblems. PubDate: 2021-06-05 DOI: 10.1007/s10898-021-01046-7