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 [2467 journals] 
 Nicely structured positive bases with maximal cosine measure

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 The properties of positive bases make them a useful tool in derivativefree optimization and an interesting concept in mathematics. The notion of the cosine measure helps to quantify the quality of a positive basis. It provides information on how well the vectors in the positive basis uniformly cover the space considered. The number of vectors in a positive basis is known to be between \(n+1\) and 2n inclusively. When the number of vectors is strictly between \(n+1\) and 2n, we say that it is an intermediate positive basis. In this paper, the structure of intermediate positive bases with maximal cosine measure is investigated. The structure of an intermediate positive basis with maximal cosine measure over a certain subset of positive bases is provided. This type of positive bases has a simple structure that makes them easy to generate with a computer software.
PubDate: 20230130

 An SDP method for fractional semiinfinite programming problems with
SOSconvex polynomials
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 study a class of fractional semiinfinite polynomial programming problems involving sosconvex polynomial functions. For such a problem, by a conic reformulation proposed in our previous work and the quadratic modules associated with the index set, a hierarchy of semidefinite programming (SDP) relaxations can be constructed and convergent upper bounds of the optimum can be obtained. In this paper, by introducing Lasserre’s measurebased representation of nonnegative polynomials on the index set to the conic reformulation, we present a new SDP relaxation method for the considered problem. This method enables us to compute convergent lower bounds of the optimum and extract approximate minimizers. Moreover, for a set defined by infinitely many sosconvex polynomial inequalities, we obtain a procedure to construct a convergent sequence of outer approximations which have semidefinite representations (SDr). The convergence rate of the lower bounds and outer SDr approximations are also discussed.
PubDate: 20230127

 Almost sure convergence of stochastic composite objective mirror descent
for nonconvex 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 Stochastic composite objective mirror descent (SCOMID) is an effective method for solving largescale stochastic composite problems in machine learning. This method can efficiently use the geometric properties of a problem through a general distance function. However, most existing analyses rely on the convexity of the problem and the unbiased assumption of the stochastic gradient. In addition, the convergence results are obtained in expectation. To this end, we present an almost sure convergence analysis of SCOMID with biased gradient estimation in the nonconvex nonsmooth setting. For this general case, the analysis shows that the minimum of the squared generalized projected gradient norm arbitrarily converges to zero with probability one. We also obtain the almost sure convergence of function values for SCOMID with timevarying stepsizes in the nonconvex and nonsmooth setting. Numerical experiments support our theoretical findings.
PubDate: 20230118

 Pareto efficiency without topology

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 a vector optimization problem over spaces endowed with a topological linear structure, existence results for optima (efficient points) are known. Relying only on the linear structure, the set of properly efficient points from a convex set is proved to be nonempty and the sets of Proper efficient points and Pareto efficient points coincide, provided that the set of internal points picked from the corresponding cone is nonempty. This result is appealing since the scalarization of the vector optimization problem is valid without topological requirements. A As an important consequence, we provide the Second Welfare Theorem in vector lattices and especially in Lebesgue spaces holds without topology.
PubDate: 20230113

 On an effective approach in shape optimization problem for Stokes equation

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 deal with the numerical study of a shape optimization problem governed by Stokes system. More precisely, we propose an effective numerical approach based on the shape derivative formula with respect to convex domains using Minkowski deformation (Boulkhemair and Chakib in J Convex Anal 21(1):67–87, 2014). Then, we present some numerical tests including comparison results showing that the proposed algorithm is more efficient, in term of the accuracy of the solution and central processing unit (CPU) time execution, than the one involving the classical shape derivative formula massively used in literature.
PubDate: 20230111

 Logdomain interiorpoint methods for convex quadratic programming

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 Applying an interiorpoint method to the centralpath conditions is a widely used approach for solving quadratic programs. Reformulating these conditions in the logdomain is a natural variation on this approach that to our knowledge is previously unstudied. In this paper, we analyze logdomain interiorpoint methods and prove their polynomialtime convergence. We also prove that they are approximated by classical barrier methods in a precise sense and provide simple computational experiments illustrating their superior performance.
PubDate: 20230109

 Superiorization and bounded perturbation resilience of a gradient
projection algorithm solving the convex minimization 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 In this article, we use the superiorization methodology to investigate the bounded perturbations resilience of the gradient projection algorithm proposed in Ertürk et al. (J Nonlinear Convex Anal 21(4):943–951, 2020) for solving the convex minimization problem in Hilbert space setting. We obtain that the perturbed version of this gradient projection algorithm converges weakly to a solution of the convex minimization problem just like itself. We support our conclusion with an example in an infinitely dimensional Hilbert space. We also show that the superiorization methodology can be applied to the split feasibility and the inverse linear problems with the help of the perturbed gradient projection algorithm.
PubDate: 20230108

 Twoagent singlemachine scheduling with release dates to minimize the
makespan
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 consider twoagent scheduling on a singlemachine with release dates. There are two agents, namely, A and B. Each agent has his own job set. Each job has a release date and a processing time. All jobs need to be scheduled on a single machine. The objective function of each agent is the makespan with respect to his jobs, i.e., the maximum completion time. We consider two problems, namely the problem to minimize the makespans of agent A with the makespan of agent B not greater than a positive number Q given in advance, and the problem to minimize the weighted sum of both agents’ makespans. For the first problem, we drive an approximation algorithm with a worstcase ratio of \(\frac{3}{2}\) . Furthermore, we show that this problem admits a fully polynomialtime approximation scheme(FPTAS). For the second problem, we propose an improved approximation algorithm with a worstcase ratio of \(1 +\frac{\theta }{(1+\theta )^2}\) , where \(\theta >0\) is the weight of agent B.
PubDate: 20230106

 Combinatorial algorithms for solving the constrained knapsack problems
with divisible item sizes and penalties
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 address the constrained knapsack problem with divisible item sizes and penalties (the CKDSP problem, for short), which is modelled as follows. Given a set \(A=\{a_{1},a_{2},\ldots ,a_{n}\}\) of n items and a knapsack K with capacity L, where each item \(a_{i}\in A\) has a size \(s_{i}\in Z^{+}\) , a profit \(c_{i}\in R^{+}\) , a penalty \(p_{i}\in R^{+}\) , and these n item sizes are divisible, i.e., either \(s_{i} s_{j}\) or \(s_{j} s_{i}\) for any two distinct items \(a_{i}\) and \(a_{j}\) in A, each item \(a_{i}\in A\) must be either put into K under the constraint that the summation of sizes of items in K does not exceed L, or rejected with its penalty \(p_{i}\) that we must pay for, it is asked to find a subset \(X\subseteq A\) to satisfy the constraint \(s(X)=\sum _{a_i\in X}s_i \le L\) . We consider three versions of the CKDSP problem, respectively. (1) The constrained knapsack problem with divisible item sizes and total penalties (the CKDSTP problem, for short) is asked to find a subset \(X\subseteq A\) to satisfy the constraint \(s(X) \le L\) , the objective is to maximize the value of total profits of the items in X minus total penalties paid for the rejected items not in X; (2) The constrained knapsack problem with divisible item sizes and maximum penalty (the CKDSMP problem, for short) is asked to find a subset \(X\subseteq A\) to satisfy the constraint \(s(X) \le L\) , the objective is to maximize the value of total profits of the items in X minus maximum penalty paid for the rejected items not in X; (3) The penalized knapsack problem with divisible item sizes (the PKDS problem, for short) is asked to find a subset \(X\subseteq A\) to satisfy the constraint \(s(X) \le L\) , the objective is to maximize the value of total profits of the items in X minus maximum penalty paid for the items in X. As our contributions, we design three exact combinatorial algorithms to solve the CKDSTP problem, the CKDSMP problem and the PKDS problem, and these three algorithms run in time \(O(n\log n)\) , \(O(n^{2}\log n)\) and \(O(n^{2}\log n)\) , resp...
PubDate: 20230106

 A Riemannian subspace BFGS trust region 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 Motivated by the subspace techniques in the Euclidean space, this paper presents a subspace BFGS trust region (RTRSBFGS) algorithm to the problem of minimizing a smooth function defined on Riemannian manifolds. In each iteration of the RTRSBFGS algorithm, a lowdimensional trust region subproblem is solved, which reduces the amount of computation significantly for large scale problems. A limitedmemory variant of RTRSBFGS, named LRTRSBFGS, is introduced also. Both RTRSBFGS and LRTRSBFGS are proved to converge globally. Under some mild conditions, we establish the local linear convergence of these two methods. Numerical results demonstrate that, compared to the stateoftheart algorithms, RTRSBFGS and LRTRSBFGS are effective methods and subspace techniques are suitable for Riemannian optimization problems.
PubDate: 20230103

 Solving the probabilistic profitable tour problem on a line

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 Among the most important variants of the traveling salesman problem (TSP) are those relaxing the constraint that every locus should necessarily get visited, rather taking into account the revenues (prizes) from the visits into the objective function. In the Profitable Tour Problem (PTP) we seek for a tour visiting a suitable subset of customers with the target to maximize the net gain (profit) defined as the difference between the total revenue collected from the visited customers and the incurred traveling costs. The metric TSP can be modeled as a PTP with large revenues. As such, PTP is wellknown to be NPhard and also APXhardness follows. Nevertheless, PTP is solvable in polynomial time on particular graph structures like lines, trees and circles. In line with the recent emphasis on robust optimization, and motivated by the current flourishing of retailed delivery services, in this paper we initiate the study of the Probabilistic Profitable Tour Problem (PPTP), the probabilistic generalization of PTP in which the customers will show up with a known probability, in their respective loci, only after the tour has been designed and committed to. Here, the selection of the customers has to be made a priori, before knowing if a customer will actually submit his request or not. While the tour has to be designed and committed to without this knowledge, the revenues will be collected only from customers who will require the service. The objective is to maximize the expected net gain obtained visiting only the customers that show up. We offer a polynomial time algorithm computing and characterizing the space of optimal solutions for the special case of the PPTP where customers are distributed on a line.
PubDate: 20230102

 An exact explicit dual for the linear copositive programming 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 Recently, for a linear copositive programming problem, we formulated an exact explicit dual problem in the form of the extended LagrangeSlater dual. This dual problem is formulated using only the data of the primal copositive problem, satisfies the strong duality relation, and is obtained without any regularity assumptions due to the use of a concept of the normalized immobile index set. The constraints of the exact explicit dual problem are formulated in terms of completely positive matrices and their number is presented in terms of a finite integer parameter \(m_0\) . In this paper, we prove that \(m_0\le 2n\) , where n is the dimension of the primal variable’s space.
PubDate: 20230101

 Stochastic proximal subgradient descent oscillates in the vicinity of its
accumulation set
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 analyze the stochastic proximal subgradient descent in the case where the objective functions are path differentiable and verify a Sardtype condition. While the accumulation set may not be reduced to unique point, we show that the time spent by the iterates to move from one accumulation point to another goes to infinity. An oscillationtype behavior of the drift is established. These results show a strong stability property of the proximal subgradient descent. Using the theory of closed measures, Bolte et al. (2020) established this type of behavior for the deterministic subgradient descent. Our technique of proof relies on the classical works on stochastic approximation of differential inclusions, which allows us to extend results in the deterministic case to a stochastic and proximal setting, as well as to treat these different cases in a unified manner.
PubDate: 20230101

 A lowrank spectral method for learning Markov models

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 concerns with the problem of estimating the transition matrix of a lowrank discretestate Markov model from its statetransition trajectories. We propose a lowrank spectral method via the best rankr approximation of the spectral estimator based on the matrix elementwise \(l_q (q\ge 1)\) norm distance. Specifically, we establishing the Lipschitzian type error bound for the rankconstrained transition matrix set. Then, we prove a statistical upper bound for the estimation error of the proposed estimator. Numerical comparisons with the rankconstrained maximum likelihood estimator which computed by DC (difference of convex function) programming algorithm (Zhu et al. in Oper Res, 2021. https://doi.org/10.1287/opre.2021.2115) illustrate the merits of the proposed estimator in terms of the recoverability and the required computing time.
PubDate: 20230101

 Solution methodologies for minimizing a sum of pointwise minima of two
functions
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, an NPhard problem of minimizing a sum of pointwise minima of two functions is considered. Using a new equivalent formula, we propose a smooth approximation and an ADMM algorithm for solving the problem. In numerical experiments, we survey four methods including the algorithms proposed in this paper and the known methods. The results of numerical experiments indicate that the performance of each of algorithms could highly depend on the problem and simulation settings.
PubDate: 20230101

 Optimal TSP tour length estimation using Sammon maps

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 The optimal tour length of a nonEuclidean traveling salesman problem (TSP) can be estimated using the locations of vertices and the circuity factor. In this paper, we propose a method to estimate the optimal tour length of a nonEuclidean TSP using Sammon mapping. While providing accuracy comparable to the approach using the circuity factor, this new method has a number of advantages.
PubDate: 20230101

 An upper bound on the Hausdorff distance between a Pareto set and its
discretization in biobjective convex quadratic 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 provide upper bounds on the Hausdorff distances between the efficient set and its discretization in the decision space, and between the Pareto set (also called the Pareto front) and its discretization in the objective space, in the context of biobjective convex quadratic optimization on a compact feasible set. Our results imply that if \(t\) is the dispersion of the sampled points in the discretized feasible set, then the Hausdorff distances in both the decision space and the objective space are \(O(\sqrt{t})\) as \(t\) decreases to zero.
PubDate: 20230101

 Exact solution approaches for a class of bilevel fractional programs

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 consider a class of bilevel programming problems (BPPs) where the leader’s decision variables are all binary, the follower’s decision variables are all continuous, and a fractional objective function appears in the follower’s problem. This class of problems generalizes standard bilevel linear mixedinteger programs with a linear program (LP) in the lower level. One motivating application example for this generalization arises in a network interdiction context, where the follower (i.e., the evader) instead of minimizing his/her shortest path, optimizes some fractional objective function, e.g., a costtotime ratio. By applying CharnesCooper transformation, we first reformulate the original BPP as an equivalent BPP with a fractional objective in the upper level, but an LP in the lower level. Using a combination of the LP strongduality property and linearization techniques, we show how to address the resulting reformulation via a parametric approach that solves a sequence of linear mixedinteger programs. The latter can be handled by offtheshelf solvers, which implies that our overall solution scheme is easy to implement. Finally, we perform a brief computational study to illustrate the performance of the proposed approaches.
PubDate: 20230101

 A note on the implications of approximate submodularity in discrete
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 Submodularity is a key property in discrete optimization. Submodularity has been widely used for analyzing the greedy algorithm to give performance bounds and providing insight into the construction of valid inequalities for mixedinteger programs. In recent years, researchers started to study approximate submodularity, with a primary focus on providing performance bounds for iterative approaches. In this paper, we study approximate submodularity from a different perspective in order to broaden its use cases in discrete optimization. We define metrics that quantify approximate submodularity, which we then use to derive new properties about both approximate submodularity preservation and the wellknown Lovász extension for set functions. We also show that previous analyses of mixedinteger sets, such as the submodular knapsack polytope, can be extended to the approximate submodularity setting. Our work demonstrates that one may generalize many of the analytical tools used in submodular optimization into the approximate submodularity context.
PubDate: 20230101

 Using regression models to understand the impact of routelength
variability in practical vehicle routing
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 short paper, we use regression models to highlight a key point in practical vehicle routing. In particular, we focus on an important problem experienced by delivery and service companies. These companies dispatch vehicles to deliver products and provide services to customers. For the capacitated vehicle routing problem, we show that reducing routelength variability while generating vehicle routes is an important consideration to minimize the total operating and delivery costs for a company encountering random traffic.
PubDate: 20230101
