Search

We propose a comparative study of sequential optimality conditions for mathematical programs with cardinality constraints. Besides analyzing some of the classical approximate conditions for nonlinear programming, such as AKKT, CAKKT and PAKKT, we also propose an approximate weak stationarity ( AW -stationarity) concept designed to deal with this class of problems and we prove that it is a legitimate optimality condition independently of any constraint qualification. We point out that, despite the computational appeal of the sequential optimality conditions, in this work we are not concerned with algorithmic consequences. Our aim is purely to discuss theoretical aspects of such conditions for MPCaC problems. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of optimization problems, called Mathematical Programs with Cardinality Constraints (MPCaC). This kind of problem is generally difficult to deal with, because it involves a constraint that is not continuous neither convex, but provides sparse solutions. Thereby we reformulate MPCaC in a suitable way, by modeling it as mixed-integer problem and then addressing its continuous counterpart, which will be referred to as relaxed problem. We investigate the relaxed problem by analyzing the classical constraints in two cases: linear and nonlinear. In the linear case, we propose a general approach and present a discussion of the Guignard and Abadie constraint qualifications, proving in this case that every minimizer of the relaxed problem satisfies the Karush–Kuhn–Tucker (KKT) conditions. On the other hand, in the nonlinear case, we show that some standard constraint qualifications may be violated. Therefore, we cannot assert about KKT points. Motivated to find a minimizer for the MPCaC problem, we define new and weaker stationarity conditions, by proposing a unified approach. [ABSTRACT FROM AUTHOR]

A new class of methods for solving systems of nonlinear equations that can attain cubic convergence rate, named the inexact tensor-free Chebyshev-Halley class, is introduced. As its name implies, the methods belonging to this class do not require second-order derivative information (a third-order tensor of size n×n×n) and find the next iterate by approximately solving two linear systems. This new class can be seen as a generalization of the Chebyshev-Halley class. No norm reduction in the quadratic model is needed to ensure convergence as required by Steihaug and Suleiman (Appl Numer Math 67:230-242, 2013). This gives more flexibility for choosing the step than the Steihaug and Suleiman algorithm does. In addition, in the convergence analysis section, we show that, depending on reasonable assumptions, the methods of this class can have superlinear, quadratic, superquadratic, or cubic convergence rates. We presented numerical evidence that demonstrates significant improvement when utilizing the proposed inexact tensor-free methods when compared to the Steihaug and Suleiman algorithm. This new class of methods also enlarges the Inexact Newton step by an additional step. The role of this extra step is to accelerate the convergence of the Inexact Newton method, so that cubic convergence rate is achieved by the inexact tensor-free Chebyshev-Halley methods. For this reason, we also tested them numerically against Newton-GMRES and the results have shown that the extra-cost due to the computation of the further step is more than counterbalanced by the gain in convergence rate. [ABSTRACT FROM AUTHOR]

Within the context of sequential methods for solving general nonlinear programming problems, and on the grounds of a previous work of the same authors, this study deals with the theoretical reasoning behind handling the original subproblems by an augmentation strategy. We do not assume feasibility of the original problem, nor the fulfillment of any constraint qualification. The previous analysis is extended along two directions. First and foremost, the exact nature of the stationary points previously considered is alleviated under an approximate stationary perspective. Second, the current analysis has been developed using general vector norms. Therefore, despite the similarities of the obtained results with those of the prior study, the present ones have been obtained under less restrictive hypotheses, and with a more involved examination. As before, we are not concerned with the sequential method itself, nor with computational results. We focus on the features of the original problem that can be inferred from the properties of the solution of the augmented problem, with the solutions being now analyzed in an approximate sense. Examples illustrating the obtained results are included. [ABSTRACT FROM AUTHOR]

In this work, we study the primal and dual formulations of the regularized least squares problem, in special norm L2, named ridge regression. We state the Gradient method for the corresponding primal-dual problem through a fixed point approach. For this formulation, we present an original convergence analysis involving the spectral radius of a suitable iteration matrix. The main contribution of this work is to accelerate the studied method by means of a memory-like strategy. Some connections with the spectral properties of the associated iteration matrices were established to prove the convergence of the accelerated method. Preliminary experiments showed the good performance of the proposed algorithm when applied to solve ill-conditioned problems, providing better results than the conjugate gradient method for this class of problems. [ABSTRACT FROM AUTHOR]

In the context of sequential methods for solving general nonlinear programming problems, it is usual to work with augmented subproblems instead of the original ones. This paper addresses the theoretical reasoning behind handling the original subproblems by an augmentation strategy related to the differentiable reformulation of the $$\ell _1$$ -penalized problem. Nevertheless, this paper is not concerned with the sequential method itself, but with the features about the original problem that can be inferred from the properties of the solution of the augmented problem. Moreover, no assumption is made upon the feasibility of the original problem, neither about the fulfillment of any constraint qualification, nor of any regularity condition, such as calmness. The convergence analysis of the involved sequences is presented, independent of the strategy employed to produce the iterates. Examples that elucidate the interrelations among the obtained results are also provided. [ABSTRACT FROM AUTHOR]

Inexact Restoration methods have been introduced for solving nonlinear programming problems. Each iteration is composed of two phases. The first one reduces a measure of infeasibility, while in the second one the objective function value is reduced in a tangential approximation of the feasible set. The point obtained from the second phase is compared with the current point either by means of a merit function or by using a filter criterion. A comparative numerical study about these criteria by using a family of Hard-Spheres Problems is presented. [ABSTRACT FROM AUTHOR]

For solving nonsmooth convex constrained optimization problems, we propose an algorithm which combines the ideas of the proximal bundle methods with the filter strategy for evaluating candidate points. The resulting algorithm inherits some attractive features from both approaches. On the one hand, it allows effective control of the size of quadratic programming subproblems via the compression and aggregation techniques of proximal bundle methods. On the other hand, the filter criterion for accepting a candidate point as the new iterate is sometimes easier to satisfy than the usual descent condition in bundle methods. Some encouraging preliminary computational results are also reported. [ABSTRACT FROM AUTHOR]