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 presents general theoretical studies on asymptotic convergence rate (ACR) for finite dimensional optimization. Given the continuous problem function and discrete time stochastic optimization process, the ACR is the optimal constant for control of the asymptotic behaviour of the expected approximation errors. Under general assumptions, condition ACR \(<1\) implies the linear behaviour of the expected time of hitting the \(\varepsilon \) - optimal sublevel set with \(\varepsilon \rightarrow 0^+ \) and determines the upper bound for the convergence rate of the trajectories of the process. This paper provides general characterization of ACR and, in particular, shows that some algorithms cannot converge linearly fast for any nontrivial continuous optimization problem. The relation between asymptotic convergence rate in the objective space and asymptotic convergence rate in the search space is provided. Examples and numerical simulations with use of a (1+1) self-adaptive evolution strategy and other algorithms are presented. PubDate: 2023-11-24

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 give some existence theorems of solutions to \(\Gamma \) -robust counterparts of gap function formulations of uncertain linear complementarity problems, in which \(\Gamma \) plays a role in adjusting the robustness of the model against the level of conservatism of solutions. If the \(\Gamma \) -robust uncertainty set is nonconvex, it is hard to prove the existence of solutions to the corresponding robust counterpart. Using techniques of asymptotic functions, we establish existence theorems of solutions to the corresponding robust counterpart. For the case of nonconvex \(\Gamma \) -robust ellipsoidal uncertainty sets, these existence results are not proved in the paper [Krebs et al., Int. Trans. Oper. Res. 29 (2022), pp. 417–441]; for the case of convex \(\Gamma \) -robust ellipsoidal uncertainty sets, our existence theorems are obtained under the conditions which are much weaker than those in Krebs’ paper. Finally, a case study for the uncertain traffic equilibrium problem is considered to illustrate the effects of nonconvex uncertainty sets on the level of conservatism of robust solutions. PubDate: 2023-11-24

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 has two parts. In the mathematical part, we present two inexact versions of the proximal point method for solving quasi-equilibrium problems (QEP) in Hilbert spaces. Under mild assumptions, we prove that the methods find a solution to the quasi-equilibrium problem with an approximated computation of each iteration or using a perturbation of the regularized bifunction. In the behavioral part, we justify the choice of the new perturbation, with the help of the main example that drives quasi-equilibrium problems: the Cournot duopoly model, which founded game theory. This requires to exhibit a new QEP reformulation of the Cournot model that will appear more intuitive and rigorous. It leads directly to the formulation of our perturbation function. Some numerical experiments show the performance of the proposed methods. PubDate: 2023-11-24

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 address the problem of configuring a power distribution network with reliability and resilience objectives by satisfying the demands of the consumers and saturating each production source as little as possible. We consider power distribution networks containing source nodes producing electricity, nodes representing electricity consumers and switches between them. Configuring this network consists in deciding the orientation of the links between the nodes of the network. The electric flow is a direct consequence of the chosen configuration and can be computed in polynomial time. It is valid if it satisfies the demand of each consumer and capacity constraints on the network. In such a case, we study the problem of determining a feasible solution that balances the loads of the sources, that is their production rates. We use three metrics to measure the quality of a solution: minimizing the maximum load, maximizing the minimum load and minimizing the difference of the maximum and the minimum loads. This defines optimization problems called respectively \(\min \) -M, \(\max \) -m and \(\min \) -R. In the case where the graph of the network is a tree, it is known that the problem of building a valid configuration is polynomial. We show the three optimization variants have distinct properties regarding the theoretical complexity and the approximability. Particularly, we show that \(\min \) -M is polynomial, that \(\max \) -m is NP-Hard but belongs to the class FPTAS and that \(\min \) -R is NP-Hard, cannot be approximated to within any exponential relative ratio but, for any \(\varepsilon > 0\) , there exists an algorithm for which the value of the returned solution equals the value of an optimal solution shifted by at most \(\varepsilon \) . PubDate: 2023-11-14

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 the present paper, the strict feasibility of the polynomial complementarity problem (PCP) is investigated. To this end, as a generalization of the concept of S-tensor, a concept of S-tensor tuple is introduced. Some properties of S-tensor tuples are investigated. In particular, several conditions are proposed to judge whether a tensor tuple is an S-tensor tuple or not. Then, based on the S-tensor tuple, the strict feasibility of PCP is investigated. PubDate: 2023-11-14

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 discrete approximation of two-stage stochastic variational inequalities has been investigated when the second stage problem has multiple solutions. First, a discrete approximation scheme is given by a series of models with the aid of merit functions. After that, the convergence relationships between these models are analysed, which therefore yields the convergence guarantee of the proposed discrete approximation scheme. Finally, we use the well-known progressive hedging algorithm to report some numerical results and to validate the effectiveness of the discrete approximation approach. PubDate: 2023-11-14

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 Given a quadratic function \(f(x) = x^T A x + 2 a^T x + a_0\) and its level sets, including \(\{x\in \mathbb {R}^n \mid f(x) < 0\}\) , \(\{x\in \mathbb {R}^n \mid f(x) \le 0\}\) , \(\{x\in \mathbb {R}^n \mid f(x) = 0\}\) , \(\{x\in \mathbb {R}^n \mid f(x) \ge 0\}\) , \(\{x\in \mathbb {R}^n \mid f(x) > 0\},\) we derive conditions on the coefficients \((A, a, a_0)\) for each of the five level sets to be disconnected with exactly two connected components, say \(L^{-}\) and \(L^{+}\) . Once so, we are interested in, when the two connected components can be separated by another quadratic level set \(\{x\in \mathbb {R}^n \mid g(x) = x^T B x + 2b^T x + b_0 = 0\}\) such that \(L^{-} \subset \{x\in \mathbb {R}^n \mid g(x) < 0\}\) and \(L^{+} \subset \{x\in \mathbb {R}^n \mid g(x) > 0\}\) . It has been shown that the particular case for \(\{x\in \mathbb {R}^n \mid g(x) = 0\}\) to separate \(\{x\in \mathbb {R}^n \mid f(x) < 0\}\) is equivalent to the \(\mathcal {S}\) -lemma with equality, and thus answers the strong duality for \(\min \{f(x) \mid g(x) = 0\}.\) In addition, the case when \(\{x\in \mathbb {R}^n \mid g(x) = 0\}\) separates \(\{x\in \mathbb {R}^n \mid f(x) = 0\}\) is closely related to the convexity of the joint range for a pair of quadratic functions (f, g). This paper completes the characterization for all five cases of separation, namely, for \(\{x\in \mathbb {R}^n \mid g(x) = 0\}\) to separate \(\{x\in \mathbb {R}^n \mid f(x) \star 0\}\) where \(\star \in \{<, \le , =, \ge , >\}\) , which is expected to provide a new tool in solving quadratic optimization problems. PubDate: 2023-11-13

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 many real world optimization problems observations are corrupted by a heteroscedastic noise, which depends on the input location. Bayesian optimization (BO) is an efficient approach for global optimization of black-box functions, but the performance of using a Gaussian process (GP) model can degrade with changing levels of noise due to a homoscedastic noise assumption. However, a generalized product of experts (GPOE) model allows us to build independent GP experts on the subsets of observations with individual set of hyperparameters, which is flexible enough to capture the changing levels of noise. In this paper we propose a heteroscedastic Bayesian optimization algorithm by combining the GPOE model with two modifications of existing acquisition functions, which are capable of representing and penalizing heteroscedastic noise across the input space. We compare and evaluate the performance of GPOE based BO (GPOEBO) model on 6 synthetic global optimization functions corrupted with the heteroscedastic noise as well as on two real-world scientific datasets. The results show that GPOEBO is able to improve the accuracy compared to other methods. PubDate: 2023-11-04

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 focus on nonconvex and non-smooth block optimization problems, where the smooth coupling part of the objective does not satisfy a global/partial Lipschitz gradient continuity assumption. A general alternating minimization algorithm is proposed that combines two proximal-based steps, one classical and another with respect to the Bregman divergence. Combining different analytical techniques, we provide a complete analysis of the behavior—from global to local—of the algorithm, and show when the iterates converge globally to critical points with a locally linear rate for sufficiently regular (though not necessarily convex) objectives. Numerical experiments illustrate the theoretical findings. PubDate: 2023-11-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.

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 max hypergraph 3-cut problem with limited unbalance (MH3C-LU). The objective is to divide the vertex set of an edge-weighted hypergraph \(H=(V,E,w)\) into three disjoint subsets \(V_{1}\) , \(V_{2}\) , and \(V_{3}\) such that the sum of edge weights cross different parts is maximized subject to \( V_{i} - V_{l} \le B\) ( \(\forall i\ne l\in \{1,2,3\}\) ) for a given parameter B. This problem is NP-hard because it includes some well-known problems like the max 3-section problem and the max 3-cut problem as special cases. We formulate the MH3C-LU as a ternary quadratic program and present a randomized approximation algorithm based on the complex semidefinite programming relaxation technique. PubDate: 2023-11-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 a recent paper by Li et al. (Comput Optim Appl 78(3):853–891, 2021), the authors propose an SDP relaxation for solving the minimum cut problem. In this note, we derive this SDP relaxation by Li et al. in a different way which provides a new perspective. Moreover, we give a rigorous proof that this relaxation by Li et al. is a stronger relaxation than the SDP relaxation presented in Pong et al. (Comput Optim Appl 63(2):333–364, 2016). The technique that we use to compare these two relaxations is through establishing a containment relationship between the feasible sets of these two relaxations. This technique is then studied and analyzed in a more general setting. We present some interesting observations about the differences in the optimal sets and values under this technique. Finally, we verify the strength of the SDP relaxation by Li et al. on some random graphs and also on some classical graphs for solving the vertex separator problems in the numerical experiments. PubDate: 2023-11-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 Data trading has become increasingly attractive and crucial in the era of the digital economy. Previous studies present insightful but only partial analysis on data-trading coordination which is of great societal value. One particular case in point is government subsidy that has been a common practice in real-life data trading markets among different countries. We propose a differential game with government subsidies that consists of three agents, a data-providing enterprise, a data trading platform, and the government. We analyze and compare the social welfares for both the centralized and decentralized systems, and present a cost-sharing contract and a revenue sharing contract to maximize the system social welfare, in which the quality and the advertising effort are important factors on data products goodwill. Our results reveal that centralization enhances the efficiency of the data trading system, and the government achieves a higher social welfare level with a lower cost subsidy coefficient. Numerical analyses are also carried to provide further managerial insights by comparative statics analysis on system parameters. PubDate: 2023-11-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 study a class of nonconvex and nonsmooth optimization problems, whose objective function can be split into two separable terms and one coupling term. Alternating proximal gradient methods combining with extrapolation are proposed to solve such problems. Under some assumptions, we prove that every cluster point of the sequence generated by our algorithms is a critical point. Furthermore, if the objective function satisfies Kurdyka–Łojasiewicz property, the generated sequence is globally convergent to a critical point. In order to make the algorithm more effective and flexible, we also use some strategies to update the extrapolation parameter and solve the problems with unknown Lipschitz constant. Numerical experiments demonstrate the effectiveness of our algorithms. PubDate: 2023-11-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 describe a method for fitting a Markov chain, with a state transition matrix that depends on a feature vector, to data that can include missing values. Our model consists of separate logistic regressions for each row of the transition matrix. We fit the parameters in the model by maximizing the log-likelihood of the data minus a regularizer. When there are missing values, the log-likelihood becomes intractable, and we resort to the expectation-maximization (EM) heuristic. We illustrate the method on several examples, and describe our efficient Python open-source implementation. PubDate: 2023-11-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 give some characterizations of the robust optimal solution set for nonconvex uncertain semi-infinite programming problems in terms of tangential subdifferentials. By using a new robust-type constraint qualification, we first obtain some necessary and sufficient optimality conditions of the robust optimal solution for the nonconvex uncertain semi-infinite programming problem via the robust optimization approach. Then, by using the Dini pseudoconvexity, we obtain some characterizations of the robust optimal solution set for the nonconvex uncertain semi-infinite programming problem. Finally, as applications of our results, we derive some optimality conditions of the robust optimal solution and characterizations of the robust optimal solution set for the cone-constrained nonconvex uncertain optimization problem. Some examples are given to illustrate the advantage of the results. PubDate: 2023-11-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 multivariate regression analysis, a coefficient matrix is used to relate multiple response variables to regressor variables in a noisy linear system from given data. Optimization is a natural approach to find such coefficient matrix with few nonzero rows. However, the relationship of most group sparse optimization models with cardinality penalty or cardinality constraints is not clear. In this paper, we give a comprehensive description of the relationship between three widely used group sparse optimization problems with cardinality terms: (i) the number of nonzero rows is minimized subject to an error tolerance for regression; (ii) the error for regression is minimized subject to a row cardinality constraint; (iii) the sum of the number of nonzero rows and error for regression is minimized. The first two problems have convex constraints and cardinality constraints respectively, while the third one is an unconstrained optimization problem with a cardinality penalty. We provide sufficient conditions under which the three optimization problems have the same global minimizers. Moreover, we analyze the relationship of stationary points and local minimizers of the three problems. Finally, we use two examples to illustrate our theoretical results for finding solutions of constrained optimization problems involving cardinality terms by unconstrained optimization problems with penalty functions. PubDate: 2023-11-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 study zeroth-order algorithms for minimax optimization problems that are nonconvex in one variable and strongly-concave in the other variable. Such minimax optimization problems have attracted significant attention lately due to their applications in modern machine learning tasks. We first consider a deterministic version of the problem. We design and analyze the Zeroth-Order Gradient Descent Ascent (ZO-GDA) algorithm, and provide improved results compared to existing works, in terms of oracle complexity. We also propose the Zeroth-Order Gradient Descent Multi-Step Ascent (ZO-GDMSA) algorithm that significantly improves the oracle complexity of ZO-GDA. We then consider stochastic versions of ZO-GDA and ZO-GDMSA, to handle stochastic nonconvex minimax problems. For this case, we provide oracle complexity results under two assumptions on the stochastic gradient: (i) the uniformly bounded variance assumption, which is common in traditional stochastic optimization, and (ii) the Strong Growth Condition (SGC), which has been known to be satisfied by modern over-parameterized machine learning models. We establish that under the SGC assumption, the complexities of the stochastic algorithms match that of deterministic algorithms. Numerical experiments are presented to support our theoretical results. PubDate: 2023-11-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 Stochastic gradient descent method is popular for large scale optimization but has slow convergence asymptotically due to the inherent variance. To remedy this problem, there have been many explicit variance reduction methods for stochastic descent, such as SVRG Johnson and Zhang [Advances in neural information processing systems, (2013), pp. 315–323], SAG Roux et al. [Advances in neural information processing systems, (2012), pp. 2663–2671], SAGA Defazio et al. [Advances in neural information processing systems, (2014), pp. 1646–1654] and so on. Conjugate gradient method, which has the same computation cost with gradient descent method, is considered. In this paper, in the spirit of SAGA, we propose a stochastic conjugate gradient algorithm which we call SCGA. With the Fletcher and Reeves type choices, we prove a linear convergence rate for smooth and strongly convex functions. We experimentally demonstrate that SCGA converges faster than the popular SGD type algorithms for four machine learning models, which may be convex, nonconvex or nonsmooth. Solving regression problems, SCGA is competitive with CGVR, which is the only one stochastic conjugate gradient algorithm with variance reduction so far, as we know. PubDate: 2023-11-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 an entropy regularized splitting model using low-rank factorization for solving binary quadratic programming with linear inequality constraints. Different from the semidefinite programming relaxation model, our model preserves the rank-one constraint and aims to find high quality rank-one solutions directly. The factorization transforms the variables into low-rank matrices, while the entropy term enforces the low-rank property of the splitting variable . A customized alternating direction method of multipliers is utilized to solve the proposed model. Specifically, our method uses the augmented Lagrangian function to deal with inequality constraints, and solves one subproblem on the oblique manifold by a regularized Newton method. Numerical results on the multiple-input multiple-output detection problem, the maxcut problem and the quadratic \(0-1\) problem indicate that our proposed algorithm has advantage over the SDP methods. PubDate: 2023-11-01