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 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
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 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
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 \(\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
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 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
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 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
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 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
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 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
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 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
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 paper, the connectedness of solution sets for generalized vector equilibrium problems via free-disposal sets (GVEPVF) in complete metric space is discussed. Firstly, by virtue of Gerstewitz scalarization functions and oriented distance functions, a new scalarization function \(\omega \) is constructed and some properties of it are given. Secondly, with the help of \(\omega \) , the existence of solutions for scalarization problems (GVEPVF) \(_\omega \) and the relationship between the solution sets of (GVEPVF) \(_\omega \) and (GVEPVF) are obtained. Then, under some suitable assumptions, sufficient conditions of (path) connectedness of solution sets for (GVEPVF) are established. Finally, as an application, the connectedness results of E-efficient solution set for a class of vector programming problems are derived. The obtained results are new, and some examples are given to illustrate the main results. PubDate: 2022-09-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 a polyhedron P be defined by one of the following ways: \(P = \{x \in {{\,\mathrm{{\mathbb {R}}}\,}}^n :A x \le b\}\) , where \(A \in {{\,\mathrm{{\mathbb {Z}}}\,}}^{(n+k) \times n}\) , \(b \in {{\,\mathrm{{\mathbb {Z}}}\,}}^{(n+k)}\) and \({{\,\mathrm{rank}\,}}A = n\) , \(P = \{x \in {{\,\mathrm{{\mathbb {R}}}\,}}_+^n :A x = b\}\) , where \(A \in {{\,\mathrm{{\mathbb {Z}}}\,}}^{k \times n}\) , \(b \in {{\,\mathrm{{\mathbb {Z}}}\,}}^{k}\) and \({{\,\mathrm{rank}\,}}A = k\) , and let all rank order minors of A be bounded by \(\varDelta \) in absolute values. We show that the short rational generating function for the power series $$\begin{aligned} \sum \limits _{m \in P \cap {{\,\mathrm{{\mathbb {Z}}}\,}}^n} {{\,\mathrm{{\mathbf {x}}}\,}}^m \end{aligned}$$ can be computed with the arithmetical complexity \( O\left( T_{{\mathrm{SNF}}}(d) \cdot d^{k} \cdot d^{\log _2 \varDelta }\right) , \) where k and \(\varDelta \) are fixed, \(d = \dim P\) , and \(T_{{\mathrm{SNF}}}(m)\) is the complexity of computing the Smith Normal Form for \(m \times m\) integer matrices. In particular, \(d = n\) , for the case (i), and \(d = n-k\) , for the case (ii). The simplest examples of polyhedra that meet the conditions (i) or (ii) are the simplices, the subset sum polytope and the knapsack or multidimensional knapsack polytopes. Previously, the existence of a polynomial time algorithm in varying dimension for the considered class of problems was unknown already for simplicies ( \(k = 1\) ). We apply these results to parametric polytopes and show that the step polynomial representation of the function \(c_P({{\,\mathrm{{\mathbf {y}}}\,}}) = P_{{{\,\mathrm{{\mathbf {y}}}\,}}} \cap {{\,\mathrm{{\mathbb {Z}}}\,}}^n \) , where \(P_{{{\,\mathrm{{\mathbf {y}}}\,}}}\) is a parametric polytope, whose structure is close to the cases (i) or (ii), can be computed in polynomial time even if the dimension of \(P_{{{\,\mathrm{{\mathbf {y}}}\,}}}\) is not fixed. As another consequence, we show that the coefficients \(e_i(P,m)\) of the Ehrhart quasi-polynomial $$\begin{aligned} \left mP \cap {{\,\mathrm{{\mathbb {Z}}}\,}}^n\right = \sum \limits _{j = 0}^n e_j(P,m)m^j \end{aligned}$$ can be computed with a polynomial-... PubDate: 2022-09-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 contribution, we consider the optimal control problem for a switched dynamical system. While such systems can exhibit rather complex behavior in the case of only one switch, the most interesting problem corresponds to the case, when the system undergoes an infinite number of switches. We study the limiting behavior of optimal solutions under such assumption and show that there are three types of solutions, two of which correspond to cyclic evolution of the system state and control. PubDate: 2022-09-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 paper, a Positron Emission Tomography/Computed Tomography (PET/CT) examination scheduling problem considering multi-stage processes is studied. Before the actual examination process, imaging agents (a drug with radioactivity) need to be injected into patients. The radioactivity of the imaging agents continuously decays, which results in the required dose by patients increasing with time, i.e., the later the injection time, the more imaging agents need to be prepared for the patients at the beginning. Considering the imaging agents are expensive and non-storable, the studied problem is to determine the start time of the examination service and injection time for the patients, to minimize the total dose of purchased imaging agents. An integer programming model and a set partitioning model are formulated for this problem. A variable neighborhood search heuristic is proposed, in which a scheduling rule based on some derived optimal properties is embedded as one of the search operators. Computational experiments show that the proposed algorithm can obtain near-optimal solutions in a short time, and moreover find much better results than the commonly used First Come First Service (FCFS) rule in most medical institutions, i.e., our approach’s results need much fewer required dose of the imaging agents, and hence can save a lot of costs for the medical institutions. PubDate: 2022-08-03
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 convex optimization problems, characterizations of the solution set in terms of the classical subdifferentials have been investigated by Mangasarian. In quasiconvex optimization problems, characterizations of the solution set for quasiconvex programming in terms of the Greenberg–Pierskalla subdifferentials were given by Suzuki and Kuroiwa. In this paper, our attention focuses on the class of tangentially convex functions. Indeed, we study characterizations of the solution set for tangentially convex optimization problems in terms of subdifferentials. For this purpose, we use tangential subdifferentials and the Greenberg-Pierskalla subdifferentials and present necessary and sufficient optimality conditions for tangentially convex optimization problems. As a consequence, we investigate characterizations of the solution set in terms of tangential subdifferentials and the Greenberg–Pierskalla subdifferentials for tangentially convex optimization problems. Moreover, we compare our results with previous ones. PubDate: 2022-08-03
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 Portfolio risk management has become more important since some unpredictable factors, such as the 2008 financial crisis and the recent COVID-19 crisis. Although the risk can be actively managed by risk diversification, the high transaction cost and managerial concerns ensue by over diversifying portfolio risk. In this paper, we jointly integrate risk diversification and sparse asset selection into mean-variance portfolio framework, and propose an optimal portfolio selection model labeled as JMV. The weighted piecewise quadratic approximation is considered as a penalty promoting sparsity for the asset selection. The variance associated with the marginal risk regard as another penalty term to diversify the risk. By exposing the feature of JMV, we prove that the KKT point of JMV is the local minimizer if the regularization parameter satisfies a mild condition. To solve this model, we introduce the accelerated proximal gradient (APG) algorithm [Wen in SIAM J. Optim 27:124–145, 2017], which is one of the most efficient first-order large-scale algorithm. Meanwhile, the APG algorithm is linearly convergent to a local minimizer of the JMV model. Furthermore, empirical analysis consistently demonstrate the theoretical results and the superiority of the JMV model. PubDate: 2022-07-31
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 paper, the single machine scheduling problem to minimize the total early work is studied. The aim of this problem is to minimize the total amount of processing performed on the jobs before their due dates. We have proposed a better implementation of the existing dynamic programming method and thus solved large problems in an exact way. In particular, we can currently resolve instances of sizes 10,000 exactly instead of 200 with a pseudo-polynomial dynamic programming algorithm. Since the considered problem was proven to be NP-hard, a heuristic based on the Variable Neighborhood Search (VNS) method is proposed to solve larger instances. Computational experiments show that both methods are efficient. PubDate: 2022-07-26
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 paper, we focus on the local convergence rate analysis of the proximal iteratively reweighted \(\ell _1\) algorithms for solving \(\ell _p\) regularization problems, which are widely applied for inducing sparse solutions. We show that if the Kurdyka–Łojasiewicz property is satisfied, the algorithm converges to a unique first-order stationary point; furthermore, the algorithm has local linear convergence or local sublinear convergence. The theoretical results we derived are much stronger than the existing results for iteratively reweighted \(\ell _1\) algorithms. PubDate: 2022-07-26
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 paper, we mainly propose a new Bregman projection method with a different self-adaptive process for solving variational inequalities in a real reflexive Banach space. Exactly, we obtain that the iterative sequence generated by our new algorithm converges strongly to an element of solution set for the variational inequality problem. Our algorithm is interesting and easy to implement in numerical experiments because it has only one projection and does not need to know the Lipschitz constant of the considered operator in advance. The results obtained in this paper can be considered as an improvement and supplement of many recent ones in the field. PubDate: 2022-07-21
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 paper we provide the resolvent computation of the parallel composition of a maximally monotone operator by a linear operator under mild assumptions. Connections with a modification of the warped resolvent are provided. In the context of convex optimization, we obtain the proximity operator of the infimal postcomposition of a convex function by a linear operator and we relax full range conditions on the linear operator to mild qualification conditions. We also introduce a generalization of the proximity operator involving a general linear bounded operator leading to a generalization of Moreau’s decomposition for composite convex optimization. PubDate: 2022-07-18
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 evaluate the dual cone of the set of diagonally dominant matrices (resp., scaled diagonally dominant matrices), namely \(\mathcal{DD}_n^*\) (resp., \(\mathcal{SDD}_n^*\) ), as an approximation of the semidefinite cone. We prove that the norm normalized distance, proposed by Blekherman et al. [5], between a set \(\mathcal{S}\) and the semidefinite cone has the same value whenever \(\mathcal{SDD}_n^* \subseteq \mathcal{S} \subseteq \mathcal{DD}_n^*\) . This implies that the norm normalized distance is not a sufficient measure to evaluate these approximations. As a new measure to compensate for the weakness of that distance, we propose a new distance, called the trace normalized distance. We prove that the trace normalized distance between \(\mathcal{DD}_n^*\) and \(\mathcal{S}^n_+\) has a different value from the one between \(\mathcal{SDD}_n^*\) and \(\mathcal{S}^n_+\) and give the exact values of these distances. PubDate: 2022-07-15
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.
Hybrid journal (It can contain Open Access articles)
