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: Paatero [1] and Kolda and Bader [2] pointed out that optimal solutions of the best rank-R approximation of a tensor may not exist in general. This problem is also called as the degeneration problem. In this paper, we study the issue of numerical algorithms of structure preserving rank-R approximation and structure preserving CP-decomposition of partially symmetric tensors. We prove that the rank-2 approximation optimization model based on the alternating best rank-1 approximation is non-degenerate. We then propose an alternating symmetric high-order power method (a-SHOPM) for the best structure preserving rank-R approximation problem and prove the convergence of the algorithm. Furthermore, we find that if the classic BFGS algorithm is used to obtain the initial point first, then the a-SHOPM has better computational performance. So, we then propose a BFGS-a-SHOPM algorithm. Numerical examples show that the BFGS-a-SHOPM algorithm has a better success rate and less computation time for the best structure preserving rank-R approximation or structure preserving CP-decomposition. PubDate: 2025-06-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: This paper proposes a new efficient method for a sparse Gaussian graphical model with hidden clustering structures by extending a dual spectral projected gradient (DSPG) method proposed by Nakagaki et al. (Comput Opt Appl, 76(1):33–68, 2020). We establish the global convergence of the proposed method to an optimal solution, and we show that the projection onto the feasible region can be solved with low computational complexity by using the pool-adjacent-violators algorithm. Numerical experiments on synthetic data and real data demonstrate the efficiency of the proposed method. The proposed method takes 0.91 s to achieve a similar solution to the direct application of the DSPG method which takes 4361 s. PubDate: 2025-06-23
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: This paper proposes a Heaviside composite optimization approach and presents a progressive method for solving multi-treatment learning problems with non-convex constraints. A Heaviside composite function is a composite of a Heaviside function (i.e., the indicator function of either the open $$( \, 0,\infty )$$ or closed $$[ \, 0,\infty \, )$$ interval) with a possibly nondifferentiable function. Modeling-wise, we show how Heaviside composite optimization provides a rigorous mathematical formulation for learning multi-treatment rules subject to Gini constraints. A Heaviside composite function has an equivalent discrete formulation and the resulting optimization problem can in principle be solved by integer programming (IP) methods. Nevertheless, for constrained treatment learning problems with large datasets, a straightforward application of off-the-shelf IP solvers is usually ineffective in achieving global optimality. To alleviate such a computational burden, our major contribution is the proposal of the progressive method by leveraging the effectiveness of state-of-the-art IP solvers for problems of modest sizes. We provide the theoretical advantage of the progressive method with the connection to continuous optimization and show that the computed solution is locally optimal for a broad class of Heaviside composite optimization problems. The superior numerical performance of the proposed method is demonstrated by extensive computational experimentation. A brief discussion of how score-based and tree-based multi-classification problems can also be formulated as Heaviside composite optimization problems and thus treated by the same progressive method is presented in an appendix. PubDate: 2025-06-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: The sequence-form representation has shown remarkable efficacy in computing Nash equilibria for two-player extensive-form games with perfect recall. Nonetheless, devising an efficient algorithm for n-player games using the sequence form remains a substantial challenge. To bridge this gap, we establish a necessary and sufficient condition, characterized by a polynomial system, for Nash equilibrium within the sequence-form framework. Building upon this, we develop a sequence-form differentiable path-following method for computing a Nash equilibrium. This method involves constructing an artificial logarithmic-barrier game in sequence form, where two functions of an auxiliary variable are introduced to incorporate logarithmic-barrier terms into the payoff functions and construct the strategy space. Afterward, we prove the existence of a smooth path determined by the artificial game, originating from an arbitrary totally mixed behavioral-strategy profile and converging to a Nash equilibrium of the original game as the auxiliary variable approaches zero. In addition, a convex-quadratic-penalty method and a variant of linear tracing procedure in sequence form are presented as two alternative techniques for computing a Nash equilibrium. Numerical comparisons further illuminate the effectiveness and efficiency of these methods. PubDate: 2025-06-17
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: In this paper, based on the methodology of the preconditioning technique, our objective is devoted to solving a class of vertical tensor complementarity problems (VTCP) by the preconditioned fixed point method based on tensor splitting. We firstly propose a general preconditioner based on the amount of negative components of special vector involved. Secondly, some convergence and comparison theorems of the proposed method are given. Thirdly, we analyze the influence of the parameter on the convergence rate of the proposed method. Finally, numerical examples are given to illustrate the effectiveness of the proposed method. PubDate: 2025-06-17
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: The cosine measure was introduced in 2003 to quantify the richness of finite positive spanning sets of directions in the context of derivative-free directional methods. A positive spanning set is a set of vectors... PubDate: 2025-06-06
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: In this paper, we consider a class of mathematical programs with inequality and equality constraints where the objective involves a cardinality penalty. The introduction of cardinality penalty can make the model automatically generate sparse solutions, but solving the cardinality objective nonlinear program is highly challenging since the objective function is discontinuous. We first give a continuous approximation and discuss its relationship with the original problem. Second, we propose a proximal augmented Lagrangian method for finding a weak directional(d)-stationary point of the continuous approximation. The proposed algorithm is a novel combination of the classical augmented Lagrangian method and proximal gradient algorithm. We prove that the proposed method globally converges to a weak d-stationary point of the continuous approximation, which is stronger than Clarke stationary point. Third, we demonstrate that the cardinality objective nonlinear program is a better model for the facility capacity expansion problem, which can generate key capacity expansion locations to avoid the high operating costs caused by expanding a large number of facilities. Finally, a systematic computational study on two capacity expansion problems is presented. The numerical results demonstrate the benefit of the cardinality objective nonlinear program and the effectiveness of the proposed algorithm. PubDate: 2025-06-02
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: In penalty methods for inequality-constrained optimization problems, the nondifferentiability of the exact $$\ell _1$$-penalty function limits the use of efficient smooth algorithms for solving the subproblems. In light of this, a great number of smoothing techniques has been proposed in the literature. In this paper we present, in a unified manner, results and methods based on functions that smooth and approximate the exact penalty function. We show that these functions define a class of algorithms that converges to global and local minimizers. This unified approach allows us to derive sufficient conditions that guarantee the existence of local minimizers for the subproblems and to establish a linear convergence rate for this class of methods, using an error bound-type condition. Finally, numerical experiments with problems of the CUTEst collection are presented to illustrate the computational performance of some methods from the literature which can be recovered as particular cases of our unified approach. PubDate: 2025-05-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: In this paper we deal with batch Bayesian Optimization (Bayes-Opt) problems over a box. Bayes-Opt approaches find their main applications when the objective function is very expensive to evaluate. Sometimes, given the availability of multi-processor computing architectures, function evaluation might be performed in parallel in order to lower the clock-time of the overall computation. This paper fits this situation and is devoted to the development of a novel bi-objective optimization (BOO) acquisition strategy to sample batches of points where to evaluate the objective function. The BOO problem involves the Gaussian Process posterior mean and variance functions, which, in most of the acquisition strategies from the literature, are generally used in combination, frequently through scalarization. However, such scalarization could compromise the Bayes-Opt process performance, as getting the desired trade-off between exploration and exploitation is not trivial in most cases. We instead aim to reconstruct the Pareto front of the BOO problem exploiting first order information of the posterior mean and variance, thus generating multiple trade-offs of the two functions without any a priori knowledge. The algorithm used for the reconstruction is the Non-dominated Sorting Memetic Algorithm (NSMA), recently proposed in the literature and proved to be effective in solving hard MOO problems. Finally, we present two clustering approaches, each of them operating on a different space, to select potentially optimal points from the Pareto front. We compare our methodology with well-known acquisition strategies from the literature, showing its effectiveness on a wide set of experiments. PubDate: 2025-05-23
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: In this paper, we propose a randomized feasible algorithm for optimization over the Stiefel manifold, where only some randomly chosen columns of the variable matrix are updated at each iteration. It is proved that the sequence of Riemannian gradients generated by the algorithm converges to zero with probability one. Numerical results show that the algorithm is efficient, especially for the problems when the matrices involved are sparse. PubDate: 2025-05-22
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: This paper presents strong worst-case iteration and operation complexity guarantees for Riemannian adaptive regularized Newton methods, a unified framework encompassing both Riemannian adaptive regularization (RAR) methods and Riemannian trust region (RTR) methods. We comprehensively characterize the sources of approximation in second-order manifold optimization methods: the objective function’s smoothness, retraction’s smoothness, and subproblem solver’s inexactness. Specifically, for a function with a $$\mu $$-Hölder continuous Hessian, when equipped with a retraction featuring a $$\nu $$-Hölder continuous differential and a $$\theta $$-inexact subproblem solver, both RTR and RAR with $$2\!+\!\alpha $$ regularization (where $$\alpha =\min \{\mu ,\nu ,\theta \}$$) locate an $$(\epsilon ,\epsilon ^{\alpha /(1+\alpha )})$$-approximate second-order stationary point within at most $$O(\epsilon ^{-(2+\alpha )/(1+\alpha )})$$ iterations and at most $${\widetilde{O}}(\epsilon ^{- (4+3\alpha ) /(2(1+\alpha ))})$$ Hessian-vector products with high probability. These complexity results are novel and sharp, and reduce to an iteration complexity of $$O(\epsilon ^{-3 /2})$$ and an operation complexity of $${\widetilde{O}}(\epsilon ^{-7 /4})$$ when $$\alpha =1$$. PubDate: 2025-05-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: In this paper, we exploit some properties of points in a neighborhood of the solution set of degenerate optimization problems. Combining these facts with the boundedness of the inverse of regularized Jacobian matrix arising in a mixed logarithmic barrier-augmented lagrangian method, we propose an updating rule for parameters of a mixed logarithmic barrier-augmented Lagrangian algorithm. The superlinear convergence of this algorithm is then proved without any constraint qualification. Numerical results on degenerate problems are also presented to confirm theoretical results. PubDate: 2025-05-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: Gradient method is an important method for solving large scale problems. In this paper, a new gradient method framework for unconstrained optimization problem is proposed, where the stepsize is updated in a cyclic way. The Cauchy step is approximated by the quadratic interpolation. And the cycle for stepsize update is adjusted adaptively. Combining with the adaptive nonmonotone line search technique, we prove the global convergence of the proposed method. Furthermore, its sublinear convergence rate for convex problems and R-linear convergence rate for problems with quadratic functional growth property are analyzed. Numerical results show that our proposed algorithm enjoys good performances in terms of both computational cost and obtained function values. PubDate: 2025-05-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: In decentralized optimization over networks, each node in the network has a portion of the global objective function and the aim is to collectively optimize this function. Gradient tracking methods have emerged as a popular alternative for solving such problems due to their strong theoretical guarantees and robust empirical performance. These methods perform two operations (steps) at each iteration: (1) compute local gradients at each node, and (2) communicate local information with neighboring nodes. The complexity of these two steps can vary significantly across applications. In this work, we present a flexible gradient tracking algorithmic framework designed to balance the composition of communication and computation steps over the optimization process using a randomized scheme. The proposed framework is general, unifies gradient tracking methods, and recovers classical gradient tracking methods as special cases. We establish convergence guarantees in expectation and illustrate how the complexity of communication and computation steps can be balanced using the provided flexibility. Finally, we illustrate the performance of the proposed methods on quadratic and logistic regression problems, and compare against popular algorithms from the literature. PubDate: 2025-05-11
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: In this work, we propose Model-and-Search (MAS), a novel local-search derivative-free optimization algorithm, and show that it is convergent to a Karush-Kuhn-Tucker point. MAS aims to optimize a deterministic function over a box-bounded domain and is designed to work well within a confined budget of function evaluations. In MAS, the search is oriented to improve the value of the incumbent by combining a set of techniques, including gradient estimation and quadratic model building and optimization. We propose a novel sensitivity-based approach to construct an incomplete quadratic model when points are not enough to build a complete quadratic surrogate model of the true function. The surrogate model is then used to guide the search. We present extensive computational results on a collection of 501 publicly available test problems with varying dimensions and complexity. The computational results demonstrate that MAS performs well regardless of problem convexity and smoothness. PubDate: 2025-05-11
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: For smooth optimization problems with a Hermitian positive semidefinite fixed-rank constraint, we consider three existing approaches including the simple Burer–Monteiro method, and Riemannian optimization over quotient geometry and the embedded geometry. These three methods can be all represented via quotient geometry with three Riemannian metrics $$g^i(\cdot , \cdot )$$ $$(i=1,2,3)$$. By taking the nonlinear conjugate gradient method (CG) as an example, we show that CG in the factor-based Burer–Monteiro approach is equivalent to Riemannian CG on the quotient geometry with the Bures–Wasserstein metric $$g^1$$. Riemannian CG on the quotient geometry with the metric $$g^3$$ is equivalent to Riemannian CG on the embedded geometry. For comparing the three approaches, we analyze the condition number of the Riemannian Hessian near a minimizer under the three different metrics. Under certain assumptions, the condition number from the Bures–Wasserstein metric $$g^1$$ is significantly worse than the other two metrics. Numerical experiments show that the Burer–Monteiro CG method has obviously slower asymptotic convergence rate either when the minimizer has a large condition number or when it is rank deficient, which is consistent with the condition number analysis. PubDate: 2025-05-09
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: This paper provides a comprehensive study of the nonmonotone forward–backward splitting (FBS) method for solving a class of nonsmooth composite problems in Hilbert spaces. The objective function is the sum of a Fréchet differentiable (not necessarily convex) function and a proper lower semicontinuous convex (not necessarily smooth) function. These problems appear, for example, frequently in the context of optimal control of nonlinear partial differential equations (PDEs) with nonsmooth sparsity-promoting cost functionals. We discuss the convergence and complexity of FBS equipped with the nonmonotone linesearch under different conditions. In particular, R-linear convergence will be derived under quadratic growth-type conditions. We also investigate the applicability of the algorithm to problems governed by PDEs. Numerical experiments are also given that justify our theoretical findings. PubDate: 2025-05-08
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: Off-the-grid regularisation has been extensively employed over the last decade in the context of ill-posed inverse problems formulated in the continuous setting of the space of Radon measures $${{\mathcal {M}}(\Omega )}$$. These approaches enjoy convexity and counteract the discretisation biases as well the numerical instabilities typical of their discrete counterparts. In the framework of sparse reconstruction of discrete point measures (sum of weighted Diracs), a Total Variation regularisation norm in $${{\mathcal {M}}(\Omega )}$$ is typically combined with an $$L^2$$ data term modelling additive Gaussian noise. To assess the framework of off-the-grid regularisation in the presence of signal-dependent Poisson noise, we consider in this work a variational model where Total Variation regularisation is coupled with a Kullback–Leibler data term under a non-negativity constraint. Analytically, we study the optimality conditions of the composite functional and analyse its dual problem. Then, we consider an homotopy strategy to select an optimal regularisation parameter and use it within a Sliding Frank-Wolfe algorithm. Several numerical experiments on both 1D/2D/3D simulated and real 3D fluorescent microscopy data are reported. PubDate: 2025-05-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.
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: In this paper, we consider the composite convex optimization problem with a linear equality constraint. We propose a practical inexact augmented Lagrangian (IAL) framework that employs two relative error criteria. Under the first criterion, we demonstrate convergence and establish sublinear ergodic convergence rates. By incorporating the second criterion, we achieve sublinear non-ergodic convergence rates. Furthermore, we determine the total iteration complexity of the IAL framework by slightly relaxing these criteria. Numerical experiments on both synthetic and real-world problems are conducted to illustrate the efficiency of the proposed IAL method. PubDate: 2025-04-28
Hybrid journal (It can contain Open Access articles)
[2468 journals]
