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  [2469 journals]
• A gradient method exploiting the two dimensional quadratic termination
property

Abstract: Abstract The quadratic termination property is important to the efficiency of gradient methods. We consider equipping a family of gradient methods, where the stepsize is given by the ratio of two norms, with two dimensional quadratic termination. Such a desired property is achieved by cooperating with a new stepsize which is derived by maximizing the stepsize of the considered family in the next iteration. It is proved that each method in the family will asymptotically alternate in a two dimensional subspace spanned by the eigenvectors corresponding to the largest and smallest eigenvalues. Based on this asymptotic behavior, we show that the new stepsize converges to the reciprocal of the largest eigenvalue of the Hessian. Furthermore, by adaptively taking the long Barzilai–Borwein stepsize and reusing the new stepsize with retard, we propose an efficient gradient method for unconstrained quadratic optimization. We prove that the new method is R-linearly convergent with a rate of $$1-1/\kappa$$ , where $$\kappa$$ is the condition number of Hessian. Numerical experiments show the efficiency of our proposed method.
PubDate: 2022-09-22

• Regularized quasi-monotone method for stochastic optimization

Abstract: Abstract We adapt the quasi-monotone method, an algorithm characterized by uniquely having convergence quality guarantees for the last iterate, for composite convex minimization in the stochastic setting. For the proposed numerical scheme we derive the optimal convergence rate of $$\text{ O }\left( \frac{1}{\sqrt{k+1}}\right)$$ in terms of the last iterate, rather than on average as it is standard for subgradient methods. The theoretical guarantee for individual convergence of the regularized quasi-monotone method is confirmed by numerical experiments on $$\ell _1$$ -regularized robust linear regression.
PubDate: 2022-09-21

• Computing tighter bounds on the n-queens constant via Newton’s
method

Abstract: Abstract In recent work Simkin shows that bounds on an exponent occurring in the famous n-queens problem can be evaluated by solving convex optimization problems, allowing him to find bounds far tighter than previously known. In this note we use Simkin’s formulation, a sharper bound developed by Knuth, and a Newton method that scales to large problem instances, to find even sharper bounds.
PubDate: 2022-09-17

• Two-machine flow shop scheduling with convex resource consumption
functions

Abstract: Abstract We consider a two-machine flow shop scheduling problem in which the processing time of each operation is inversely proportional to the power of the amount of resources consumed by it. The objective is to minimize the sum of the makespan and the total resource consumption cost. We show that the problem is NP-hard, and its constrained version remains so. Then, we develop 1.25- and 2-approximation algorithms for the problem and its constrained version, respectively.
PubDate: 2022-09-16

• An effective version of Schmüdgen’s Positivstellensatz for the
hypercube

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: 2022-09-15

• On the weak and strong convergence of modified
forward-backward-half-forward splitting methods

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: 2022-09-15

• On unique recovery of finite-valued integer signals and admissible
lattices of sparse hypercubes

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: 2022-09-13

• An improved algorithm for parallel machine scheduling under additional
resource constraints

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: 2022-09-12

• General variable neighborhood search for the parallel machine scheduling
problem with two common servers

Abstract: Abstract We address in this paper the parallel machine scheduling problem with a shared loading server and a shared unloading server. Each job has to be loaded by the loading server before being processed on one of the available machines and unloaded immediately by the unloading server after its processing. The objective function involves the minimization of the overall completion time, known as the makespan. This important problem raises in flexible manufacturing systems, automated material handling, healthcare, and many other industrial fields, and has been little studied up to now. To date, research on it has focused on the case of two machines. The regular case of this problem is considered. A mixed integer programming formulation based on completion time variables is suggested to solve small-sized instances of the problem. Due to its $$\mathcal{NP}\mathcal{}$$ -hardness, we propose two greedy heuristics based on the minimization of the loading, respectively unloading, server waiting time, and an efficient General Variable Neighborhood Search (GVNS) algorithm. In the computational experiments, the proposed methods are compared using 120 new and publicly available instances. It turns out that, the proposed GVNS with an initial solution-finding mechanism based on the unloading server waiting time minimization significantly outperforms the other approaches.
PubDate: 2022-09-10

• Numerical solution of delay fractional optimal control problems with free
terminal time

Abstract: Abstract This paper considers a class of delay fractional optimal control problems with free terminal time. The fractional derivatives in this class of problems are described in the Caputo sense and they can be of different orders. We first show that for this class of problems, the well-known time-scaling transformation for mapping the free time horizon into a fixed time interval yields a new fractional-order system with variable time-delay. Then, we propose an explicit numerical scheme for solving the resulting fractional time-delay system, which gives rise to a discrete-time optimal control problem. Furthermore, we derive gradient formulas of the cost and constraint functions with respect to decision variables. On this basis, a gradient-based optimization approach is developed to solve the resulting discrete-time optimal control problem. Finally, an example problems is solved to demonstrate the effectiveness of our proposed solution approach.
PubDate: 2022-09-10

• A unified analysis of convex and non-convex $$\ell _p$$ ℓ p -ball
projection problems

Abstract: Abstract The task of projecting onto $$\ell _p$$ norm balls is ubiquitous in statistics and machine learning, yet the availability of actionable algorithms for doing so is largely limited to the special cases of $$p \in \left\{ 0, 1,2, \infty \right\}$$ . In this paper, we introduce novel, scalable methods for projecting onto the $$\ell _p$$ -ball for general $$p>0$$ . For $$p \ge 1$$ , we solve the univariate Lagrangian dual via a dual Newton method. We then carefully design a bisection approach for $$p<1$$ , presenting theoretical and empirical evidence of zero or a small duality gap in the non-convex case. The success of our contributions is thoroughly assessed empirically, and applied to large-scale regularized multi-task learning and compressed sensing. The code implementing our methods is publicly available on Github.
PubDate: 2022-09-04

• Stochastic saddle-point optimization for the Wasserstein barycenter
problem

Abstract: Abstract We consider the population Wasserstein barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. This leads to a complicated stochastic optimization problem where the objective is given as an expectation of a function given as a solution to a random optimization problem. We employ the structure of the problem and obtain a convex–concave stochastic saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose a stochastic optimization algorithm and estimate its complexity. The second result, based on kernel methods, extends the previous one to the arbitrary distribution of random probability measures. Moreover, this new algorithm has a total complexity better than the Stochastic Approximation approach combined with the Sinkhorn algorithm in many cases. We also illustrate our developments by a series of numerical experiments.
PubDate: 2022-09-01

• Zeroth-order methods for noisy Hölder-gradient functions

Abstract: Abstract In this paper, we prove new complexity bounds for zeroth-order methods in non-convex optimization with inexact observations of the objective function values. We use the Gaussian smoothing approach of Nesterov and Spokoiny(Found Comput Math 17(2): 527–566, 2015. https://doi.org/10.1007/s10208-015-9296-2) and extend their results, obtained for optimization methods for smooth zeroth-order non-convex problems, to the setting of minimization of functions with Hölder-continuous gradient with noisy zeroth-order oracle, obtaining noise upper-bounds as well. We consider finite-difference gradient approximation based on normally distributed random Gaussian vectors and prove that gradient descent scheme based on this approximation converges to the stationary point of the smoothed function. We also consider convergence to the stationary point of the original (not smoothed) function and obtain bounds on the number of steps of the algorithm for making the norm of its gradient small. Additionally we provide bounds for the level of noise in the zeroth-order oracle for which it is still possible to guarantee that the above bounds hold. We also consider separately the case of $$\nu = 1$$ and show that in this case the dependence of the obtained bounds on the dimension can be improved.
PubDate: 2022-09-01

• Improved exploitation of higher order smoothness in derivative-free
optimization

Abstract: Abstract We consider $$\beta$$ -smooth (satisfies the generalized Hölder condition with parameter $$\beta > 2$$ ) stochastic convex optimization problem with zero-order one-point oracle. The best known result was (Akhavan et al. in Exploiting higher order smoothness in derivative-free optimization and continuous bandits, 2020): \begin{aligned} {\mathbb {E}}\left[ f(\overline{x}_N) - f(x^*)\right] = {\mathcal {O}} \left( \dfrac{n^{2}}{\gamma N^{\frac{\beta -1}{\beta }}} \right) \end{aligned} in $$\gamma$$ -strongly convex case, where n is the dimension. In this paper we improve this bound: \begin{aligned} {\mathbb {E}} \left[ f(\overline{x}_N) - f(x^*)\right] = {\mathcal {O}} \left( \dfrac{n^{2-{\frac{1}{\beta }}}}{\gamma N^{\frac{\beta -1}{\beta }}} \right) . \end{aligned}
PubDate: 2022-09-01

• Efficient PTAS for the maximum traveling salesman problem in a metric
space of fixed doubling dimension

Abstract: Abstract The maximum traveling salesman problem (Max TSP) consists of finding a Hamiltonian cycle with the maximum total weight of the edges in a given complete weighted graph. This problem is APX-hard in the general metric case but admits polynomial-time approximation schemes in the geometric setting, when the edge weights are induced by a vector norm in fixed-dimensional real space. We propose the first approximation scheme for Max TSP in an arbitrary metric space of fixed doubling dimension. The proposed algorithm implements an efficient PTAS which, for any fixed $$\varepsilon \in (0,1)$$ , computes a $$(1-\varepsilon )$$ -approximate solution of the problem in cubic time. Additionally, we suggest a cubic-time algorithm which finds asymptotically optimal solutions of the metric Max TSP in fixed and sublogarithmic doubling dimensions.
PubDate: 2022-09-01

• Equilibrium uniqueness in aggregative games: very practical conditions

Abstract: Abstract Various Nash equilibrium results for a broad class of aggregative games are presented. The main ones concern equilibrium uniqueness. The setting presupposes that each player has $$\mathbb {R}_+$$ as strategy set, makes smoothness assumptions but allows for a discontinuity of stand-alone payoff functions at 0; this possibility is especially important for various contest and oligopolistic games. Conditions are completely in terms of marginal reductions which may be considered as primitives of the game. For many games in the literature they can easily be checked. They automatically imply that conditional payoff functions are strictly quasi-concave. The results are proved by means of the Szidarovszky variant of the Selten–Szidarovszky technique. Their power is illustrated by reproducing quickly and improving upon various results for economic games.
PubDate: 2022-09-01

• How to find the convex hull of all integer points
in a polyhedron'

Abstract: Abstract We propose a cut-based algorithm for finding all vertices and all facets of the convex hull of all integer points of a polyhedron defined by a system of linear inequalities. Our algorithm, DDMCuts, is based on the Gomory cuts and the dynamic version of the double description method. We describe the computer implementation of the algorithm and present the results of computational experiments comparing our algorithm with a naive one and an algorithm implemented in Normaliz.
PubDate: 2022-09-01

• Gain-optimized spectral distortions for pronunciation training

Abstract: Abstract This paper considers an assessment and evaluation of speech sound pronunciation quality in computer-aided language learning systems. We examine the gain optimization of spectral distortion measures between the speech signals of a native speaker and a learner. During training, a learner has to achieve stable pronunciation of all sounds. This is measured by computing the distances between the sounds produced by the learner and the model speaker. In order to improve pronunciation, it is proposed to adapt the linear prediction coding coefficients of reference sounds by using the gradient descent optimization of the gain-optimized dissimilarity. As a result, we demonstrate the possibility of synthesizing sounds that will be either close to the model pronunciation or achievable by a learner. An experimental study shows that the proposed procedure leads to high efficiency for pronunciation training even in the presence of noise in the observed utterance.
PubDate: 2022-09-01

• Optimal externalities in a parallel transportation network

Abstract: Abstract We consider the Wardrop model with splittable traffic and externalities applied to the parallel transportation network. These externalities are introduced into the players’ latency functions as a tool of the system’s influence on the equilibrium distribution of traffic flows and also on the PoA values. In the general case, the externalities can be interpreted as elements of centralized control, which can be included, e.g., in traffic rules (speed-limit signs, controlled traffic lights), pricing policy for public transport, fuel, etc. This paper investigates the influence of traffic lane rules on the Price of Anarchy. We show that for the parallel transportation system there exist externality values such that the equilibrium and optimal profiles will coincide with one another and the Price of Anarchy will be equal to 1. Also we propose the socialization procedure of user behavior for which the parallel transportation system ensures an optimal profile of user behavior and the same value of the social costs as in the optimal profile with initial externalities.
PubDate: 2022-09-01

• Preface to the special issue dedicated to the International Conference
“Mathematical optimization theory and Operations Research” (MOTOR
2020) held online from July 6 to July 10, 2020

PubDate: 2022-07-09
DOI: 10.1007/s11590-022-01903-8

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