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 In this paper, some properties of implicit Z-tensors are studied, and it is proved that an implicit Z-tensor is a nonsingular implicit M-tensor if and only if it is semi-positive. Then, a linearized method to solve tensor complementarity problem with an implicit Z-tensor is presented. Under the condition that the feasible set is nonempty, it is proved that the iterative sequence generated by the the method is monotonic convergence, which weakens the convergence condition of the related method in the literature. Final numerical experiments demonstrate the effectiveness of the method. PubDate: 2024-06-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 consider the minimization of a differentiable Lipschitz gradient but non necessarily convex, function F defined on \({\mathbb {R}}^N\) . We propose an accelerated gradient descent approach which combines three strategies, namely (i) a variable metric derived from the majorization-minimization principle; (ii) a subspace strategy incorporating information from the past iterates; (iii) a block alternating update. Under the assumption that F satisfies the Kurdyka–Łojasiewicz property, we give conditions under which the sequence generated by the resulting block majorize-minimize subspace algorithm converges to a critical point of the objective function, and we exhibit convergence rates for its iterates. PubDate: 2024-06-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 deals with a single-machine scheduling problem with a general linear deterioration effect. The goal is to determine the job schedule such that the total weighted number of late jobs is minimized. We present three properties, one heuristic algorithm and a lower bound to speed up the search process of the branch-and-bound algorithm. In addition, some complex heuristics (including tabu search and simulated annealing algorithms) are proposed as solutions to this problem. The computational results show that the proposed algorithms are effective and efficient. PubDate: 2024-06-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 The generalized alternating direction method of multipliers (ADMM) of Xiao et al. (Math Prog Comput 10:533–555, 2018) aims at the two-block linearly constrained composite convex programming problem, in which each block is in the form of “nonsmooth + quadratic”. However, in the case of non-quadratic (but smooth), this method may fail unless the favorable structure of “nonsmooth + smooth” is no longer used. This paper aims to remedy this defect by using a majorized technique to approximate the augmented Lagrangian function, so that the corresponding subproblems can be decomposed into some smaller problems and then solved separately. Furthermore, the recent symmetric Gauss–Seidel (sGS) decomposition theorem guarantees the equivalence between the bigger subproblem and these smaller ones. This paper focuses on convergence analysis, that is, we prove that the sequence generated by the proposed method converges globally to a Karush–Kuhn–Tucker point of the considered problem. Finally, we do some numerical experiments on a kind of simulated convex composite optimization problems which illustrate that the proposed method is evidently efficient. PubDate: 2024-06-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 consider adjustable robust linear complementarity problems and extend the results of Biefel et al. (SIAM J Optim 32:152–172, 2022) towards convex and compact uncertainty sets. Moreover, for the case of polyhedral uncertainty sets, we prove that computing an adjustable robust solution of a given linear complementarity problem is equivalent to solving a properly chosen mixed-integer linear feasibility problem. PubDate: 2024-06-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 One of the problematic research areas in optimization is determining a global optimum for non-convex quadratic fractional optimization problems as a hard problem. This study seeks the quadratic fractional optimization problem in the complex field with two second-order cone constraints. An equivalent quadratic reformulation of the problem is given using the well-known Dinkelbach method, which can obtain its global optimum by applying the semidefinite relaxation approach and rank-one decomposition algorithm at each iteration of some classical methods. Finally, the results show the effectiveness of the proposed methods. PubDate: 2024-06-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 In this paper, we consider the problem of minimizing the sum of a large number of smooth convex functions subject to a complicated constraint set defined by a smooth convex function. Such a problem has wide applications in many areas, such as machine learning and signal processing. By utilizing variance reduction and moving balls approximation techniques, we propose a new variance reduced moving balls approximation method. Compared with existing convergence rates of moving balls approximation-type methods that require the strong convexity of the objective function, a notable advantage of the proposed method is that the linear and sublinear convergence rates can be guaranteed under the quadratic gradient growth property and convexity condition, respectively. To demonstrate its effectiveness, numerical experiments for solving the smooth regularized logistic regression problem and the Neyman-Pearson classification problem are presented. PubDate: 2024-06-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 Denoising is an important preprocessing step that can improve the quality of the data and make it more suitable for further analysis, enhance the performance of machine learning models, identify underlying patterns, reduce computation time, and make data more interpretable by humans. Here we propose a tensor denoising approach based on Pareto efficient pairs and its relation with dual norms. We relate the problem of tensor denoising to that of maximizing the norm of the clean part while minimizing the norm of the noise. We propose a simple efficient method to remove additive noise of signals and compare the results, in terms of PSNR and MSE, with those of standard decomposition-based denoising methods over synthetically generated data. PubDate: 2024-06-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 a generalized Farkas’ Lemma for an inequality system involving distributions. This lemma establishes an equivalence between an infinite-dimensional system of moment inequalities and a semi-definite system, assuming that the support for the distributions is a spectrahedron. To the best of our knowledge, it is the first extension of Farkas’ Lemma to the distributional paradigm. Applying the new Lemma, we then establish no-gap duality results between a class of moment optimization problems and numerically tractable semi-definite programs. PubDate: 2024-06-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 The fixed-charge network flow problem (FCNFP) is widely used in industrial production and can be exactly solved by converting to mixed-integer linear programming (MILP). However, the long solving time of MILP solvers limits their applicability to large-scale problems. This paper proposes a sequential reduction algorithm called adaptive dynamic slope scaling procedure (ADSSP). ADSSP introduces an adaptive edge deletion strategy to improve solution quality and efficiency. Theoretical analysis proves the algorithm convergence and provides the best-case and worst-case time upper bounds of ADSSP. Numerical experiments show that ADSSP outperforms the previous linear programming-based iterative algorithms on different scales. In instances with hundreds of thousands of variables, ADSSP achieves a 2% improvement in the objective and takes only 3% solving time compared to the Cplex MILP Solver. The results demonstrate that ADSSP can significantly improve the solution quality with high efficiency for large-scale FCNFP. As a widely applicable optimization method, ADSSP can be a valuable tool for optimizing FCNFP and other similar problems. PubDate: 2024-06-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 propose a level proximal subdifferential for a proper lower semicontinuous function. Level proximal subdifferential is a uniform refinement of the well-known proximal subdifferential, and has the pleasant feature that its resolvent always coincides with the proximal mapping of a function. It turns out that the resolvent representation of proximal mapping in terms of Mordukhovich limiting subdifferential is only valid for hypoconvex functions. We also provide properties of level proximal subdifferential and numerous examples to illustrate our results. PubDate: 2024-06-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 consider the generalized Newton method (GNM) for the absolute value equation (AVE) \(Ax- x =b\) . The method has finite termination property whenever it is convergent, no matter whether the AVE has a unique solution. We prove that GNM is convergent whenever \(\rho ( A^{-1} )<1/3\) . We also present new results for the case where \(A-I\) is a nonsingular M-matrix or an irreducible singular M-matrix. When \(A-I\) is an irreducible singular M-matrix, the AVE may have infinitely many solutions. In this case, we show that GNM always terminates with a uniquely identifiable solution, as long as the initial guess has at least one nonpositive component. PubDate: 2024-05-20

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 the problem of determining the optimal node interception strategy during influence propagation over a (directed) network \(G=(V,A)\) . More specifically, this work aims to find an interception set \(D \subseteq V\) such that the influence spread over the remaining network \(G \backslash D\) under the linear threshold diffusion model is minimized. We prove its NP-hardness, even in the case when G is an undirected graph with unit edge weights. An exact algorithm based on integer linear programming and delayed constraint generation is proposed to determine the most critical nodes in the influence propagation process. Additionally, we investigate the technique of lifting inequalities of minimal activation sets. Experiments on the connected Watts-Strogatz small-world networks and real-world networks are also conducted to validate the effectiveness of our methodology. PubDate: 2024-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: Abstract In this article, we study weak stationarity conditions (A- and C-) for a particular class of degenerate stochastic mathematical programming problems with complementarity constraints (SMPCC, for short). Importance of the weak stationarity concepts in absence of SMPCC-LICQ are presented through toy problems in which the point of local or global minimizers are weak stationary points rather than satisfying other stronger stationarity conditions. Finally, a well known technique to solve stochastic programming problems, namely sample average approximation (SAA) method, is studied to show the significance of the weak stationarity conditions for degenerate SMPCC problems. Consistency of weak stationary estimators are established under weaker constraint qualifications than SMPCC-LICQ. PubDate: 2024-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: Abstract We propose a multistart algorithm to identify all local minima of a constrained, nonconvex stochastic optimization problem. The algorithm uniformly samples points in the domain and then starts a local stochastic optimization run from any point that is the “probabilistically best” point in its neighborhood. Under certain conditions, our algorithm is shown to asymptotically identify all local optima with high probability; this holds even though our algorithm is shown to almost surely start only finitely many local stochastic optimization runs. We demonstrate the performance of an implementation of our algorithm on nonconvex stochastic optimization problems, including identifying optimal variational parameters for the quantum approximate optimization algorithm. PubDate: 2024-05-07

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 In the game theoretical approach of the basic problem in Combinatorial Search an adversary thinks of a defective element d of an n-element pool X, and the questioner needs to find x by asking questions of type is \(d\in Q'\) for certain subsets Q of X. We study cooperative versions of this problem, where there are multiple questioners, but not all of them learn the answer to the queries. We consider various models that differ in how it is decided who gets to ask the next query, who obtains the answer to the query, and who needs to know the defective element by the end of the process. PubDate: 2024-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 In this note, we present an elementary proof for a well-known second-order sufficient optimality condition in nonlinear semidefinite optimization which does not rely on the enhanced theory of second-order tangents. Our approach builds on an explicit elementary computation of the so-called second subderivative of the indicator function associated with the semidefinite cone which recovers the best curvature term known in the literature. PubDate: 2024-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 propose a new sequential lifting algorithm for robust cover inequalities by extending a recent lifting procedure for the deterministic case. In the proposed algorithm, the coefficients of some items in the robust cover are also lifted. The lifting subproblem is defined as a special case of the robust knapsack problem with generalized upper bounds. We present a dynamic programming algorithm to solve the subproblem in polynomial time. The computational results applied to the robust bandwidth packing problem show the effectiveness of the proposed lifting approach. PubDate: 2024-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 extend the concept of well-posedness to the split equilibrium problem and establish Furi–Vignoli-type characterizations for the well-posedness. We prove that the well-posedness of the split equilibrium problem is equivalent to the existence and uniqueness of its solution under certain assumptions on the bifunctions involved. We also characterize the generalized well-posedness of the split equilibrium problem via the Kuratowski measure of noncompactness. We illustrate our theoretical results by several examples. PubDate: 2024-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 For given edge-capacitated connected graph and two its vertices s and t, the bottleneck (or \(\max \min \) ) path problem is to find the maximum value of path-minimum edge capacities among all paths, connecting s and t. It can be generalized by finding the bottleneck values between s and all possible t. These problems arise as subproblems in the known maximum flow problem, having applications in many real-life tasks. For any graph with n vertices and m edges, they can be solved in O(m) and O(t(m, n)) times, respectively, where \(t(m,n)=\min (m+n\log (n),m\alpha (m,n))\) and \(\alpha (\cdot ,\cdot )\) is the inverse Ackermann function. In this paper, we generalize of the bottleneck path problems by considering their versions with k sources. For the first of them, where k pairs of sources and targets are (offline or online) given, we present an \(O((m+k)\log (n))\) -time randomized and an \(O(m+(n+k)\log (n))\) -time deterministic algorithms for the offline and online versions, respectively. For the second one, where the bottleneck values are found between k sources and all targets, we present an \(O(t(m,n)+kn)\) -time offline/online algorithm. PubDate: 2024-04-18