A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z  

  Subjects -> STATISTICS (Total: 130 journals)
The end of the list has been reached or no journals were found for your choice.
Similar Journals
Journal Cover
Optimization Letters
Journal Prestige (SJR): 0.721
Citation Impact (citeScore): 1
Number of Followers: 2  
 
  Hybrid Journal Hybrid journal (It can contain Open Access articles)
ISSN (Print) 1862-4480 - ISSN (Online) 1862-4472
Published by Springer-Verlag Homepage  [2468 journals]
  • Exact QR factorizations of rectangular matrices

    • Free pre-print version: Loading...

      Abstract: Abstract QR factorization is a key tool in mathematics, computer science, operations research, and engineering. This paper presents the roundoff-error-free (REF) QR factorization framework comprising integer-preserving versions of the standard and the thin QR factorizations and associated algorithms to compute them. Specifically, the standard REF QR factorization factors a given matrix \(A\in {\mathbb {Z}}^{m\times n}\) as \(A=QDR\) , where \(Q\in {\mathbb {Z}}^{m\times m}\) has pairwise orthogonal columns, D is a diagonal matrix, and \(R\in {\mathbb {Z}}^{m\times n}\) is an upper trapezoidal matrix; notably, the entries of Q and R are integral, while the entries of D are reciprocals of integers. In the thin REF QR factorization, \(Q\in {\mathbb {Z}}^{m\times n}\) also has pairwise orthogonal columns, and \(R\in {\mathbb {Z}}^{n\times n}\) is also an upper triangular matrix. In contrast to traditional (i.e., floating-point) QR factorizations, every operation used to compute these factors is integral; thus, REF QR is guaranteed to be an exact orthogonal decomposition. Importantly, the bit-length of every entry in the REF QR factorizations (and within the algorithms to compute them) is bounded polynomially. Notable applications of our REF QR factorizations include finding exact least squares or exact basic solutions, \({\textbf{x}}\in {\mathbb {Q}}^n\) , to any given full column rank or rank deficient linear system \(A {\textbf{x}}= {\textbf{b}}\) , respectively. In addition, our exact factorizations can be used as a subroutine within exact and/or high-precision quadratic programming. Altogether, REF QR provides a framework to obtain exact orthogonal factorizations of any rational matrix (as any rational/decimal matrix can be easily transformed into an integral matrix).
      PubDate: 2024-02-22
       
  • Local convergence analysis of an inexact trust-region method for nonsmooth
           optimization

    • Free pre-print version: Loading...

      Abstract: Abstract In Baraldi (Math Program 20:1–40, 2022), we introduced an inexact trust-region algorithm for minimizing the sum of a smooth nonconvex function and a nonsmooth convex function in Hilbert space—a class of problems that is ubiquitous in data science, learning, optimal control, and inverse problems. This algorithm has demonstrated excellent performance and scalability with problem size. In this paper, we enrich the convergence analysis for this algorithm, proving strong convergence of the iterates with guaranteed rates. In particular, we demonstrate that the trust-region algorithm recovers superlinear, even quadratic, convergence rates when using a second-order Taylor approximation of the smooth objective function term.
      PubDate: 2024-02-21
       
  • Optimality conditions for robust weakly efficient solutions in uncertain
           optimization

    • Free pre-print version: Loading...

      Abstract: Abstract In this paper, we find the flimsily robust weakly efficient solution to the uncertain vector optimization problem by means of the weighted sum scalarization method and strictly robust counterpart. In addition, we introduce a higher-order weak upper inner Studniarski epiderivative of set-valued maps, and obtain two properties of the new notion under the assumption of the star-shaped set. Finally, by applying the higher-order weak upper inner Studniarski epiderivative, we obtain a sufficient and necessary optimality condition of the vector-based robust weakly efficient solution to an uncertain vector optimization problem under the condition of the higher-order strictly generalized cone convexity. As applications, the corresponding optimality conditions of the robust (weakly) Pareto solutions are obtained by the current methods.
      PubDate: 2024-02-13
       
  • Characterization of unique solvability of absolute value equations: an
           overview, extensions, and future directions

    • Free pre-print version: Loading...

      Abstract: Abstract This paper provides an overview of the necessary and sufficient conditions for guaranteeing the unique solvability of absolute value equations. In addition to discussing the basic form of these equations, we also address several generalizations, including generalized absolute value equations and matrix absolute value equations. Our survey encompasses known results as well as novel characterizations proposed in this study.
      PubDate: 2024-02-09
       
  • A fast primal-dual algorithm via dynamical system with variable mass for
           linearly constrained convex optimization

    • Free pre-print version: Loading...

      Abstract: Abstract We aim to solve the linearly constrained convex optimization problem whose objective function is the sum of a differentiable function and a non-differentiable function. We first propose an inertial continuous primal-dual dynamical system with variable mass for linearly constrained convex optimization problems with differentiable objective functions. The dynamical system is composed of a second-order differential equation with variable mass for the primal variable and a first-order differential equation for the dual variable. The fast convergence properties of the proposed dynamical system are proved by constructing a proper energy function. We then extend the results to the case where the objective function is non-differentiable, and a new accelerated primal-dual algorithm is presented. When both variable mass and time scaling satisfy certain conditions, it is proved that our new algorithm owns fast convergence rates for the objective function residual and the feasibility violation. Some preliminary numerical results on the \(\ell _{1}\) – \(\ell _{2}\) minimization problem demonstrate the validity of our algorithm.
      PubDate: 2024-01-28
       
  • Constrained many-to-many point matching in two dimensions

    • Free pre-print version: Loading...

      Abstract: Abstract In the minimum-weight many-to-many point matching problem, we are given a set R of red points and a set B of blue points in the plane, of total size N, and we want to pair up each point in R to one or more points in B and vice versa so that the sum of distances between the paired points is minimized. This problem can be solved in \(O(N^3)\) time by using a reduction to the minimum-weight perfect matching problem, and thus, it is not fast enough to be used for on-line systems where a large number of tunes need to be compared. Motivated by similarity problems in music theory, in this paper we study several constrained minimum-weight many-to-many point matching problems in which the allowed pairings are given by geometric restrictions, i.e., a bichromatic pair can be matched if and only if the corresponding points satisfy a specific condition of closeness. We provide algorithms to solve these constrained versions in O(N) time when the sets R and B are given ordered by abscissa.
      PubDate: 2024-01-26
       
  • Differentially private k-center problems

    • Free pre-print version: Loading...

      Abstract: Abstract Data privacy has become one of the most important concerns in the big data era. Because of its broad applications in machine learning and data analysis, many algorithms and theoretical results have been established for privacy clustering problems, such as k-means and k-median problems with privacy protection. However, there is little work on privacy protection in k-center clustering. Our research focuses on the k-center problem, its distributed variant, and the distributed k-center problem under differential privacy constraints. These problems model the concept of safeguarding the privacy of individual input elements, with the integration of differential privacy aimed at ensuring the security of individual information during data processing and analysis. We propose three approximation algorithms for these problems, respectively, and achieve a constant factor approximation ratio.
      PubDate: 2024-01-25
       
  • Duality in the problems of optimal control described by Darboux-type
           differential inclusions

    • Free pre-print version: Loading...

      Abstract: Abstract This paper is devoted to the optimization of the Mayer problem with hyperbolic differential inclusions of the Darboux type and duality. We use the discrete approximation method to get sufficient conditions of optimality for the convex problem given by Darboux differential inclusions and the polyhedral problem for a hyperbolic differential inclusion with state constraint. We formulate the adjoint inclusions in the Euler-Lagrange inclusion and Hamiltonian forms. Then, we construct the dual problem to optimal control problem given by Darboux differential inclusions with state constraint and prove so-called duality results. Moreover, we show that each pair of primal and dual problem solutions satisfy duality relations and that the optimal values in the primal convex and dual concave problems are equal. Finally, we establish the dual problem to the polyhedral Darboux problem and provide an example to demonstrate the main constructions of our approach.
      PubDate: 2024-01-25
       
  • Determining optimal channel partition for 2:4 fine grained structured
           sparsity

    • Free pre-print version: Loading...

      Abstract: Abstract Deep Neural Networks (DNNs) have demonstrated tremendous success in many applications, but incur high computational burden on the inference side. The 2:4 sparsity pruning method has recently been developed to effectively compress and accelerate DNNs with little to no loss in performance. The method comprises a training phase followed by a pruning step where 2 out of 4 consecutive weights are eliminated to obtain a pruned matrix, which is then retrained to fine-tune the remaining weights. The accuracy of the resultant sparse network is maximized by permuting the matrix along the channel dimension in a way that maximizes the total magnitude of weights preserved during pruning. While earlier works have proposed heuristic methods to generate good permutations, we formalized the problem as a discrete optimization problem. In this paper, we propose four different mathematical programs to determine the optimal permutations and compare their performance for small-sized instances using a standard solver. Further, we develop a complementary column generation scheme to solve DNNs with realistic number of channels.
      PubDate: 2024-01-11
       
  • Representation of positive polynomials on a generalized strip and its
           application to polynomial optimization

    • Free pre-print version: Loading...

      Abstract: Abstract We study the representation of nonnegative polynomials in two variables on a certain class of unbounded closed basic semi-algebraic sets (which are called generalized strips). This class includes the strip \([a,b] \times {\mathbb {R}}\) which was studied by Marshall in (Proc Am Math Soc 138(5):1559–1567, 2010). A denominator-free Nichtnegativstellensätz holds true on a generalized strip when the width of the generalized strip is constant and fails otherwise. As a consequence, we confirm that the standard hierarchy of semidefinite programming relaxations defined for the compact case can indeed be adapted to the generalized strip with constant width. For polynomial optimization problems on the generalized strip with non-constant width, we follow Ha-Pham’s work: Solving polynomial optimization problems via the truncated tangency variety and sums of squares.
      PubDate: 2024-01-11
       
  • A reduced Jacobian method with full convergence property

    • Free pre-print version: Loading...

      Abstract: Abstract In this paper, we propose a variant of the reduced Jacobian method (RJM) introduced by El Maghri and Elboulqe (J Optim Theory Appl 179:917–943, 2018) for multicriteria optimization under linear constraints. Motivation is that, contrarily to RJM which has only global convergence to Pareto KKT-stationary points in the classical sense of accumulation points, this new variant possesses the full convergence property in the sense that the entire sequence converges whenever the objectives are quasiconvex. Simulations are reported showing the performance of this variant compared to RJM and the nondominated sorting genetic algorithm (NSGA-II).
      PubDate: 2024-01-07
       
  • Single machine scheduling to minimize maximum earliness/tardiness cost
           with job rejection

    • Free pre-print version: Loading...

      Abstract: Abstract We study a single machine due-date assignment problem with a common due-date. The objective function is minimizing the maximum earliness/tardiness cost. The scheduler may process only a subset of the jobs and the remaining jobs are rejected. Job-dependent rejection-costs are considered, and an upper bound on the total permitted rejection cost is assumed. The problem is proved to be NP-Hard. We present and test a pseudo-polynomial dynamic programming solution algorithm. An extension to the setting containing additional due-date cost component is also discussed. An efficient implementation of the algorithm is introduced, and medium size problems (containing hundreds of jobs) are shown to be solved in very reasonable running time. In addition, an intuitive heuristic is introduced, tested numerically, and is shown to produce very small optimality gaps.
      PubDate: 2024-01-05
       
  • A parallel greedy approach enhanced by genetic algorithm for the
           stochastic rig routing problem

    • Free pre-print version: Loading...

      Abstract: Abstract Scheduling drilling activities for oil and gas exploration involves solving a problem of optimal routing of a fleet of vehicles that represent drilling rigs. Given a set of sites in some geographic area and a certain number of wells to drill in each site, the problem asks to find routes for all the rigs, minimizing the total travel time and respecting the time windows constraints. It is allowed that the same site can be visited by many rigs until all the required wells are drilled. An essential part of the considered problem is the uncertain drilling time in each site due to geological characteristics that cannot be fully predicted. A mixed integer programming model and a parallel greedy algorithm proposed in an earlier study can be used for solving very small-sized instances. In this paper, a graphics processing unit (GPU) accelerated genetic algorithm is developed for using in the greedy algorithm as a subroutine. This approach was implemented and tested on a high-performance computing cluster and the experiments have shown good ability to solve large-scale problems.
      PubDate: 2024-01-01
       
  • Uniqueness of solutions in multivariate Chebyshev approximation problems

    • Free pre-print version: Loading...

      Abstract: Abstract We study the solution set to multivariate Chebyshev approximation problem, focussing on the ill-posed case when the uniqueness of solutions can not be established via strict polynomial separation. We obtain an upper bound on the dimension of the solution set and show that nonuniqueness is generic for ill-posed problems on discrete domains. Moreover, given a prescribed set of points of minimal and maximal deviation we construct a function for which the dimension of the set of best approximating polynomials is maximal for any choice of domain. We also present several examples that illustrate the aforementioned phenomena, demonstrate practical application of our results and propose a number of open questions.
      PubDate: 2024-01-01
       
  • Checking weak and strong optimality of the solution to interval convex
           quadratic programming in a general form

    • Free pre-print version: Loading...

      Abstract: Abstract We discuss the problems of checking weak and strong optimality of the solution to interval convex quadratic programs in a general form. A given vector is called a weakly(strongly) optimal solution to an interval convex quadratic program if it is an optimal solution for some(each) concrete setting of the interval convex quadratic program. Based on the feature of feasible directions, different methods to test weak and strong optimality of a given vector corresponding to general interval convex quadratic programs, including both equations and inequalities, are proposed respectively, as well as some useful corollaries. Several numerical examples are given to show the effectiveness of the main results.
      PubDate: 2024-01-01
       
  • k-sparse vector recovery via Truncated $$\ell _1-\ell _2$$ local
           minimization

    • Free pre-print version: Loading...

      Abstract: Abstract This article mainly solves the following model, $$\begin{aligned} min\ \Vert x_{\Gamma ^C_{x,t}}\Vert _1-\Vert x_{\Gamma ^C_{x,t}}\Vert _2\qquad subject \quad to \qquad Ax=y, \end{aligned}$$ where \(\Gamma _{x,t}\subset [n]\) represents the index of the maximum number of t elements in x after taking the absolute value. We call this model Truncated \(\ell _1-\ell _2\) model. We mainly deal with the recovery of unknown signals under the condition of \( supp(x) >t\) , \(\sigma _t(x)>\sigma _{t+1}(x)\) , where \(\sigma _t(x)\) represents the t largest number in x . Firstly, we give the necessary and sufficient condition for recovering the fixed unknown signal satisfying the above two conditions via Truncated \(\ell _1-\ell _2\) local minimization. Then, according to this condition, we give the necessary and sufficient conditions to recovering for all unknown signals satisfying the above two conditions via Truncated \(\ell _1-\ell _2\) local minimization. Compared with N. Bi’s recent proposed condition in Bi and Tang (Appl Comput Harmon Anal 56:337–350, 2022), we will show that our condition is weaker and the detail of such discussion is in Remark 3 of the manuscript. Then, we give the algorithm of Truncated \(\ell _1-\ell _2\) model. According to this algorithm, we do data experiments and the data experiments show that the recovery rate of Truncated \(\ell _1-\ell _2\) is better than that of model \(\ell _1-\ell _2\) .
      PubDate: 2024-01-01
       
  • Worst-case evaluation complexity of a derivative-free quadratic
           regularization method

    • Free pre-print version: Loading...

      Abstract: Abstract This manuscript presents a derivative-free quadratic regularization method for unconstrained minimization of a smooth function with Lipschitz continuous gradient. At each iteration, trial points are computed by minimizing a quadratic regularization of a local model of the objective function. The models are based on forward finite-difference gradient approximations. By using a suitable acceptance condition for the trial points, the accuracy of the gradient approximations is dynamically adjusted as a function of the regularization parameter used to control the stepsizes. Worst-case evaluation complexity bounds are established for the new method. Specifically, for nonconvex problems, it is shown that the proposed method needs at most \({\mathcal {O}}\left( n\epsilon ^{-2}\right)\) function evaluations to generate an \(\epsilon\) -approximate stationary point, where n is the problem dimension. For convex problems, an evaluation complexity bound of \({\mathcal {O}}\left( n\epsilon ^{-1}\right)\) is obtained, which is reduced to \({\mathcal {O}}\left( n\log (\epsilon ^{-1})\right)\) under strong convexity. Numerical results illustrating the performance of the proposed method are also reported.
      PubDate: 2024-01-01
       
  • A local search algorithm for the k-path partition problem

    • Free pre-print version: Loading...

      Abstract: Abstract Given an undirected graph \(G=(V,E)\) , the k-path partition problem is to find a collection of vertex-disjoint paths containing at most k vertices to cover all the vertices of V. The objective is to minimize the number of paths in the collection. For the k-path partition problem with \(k\ge 3\) , we propose a simple local search algorithm, whose approximation ratio improves on the best-known approximation algorithm in Chen (in: Chen, Li, Zhang (eds) Frontiers of algorithmics, Springer, Cham, 2022) for every \(k\ge 4\) , especially for \(k=4,5,6,7\) . In addition, we give examples to show that our algorithm is tight when k is odd. When k is even, we give almost tight examples.
      PubDate: 2024-01-01
       
  • Linear-size formulations for connected planar graph partitioning and
           political districting

    • Free pre-print version: Loading...

      Abstract: Abstract Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation for this task that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (ii) it is perfect. To explore its ability to solve real-world problems, we apply it to a political districting problem in which contiguity and population balance are imposed as hard constraints and compactness is optimized. Computational experiments show that, despite the model’s small size and integrality for connected partitioning, the population balance constraints are more troublesome to effectively impose. Nevertheless, we share our findings in hopes that others may find better ways to impose them.
      PubDate: 2024-01-01
       
  • A clustering heuristic to improve a derivative-free algorithm for
           nonsmooth optimization

    • Free pre-print version: Loading...

      Abstract: Abstract In this paper we propose an heuristic to improve the performances of the recently proposed derivative-free method for nonsmooth optimization CS-DFN. The heuristic is based on a clustering-type technique to compute an estimate of Clarke’s generalized gradient of the objective function, obtained via calculation of the (approximate) directional derivative along a certain set of directions. A search direction is then calculated by applying a nonsmooth Newton-type approach. As such, this direction (as it is shown by the numerical experiments) is a good descent direction for the objective function. We report some numerical results and comparison with the original CS-DFN method to show the utility of the proposed improvement on a set of well-known test problems.
      PubDate: 2024-01-01
       
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
 


Your IP address: 18.207.129.175
 
Home (Search)
API
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-
JournalTOCs
 
 

 A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z  

  Subjects -> STATISTICS (Total: 130 journals)
The end of the list has been reached or no journals were found for your choice.
Similar Journals
Similar Journals
HOME > Browse the 73 Subjects covered by JournalTOCs  
SubjectTotal Journals
 
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
 


Your IP address: 18.207.129.175
 
Home (Search)
API
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-