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: Nonconvex minimax problems have attracted significant interest in machine learning and many other fields in recent years. In this paper, we propose a new zeroth-order alternating randomized gradient projection algorithm to solve smooth nonconvex-linear problems and its iteration complexity to find an \(\varepsilon \) -first-order Nash equilibrium is \({\mathcal {O}}\left( \varepsilon ^{-3} \right) \) and the number of function value estimation per iteration is bounded by \({\mathcal {O}}\left( d_{x}\varepsilon ^{-2} \right) \) . Furthermore, we propose a zeroth-order alternating randomized proximal gradient algorithm for block-wise nonsmooth nonconvex-linear minimax problems and its corresponding iteration complexity is \({\mathcal {O}}\left( K^{\frac{3}{2}} \varepsilon ^{-3} \right) \) and the number of function value estimation is bounded by \({\mathcal {O}}\left( d_{x}\varepsilon ^{-2} \right) \) per iteration. The numerical results indicate the efficiency of the proposed algorithms. PubDate: 2022-05-18
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 max+sum spanning tree (MSST) problem is to determine a spanning tree T whose combined weight \(\max _{e\in T}w(e)+\sum _{e\in T}c(e)\) is minimum for a given edge-weighted undirected network G(V, E, c, w). This problem can be solved within \(O(m \log n)\) time, where m and n are the numbers of edges and nodes, respectively. An inverse MSST problem (IMSST) aims to determine a new weight vector \(\bar{w}\) so that a given \(T^0\) becomes an optimal MSST of the new network \(G(V,E,c,\bar{w})\) . The IMSST problem under weighted \(l_\infty \) norm is to minimize the modification cost \(\max _{e\in E} q(e) \bar{w}(e)-w(e) \) , where q(e) is a cost modifying the weight w(e). We first provide some optimality conditions of the problem. Then we propose a strongly polynomial time algorithm in \(O(m^2\log n)\) time based on a binary search and a greedy method. There are O(m) iterations and we solve an MSST problem under a new weight in each iteration. Finally, we perform some numerical experiments to show the efficiency of the algorithm. PubDate: 2022-05-16
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: Data uncertainty has a great impact on portfolio selection. Based on the popular mean-absolute deviation (MAD) model, we investigate how to make robust portfolio decisions. In this paper, a novel Wasserstein metric-based data-driven distributionally robust mean-absolute deviation (DR-MAD) model is proposed. However, the proposed model is non-convex with an infinite-dimensional inner problem. To solve this model, we prove that it can be transformed into two simple finite-dimensional linear programs. Consequently, the problem can be solved as easily as solving the classic MAD model. Furthermore, the proposed DR-MAD model is compared with the 1/N, classic MAD and mean-variance model on S &P 500 constituent stocks in six different settings. The experimental results show that the portfolios constructed by DR-MAD model are superior to the benchmarks in terms of profitability and stability in most fluctuating markets. This result suggests that Wasserstein distributionally robust optimization framework is an effective approach to address data uncertainty in portfolio optimization. PubDate: 2022-05-16
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: Bilevel optimization is an increasingly important tool to model hierarchical decision making. However, the ability of modeling such settings makes bilevel problems hard to solve in theory and practice. In this paper, we add on the general difficulty of this class of problems by further incorporating convex black-box constraints in the lower level. For this setup, we develop a cutting-plane algorithm that computes approximate bilevel-feasible points. We apply this method to a bilevel model of the European gas market in which we use a joint chance constraint to model uncertain loads. Since the chance constraint is not available in closed form, this fits into the black-box setting studied before. For the applied model, we use further problem-specific insights to derive bounds on the objective value of the bilevel problem. By doing so, we are able to show that we solve the application problem to approximate global optimality. In our numerical case study we are thus able to evaluate the welfare sensitivity in dependence of the achieved safety level of uncertain load coverage. PubDate: 2022-05-13
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: Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type \(\max \{c^\top x :A x = b,\, x \in {{\,\mathrm{\mathbb {Z}}\,}}^n_{\ge 0}\}\) , where all the entries of A, b, c are integer, parameterized by the number of rows of A and \(\Vert A\Vert _{\max }\) . This class of problems is known under the name of ILP problems in the standard form, adding the word ”bounded” if \(x \le u\) , for some integer vector u. Recently, many new sparsity, proximity, and complexity results were obtained for bounded and unbounded ILP problems in the standard form. In this paper, we consider ILP problems in the canonical form $$\begin{aligned} \max \{c^\top x :b_l \le A x \le b_r,\, x \in {{\,\mathrm{\mathbb {Z}}\,}}^n\}, \end{aligned}$$ where \(b_l\) and \(b_r\) are integer vectors. We assume that the integer matrix A has the rank n, \((n + m)\) rows, n columns, and parameterize the problem by m and \(\Delta (A)\) , where \(\Delta (A)\) is the maximum of \(n \times n\) sub-determinants of A, taken in the absolute value. We show that any ILP problem in the standard form can be polynomially reduced to some ILP problem in the canonical form, preserving m and \(\Delta (A)\) , but the reverse reduction is not always possible. More precisely, we define the class of generalized ILP problems in the standard form, which includes an additional group constraint, and prove the equivalence to ILP problems in the canonical form. We generalize known sparsity, proximity, and complexity bounds for ILP problems in the canonical form. Additionally, sometimes, we strengthen previously known results for ILP problems in the canonical form, and, sometimes, we give shorter proofs. Finally, we consider the special cases of \(m \in \{0,1\}\) . By this way, we give specialised sparsity, proximity, and complexity bounds for the problems on simplices, Knapsack problems and Subset-Sum problems. PubDate: 2022-05-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: Cutting planes from the Boolean Quadric Polytope can be used to reduce the optimality gap of the \(\mathcal {NP}\) -hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal–Gomory closure of the Boolean Quadric Polytope are A-odd cycle inequalities. We obtain a compact extended relaxation of all A-odd cycle inequalities, which allows to optimize over the Chvátal–Gomory closure without repeated calls to separation algorithms and has less inequalities than the formulation provided by Boros et al. (SIAM J Discrete Math 5(2):163–177, 1992) for sparse matrices. In a computational study, we confirm the strength of this relaxation and show that we can provide very strong bounds for the BoxQP, even with a plain linear program. The resulting bounds are significantly stronger than these from Bonami et al. (Math Program Comput 10(3):333–382, 2018), which arise from separating A-odd cycle inequalities heuristically. PubDate: 2022-05-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: We study convergence of the trajectories of the Heavy Ball dynamical system, with constant damping coefficient, in the framework of convex and non-convex smooth optimization. By using the Polyak–Łojasiewicz condition, we derive new linear convergence rates for the associated trajectory, in terms of objective function values, without assuming uniqueness of the minimizer. PubDate: 2022-05-06
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: Abstract The aim of this paper is to explore the stability of (weak)-minimal solutions for set-valued optimization problems via improvement sets. Firstly, the optimality and closedness of solution sets for the set-valued optimization problem under the upper order relation are discussed. Then, a new convergence concept for set-valued mapping sequences is introduced, and some properties of the set-valued mapping sequences are shown under the new convergence assumption. Moreover, by means of upper level sets, Painlevé-Kuratowski convergences of (weak) E-u-solutions to set-valued optimization problems with respect to the perturbations of feasible sets and objective mappings are established under mild conditions. The order that we use to establish the result depends on the improvement set, which is not necessarily a cone order. Our results can be seen as the extension of the related work established recently in this field. PubDate: 2022-05-03
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: Abstract We consider higher-order conditions and sensitivity analysis for solutions to equilibrium problems. The conditions for solutions are in terms of quasi-contingent derivatives and involve higher-order complementarity slackness for both the objective and the constraints and under Hölder metric subregularity assumptions. For sensitivity analysis, a formula of this type of derivative of the solution map to a parametric equilibrium problem is established in terms of the same types of derivatives of the data of the problem. Here, the concepts of a quasi-contingent derivative and critical directions are new. We consider open-cone solutions and proper solutions. We also study an important and typical special case: weak solutions of a vector minimization problem with mixed constraints. The results are significantly new and improve recent corresponding results in many aspects. PubDate: 2022-05-03
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: Abstract New mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in d-space (with \(d\ge 3\) ) will be presented in this work. All models feature a nonsmooth objective function but the continuous relaxations of their set of feasible solutions are convex. From these models, four convex mixed integer linear and nonlinear relaxations will be considered. Each relaxation has the same set of feasible solutions as the set of feasible solutions of the model from which it is derived. Finally, preliminary computational results highlighting the main features of the presented relaxations will be discussed. PubDate: 2022-05-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: Abstract Nuclear Magnetic Resonance (NMR) Spectroscopy is the second most used technique (after X-ray crystallography) for structural determination of proteins. A computational challenge in this technique involves solving a discrete optimization problem that assigns the resonance frequency to each atom in the protein. This paper introduces LIAN (LInear programming Assignment for NMR), a novel linear programming formulation of the problem which yields state-of-the-art results in simulated and experimental datasets. PubDate: 2022-05-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: 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: 2022-05-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: 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: 2022-05-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: 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: 2022-05-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: Abstract A Euclidean skeleton is a set of edges in the interior (or on the boundary) of a polygon that intersects any line segment that joins two points outside of the polygon and that intersects the polygon. In this paper we study minimum cardinality Euclidean skeletons and develop an algorithm for constructing them. We first prove a number of structural properties of minimum skeletons and use these to develop a canonical form. We then design an exact algorithm which initially generates a set of canonical skeleton edges, then executes a pruning module to reduce the set of candidate edges, and finally runs existing integer linear programming code to output an optimal solution. Finally, we perform computational testing on our algorithm to demonstrate its performance, and observe a number of experimental properties of minimum skeletons. PubDate: 2022-05-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: Abstract We study the problem of satisfying the maximum number of distance geometry constraints with minimum experimental error. This models the determination of the shape of proteins from atomic distance data which are obtained from nuclear magnetic resonance experiments and exhibit experimental and systematic errors. Experimental errors are represented by interval constraints on Euclidean distances. Systematic errors occur from a misassignment of distances to wrong atomic pairs: we represent such errors by maximizing the number of satisfiable distance constraints. We present many mathematical programming formulations, as well as a “matheuristic” algorithm based on reformulations, relaxations, restrictions and refinement. We show that this algorithm works on protein graphs with hundreds of atoms and thousands of distances. PubDate: 2022-05-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: Abstract We present three results which support the conjecture that a graph is minimally rigid in d-dimensional \(\ell _p\) -space, where \(p\in (1,\infty )\) and \(p\not =2\) , if and only if it is (d, d)-tight. Firstly, we introduce a graph bracing operation which preserves independence in the generic rigidity matroid when passing from \(\ell _p^d\) to \(\ell _p^{d+1}\) . We then prove that every (d, d)-sparse graph with minimum degree at most \(d+1\) and maximum degree at most \(d+2\) is independent in \(\ell _p^d\) . Finally, we prove that every triangulation of the projective plane is minimally rigid in \(\ell _p^3\) . A catalogue of rigidity preserving graph moves is also provided for the more general class of strictly convex and smooth normed spaces and we show that every triangulation of the sphere is independent for 3-dimensional spaces in this class. PubDate: 2022-05-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: Abstract Algorithm portfolios are multi-algorithmic schemes that combine a number of solvers into a joint framework for solving global optimization problems. A crucial part of such schemes is the resource allocation process that is responsible for assigning computational resources to the constituent algorithms. We propose a resource allocation process based on adaptive decision-making procedures. The proposed approach is incorporated in algorithm portfolios composed of three essential types of numerical optimization algorithms, namely gradient-based, direct search, and swarm intelligence algorithms. The designed algorithm portfolios are experimentally demonstrated on a challenging optimization problem for different dimensions and experimental settings. The accompanying statistical analysis offers interesting conclusions and insights on the performance of the algorithm portfolio compared to its constituent algorithms, as well as on the effect of its parameters. PubDate: 2022-04-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: Abstract Nonnegative Matrix Factorization (NMF) has attracted a great deal of attention as an effective technique for dimensionality reduction of large-scale nonnegative data. Given a nonnegative matrix, NMF aims to obtain two low-rank nonnegative factor matrices by solving a constrained optimization problem. The Hierarchical Alternating Least Squares (HALS) algorithm is a well-known and widely-used iterative method for solving such optimization problems. However, the original update rule used in the HALS algorithm is not well defined. In this paper, we propose a novel well-defined update rule of the HALS algorithm, and prove its global convergence in the sense of Zangwill. Unlike conventional globally-convergent update rules, the proposed one allows variables to take the value of zero and hence can obtain sparse factor matrices. We also present two stopping conditions that guarantee the finite termination of the HALS algorithm. The practical usefulness of the proposed update rule is shown through experiments using real-world datasets. PubDate: 2022-04-30
Hybrid journal (It can contain Open Access articles)
