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 Pareto efficiency for robust linear programs was introduced by Iancu and Trichakis in [Manage Sci 60(1):130–147, 9]. We generalize their approach and theoretical results to robust optimization problems in Euclidean spaces with affine uncertainty. Additionally, we demonstrate the value of this approach in an exemplary manner in the area of robust semidefinite programming (SDP). In particular, we prove that computing a Pareto robustly optimal solution for a robust SDP is tractable and illustrate the benefit of such solutions at the example of the maximal eigenvalue problem. Furthermore, we modify the famous algorithm of Goemans and Williamson [Assoc Comput Mach 42(6):1115–1145, 8] in order to compute cuts for the robust max-cut problem that yield an improved approximation guarantee in non-worst-case scenarios. PubDate: 2023-04-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 notion of Fejér monotonicity is instrumental in unifying the convergence proofs of many iterative methods, such as the Krasnoselskii–Mann iteration, the proximal point method, the Douglas-Rachford splitting algorithm, and many others. In this paper, we present directionally asymptotical results of strongly convergent subsequences of Fejér monotone sequences. We also provide examples to show that the sets of directionally asymptotic cluster points can be large and that weak convergence is needed in infinite-dimensional spaces. PubDate: 2023-04-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 explore novel approaches for solving nonlinear optimization problems with unrelaxable bound constraints, which must be satisfied before the objective function can be evaluated. Our method reformulates the unrelaxable bound-constrained problem as an unconstrained optimization problem that is amenable to existing unconstrained optimization methods. The reformulation relies on a domain warping to form a merit function; the choice of the warping determines the level of exactness with which the unconstrained problem can be used to find solutions to the bound-constrained problem, as well as key properties of the unconstrained formulation such as smoothness. We develop theory when the domain warping is a multioutput sigmoidal warping, and we explore the practical elements of applying unconstrained optimization methods to the formulation. We develop an algorithm that exploits the structure of the sigmoidal warping to guarantee that unconstrained optimization algorithms applied to the merit function will find a stationary point to the desired tolerance. PubDate: 2023-04-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 paper considers the problem of unique recovery of sparse finite-valued integer signals using a single linear integer measurement. For l-sparse signals in \({\mathbb {Z}}^n\) , \(2l<n\) , with absolute entries bounded by r, we construct an \(1\times n\) measurement matrix with maximum absolute entry \(\Delta =O(r^{2l-1})\) . Here the implicit constant depends on l and n and the exponent \(2l-1\) is optimal. Additionally, we show that, in the above setting, a single measurement can be replaced by several measurements with absolute entries sub-linear in \(\Delta\) . The proofs make use of results on admissible \((n-1)\) -dimensional integer lattices for m-sparse n-cubes that are of independent interest. PubDate: 2023-04-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 singly linearly constrained separable binary quadratic programming problem (SLSBQP) has a wide variety of applications in practice. In real-life applications, the coefficients in the objective function and constraints generally appear with symmetric structure. In this paper, we propose an extremely efficient global optimization algorithm for solving SLSBQP with symmetric structure. We first develop a reformulation of SLSBQP based on an aggregate function defined on the symmetric structure in the problem, and derive the convex envelop function for the aggregate function. A branch-and-bound algorithm is then proposed to find the global solution of the reformulation of SLSBQP. Computational experiments show that the proposed algorithm is able to solve test instances with thousands of variables in less than 0.04 seconds on average, whereas the current state-of-the-art algorithms may fail to solve the same test instances in 200 seconds. The superior performance of the proposed algorithm clearly indicates the potential of the proposed algorithm in real-life applications. PubDate: 2023-04-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 article, we focus on the Tikhonov–Browder regularization scheme for both weak and strong vector equilibrium problems. Under suitable coercive conditions, the existence of solutions to weak vector equilibrium problems and their regularized problems are established in both monotone and nonmonotone cases, and furthermore we show that the conditions, which guarantee the boundedness of regularized solutions, become sufficient conditions for the solvability of the original problems. For the strong problems, we use generalized convexities and/or coercivity properties concerning a vector optimization problem to establish convergence results of the regularization method. PubDate: 2023-04-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 Let \(S \subseteq \mathbb {R}^n\) be a compact semialgebraic set and let f be a polynomial nonnegative on S. Schmüdgen’s Positivstellensatz then states that for any \(\eta > 0\) , the nonnegativity of \(f + \eta\) on S can be certified by expressing \(f + \eta\) as a conic combination of products of the polynomials that occur in the inequalities defining S, where the coefficients are (globally nonnegative) sum-of-squares polynomials. It does not, however, provide explicit bounds on the degree of the polynomials required for such an expression. We show that in the special case where \(S = [-1, 1]^n\) is the hypercube, a Schmüdgen-type certificate of nonnegativity exists involving only polynomials of degree \(O(1 / \sqrt{\eta })\) . This improves quadratically upon the previously best known estimate in \(O(1/\eta )\) . Our proof relies on an application of the polynomial kernel method, making use in particular of the Jackson kernel on the interval \([-1, 1]\) . PubDate: 2023-04-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 Cross validation is widely used to assess the performance of prediction models for unseen data. Leave-k-out and m-fold are among the most popular cross validation criteria, which have complementary strengths and limitations. Leave-k-out (with leave-1-out being the most common special case) is exhaustive and more reliable but computationally prohibitive when \(k > 2\) ; whereas m-fold is much more tractable at the cost of uncertain performance due to non-exhaustive random sampling. We propose a new cross validation criterion, leave-worst-k-out, which attempts to combine the strengths and avoid limitations of leave-k-out and m-fold. The leave-worst-k-out criterion is defined as the largest validation error out of \(C_{n^{k}}\) possible ways to partition n data points into a subset of \((n-k)\) for training a prediction model and the remaining k for validation. In contrast, the leave-k-out criterion takes the average of the \(C_{n^{k}}\) validation errors from the aforementioned partitions, and m-fold samples m random (but non-independent) such validation errors. We prove that, for the special case of multiple linear regression model under the \({\mathcal {L}}_1\) norm, the leave-worst-k-out criterion can be computed by solving a mixed integer linear program. We also present a random sampling algorithm for approximately computing the criterion for general prediction models under general norms. Results of two computational experiments suggested that the leave-worst-k-out criterion clearly outperformed leave-k-out and m-fold in assessing the generalizability of prediction models; moreover, leave-worst-k-out can be approximately computed using the random sampling algorithm almost as efficiently as leave-1-out and m-fold, and the effectiveness of the approximated criterion may be as high as, or even higher than, the exactly computed criterion. PubDate: 2023-04-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 paper is devoted to the classical variational problem with a nonsmooth integrand of the functional to be minimized. The integrand is supposed to be subdifferentiable. Under some natural conditions the subdifferentiability of the functional considered is proved. The problem of finding the subdifferential descent direction is solved and the subdifferential descent method is applied to solve the original problem. The algorithm developed is demonstrated by examples. PubDate: 2023-04-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 Finding the partially symmetric rank-1 approximation to a given fourth-order partially symmetric tensor has close relationship with its largest M-eigenvalue. In this paper, we study the partially symmetric rank-1 approximation by a proximal alternating linearized minimization method. Furthermore, the global convergence of the algorithm is established, and several numerical experiments show the efficiency and accuracy of the proposed algorithm. PubDate: 2023-04-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 a classic machine scheduling problem under resource constraints. Given m parallel identical machines and a collection of additional but renewable resources, each task requires both a machine and one particular resource at any time of its processing. The goal is to allocate the machines and resources to the tasks so as to minimize the makespan, that is, the maximum completion time of all tasks. Because of NP-hardness of the problem, we design a three-stage combinatorial algorithm with performance ratio \(\frac{2m+2}{m+3}\) that improves the best prior ratio for \(m\ge 3\) machines and ties with that for \(m=2\) machines. PubDate: 2023-04-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 To minimize the average of a set of log-convex functions, the stochastic Newton method iteratively updates its estimate using subsampled versions of the full objective’s gradient and Hessian. We contextualize this optimization problem as sequential Bayesian inference on a latent state-space model with a discriminatively-specified observation process. Applying Bayesian filtering then yields a novel optimization algorithm that considers the entire history of gradients and Hessians when forming an update. We establish matrix-based conditions under which the effect of older observations diminishes over time, in a manner analogous to Polyak’s heavy ball momentum. We illustrate various aspects of our approach with an example and review other relevant innovations for the stochastic Newton method. PubDate: 2023-04-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 two modified forward-backward-half-forward splitting methods for solving three-operator monotone inclusion problems. The forward-backward-half-forward splitting method adjusts, improves, and recovers Tseng’s forward-backward-forward splitting method, allowing a cocoercive third-part operator in the inclusion problem. The proposed scheme chooses two different projection (forward) steps deriving two variants, which work efficiently without assuming the Lipschitz continuity or directly using the cocoercive constant. Both derived methods have some desired features: (i) the cocoercive operator is not evaluated in the forward step; (ii) if the projection steps are over-relaxing, very general iterations may be derived for both proposed methods, recovering the forward-backward-forward and the forward-backward-half-forward iterations and allowing possibly larger stepsizes; and (iii) strong convergence to the best approximation solution of the problem is proved for the second method. To the best of our knowledge, this is the first time that a forward-backward-forward-type method is strongly convergent to the best approximation solution of the three operator monotone inclusion. PubDate: 2023-04-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 concentrates on a general vector optimization problem (VOP) with geometrical constraints, where the variable domination structures are defined by coradiant sets. Utilizing asymptotic and recession cones, we provide some new characterizations of coradiant sets. The related approximate weak and strong duality theorems between a general primal set and some different dual sets are formulated. Moreover, the corresponding duality theories are especially derived for VOP. Finally, several sufficient and necessary optimality conditions of approximate (properly) optimal solutions of VOP are proved by maximizing two different nonlinear scalarization functionals about objectives and constraints. PubDate: 2023-04-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 many iterative optimization methods, fixed-point theory enables the analysis of the convergence rate via the contraction factor associated with the linear approximation of the fixed-point operator. While this factor characterizes the asymptotic linear rate of convergence, it does not explain the non-linear behavior of these algorithms in the non-asymptotic regime. In this letter, we take into account the effect of the first-order approximation error and present a closed-form bound on the convergence in terms of the number of iterations required for the distance between the iterate and the limit point to reach an arbitrarily small fraction of the initial distance. Our bound includes two terms: one corresponds to the number of iterations required for the linearized version of the fixed-point operator and the other corresponds to the overhead associated with the approximation error. With a focus on the convergence in the scalar case, the tightness of the proposed bound is proven for positively quadratic first-order difference equations. PubDate: 2023-04-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 studies three online scheduling problems on the single-machine, denoted by (P1), (P2) and (P3), to minimize the maximum weighted completion time or the maximum delivery completion time with or without the NDP constraint. Here, “NDP” means that the available jobs cannot be delayed for processing when the machine is idle. Problems (P1) and (P2) aim to minimize the maximum weighted completion time, where (P1) has not the NDP constraint and (P2) has the NDP constraint. Problem (P3) aims to minimize the maximum delivery completion time under the NDP constraint. For problems (P1) and (P2), we study the restricted version in which the jobs have agreeable processing times and weights (i.e., if \(p_{i}> p_{j}\) , then \(w_{i}\ge w_{j}\) ). For problem (P3), we study the restricted version in which the jobs have small delivery times (i.e., \(p_{j}\ge q_{j}\) ). We show that problem (P1) admits a best possible online algorithm with a competitive ratio of 1.618, problem (P2) has a lower bound 3/2 and admits a \(\sqrt{3}\) -competitive online algorithm, and problem (P3) admits a best possible online algorithm with a competitive ratio of 4/3. PubDate: 2023-04-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 Health and convenience are two indispensable indicators of the society promotion. Nowadays, to improve community health levels, the comfort of patients and those in need of health services has received much attention. Providing Home Health Care (HHC) services is one of the critical issues of health care to improve the patient convenience. However, manual nurse planning which is still performed in many HHC institutes results in a waste of time, cost, and ultimately lower efficiency. In this research, a multi-objective mixed-integer model is presented for home health care planning so that in addition to focusing on the financial goals of the institution, other objectives that can help increase productivity and quality of services are highlighted. Therefore, four different objectives of the total cost, environmental emission, workload balance, and service quality are addressed. Taking into account medical staff with different service levels, and the preferences of patients in selecting a service level, as well as different vehicle types, are other aspects discussed in this model. The epsilon-constraint method is implemented in CPLEX to solve small-size instances. Moreover, a Multi-Objective Variable Neighborhood Search (MOVNS) composed of nine local neighborhood moves is developed to solve the practical-size instances. The results of the MOVNS are compared with the epsilon-constraint method, and the strengths and weaknesses of the proposed algorithm are demonstrated by a comprehensive sensitivity analysis. To show the applicability of the algorithm, a real example is designed based on a case study, and the results of the algorithm over real data are evaluated. PubDate: 2023-03-17
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 Given an undirected graph \(G=(V,E;w,p)\) with a depot \(r\in V\) and an integer \(k\in {{\mathbb {Z}}}^{+}\) , each edge \(e\in E\) has a weight \(w(e)\in {{\mathbb {R}}}^{+}\) and a penalty \(p(e)\in {\mathbb R}^{+}_{0}\) , where the weights satisfy the triangle inequality, we consider two types of restricted k-Chinese postman problems with penalties. (1) The restricted min–max k-Chinese postman problem with penalties (MM-RPCPP) is asked to find a set of k tours starting from r and collectively covering all vertices, such that the maximum tour weight plus the total penalty paid for the uncovered edges is minimized. (2) The restricted min-sum k-Chinese postman problem with penalties (MS-RPCPP) is asked to find a set of k tours satisfying the constraint mentioned above and that each edge appears in at most one tour and each tour contains at least one edge, such that the sum of weights of all tours plus the total penalty paid for the uncovered edges is minimized. In the paper, we design a combinatorial \((\frac{7}{2}-\frac{2}{k})\) -approximation algorithm to solve the MM-RPCPP. Furthermore, we present a combinatorial 2-approximation algorithm to solve the MS-RPCPP. PubDate: 2023-03-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 This paper presents an algorithm based on the variable neighborhood search (VNS) metaheuristic, called smart general VNS (SGVNS), to solve the multi-depot open vehicle routing problem with time windows (MDOVRPTW). For the problem, two single-objective approaches are proposed for cost assessment: one for reducing the total distance covered and the other for reducing the total number of vehicles used and, after, the total distance covered. SGVNS involves the perturbation and local search phases. In the perturbation phase, gradual changes are carried out in the neighborhoods to expand the diversification of solutions and escape from local optima. The random combination of specific neighborhood structures is used in the local search to refine the solution generated in the previous phase. As no instances are known in the literature for MDOVRPTW, the computational tests are executed in two groups of classic MDVRPTW instances, involving up to 960 customers, 12 depots, and 120 vehicles. The present study made it possible to investigate cost improvements through the use of the MDOVRPTW model when compared to the MDVRPTW. There was a reduction in the distance covered in all instances evaluated. The total distance covered decreased by 12.07% in one of the reference groups and 10.43% in the other. For the first group, the fleet reduction occurred in 75% of the instances. In the second group, there was a reduction in all instances. It corresponds to \(-\,10.42\%\) and \(-\,24.13\%\) of the total vehicles used in each group, respectively. The SGVNS algorithm proved effective for the two problems for which it was applied, either in reducing the total traveled distance or in reducing the fleet. PubDate: 2023-03-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 Real-world problems are often nonconvex and involve integer variables, representing vexing challenges to be tackled using state-of-the-art solvers. We introduce a mathematical identity-based reformulation of a class of polynomial integer nonlinear optimization (PINLO) problems using a technique that linearizes polynomial functions of separable and bounded integer variables of any degree. We also introduce an alternative reformulation and conduct computational experiments to understand their performance against leading commercial global optimization solvers. Computational experiments reveal that our integer linear optimization reformulations are computationally tractable for solving large PINLO problems via Gurobi (up to 10,000 constraints and 20,000 variables). This is much larger than current leading commercial global optimization solvers such as BARON, thereby demonstrating its promise for use in real-world applications of integer linear optimization with a polynomial objective function. PubDate: 2023-03-02
Hybrid journal (It can contain Open Access articles)
