Search

In this article, two Hager–Zhang (HZ) type projection algorithms are presented for large-dimension nonlinear monotone problems and sparse signal recovery in compressed sensing. This goal is attained by conducting singular value analysis of a nonsingular HZ-type search direction matrix as well as applying the idea by Piazza and Politi [J Comput Appl Math. 2002;143(1):141–144] and minimizing the Frobenius norm of an orthornormal matrix. The paper attempts to fill the gap in the work of Hager and Zhang [Pac J Optim. 2006;2(1):35–58], Waziri et al. [Appl Math Comput. 2019;361:645–660], Sabi'u et al. [Appl Numer Math. 2020;153:217–233] and Babaie-Kafaki [4OR-Q J Oper Res. 2014;12:285-292], where the sufficient descent or global convergence condition is not satisfied when the HZ parameter is in the interval $ (0,\frac {1}{4}) $ (0 , 1 4). The proposed schemes are also suitable for solving non-smooth nonlinear problems. Also, by employing some mild conditions, global convergence of the schemes are established, while numerical comparison with four effective HZ-type methods show that the new methods are efficient. Furthermore, to illustrate their practical application, both methods are applied to solve the $ \ell _1 $ ℓ 1 -norm regularization problems to recover a sparse signal in compressive sensing. The experiments conducted in that regard show that the methods are promising and perform better than two other methods in the literature. [ABSTRACT FROM AUTHOR]

We explore the potential for using a nonsmooth loss function based on the max-norm in the training of an artificial neural network without hidden layers. We hypothesise that this may lead to superior classification results in some special cases where the training data are either very small or the class size is disproportional. Our numerical experiments performed on a simple artificial neural network with no hidden layer appear to confirm our hypothesis. [ABSTRACT FROM AUTHOR]

A novel subgradient evaluation method is proposed for nonsmooth convex relaxations of parametric solutions of ordinary differential equations (ODEs) arising in global dynamic optimization, assuming that the relaxations always lie strictly within interval bounds during integration. We argue that this assumption is reasonable in practice. These subgradients are computed as the unique solution of an auxiliary parametric affine ODE, analogous to classical forward/tangent sensitivity evaluation methods for smooth dynamic systems. Unlike established subgradient evaluation approaches for nonsmooth dynamic systems, this new method does not require smoothness or transversality assumptions, and is compatible with existing subgradient evaluation methods for closed-form convex functions, as implemented in subgradient evaluation software such as EAGO.jl and MC++. Moreover, we show that a subgradient for a lower-bounding problem in global dynamic optimization can be directly evaluated using reverse/adjoint sensitivity analysis, which may reduce the overall computational effort for an overarching global optimization method. Numerical examples are presented, based on a proof-of-concept implementation in Julia. [ABSTRACT FROM AUTHOR]

In this paper, we propose a sparse least squares (SLS) optimization model for solving multilinear equations, in which the sparsity constraint on the solutions can effectively reduce storage and computation costs. By employing variational properties of the sparsity set, along with differentiation properties of the objective function in the SLS model, the first-order optimality conditions are analysed in terms of the stationary points. Based on the equivalent characterization of the stationary points, we propose the Newton Hard-Threshold Pursuit (NHTP) algorithm and establish its locally quadratic convergence under some regularity conditions. Numerical experiments conducted on simulated datasets including cases of Completely Positive(CP)-tensors and symmetric strong M-tensors illustrate the efficiency of our proposed NHTP method. [ABSTRACT FROM AUTHOR]

This paper addresses the numerical computation of critical angles between two convex cones in Euclidean spaces. We present a novel approach to computing these critical angles by reducing the problem to finding stationary points of a fractional programming problem. To efficiently compute these stationary points, we introduce a partial linearization-like algorithm that offers significant computational advantages. Solving a sequence of strictly convex subproblems with straightforward solutions in several settings gives the proposed algorithm high computational efficiency while delivering reliable results: our theoretical analysis demonstrates that the proposed algorithm asymptotically computes critical angles. Numerical experiments validate the efficiency of our approach, even when dealing with problems of relatively large dimensions: only a few seconds are necessary to compute critical angles between different types of cones in spaces of dimension 1000. [ABSTRACT FROM AUTHOR]

This paper proposes a novel Difference-of-Convex (DC) decomposition for polynomials using a power-sum representation, achieved by solving a sparse linear system. We introduce the Boosted DCA with Exact Line Search ( BDCA e ) for addressing linearly constrained polynomial programs within the DC framework. Notably, we demonstrate that the exact line search equates to determining the roots of a univariate polynomial in an interval, with coefficients being computed explicitly based on the power-sum DC decompositions. The subsequential convergence of BDCA e to critical points is proven, and its convergence rate under the Kurdyka–Łojasiewicz property is established. To efficiently tackle the convex subproblems, we integrate the Fast Dual Proximal Gradient method by exploiting the separable block structure of the power-sum DC decompositions. We validate our approach through numerical experiments on the Mean–Variance–Skewness–Kurtosis portfolio optimization model and box-constrained polynomial optimization problems. Comparative analysis of BDCA e against DCA, BDCA with Armijo line search, UDCA, and UBDCA with projective DC decomposition, alongside standard nonlinear optimization solvers FMINCON and FILTERSD, substantiates the efficiency of our proposed approach. [ABSTRACT FROM AUTHOR]

Sufficient optimality conditions for a D.C. vector optimization problem are given by Guo and Li (Journal of Optimization Theory and Applications 162, 821–844, 2014). Guo and Li's main result turned out to be false and was corrected by Shafie and Bozorgnia (Journal of Optimization Theory and Applications 182, 837–849, 2019). In this work, we have pointed out that Shafie and Bozorgnia's result is wrong. We correct the flaws and present an alternative proof for the main result. [ABSTRACT FROM AUTHOR]

In this paper, we study the radial epiderivative notion for nonconvex functions, which extends the (classical) directional derivative concept. The paper presents new definition and new properties for this notion and establishes relationships between the radial epiderivative, the Clarke’s directional derivative, the Rockafellar’s subderivative and the directional derivative. The radial epiderivative notion is used to establish new regularity conditions without convexity conditions. The paper presents explicit formulations for computing the radial epiderivatives in terms of weak subgradients and vice versa. We also present an iterative algorithm for approximate computing of radial epiderivatives and show that the algorithm terminates in a finite number of iterations. The paper analyzes necessary and sufficient conditions for global optimums in nonconvex optimization via the radial epiderivatives. We formulate a necessary and sufficient condition for a global descent direction for radially epidifferentiable nonconvex functions. All the properties and theorems presented in this paper are illustrated and interpreted on examples. [ABSTRACT FROM AUTHOR]

In this paper, we use the Mordukhovich/limiting subdifferential to establish approximate optimality conditions/approximate duality theorems/approximate saddle point theorems for multiobjective optimization problems with infinite constraints. The main results obtained in this paper are new and extend some corresponding known results. Some examples are given for the illustration of our results. [ABSTRACT FROM AUTHOR]

In this paper, we propose a Riemannian version of the difference of convex algorithm (DCA) to solve a minimization problem involving the difference of convex (DC) function. The equivalence between the classical and simplified Riemannian versions of the DCA is established. We also prove that under mild assumptions the Riemannian version of the DCA is well defined and every cluster point of the sequence generated by the proposed method, if any, is a critical point of the objective DC function. Some duality relations between the DC problem and its dual are also established. To illustrate the algorithm's effectiveness, some numerical experiments are presented. [ABSTRACT FROM AUTHOR]

In this paper, we consider multi-objective optimization problems with a sparsity constraint on the vector of variables. For this class of problems, inspired by the homonymous necessary optimality condition for sparse single-objective optimization, we define the concept of L-stationarity and we analyze its relationships with other existing conditions and Pareto optimality concepts. We then propose two novel algorithmic approaches: the first one is an iterative hard thresholding method aiming to find a single L-stationary solution, while the second one is a two-stage algorithm designed to construct an approximation of the whole Pareto front. Both methods are characterized by theoretical properties of convergence to points satisfying necessary conditions for Pareto optimality. Moreover, we report numerical results establishing the practical effectiveness of the proposed methodologies. [ABSTRACT FROM AUTHOR]

Orthogonally decomposable (odeco) tensors is a special class of symmetric tensors. Previous works have focused on investigating its E-eigenpairs problem, and made some theoretical achievements concerning the number and the local optimality of E-eigenpairs. However, concerning local optimality of each eigenpair, the existing work only analyzed the third-order tensor case. In this paper, we further exploit this issue for any higher-order tensors by checking second-order necessary condition of the related constrained optimization model and deducing an equivalent matrix formula criterion for local optimality identification. Finally, a generalized conclusion for local optimality of eigenpairs for odeco tensors is provided, and some simulated experiments are conducted for validation. [ABSTRACT FROM AUTHOR]

This paper aims to globally solve a generalized affine fractional program problem (GAFPP). Firstly, by introducing some outer space variables and performing equivalent transformations, we can derive the equivalence problem (EP) of the GAFPP. Secondly, by constructing a novel linear relaxation method, we can deduce the affine relaxation problem (ARP) of the EP. Next, by solving the ARP to compute the lower bound, we propose a new outer space branch-and-bound algorithm for tackling the GAFPP. Then, the global convergence of the algorithm is proved, and the computational complexity of the algorithm in the worst case is analyzed. Finally, numerical experimental results are reported to illustrate the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

In the last two decades, several properties of operators that are weaker than monotonicity have received attention by researchers from many areas including mathematical economics, with the goal to develop new tools applicable in convex analysis and related topics. This paper puts in perspective notions that are extensions of monotoniticity but not beyond quasimonotonicity like pseudomonotonicity, semistrict quasimonotonicity, strict quasimonotonicity and proper quasimonotonicity, and discusses systematically when the sum of two operators satisfying one of those properties, inherits the same property. The case of properly quasimonotone operators deserves a special attention since this notion, being stronger than quasimonotonicity, suffices to obtain many results, including the solvability of variational inequality problems. Several examples showing the optimality in some sense of our results, are presented. [ABSTRACT FROM AUTHOR]

In this paper, we consider a finite family of sets (geometric constraints) F 1 , F 2 , ... , F r in the Euclidean space R n. We show under mild conditions on the geometric constraints that the "perturbation property" of the constrained best approximation from a nonempty closed set K ∩ F is characterized by the "convex conical hull intersection property" (CCHIP in short) at a reference feasible point in F. In this case, F is the intersection of the geometric constraints F 1 , F 2 , ... , F r , and K is a nonempty closed convex set in R n such that K ∩ F ≠ ∅. We do this by first proving a dual cone characterization of the contingent cone of the set F. Finally, we obtain the "Lagrange multiplier characterizations" of the constrained best approximation. Several examples are given to illustrate and clarify our results. [ABSTRACT FROM AUTHOR]

The paper proposes and develops a novel inexact gradient method (IGD) for minimizing $ {\mathcal {C}}^1 $ C1-smooth functions with Lipschitzian gradients, i.e. for problems of $ {\mathcal {C}}^{1,1} $ C1,1 optimization. We show that the sequence of gradients generated by IGD converges to zero. The convergence of iterates to stationary points is guaranteed under the Kurdyka-Łojasiewicz (KL) property of the objective function with convergence rates depending on the KL exponent. The newly developed IGD is applied to designing two novel gradient-based methods of nonsmooth convex optimization such as the inexact proximal point methods (GIPPM) and the inexact augmented Lagrangian method (GIALM) for convex programs with linear equality constraints. These two methods inherit global convergence properties from IGD and are confirmed by numerical experiments to have practical advantages over some well-known algorithms of nonsmooth convex optimization. [ABSTRACT FROM AUTHOR]

We present an analysis of generalized Nash equilibrium problems in infinite-dimensional spaces with possibly non-convex objective functions of the players. Such settings arise, for instance, in games that involve nonlinear partial differential equation constraints. Due to non-convexity, we work with equilibrium concepts that build on first order optimality conditions, especially Quasi-Nash Equilibria (QNE), i.e. first-order optimality conditions for (Generalized) Nash Equilibria, and Variational Equilibria (VE), i.e. first-order optimality conditions for Normalized Nash Equilibria. We prove existence of these types of equilibria and study characterizations of them via regularized (and localized) Nikaido-Isoda merit functions. We also develop continuity and (continuous) differentiability results for these merit functions under quite weak assumptions, using a generalization of Danskin's theorem. They provide a theoretical foundation for, e.g. using globalized descent methods for computing QNE or VE. [ABSTRACT FROM AUTHOR]

We extend our study of the swarm-based gradient descent method for non-convex optimization, (Lu et al., Swarm-based gradient descent method for non-convex optimization, 2022, arXiv:2211.17157), to allow random descent directions. We recall that the swarm-based approach consists of a swarm of agents, each identified with a position, x , and mass, m . The key is the transfer of mass from high ground to low(-est) ground. The mass of an agent dictates its step size: lighter agents take larger steps. In this paper, the essential new feature is the choice of direction: rather than restricting the swarm to march in the steepest gradient descent, we let agents proceed in randomly chosen directions centered around — but otherwise different from — the gradient direction. The random search secures the descent property while at the same time, enabling greater exploration of ambient space. Convergence analysis and benchmark optimizations demonstrate the effectiveness of the swarm-based random descent method as a multi-dimensional global optimizer. [ABSTRACT FROM AUTHOR]

A polyhedron is Rupert if it is possible to cut a hole in it and thread an identical polyhedron through the hole. It is known that all 5 Platonic solids, 10 of the 13 Archimedean solids, 9 of the 13 Catalan solids, and 82 of the 92 Johnson solids are Rupert. Here, a nonlinear optimization method is devised that is able to validate the previously known results in seconds. It is also used to show that 2 additional Catalan solids—the triakis tetrahedron and the pentagonal icositetrahedron—and 5 additional Johnson solids are Rupert. [ABSTRACT FROM AUTHOR]

This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the " ℓ 0 -path" where the discontinuous ℓ 0 -function provides the exact sparsity count; the " ℓ 1 -path" where the ℓ 1 -function provides a convex surrogate of sparsity count; and the "capped ℓ 1 -path" where the nonconvex nondifferentiable capped ℓ 1 -function aims to enhance the ℓ 1 -approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new) properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped ℓ 1 -path. Our study of the capped ℓ 1 -path is interesting in its own right as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped ℓ 1 -regularized problem offers interesting theoretical properties and practical compromise between the ℓ 0 -path and the ℓ 1 -path. Indeed, while the ℓ 0 -path is computationally prohibitive and greatly handicapped by the repeated solution of mixed-integer nonlinear programs, the quality of ℓ 1 -path, in terms of the two criteria—loss and sparsity—in the estimation objective, is inferior to the capped ℓ 1 -path; the latter can be obtained efficiently by a combination of a parametric pivoting-like scheme supplemented by an algorithm that takes advantage of the Z-matrix structure of the loss function. [ABSTRACT FROM AUTHOR]

A parametric class of trust-region algorithms for unconstrained non-convex optimization is considered where the value of the objective function is never computed. The class contains a deterministic version of the first-order Adagrad method typically used for minimization of noisy function, but also allows the use of (possibly approximate) second-order information when available. The rate of convergence of methods in the class is analysed and is shown to be identical to that known for first-order optimization methods using both function and gradients values, recovering existing results for purely-first order variants and improving the explicit dependence on problem dimension. This rate is shown to be essentially sharp. A new class of methods is also presented, for which a slightly worse and essentially sharp complexity result holds. Limited numerical experiments show that the new methods' performance may be comparable to that of standard steepest descent, despite using significantly less information, and that this performance is relatively insensitive to noise. [ABSTRACT FROM AUTHOR]

Distributed optimization has many applications, in communication networks, sensor networks, signal processing, machine learning, and artificial intelligence. Methods for distributed convex optimization are widely investigated, while those for non-convex objectives are not well understood. One of the first non-convex distributed optimization frameworks over an arbitrary interaction graph was proposed by Di Lorenzo and Scutari (IEEE Trans Signal Inf Process Netw 2:120–136, 2016), which iteratively applies a combination of local optimization with convex approximations and local averaging. Motivated by application problems such as the resource allocation problems in multi-cellular networks, we generalize the existing results in two ways. In the case when the decision variables are separable such that there is partial dependency in the objectives, we reduce the communication and memory complexity of the algorithm so that nodes only keep and communicate local variables instead of the whole vector of variables. In addition, we relax the assumption that the objectives' gradients are bounded and Lipschitz by means of successive proximal approximations. The proposed algorithmic framework is shown to be more widely applicable and numerically stable. [ABSTRACT FROM AUTHOR]

The concept of adjusted sublevel set for a quasiconvex function was introduced by Aussel and Hadjisavvas who proved the local existence of a norm-to-weak ∗ upper semicontinuous base-valued submap of the normal operator associated with the adjusted sublevel set. When the space is finite-dimensional, a globally defined upper semicontinuous base-valued submap is obtained by taking the intersection of the unit sphere, which is compact, with the normal operator, which is closed. Unfortunately, this technique does not work in the infinite-dimensional case. We propose a partition of unity technique to overcome this problem in Banach spaces. An application is given to a quasiconvex quasioptimization problem through the use of a new existence result for generalized quasivariational inequalities which is based on the Schauder fixed point theorem. [ABSTRACT FROM AUTHOR]

In this paper, a new Dai–Liao (DL)-type projection algorithm is presented for large-dimension nonlinear monotone problems with signal reconstruction and image recovery applications. The inspiration behind the work comes from two of the open problems propounded by Andrei (Bull Malays Math Sci Soc 34(2):319–330, 2011) involving the optimal value for the DL nonnegative parameter and the best conjugacy condition as well as the fine attributes expressed by four-term methods for unconstrained optimization. Based on the eigenvalue study of a symmetric DL-type iteration matrix, another optimal choice of the DL parameter is obtained, which is incorporated in a five-term direction scheme. Combining this with the projection method, a new DL algorithm which converges globally is developed. To implement the algorithm, a derivative-free line search mechanism is employed. Also, by conducting some numerical experiments with the new scheme and some recent DL-type methods, the efficiency of the former in solving nonlinear monotone problems as well as the ℓ 1 - n o r m regularized problems in compressed sensing is demonstrated. [ABSTRACT FROM AUTHOR]

In this note we explore duality in reverse convex optimization with reverse convex inequality constraints. While we are examining the special case of a finite index set of inequality constraints, we are primarily interested in the general case of an arbitrary infinite index set with neither extra topological structure nor extra measure structure. [ABSTRACT FROM AUTHOR]

Algorithms for solving certain nonconvex, nonsmooth, finite-sum optimization problems are proposed and tested. In particular, the algorithms are proposed and tested in the context of a transductive support vector machine (TSVM) problem formulation arising in semi-supervised machine learning. The common feature of all algorithms is that they employ an incremental quasi-Newton (IQN) strategy, specifically an incremental BFGS (IBFGS) strategy. One applies an IBFGS strategy to the problem directly, whereas the others apply an IBFGS strategy to a difference-of-convex reformulation, smoothed approximation, or (strongly) convex local approximation. Experiments show that all IBFGS approaches fare well in practice, and all outperform a state-of-the-art bundle method when solving TSVM problem instances. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of possibly non-convex and non-smooth optimization problems arising in many contemporary applications such as machine learning, variable selection and image processing. To solve this class of problems, we propose a proximal gradient method with extrapolation and line search (PGels). This method is developed based on a special potential function and successfully incorporates both extrapolation and non-monotone line search, which are two simple and efficient acceleration techniques for the proximal gradient method. Thanks to the non-monotone line search, this method allows more flexibility in choosing the extrapolation parameters and updates them adaptively at each iteration if a certain criterion is not satisfied. Moreover, with proper choices of parameters, our PGels reduces to many existing algorithms. We also show that, under some mild conditions, our line search criterion is well defined and any cluster point of the sequence generated by the PGels is a stationary point of our problem. In addition, by making assumptions on the Kurdyka–Łojasiewicz exponent of the objective in our problem, we further analyze the local convergence rate of two special cases of the PGels, including the widely used non-monotone proximal gradient method as one case. Finally, we conduct some preliminary numerical experiments for solving the ℓ 1 regularized logistic regression problem and the ℓ 1 - 2 regularized least squares problem. The obtained numerical results show the promising performance of the PGels and validate the potential advantage of combining two acceleration techniques. [ABSTRACT FROM AUTHOR]

This paper presents sum-of-squares (SOS) relaxation results to a difference-of-convex-max (DC-max) optimization involving SOS-convex polynomials in the face of constraint data uncertainty and their applications to robust feature selection. The main novelty of the present work in relation to the recent research in robust convex and DC optimization is the derivation of a new form of minimally exact SOS relaxations for robust DC-max problems. This leads to the identification of broad classes of robust DC-max problems with finitely exact SOS relaxations that are numerically tractable. They allow one to find the optimal values of these classes of DC-max problems by solving a known finite number of semi-definite programs (SDPs) for certain concrete cases of commonly used uncertainty sets in robust optimization. In particular, we derive relaxation results for a class of robust fractional programs. Also, we provide a finitely exact SDP relaxation for a DC approximation problem of an NP-hard robust feature selection model which gives computable upper bounds for the global optimal value. [ABSTRACT FROM AUTHOR]

Convergence and convergence rate analyses of adaptive methods, such as Adaptive Moment Estimation (Adam) and its variants, have been widely studied for nonconvex optimization. The analyses are based on assumptions that the expected or empirical average loss function is Lipschitz smooth (i.e., its gradient is Lipschitz continuous) and the learning rates depend on the Lipschitz constant of the Lipschitz continuous gradient. Meanwhile, numerical evaluations of Adam and its variants have clarified that using small constant learning rates without depending on the Lipschitz constant and hyperparameters ( β 1 and β 2 ) close to one is advantageous for training deep neural networks. Since computing the Lipschitz constant is NP-hard, the Lipschitz smoothness condition would be unrealistic. This paper provides theoretical analyses of Adam without assuming the Lipschitz smoothness condition in order to bridge the gap between theory and practice. The main contribution is to show theoretical evidence that Adam using small learning rates and hyperparameters close to one performs well, whereas the previous theoretical results were all for hyperparameters close to zero. Our analysis also leads to the finding that Adam performs well with large batch sizes. Moreover, we show that Adam performs well when it uses diminishing learning rates and hyperparameters close to one. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the globally proper efficiency of set optimization problems. Firstly, we use the so-called certainly set less order relation to define a new kind of set order relation. Based on the new set order relation, we introduce the notion of the globally proper efficient solution of the set optimization problem. Secondly, we establish Lagrange multiplier rule of the set optimization problem. Finally, we obtain Lagrangian duality theorems and saddle point theorems. We also give some examples to illustrate our results. [ABSTRACT FROM AUTHOR]

In this paper, by using the inexact scalarization proximal methods, we solve quasiconvex multiobjective optimization problems on Hadamard manifolds. Under some assumptions on the multifunction of problem and vector fields, our methods are proved to be convergent to a Pareto critical point of the problem. For the convex case, the sequences generated by the methods converge to a weak Pareto solution. [ABSTRACT FROM AUTHOR]

We focus on deterministic global optimization (DGO) for nonconvex parameter estimation problems. Realistic and accurate solutions often require a fitting against very large measurement data sets, resulting in intractable size for DGO. Thus, we aim at accelerating the branch-and-bound algorithm by using reduced data sets for constructing valid bounds. We focus on fitting the equation of state for propane, which is of high interest for the chemical industry. The resulting estimation problem is a challenging nonconvex mixed-integer nonlinear optimization problem. We investigate the validity of using reduced data sets by comparing how the lower and upper bounds change when replacing the full data set with different reduced data sets. We account for regions with high and low quality fits by considering the results for the whole feasible region and 100 different subregions. Our results indicate that both regions containing solution candidates and regions containing only low quality fits can be identified based on reduced data sets. Moreover, we observe that the average CPU time per branch-and-bound iteration typically decreases if reduced data sets are used. [ABSTRACT FROM AUTHOR]

In this paper, some concepts related to the intrinsic convexity of non-homogeneous quadratic functions on the hyperbolic space are studied. Unlike in the Euclidean space, the study of intrinsic convexity of non-homogeneous quadratic functions in the hyperbolic space is more elaborate than that of homogeneous quadratic functions. Several characterizations that allow the construction of many examples will be presented. [ABSTRACT FROM AUTHOR]

This paper addresses a linear programming problem with interval right-hand sides, forming a family of linear programs associated with each realization of the interval data. The paper focuses on the outcome range problem, which seeks the range of an additional function—termed the outcome function—over all possible optimal solutions of such linear programs. We explore the problem's applicability in diverse contexts, discuss its connections to certain existing problems, and analyze its computational complexity and theoretical foundations. Given the inherent computational challenges, we propose three heuristics to solve the problem. The first heuristic employs a reformulation–linearization technique (RLT) to obtain an outer approximation of the range of the outcome function. We also present two algorithms—a gradient-restoration-based approach (GI) and a bases inspection method (BI)—for computing an inner approximation of the range. Computational experiments illustrate the competitive advantage of our proposed approaches versus off-the-shelf solvers. The GI and BI methods present promising results in finding a cheap but tight inner approximation, while the performance of the RLT technique decreases as problem size and uncertainty increase. [ABSTRACT FROM AUTHOR]

Motivated by a recent framework for proving global convergence to critical points of nested alternating minimization algorithms, which was proposed for the case of smooth subproblems, we first show here that non-smooth subproblems can also be handled within this framework. Specifically, we present a novel analysis of an optimization scheme that utilizes the FISTA method as a nested algorithm. We establish the global convergence of this nested scheme to critical points of non-convex and non-smooth optimization problems. In addition, we propose a hybrid framework that allows to implement FISTA when applicable, while still maintaining the global convergence result. The power of nested algorithms using FISTA in the non-convex and non-smooth setting is illustrated with some numerical experiments that show their superiority over existing methods. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of structured nonconvex nonsmooth optimization problems, in which the objective function is formed by the sum of a possibly nonsmooth nonconvex function and a differentiable function with Lipschitz continuous gradient, subtracted by a weakly convex function. This general framework allows us to tackle problems involving nonconvex loss functions and problems with specific nonconvex constraints, and it has many applications such as signal recovery, compressed sensing, and optimal power flow distribution. We develop a proximal subgradient algorithm with extrapolation for solving these problems with guaranteed subsequential convergence to a stationary point. The convergence of the whole sequence generated by our algorithm is also established under the widely used Kurdyka–Łojasiewicz property. To illustrate the promising numerical performance of the proposed algorithm, we conduct numerical experiments on two important nonconvex models. These include a compressed sensing problem with a nonconvex regularization and an optimal power flow problem with distributed energy resources. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of generalized ϵ -stationarity for a class of nonconvex and nonsmooth composite minimization problems on compact Riemannian submanifold embedded in Euclidean space. To find a generalized ϵ -stationarity point, we develop a family of Riemannian gradient-type methods based on the Moreau envelope technique with a decreasing sequence of smoothing parameters, namely Riemannian smoothing gradient and Riemannian smoothing stochastic gradient methods. We prove that the Riemannian smoothing gradient method has the iteration complexity of O (ϵ - 3) for driving a generalized ϵ -stationary point. To our knowledge, this is the best-known iteration complexity result for the nonconvex and nonsmooth composite problem on manifolds. For the Riemannian smoothing stochastic gradient method, one can achieve the iteration complexity of O (ϵ - 5) for driving a generalized ϵ -stationary point. Numerical experiments are conducted to validate the superiority of our algorithms. [ABSTRACT FROM AUTHOR]

Necessary and sufficient conditions for multiobjective problems with both equality constraints and inequality constraints are presented. These conditions are applied when the constraints of the problem do not necessarily satisfy any regularity assumptions and they are based on the concept of p-regularity, introduced by Tret'yakov (1983, Necessary conditions for optimality of pth order. Control Optim.;28–35). We introduce the notion of generalized Mangasarian-Fromovitz constraint qualification. This new concept is used to obtain our results. [ABSTRACT FROM AUTHOR]

In this paper, we propose a sparse equity portfolio optimization model that aims at minimizing transaction cost by avoiding small investments while promoting diversification to help mitigate the volatility in the portfolio. The former is achieved by including the ℓ 0 -norm regularization of the asset weights to promote sparsity. Subjected to a minimum expected return, the proposed model turns out to be an objective function consisting of discontinuous and nonconvex terms. The complexity of the model calls for proximal method, which allows us to handle the objective terms separately via the corresponding proximal operators. We develop an efficient algorithm to find the optimal portfolio and prove its global convergence. The efficiency of the algorithm is demonstrated using real stock data and the model is promising in portfolio selection in terms of generating higher expected return while maintaining good level of sparsity, and thus minimizing transaction cost. [ABSTRACT FROM AUTHOR]

We show that KKT-type conditions are necessary and sufficient for global optimality for some quadratically constrained (possibly nonconvex) quadratic programming QCQP problems in Hilbert space. The key property is the convexity of an image-type set, called generalized image set, related to the functions appearing in the formulation of the problem. The proof of the main result relies on a generalized version of the (Jakubovich) S-Lemma in Hilbert spaces. As an application, we consider the class of QCQP problems with a special form of the quadratic terms of the constraints. [ABSTRACT FROM AUTHOR]

The generalized trace ratio problem (GTRP) is to maximize the quotient t r (G V T B V) / t r (G V T A V) over the Stiefel manifold. We establish the first-order necessary and sufficient optimality conditions for the global maximizer. Based on the classical second-order necessary optimality condition, we prove that GTRP has no local non-global maximizer. Finally we reveal the hidden convexity property of GTRP by applying the convex hull representation of the orthogonal similarity set. [ABSTRACT FROM AUTHOR]

We apply an approach based on parametric mean-payoff games to develop bisection and Newton schemes for solving problems of tropical pseudolinear and pseudoquadratic optimization with general two-sided constraints. [ABSTRACT FROM AUTHOR]

We propose in this paper New Q-Newton's method. The update rule is conceptually very simple, using the projections to the vector subspaces generated by eigenvectors of positive (correspondingly negative) eigenvalues of the Hessian. The main result of this paper roughly says that if a sequence { x n } constructed by the method from a random initial point x 0 converges, then the limit point is a critical point and not a saddle point, and the convergence rate is the same as that of Newton's method. A subsequent work has recently been successful incorporating Backtracking line search to New Q-Newton's method, thus resolving the global convergence issue observed for some (non-smooth) functions. An application to quickly find zeros of a univariate meromorphic function is discussed, accompanied with an illustration on basins of attraction. [ABSTRACT FROM AUTHOR]

This paper revisits the classical Linear Quadratic Gaussian (LQG) control from a modern optimization perspective. We analyze two aspects of the optimization landscape of the LQG problem: (1) Connectivity of the set of stabilizing controllers C n ; and (2) Structure of stationary points. It is known that similarity transformations do not change the input-output behavior of a dynamic controller or LQG cost. This inherent symmetry by similarity transformations makes the landscape of LQG very rich. We show that (1) The set of stabilizing controllers C n has at most two path-connected components and they are diffeomorphic under a mapping defined by a similarity transformation; (2) There might exist many strictly suboptimal stationary points of the LQG cost function over C n that are not controllable and not observable; (3) All controllable and observable stationary points are globally optimal and they are identical up to a similarity transformation. These results shed some light on the performance analysis of direct policy gradient methods for solving the LQG problem. [ABSTRACT FROM AUTHOR]

We study nonlinear optimization problems with a stochastic objective and deterministic equality and inequality constraints, which emerge in numerous applications including finance, manufacturing, power systems and, recently, deep neural networks. We propose an active-set stochastic sequential quadratic programming (StoSQP) algorithm that utilizes a differentiable exact augmented Lagrangian as the merit function. The algorithm adaptively selects the penalty parameters of the augmented Lagrangian, and performs a stochastic line search to decide the stepsize. The global convergence is established: for any initialization, the KKT residuals converge to zero almost surely. Our algorithm and analysis further develop the prior work of Na et al. (Math Program, 2022. https://doi.org/10.1007/s10107-022-01846-z). Specifically, we allow nonlinear inequality constraints without requiring the strict complementary condition; refine some of designs in Na et al. (2022) such as the feasibility error condition and the monotonically increasing sample size; strengthen the global convergence guarantee; and improve the sample complexity on the objective Hessian. We demonstrate the performance of the designed algorithm on a subset of nonlinear problems collected in CUTEst test set and on constrained logistic regression problems. [ABSTRACT FROM AUTHOR]

A key question in many low-rank problems throughout optimization, machine learning, and statistics is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet computationally tractable relaxations. We invoke the matrix perspective function—the matrix analog of the perspective function—to characterize explicitly the convex hull of epigraphs of simple matrix convex functions under low-rank constraints. Further, we combine the matrix perspective function with orthogonal projection matrices—the matrix analog of binary variables which capture the row-space of a matrix—to develop a matrix perspective reformulation technique that reliably obtains strong relaxations for a variety of low-rank problems, including reduced rank regression, non-negative matrix factorization, and factor analysis. Moreover, we establish that these relaxations can be modeled via semidefinite constraints and thus optimized over tractably. The proposed approach parallels and generalizes the perspective reformulation technique in mixed-integer optimization and leads to new relaxations for a broad class of problems. [ABSTRACT FROM AUTHOR]

We consider the gradient method with variable step size for minimizing functions that are definable in o-minimal structures on the real field and differentiable with locally Lipschitz gradients. We prove that global convergence holds if continuous gradient trajectories are bounded, with the minimum gradient norm vanishing at the rate o(1/k) if the step sizes are greater than a positive constant. If additionally the gradient is continuously differentiable, all saddle points are strict, and the step sizes are constant, then convergence to a local minimum holds almost surely over any bounded set of initial points. [ABSTRACT FROM AUTHOR]

We introduce a novel gradient descent algorithm refining the well-known Gradient Sampling algorithm on the class of stratifiably smooth objective functions, which are defined as locally Lipschitz functions that are smooth on some regular pieces—called the strata—of the ambient Euclidean space. On this class of functions, our algorithm achieves a sub-linear convergence rate. We then apply our method to objective functions based on the (extended) persistent homology map computed over lower-star filters, which is a central tool of Topological Data Analysis. For this, we propose an efficient exploration of the corresponding stratification by using the Cayley graph of the permutation group. Finally, we provide benchmarks and novel topological optimization problems that demonstrate the utility and applicability of our framework. [ABSTRACT FROM AUTHOR]

In this paper, we consider solving a broad class of large-scale nonconvex and nonsmooth minimization problems by a Bregman proximal stochastic gradient (BPSG) algorithm. The objective function of the minimization problem is the composition of a differentiable and a nondifferentiable function, and the differentiable part does not admit a global Lipschitz continuous gradient. Under some suitable conditions, the subsequential convergence of the proposed algorithm is established. And under expectation conditions with the Kurdyka-Łojasiewicz (KL) property, we also prove that the proposed method converges globally. We also apply the BPSG algorithm to solve sparse nonnegative matrix factorization (NMF), symmetric NMF via non-symmetric relaxation, and matrix completion problems under different kernel generating distances, and numerically compare it with other algorithms. The results demonstrate the robustness and effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In the context of damped second order linear dynamical systems, we study the asymptotic behavior of a time discretization of a slowly damped differential equation. We prove that this discretization can be constructed by means of a variable time step that gives rise to the same asymptotic behaviour as for the system in continuous time. [ABSTRACT FROM AUTHOR]