Subjects -> STATISTICS (Total: 130 journals)
 The end of the list has been reached or no journals were found for your choice.
Similar Journals
 Optimization LettersJournal Prestige (SJR): 0.721 Citation Impact (citeScore): 1Number of Followers: 2      Hybrid journal (It can contain Open Access articles) ISSN (Print) 1862-4480 - ISSN (Online) 1862-4472 Published by Springer-Verlag  [2467 journals]
• Nicely structured positive bases with maximal cosine measure

Abstract: Abstract The properties of positive bases make them a useful tool in derivative-free 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: 2023-01-30

• An SDP method for fractional semi-infinite programming problems with
SOS-convex polynomials

Abstract: Abstract In this paper, we study a class of fractional semi-infinite polynomial programming problems involving sos-convex 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 measure-based 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 sos-convex 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: 2023-01-27

• Almost sure convergence of stochastic composite objective mirror descent
for non-convex non-smooth optimization

Abstract: Abstract Stochastic composite objective mirror descent (SCOMID) is an effective method for solving large-scale 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 non-convex non-smooth 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 time-varying stepsizes in the non-convex and non-smooth setting. Numerical experiments support our theoretical findings.
PubDate: 2023-01-18

• Pareto efficiency without topology

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: 2023-01-13

• On an effective approach in shape optimization problem for Stokes equation

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: 2023-01-11

• Log-domain interior-point methods for convex quadratic programming

Abstract: Abstract Applying an interior-point method to the central-path conditions is a widely used approach for solving quadratic programs. Reformulating these conditions in the log-domain is a natural variation on this approach that to our knowledge is previously unstudied. In this paper, we analyze log-domain interior-point methods and prove their polynomial-time 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: 2023-01-09

• Superiorization and bounded perturbation resilience of a gradient
projection algorithm solving the convex minimization problem

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: 2023-01-08

• Two-agent single-machine scheduling with release dates to minimize the
makespan

Abstract: Abstract We consider two-agent scheduling on a single-machine 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 worst-case ratio of $$\frac{3}{2}$$ . Furthermore, we show that this problem admits a fully polynomial-time approximation scheme(FPTAS). For the second problem, we propose an improved approximation algorithm with a worst-case ratio of $$1 +\frac{\theta }{(1+\theta )^2}$$ , where $$\theta >0$$ is the weight of agent B.
PubDate: 2023-01-06

• Combinatorial algorithms for solving the constrained knapsack problems
with divisible item sizes and penalties

Abstract: Abstract In this paper, we address the constrained knapsack problem with divisible item sizes and penalties (the CK-DSP 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 CK-DSP problem, respectively. (1) The constrained knapsack problem with divisible item sizes and total penalties (the CK-DSTP 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 CK-DSMP 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 PK-DS 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 CK-DSTP problem, the CK-DSMP problem and the PK-DS 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: 2023-01-06

• A Riemannian subspace BFGS trust region method

Abstract: Abstract Motivated by the subspace techniques in the Euclidean space, this paper presents a subspace BFGS trust region (RTR-SBFGS) algorithm to the problem of minimizing a smooth function defined on Riemannian manifolds. In each iteration of the RTR-SBFGS algorithm, a low-dimensional trust region subproblem is solved, which reduces the amount of computation significantly for large scale problems. A limited-memory variant of RTR-SBFGS, named LRTR-SBFGS, is introduced also. Both RTR-SBFGS and LRTR-SBFGS 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 state-of-the-art algorithms, RTR-SBFGS and LRTR-SBFGS are effective methods and subspace techniques are suitable for Riemannian optimization problems.
PubDate: 2023-01-03

• Solving the probabilistic profitable tour problem on a line

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 well-known to be NP-hard and also APX-hardness 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: 2023-01-02

• An exact explicit dual for the linear copositive programming problem

Abstract: Abstract Recently, for a linear copositive programming problem, we formulated an exact explicit dual problem in the form of the extended Lagrange-Slater 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: 2023-01-01

• Stochastic proximal subgradient descent oscillates in the vicinity of its
accumulation set

Abstract: Abstract We analyze the stochastic proximal subgradient descent in the case where the objective functions are path differentiable and verify a Sard-type 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 oscillation-type 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: 2023-01-01

• A low-rank spectral method for learning Markov models

Abstract: Abstract This paper concerns with the problem of estimating the transition matrix of a low-rank discrete-state Markov model from its state-transition trajectories. We propose a low-rank spectral method via the best rank-r 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 rank-constrained transition matrix set. Then, we prove a statistical upper bound for the estimation error of the proposed estimator. Numerical comparisons with the rank-constrained 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: 2023-01-01

• Solution methodologies for minimizing a sum of pointwise minima of two
functions

Abstract: Abstract In this paper, an NP-hard 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: 2023-01-01

• Optimal TSP tour length estimation using Sammon maps

Abstract: Abstract The optimal tour length of a non-Euclidean 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 non-Euclidean TSP using Sammon mapping. While providing accuracy comparable to the approach using the circuity factor, this new method has a number of advantages.
PubDate: 2023-01-01

• An upper bound on the Hausdorff distance between a Pareto set and its
discretization in bi-objective convex quadratic optimization

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 bi-objective 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: 2023-01-01

• Exact solution approaches for a class of bilevel fractional programs

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 mixed-integer 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 cost-to-time ratio. By applying Charnes-Cooper 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 strong-duality property and linearization techniques, we show how to address the resulting reformulation via a parametric approach that solves a sequence of linear mixed-integer programs. The latter can be handled by off-the-shelf 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: 2023-01-01

• A note on the implications of approximate submodularity in discrete
optimization

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 mixed-integer 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 well-known Lovász extension for set functions. We also show that previous analyses of mixed-integer 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: 2023-01-01

• Using regression models to understand the impact of route-length
variability in practical vehicle routing

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 route-length variability while generating vehicle routes is an important consideration to minimize the total operating and delivery costs for a company encountering random traffic.
PubDate: 2023-01-01

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762