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 [2469 journals] 
 A gradient method exploiting the two dimensional quadratic termination
property
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 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 Rlinearly convergent with a rate of \(11/\kappa\) , where \(\kappa\) is the condition number of Hessian. Numerical experiments show the efficiency of our proposed method.
PubDate: 20220922

 Regularized quasimonotone method for stochastic 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 adapt the quasimonotone 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 quasimonotone method is confirmed by numerical experiments on \(\ell _1\) regularized robust linear regression.
PubDate: 20220921

 Computing tighter bounds on the nqueens constant via Newton’s
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 In recent work Simkin shows that bounds on an exponent occurring in the famous nqueens 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: 20220917

 Twomachine flow shop scheduling with convex resource consumption
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 We consider a twomachine 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 NPhard, and its constrained version remains so. Then, we develop 1.25 and 2approximation algorithms for the problem and its constrained version, respectively.
PubDate: 20220916

 An effective version of Schmüdgen’s Positivstellensatz for the
hypercube
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 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) sumofsquares 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üdgentype 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: 20220915

 On the weak and strong convergence of modified
forwardbackwardhalfforward splitting methods
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 investigates two modified forwardbackwardhalfforward splitting methods for solving threeoperator monotone inclusion problems. The forwardbackwardhalfforward splitting method adjusts, improves, and recovers Tseng’s forwardbackwardforward splitting method, allowing a cocoercive thirdpart 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 overrelaxing, very general iterations may be derived for both proposed methods, recovering the forwardbackwardforward and the forwardbackwardhalfforward 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 forwardbackwardforwardtype method is strongly convergent to the best approximation solution of the three operator monotone inclusion.
PubDate: 20220915

 On unique recovery of finitevalued integer signals and admissible
lattices of sparse hypercubes
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 paper considers the problem of unique recovery of sparse finitevalued integer signals using a single linear integer measurement. For lsparse 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^{2l1})\) . Here the implicit constant depends on l and n and the exponent \(2l1\) is optimal. Additionally, we show that, in the above setting, a single measurement can be replaced by several measurements with absolute entries sublinear in \(\Delta\) . The proofs make use of results on admissible \((n1)\) dimensional integer lattices for msparse ncubes that are of independent interest.
PubDate: 20220913

 An improved algorithm for parallel machine scheduling under additional
resource constraints
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 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 NPhardness of the problem, we design a threestage 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: 20220912

 General variable neighborhood search for the parallel machine scheduling
problem with two common servers
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 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 smallsized 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 solutionfinding mechanism based on the unloading server waiting time minimization significantly outperforms the other approaches.
PubDate: 20220910

 Numerical solution of delay fractional optimal control problems with free
terminal time
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 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 wellknown timescaling transformation for mapping the free time horizon into a fixed time interval yields a new fractionalorder system with variable timedelay. Then, we propose an explicit numerical scheme for solving the resulting fractional timedelay system, which gives rise to a discretetime optimal control problem. Furthermore, we derive gradient formulas of the cost and constraint functions with respect to decision variables. On this basis, a gradientbased optimization approach is developed to solve the resulting discretetime optimal control problem. Finally, an example problems is solved to demonstrate the effectiveness of our proposed solution approach.
PubDate: 20220910

 A unified analysis of convex and nonconvex $$\ell _p$$ ℓ p ball
projection problems
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 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 nonconvex case. The success of our contributions is thoroughly assessed empirically, and applied to largescale regularized multitask learning and compressed sensing. The code implementing our methods is publicly available on Github.
PubDate: 20220904

 Stochastic saddlepoint optimization for the Wasserstein barycenter
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 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 saddlepoint 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: 20220901

 Zerothorder methods for noisy Höldergradient 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, we prove new complexity bounds for zerothorder methods in nonconvex 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/s1020801592962) and extend their results, obtained for optimization methods for smooth zerothorder nonconvex problems, to the setting of minimization of functions with Höldercontinuous gradient with noisy zerothorder oracle, obtaining noise upperbounds as well. We consider finitedifference 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 zerothorder 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: 20220901

 Improved exploitation of higher order smoothness in derivativefree
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 consider \(\beta \) smooth (satisfies the generalized Hölder condition with parameter \(\beta > 2\) ) stochastic convex optimization problem with zeroorder onepoint oracle. The best known result was (Akhavan et al. in Exploiting higher order smoothness in derivativefree 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: 20220901

 Efficient PTAS for the maximum traveling salesman problem in a metric
space of fixed doubling dimension
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 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 APXhard in the general metric case but admits polynomialtime approximation schemes in the geometric setting, when the edge weights are induced by a vector norm in fixeddimensional 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 cubictime algorithm which finds asymptotically optimal solutions of the metric Max TSP in fixed and sublogarithmic doubling dimensions.
PubDate: 20220901

 Equilibrium uniqueness in aggregative games: very practical conditions

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 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 standalone 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 quasiconcave. 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: 20220901

 How to find the convex hull of all integer points
in a polyhedron'
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 propose a cutbased 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: 20220901

 Gainoptimized spectral distortions for pronunciation training

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 considers an assessment and evaluation of speech sound pronunciation quality in computeraided 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 gainoptimized 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: 20220901

 Optimal externalities in a parallel transportation network

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 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 (speedlimit 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: 20220901

 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
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.
PubDate: 20220709
DOI: 10.1007/s11590022019038
