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 Riemannian preconditioned algorithms for the tensor completion problem via tensor ring decomposition. A new Riemannian metric is developed on the product space of the mode-2 unfolding matrices of the core tensors in tensor ring decomposition. The construction of this metric aims to approximate the Hessian of the cost function by its diagonal blocks, paving the way for various Riemannian optimization methods. Specifically, we propose the Riemannian gradient descent and Riemannian conjugate gradient algorithms. We prove that both algorithms globally converge to a stationary point. In the implementation, we exploit the tensor structure and adopt an economical procedure to avoid large matrix formulation and computation in gradients, which significantly reduces the computational cost. Numerical experiments on various synthetic and real-world datasets—movie ratings, hyperspectral images, and high-dimensional functions—suggest that the proposed algorithms have better or favorably comparable performance to other candidates. PubDate: 2024-06-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 An arc-search interior-point method is a type of interior-point method that approximates the central path by an ellipsoidal arc, and it can often reduce the number of iterations. In this work, to further reduce the number of iterations and the computation time for solving linear programming problems, we propose two arc-search interior-point methods using Nesterov’s restarting strategy which is a well-known method to accelerate the gradient method with a momentum term. The first one generates a sequence of iterations in the neighborhood, and we prove that the proposed method converges to an optimal solution and that it is a polynomial-time method. The second one incorporates the concept of the Mehrotra-type interior-point method to improve numerical performance. The numerical experiments demonstrate that the second one reduced the number of iterations and the computational time compared to existing interior-point methods due to the momentum term. PubDate: 2024-06-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 Gradient-based methods have been highly successful for solving a variety of both unconstrained and constrained nonlinear optimization problems. In real-world applications, such as optimal control or machine learning, the necessary function and derivative information may be corrupted by noise, however. Sun and Nocedal have recently proposed a remedy for smooth unconstrained problems by means of a stabilization of the acceptance criterion for computed iterates, which leads to convergence of the iterates of a trust-region method to a region of criticality (Sun and Nocedal in Math Program 66:1–28, 2023. https://doi.org/10.1007/s10107-023-01941-9). We extend their analysis to the successive linear programming algorithm (Byrd et al. in Math Program 100(1):27–48, 2003. https://doi.org/10.1007/s10107-003-0485-4, SIAM J Optim 16(2):471–489, 2005. https://doi.org/10.1137/S1052623403426532) for unconstrained optimization problems with objectives that can be characterized as the composition of a polyhedral function with a smooth function, where the latter and its gradient may be corrupted by noise. This gives the flexibility to cover, for example, (sub)problems arising in image reconstruction or constrained optimization algorithms. We provide computational examples that illustrate the findings and point to possible strategies for practical determination of the stabilization parameter that balances the size of the critical region with a relaxation of the acceptance criterion (or descent property) of the algorithm. PubDate: 2024-06-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 recent advance of algorithms for nonlinear semidefinite optimization problems (NSDPs) is remarkable. Yamashita et al. first proposed a primal–dual interior point method (PDIPM) for solving NSDPs using the family of Monteiro–Zhang (MZ) search directions. Since then, various kinds of PDIPMs have been proposed for NSDPs, but, as far as we know, all of them are based on the MZ family. In this paper, we present a PDIPM equipped with the family of Monteiro–Tsuchiya (MT) directions, which were originally devised for solving linear semidefinite optimization problems as were the MZ family. We further prove local superlinear convergence to a Karush–Kuhn–Tucker point of the NSDP in the presence of certain general assumptions on scaling matrices, which are used in producing the MT search directions. Finally, we conduct numerical experiments to compare the efficiency among members of the MT family. PubDate: 2024-06-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 work, we introduce new direct-search schemes for the solution of bilevel optimization (BO) problems. Our methods rely on a fixed accuracy blackbox oracle for the lower-level problem, and deal both with smooth and potentially nonsmooth true objectives. We thus analyze for the first time in the literature direct-search schemes in these settings, giving convergence guarantees to approximate stationary points, as well as complexity bounds in the smooth case. We also propose the first adaptation of mesh adaptive direct-search schemes for BO. Some preliminary numerical results on a standard set of bilevel optimization problems show the effectiveness of our new approaches. PubDate: 2024-06-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 focuses on the minimization of a sum of a twice continuously differentiable function f and a nonsmooth convex function. An inexact regularized proximal Newton method is proposed by an approximation to the Hessian of f involving the \(\varrho \) th power of the KKT residual. For \(\varrho =0\) , we justify the global convergence of the iterate sequence for the KL objective function and its R-linear convergence rate for the KL objective function of exponent 1/2. For \(\varrho \in (0,1)\) , by assuming that cluster points satisfy a locally Hölderian error bound of order q on a second-order stationary point set and a local error bound of order \(q>1\!+\!\varrho \) on the common stationary point set, respectively, we establish the global convergence of the iterate sequence and its superlinear convergence rate with order depending on q and \(\varrho \) . A dual semismooth Newton augmented Lagrangian method is also developed for seeking an inexact minimizer of subproblems. Numerical comparisons with two state-of-the-art methods on \(\ell _1\) -regularized Student’s t-regressions, group penalized Student’s t-regressions, and nonconvex image restoration confirm the efficiency of the proposed method. PubDate: 2024-06-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 study a novel inertial proximal-gradient method for composite optimization. The proposed method alternates between a variable metric proximal-gradient iteration with momentum and an Armijo-like linesearch based on the sufficient decrease of a suitable merit function. The linesearch procedure allows for a major flexibility on the choice of the algorithm parameters. We prove the convergence of the iterates sequence towards a stationary point of the problem, in a Kurdyka–Łojasiewicz framework. Numerical experiments on a variety of convex and nonconvex problems highlight the superiority of our proposal with respect to several standard methods, especially when the inertial parameter is selected by mimicking the Conjugate Gradient updating rule. PubDate: 2024-06-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 Flag manifolds, sets of nested sequences of linear subspaces with fixed dimensions, are rising in numerical analysis and statistics. The current optimization algorithms on flag manifolds are based on the exponential map and parallel transport, which are expensive to compute. In this paper we propose practical optimization methods on flag manifolds without the exponential map and parallel transport. Observing that flag manifolds have a similar homogeneous structure with Grassmann and Stiefel manifolds, we generalize some typical retractions and vector transports to flag manifolds, including the Cayley-type retraction and vector transport, the QR-based and polar-based retractions, the projection-type vector transport and the projection of the differentiated polar-based retraction as a vector transport. Theoretical properties and efficient implementations of the proposed retractions and vector transports are discussed. Then we establish Riemannian gradient and Riemannian conjugate gradient algorithms based on these retractions and vector transports. Numerical results on the problem of nonlinear eigenflags demonstrate that our algorithms have a great advantage in efficiency over the existing ones. PubDate: 2024-06-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 consider the tensor complementarity problem (TCP). From the perspective of non-coupled equality constraint minimization problem for the symmetric TCP, we propose a generalized alternating direction method of multipliers (G-ADMM) to solve the general TCP in which the tensor may not be symmetric. The global convergence and the \(O(\frac{1}{k})\) convergence rate of the proposed method are proved under the assumption which is much weaker than the monotone assumption. Numerical results show that the method is efficient for solving the TCP. PubDate: 2024-05-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.

Abstract: Abstract We introduce a new approach to apply the boosted difference of convex functions algorithm (BDCA) for solving non-convex and non-differentiable problems involving difference of two convex functions (DC functions). Supposing the first DC component differentiable and the second one possibly non-differentiable, the main idea of BDCA is to use the point computed by the subproblem of the DC algorithm (DCA) to define a descent direction of the objective from that point, and then a monotone line search starting from it is performed in order to find a new point which decreases the objective function when compared with the point generated by the subproblem of DCA. This procedure improves the performance of the DCA. However, if the first DC component is non-differentiable, then the direction computed by BDCA can be an ascent direction and a monotone line search cannot be performed. Our approach uses a non-monotone line search in the BDCA (nmBDCA) to enable a possible growth in the objective function values controlled by a parameter. Under suitable assumptions, we show that any cluster point of the sequence generated by the nmBDCA is a critical point of the problem under consideration and provides some iteration-complexity bounds. Furthermore, if the first DC component is differentiable, we present different iteration-complexity bounds and prove the full convergence of the sequence under the Kurdyka–Łojasiewicz property of the objective function. Some numerical experiments show that the nmBDCA outperforms the DCA, such as its monotone version. PubDate: 2024-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: Abstract In this paper, we propose and analyze an away-step Frank–Wolfe algorithm designed for solving multiobjective optimization problems over polytopes. We prove that each limit point of the sequence generated by the algorithm is a weak Pareto optimal solution. Furthermore, under additional conditions, we show linear convergence of the whole sequence to a Pareto optimal solution. Numerical examples illustrate a promising performance of the proposed algorithm in problems where the multiobjective Frank–Wolfe convergence rate is only sublinear. PubDate: 2024-05-07

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 Shape optimization methods have been proven useful for identifying interfaces in models governed by partial differential equations. Here we consider a class of shape optimization problems constrained by nonlocal equations which involve interface–dependent kernels. We derive a novel shape derivative associated to the nonlocal system model and solve the problem by established numerical techniques. The code for obtaining the results in this paper is published at (https://github.com/schustermatthias/nlshape). PubDate: 2024-05-07

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 propose a hybrid inexact regularized Newton and negative curvature method for solving unconstrained nonconvex problems. The descent direction is chosen based on different conditions, either the negative curvature or the inexact regularized direction. In addition, to minimize computational costs while obtaining the negative curvature, we employ a dimensionality reduction strategy to verify if the Hessian matrix exhibits negative curvatures within a three-dimensional subspace. We show that the proposed method can achieve the best-known global iteration complexity if the Hessian of the objective function is Lipschitz continuous on a certain compact set. Two simplified methods for nonconvex and strongly convex problems are analyzed as specific instances of the proposed method. We show that under the local error bound assumption with respect to the gradient, the distance between iterations generated by our proposed method and the local solution set converges to \(0\) at a superlinear rate. Additionally, for strongly convex problems, the quadratic convergence rate can be achieved. Extensive numerical experiments show the effectiveness of the proposed method. PubDate: 2024-05-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: Abstract Approximation of subdifferentials is one of the main tasks when computing descent directions for nonsmooth optimization problems. In this article, we propose a bisection method for weakly lower semismooth functions which is able to compute new subgradients that improve a given approximation in case a direction with insufficient descent was computed. Combined with a recently proposed deterministic gradient sampling approach, this yields a deterministic and provably convergent way to approximate subdifferentials for computing descent directions. PubDate: 2024-05-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 develop rapidly convergent forward–backward algorithms for computing zeroes of the sum of two maximally monotone operators. A modification of the classical forward–backward method is considered, by incorporating an inertial term (closed to the acceleration techniques introduced by Nesterov), a constant relaxation factor and a correction term, along with a preconditioning process. In a Hilbert space setting, we prove the weak convergence to equilibria of the iterates \((x_n)\) , with worst-case rates of \( o(n^{-1})\) in terms of both the discrete velocity and the fixed point residual, instead of the rates of \(\mathcal {O}(n^{-1/2})\) classically established for related algorithms. Our procedure can be also adapted to more general monotone inclusions. In particular, we propose a fast primal-dual algorithmic solution to some class of convex-concave saddle point problems. In addition, we provide a well-adapted framework for solving this class of problems by means of standard proximal-like algorithms dedicated to structured monotone inclusions. Numerical experiments are also performed so as to enlighten the efficiency of the proposed strategy. PubDate: 2024-05-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 the formulation of convex Generalized Disjunctive Programming (GDP) problems using conic inequalities leading to conic GDP problems. We then show the reformulation of conic GDPs into Mixed-Integer Conic Programming (MICP) problems through both the big-M and hull reformulations. These reformulations have the advantage that they are representable using the same cones as the original conic GDP. In the case of the hull reformulation, they require no approximation of the perspective function. Moreover, the MICP problems derived can be solved by specialized conic solvers and offer a natural extended formulation amenable to both conic and gradient-based solvers. We present the closed form of several convex functions and their respective perspectives in conic sets, allowing users to formulate their conic GDP problems easily. We finally implement a large set of conic GDP examples and solve them via the scalar nonlinear and conic mixed-integer reformulations. These examples include applications from Process Systems Engineering, Machine learning, and randomly generated instances. Our results show that the conic structure can be exploited to solve these challenging MICP problems more efficiently. Our main contribution is providing the reformulations, examples, and computational results that support the claim that taking advantage of conic formulations of convex GDP instead of their nonlinear algebraic descriptions can lead to a more efficient solution to these problems. PubDate: 2024-05-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 two-stage risk-averse mixed-integer recourse models with law invariant coherent risk measures. As in the risk-neutral case, these models are generally non-convex as a result of the integer restrictions on the second-stage decision variables and hence, hard to solve. To overcome this issue, we propose a convex approximation approach. We derive a performance guarantee for this approximation in the form of an asymptotic error bound, which depends on the choice of risk measure. This error bound, which extends an existing error bound for the conditional value at risk, shows that our approximation method works particularly well if the distribution of the random parameters in the model is highly dispersed. For special cases we derive tighter, non-asymptotic error bounds. Whereas our error bounds are valid only for a continuously distributed second-stage right-hand side vector, practical optimization methods often require discrete distributions. In this context, we show that our error bounds provide statistical error bounds for the corresponding (discretized) sample average approximation (SAA) model. In addition, we construct a Benders’ decomposition algorithm that uses our convex approximations in an SAA-framework and we provide a performance guarantee for the resulting algorithm solution. Finally, we perform numerical experiments which show that for certain risk measures our approach works even better than our theoretical performance guarantees suggest. PubDate: 2024-05-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 Recently, Gonçalves and Prudente proposed an extension of the Hager–Zhang nonlinear conjugate gradient method for vector optimization (Comput Optim Appl 76:889–916, 2020). They initially demonstrated that directly extending the Hager–Zhang method for vector optimization may not result in descent in the vector sense, even when employing an exact line search. By utilizing a sufficiently accurate line search, they subsequently introduced a self-adjusting Hager–Zhang conjugate gradient method in the vector sense. The global convergence of this new scheme was proven without requiring regular restarts or any convex assumptions. In this paper, we propose an alternative extension of the Hager–Zhang nonlinear conjugate gradient method for vector optimization that preserves its desirable scalar property, i.e., ensuring sufficiently descent without relying on any line search or convexity assumption. Furthermore, we investigate its global convergence with the Wolfe line search under mild assumptions. Finally, numerical experiments are presented to illustrate the practical behavior of our proposed method. PubDate: 2024-05-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 A novel and highly efficient computational framework for reconstructing binary-type images suitable for models of various complexity seen in diverse biomedical applications is developed and validated. Efficiency in computational speed and accuracy is achieved by combining the advantages of recently developed optimization methods that use sample solutions with customized geometry and multiscale control space reduction, all paired with gradient-based techniques. The control space is effectively reduced based on the geometry of the samples and their individual contributions. The entire 3-step computational procedure has an easy-to-follow design due to a nominal number of tuning parameters making the approach simple for practical implementation in various settings. Fairly straightforward methods for computing gradients make the framework compatible with any optimization software, including black-box ones. The performance of the complete computational framework is tested in applications to 2D inverse problems of cancer detection by electrical impedance tomography (EIT) using data from models generated synthetically and obtained from medical images showing the natural development of cancerous regions of various sizes and shapes. The results demonstrate the superior performance of the new method and its high potential for improving the overall quality of the EIT-based procedures. PubDate: 2024-05-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 solution of finite-sum minimization problems, such as those appearing in nonlinear least-squares or general empirical risk minimization problems. We are motivated by problems in which the summand functions are computationally expensive and evaluating all summands on every iteration of an optimization method may be undesirable. We present the idea of stochastic average model (SAM) methods, inspired by stochastic average gradient methods. SAM methods sample component functions on each iteration of a trust-region method according to a discrete probability distribution on component functions; the distribution is designed to minimize an upper bound on the variance of the resulting stochastic model. We present promising numerical results concerning an implemented variant extending the derivative-free model-based trust-region solver POUNDERS, which we name SAM-POUNDERS. PubDate: 2024-04-24