Optimization Letters
Journal Prestige (SJR): 0.721 Citation Impact (citeScore): 1 Number of Followers: 2 Hybrid journal (It can contain Open Access articles) ISSN (Print) 18624480  ISSN (Online) 18624472 Published by SpringerVerlag [2468 journals] 
 Exact QR factorizations of rectangular matrices

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract QR factorization is a key tool in mathematics, computer science, operations research, and engineering. This paper presents the roundofferrorfree (REF) QR factorization framework comprising integerpreserving 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., floatingpoint) QR factorizations, every operation used to compute these factors is integral; thus, REF QR is guaranteed to be an exact orthogonal decomposition. Importantly, the bitlength 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 highprecision 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: 20240222

 Local convergence analysis of an inexact trustregion method for nonsmooth
optimization
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In Baraldi (Math Program 20:1–40, 2022), we introduced an inexact trustregion 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 trustregion algorithm recovers superlinear, even quadratic, convergence rates when using a secondorder Taylor approximation of the smooth objective function term.
PubDate: 20240221

 Optimality conditions for robust weakly efficient solutions in uncertain
optimization
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 higherorder weak upper inner Studniarski epiderivative of setvalued maps, and obtain two properties of the new notion under the assumption of the starshaped set. Finally, by applying the higherorder weak upper inner Studniarski epiderivative, we obtain a sufficient and necessary optimality condition of the vectorbased robust weakly efficient solution to an uncertain vector optimization problem under the condition of the higherorder strictly generalized cone convexity. As applications, the corresponding optimality conditions of the robust (weakly) Pareto solutions are obtained by the current methods.
PubDate: 20240213

 Characterization of unique solvability of absolute value equations: an
overview, extensions, and future directions
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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: 20240209

 A fast primaldual algorithm via dynamical system with variable mass for
linearly constrained convex optimization
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We aim to solve the linearly constrained convex optimization problem whose objective function is the sum of a differentiable function and a nondifferentiable function. We first propose an inertial continuous primaldual dynamical system with variable mass for linearly constrained convex optimization problems with differentiable objective functions. The dynamical system is composed of a secondorder differential equation with variable mass for the primal variable and a firstorder 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 nondifferentiable, and a new accelerated primaldual 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: 20240128

 Constrained manytomany point matching in two dimensions

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In the minimumweight manytomany 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 minimumweight perfect matching problem, and thus, it is not fast enough to be used for online 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 minimumweight manytomany 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: 20240126

 Differentially private kcenter problems

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 kmeans and kmedian problems with privacy protection. However, there is little work on privacy protection in kcenter clustering. Our research focuses on the kcenter problem, its distributed variant, and the distributed kcenter 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: 20240125

 Duality in the problems of optimal control described by Darbouxtype
differential inclusions
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 EulerLagrange inclusion and Hamiltonian forms. Then, we construct the dual problem to optimal control problem given by Darboux differential inclusions with state constraint and prove socalled 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: 20240125

 Determining optimal channel partition for 2:4 fine grained structured
sparsity
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 finetune 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 smallsized instances using a standard solver. Further, we develop a complementary column generation scheme to solve DNNs with realistic number of channels.
PubDate: 20240111

 Representation of positive polynomials on a generalized strip and its
application to polynomial optimization
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study the representation of nonnegative polynomials in two variables on a certain class of unbounded closed basic semialgebraic 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 denominatorfree 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 nonconstant width, we follow HaPham’s work: Solving polynomial optimization problems via the truncated tangency variety and sums of squares.
PubDate: 20240111

 A reduced Jacobian method with full convergence property

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 KKTstationary 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 (NSGAII).
PubDate: 20240107

 Single machine scheduling to minimize maximum earliness/tardiness cost
with job rejection
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study a single machine duedate assignment problem with a common duedate. 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. Jobdependent rejectioncosts are considered, and an upper bound on the total permitted rejection cost is assumed. The problem is proved to be NPHard. We present and test a pseudopolynomial dynamic programming solution algorithm. An extension to the setting containing additional duedate 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: 20240105

 A parallel greedy approach enhanced by genetic algorithm for the
stochastic rig routing problem
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 smallsized 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 highperformance computing cluster and the experiments have shown good ability to solve largescale problems.
PubDate: 20240101

 Uniqueness of solutions in multivariate Chebyshev approximation problems

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study the solution set to multivariate Chebyshev approximation problem, focussing on the illposed 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 illposed 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: 20240101

 Checking weak and strong optimality of the solution to interval convex
quadratic programming in a general form
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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: 20240101

 ksparse vector recovery via Truncated $$\ell _1\ell _2$$ local
minimization
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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: 20240101

 Worstcase evaluation complexity of a derivativefree quadratic
regularization method
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract This manuscript presents a derivativefree 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 finitedifference 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. Worstcase 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: 20240101

 A local search algorithm for the kpath partition problem

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Given an undirected graph \(G=(V,E)\) , the kpath partition problem is to find a collection of vertexdisjoint 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 kpath partition problem with \(k\ge 3\) , we propose a simple local search algorithm, whose approximation ratio improves on the bestknown 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: 20240101

 Linearsize formulations for connected planar graph partitioning and
political districting
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
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 realworld 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: 20240101

 A clustering heuristic to improve a derivativefree algorithm for
nonsmooth optimization
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper we propose an heuristic to improve the performances of the recently proposed derivativefree method for nonsmooth optimization CSDFN. The heuristic is based on a clusteringtype 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 Newtontype 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 CSDFN method to show the utility of the proposed improvement on a set of wellknown test problems.
PubDate: 20240101
