Numerical methods for the solution of nonsmooth equations are studied. A new subdifferential for a locally Lipschitzian function is proposed. Based on this subdifferential, Newton methods for solving nonsmooth equations …
Numerical methods for the solution of nonsmooth equations are studied. A new subdifferential for a locally Lipschitzian function is proposed. Based on this subdifferential, Newton methods for solving nonsmooth equations are developed and their convergence is shown. Since this subdifferential is easy to be computed, the present Newton methods can be executed easily in some applications.
Numerical methods for the solution of nonsmooth equations are studied. A new subdifferential for a locally Lipschitzian function is proposed. Based on this subdifferential, Newton methods for solving nonsmooth equations …
Numerical methods for the solution of nonsmooth equations are studied. A new subdifferential for a locally Lipschitzian function is proposed. Based on this subdifferential, Newton methods for solving nonsmooth equations are developed and their convergence is shown. Since this subdifferential is easy to be computed, the present Newton methods can be executed easily in some applications.
We present the Trust Region Adversarial Functional Subdifferential (TRAFS) algorithm for constrained optimization of nonsmooth convex Lipschitz functions. Unlike previous methods that assume a subgradient oracle model, we work with …
We present the Trust Region Adversarial Functional Subdifferential (TRAFS) algorithm for constrained optimization of nonsmooth convex Lipschitz functions. Unlike previous methods that assume a subgradient oracle model, we work with the functional subdifferential defined as a set of subgradients that simultaneously captures sufficient local information for effective minimization while being easy to compute for a wide range of functions. In each iteration, TRAFS finds the best step vector in an $\ell_2$-bounded trust region by considering the worst bound given by the functional subdifferential. TRAFS finds an approximate solution with an absolute error up to $\epsilon$ in $\mathcal{O}\left( \epsilon^{-1}\right)$ or $\mathcal{O}\left(\epsilon^{-0.5} \right)$ iterations depending on whether the objective function is strongly convex, compared to the previously best-known bounds of $\mathcal{O}\left(\epsilon^{-2}\right)$ and $\mathcal{O}\left(\epsilon^{-1}\right)$ in these settings. TRAFS makes faster progress if the functional subdifferential satisfies a locally quadratic property; as a corollary, TRAFS achieves linear convergence (i.e., $\mathcal{O}\left(\log \epsilon^{-1}\right)$) for strongly convex smooth functions. In the numerical experiments, TRAFS is on average 39.1x faster and solves twice as many problems compared to the second-best method.
In this article,we present a new modification method to solve non-linear equations. By the composition of Newton's method and Heron mean,we have compared this modified method with some other iterative …
In this article,we present a new modification method to solve non-linear equations. By the composition of Newton's method and Heron mean,we have compared this modified method with some other iterative methods,which shows that this new iterative method is robust and efficient.Numerical results show that the method has practical utility.
It is our purpose here to investigate the method of solving equations for real roots by Newton's Method and to indicate a generalization arising from this method.
It is our purpose here to investigate the method of solving equations for real roots by Newton's Method and to indicate a generalization arising from this method.
The paper presents concrete realizations of quasi-Newton methods for solving several standard problems including complementarity problems, special variational inequality problems, and the Karush--Kuhn--Tucker (KKT) system of nonlinear programming. A new …
The paper presents concrete realizations of quasi-Newton methods for solving several standard problems including complementarity problems, special variational inequality problems, and the Karush--Kuhn--Tucker (KKT) system of nonlinear programming. A new approximation idea is introduced in this paper. The Q-superlinear convergence of the Newton method and the quasi-Newton method are established under suitable assumptions, in which the existence of F'(x*) is not assumed. The new algorithms only need to solve a linear equation in each step. For complementarity problems, the QR factorization on the quasi-Newton method is discussed.
We consider a class of difference-of-convex (DC) optimization problems where the objective function is the sum of a smooth function and a possible nonsmooth DC function. The application of proximal …
We consider a class of difference-of-convex (DC) optimization problems where the objective function is the sum of a smooth function and a possible nonsmooth DC function. The application of proximal DC algorithms to address this problem class is well-known. In this paper, we combine a proximal DC algorithm with an inexact proximal Newton-type method to propose an inexact proximal DC Newton-type method. We demonstrate global convergence properties of the proposed method. In addition, we give a memoryless quasi-Newton matrix for scaled proximal mappings and consider a two-dimensional system of semi-smooth equations that arise in calculating scaled proximal mappings. To efficiently obtain the scaled proximal mappings, we adopt a semi-smooth Newton method to inexactly solve the system. Finally, we present some numerical experiments to investigate the efficiency of the proposed method, showing that the proposed method outperforms existing methods.
We focus on solving the clustered Lasso problem, which is a least squares problem with the $\ell_1$-type penalties imposed on both the coefficients and their pairwise differences to learn the …
We focus on solving the clustered Lasso problem, which is a least squares problem with the $\ell_1$-type penalties imposed on both the coefficients and their pairwise differences to learn the group structure of the regression parameters. Here we first reformulate the clustered Lasso regularizer as a weighted ordered-Lasso regularizer, which is essential in reducing the computational cost from $O(n^2)$ to $O(n\log (n))$. We then propose an inexact semismooth Newton augmented Lagrangian (Ssnal) algorithm to solve the clustered Lasso problem or its dual via this equivalent formulation, depending on whether the sample size is larger than the dimension of the features. An essential component of the Ssnal algorithm is the computation of the generalized Jacobian of the proximal mapping of the clustered Lasso regularizer. Based on the new formulation, we derive an efficient procedure for its computation. Comprehensive results on the global convergence and local linear convergence of the Ssnal algorithm are established. For the purpose of exposition and comparison, we also summarize/design several first-order methods that can be used to solve the problem under consideration, but with the key improvement from the new formulation of the clustered Lasso regularizer. As a demonstration of the applicability of our algorithms, numerical experiments on the clustered Lasso problem are performed. The experiments show that the Ssnal algorithm substantially outperforms the best alternative algorithm for the clustered Lasso problem.
The smoothly clipped absolute deviation (SCAD) and the minimax concave penalty (MCP)-penalized regression models are two important and widely used nonconvex sparse learning tools that can handle variable selection and …
The smoothly clipped absolute deviation (SCAD) and the minimax concave penalty (MCP)-penalized regression models are two important and widely used nonconvex sparse learning tools that can handle variable selection and parameter estimation simultaneously and thus have potential applications in various fields, such as mining biological data in high-throughput biomedical studies. Theoretically, these two models enjoy the oracle property even in the high-dimensional settings, where the number of predictors p may be much larger than the number of observations n . However, numerically, it is quite challenging to develop fast and stable algorithms due to their nonconvexity and nonsmoothness. In this article, we develop a fast algorithm for SCAD- and MCP-penalized learning problems. First, we show that the global minimizers of both models are roots of the nonsmooth equations. Then, a semismooth Newton (SSN) algorithm is employed to solve the equations. We prove that the SSN algorithm converges locally and superlinearly to the Karush-Kuhn-Tucker (KKT) points. The computational complexity analysis shows that the cost of the SSN algorithm per iteration is O(np) . Combined with the warm-start technique, the SSN algorithm can be very efficient and accurate. Simulation studies and a real data example suggest that our SSN algorithm, with comparable solution accuracy with the coordinate descent (CD) and the difference of convex (DC) proximal Newton algorithms, is more computationally efficient.
For solving nonsmooth systems of equations, the Levenberg‐Marquardt method and its variants are of particular importance because of their locally fast convergent rates. Finitely many maximum functions systems are very …
For solving nonsmooth systems of equations, the Levenberg‐Marquardt method and its variants are of particular importance because of their locally fast convergent rates. Finitely many maximum functions systems are very useful in the study of nonlinear complementarity problems, variational inequality problems, Karush‐Kuhn‐Tucker systems of nonlinear programming problems, and many problems in mechanics and engineering. In this paper, we present a modified Levenberg‐Marquardt method for nonsmooth equations with finitely many maximum functions. Under mild assumptions, the present method is shown to be convergent Q‐linearly. Some numerical results comparing the proposed method with classical reformulations indicate that the modified Levenberg‐Marquardt algorithm works quite well in practice.
Based on the smoothing function of penalized Fischer‐Burmeister NCP‐function, we propose a new smoothing inexact Newton algorithm with non‐monotone line search for solving the generalized nonlinear complementarity problem. We view …
Based on the smoothing function of penalized Fischer‐Burmeister NCP‐function, we propose a new smoothing inexact Newton algorithm with non‐monotone line search for solving the generalized nonlinear complementarity problem. We view the smoothing parameter as an independent variable. Under suitable conditions, we show that any accumulation point of the generated sequence is a solution of the generalized nonlinear complementarity problem. We also establish the local superlinear (quadratic) convergence of the proposed algorithm under the BD‐regular assumption. Preliminary numerical experiments indicate the feasibility and efficiency of the proposed algorithm.
The eigenvalue problem over a polyhedral cone is studied in this paper. Based on the F‐B NCP function, we reformulate this problem as a system of equations and propose a …
The eigenvalue problem over a polyhedral cone is studied in this paper. Based on the F‐B NCP function, we reformulate this problem as a system of equations and propose a Jacobian‐like method. The global convergence and local quadratic convergence of the proposed method are established under suitable assumptions. Preliminary numerical experiments for a special polyhedral cone are reported in this paper to show the validity of the proposed method.
Screening and working set techniques are important approaches to reducing the size of an optimization problem. They have been widely used in accelerating first-order methods for solving large-scale sparse learning …
Screening and working set techniques are important approaches to reducing the size of an optimization problem. They have been widely used in accelerating first-order methods for solving large-scale sparse learning problems. In this paper, we develop a new screening method called Newton screening (NS) which is a generalized Newton method with a built-in screening mechanism. We derive an equivalent KKT system for the Lasso and utilize a generalized Newton method to solve the KKT equations. Based on this KKT system, a built-in working set with a relatively small size is first determined using the sum of primal and dual variables generated from the previous iteration, then the primal variable is updated by solving a least-squares problem on the working set and the dual variable updated based on a closed-form expression. Moreover, we consider a sequential version of Newton screening (SNS) with a warm-start strategy. We show that NS possesses an optimal convergence property in the sense that it achieves one-step local convergence. Under certain regularity conditions on the feature matrix, we show that SNS hits a solution with the same signs as the underlying true target and achieves a sharp estimation error bound with high probability. Simulation studies and real data analysis support our theoretical results and demonstrate that SNS is faster and more accurate than several state-of-the-art methods in our comparative studies.
A method for evaluating lexicographical directional (LD)-derivatives of functional programs is presented, extending previous methods to programs containing conditional branches and loops. A language for imperative programs is given, and …
A method for evaluating lexicographical directional (LD)-derivatives of functional programs is presented, extending previous methods to programs containing conditional branches and loops. A language for imperative programs is given, and conditions under which LD-derivatives can be calculated automatically for conditional branches and loops are described, along with a full description of the source transformation procedures necessary.
We present a unified framework for the design and convergence analysis of a class of algorithms based on approximate solution of proximal point subproblems. Our development further enhances the constructive …
We present a unified framework for the design and convergence analysis of a class of algorithms based on approximate solution of proximal point subproblems. Our development further enhances the constructive approximation approach of the recently proposed hybrid projection–proximal and extragradient–proximal methods. Specifically, we introduce an even more flexible error tolerance criterion, as well as provide a unified view of these two algorithms. Our general method possesses global convergence and local (super)linear rate of convergence under standard assumptions, while using a constructive approximation criterion suitable for a number of specific implementations. For example, we show that close to a regular solution of a monotone system of semismooth equations, two Newton iterations are sufficient to solve the proximal subproblem within the required error tolerance. Such systems of equations arise naturally when reformulating the nonlinear complementarity problem.
A smoothing Newton method based on the CHKS smoothing function fora class of non-monotone symmetric cone linear complementarity problem (SCLCP) with the Cartesian $P$-propertyand a regularization smoothing Newton method for …
A smoothing Newton method based on the CHKS smoothing function fora class of non-monotone symmetric cone linear complementarity problem (SCLCP) with the Cartesian $P$-propertyand a regularization smoothing Newton method for SCLCP with the Cartesian $P_0$-property are proposed.The existence of Newton directions and the boundedness of iterates, two important theoretical issues encountered in the smoothing method, are showed for these two classes of non-monotone SCLCP. Finally, we show that these two algorithms are globally convergent. Moreover, they are globally linear and locally quadratic convergent under a nonsingular assumption.
The K-means algorithm, widely used in cluster analysis, is a centroid-based clustering method known for its high efficiency and scalability. However, in realistic situations, the operating environment is susceptible to …
The K-means algorithm, widely used in cluster analysis, is a centroid-based clustering method known for its high efficiency and scalability. However, in realistic situations, the operating environment is susceptible to contamination issues caused by outliers and distribution departures, which may lead to clustering results from K-means that are distorted or rendered invalid. In this paper, we introduce three other alternative algorithms, including K-weighted-medians, K-weighted-L <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> -medians, and K-weighted-HLs, to address these issues under the consideration of data with weights. The impact of contamination is investigated by examining the estimation effects on optimal cluster centroids. We explore the robustness of the clustering algorithms from the perspective of the breakdown point, and then conduct experiments on simulated and real datasets to evaluate their performance using new numerical metrics. The results demonstrate the effectiveness of the proposed K-weighted-HLs algorithm, surpassing other algorithms in scenarios involving both contamination issues.
In this paper, we present a new approach for finding a stablesolution of a system of nonlinear equations arising from dynamicalsystems. We introduce the concept ofstability functions and use this …
In this paper, we present a new approach for finding a stablesolution of a system of nonlinear equations arising from dynamicalsystems. We introduce the concept ofstability functions and use this idea to constructstability solution models of severaltypical small signal stability problems in dynamical systems.Each model consists of a system of constrainedsemismooth equations. The advantage of the new models is twofold.Firstly, the stability requirement of dynamical systems iscontrolled by nonlinear inequalities. Secondly, the semismoothnessproperty of the stability functions makes the models solvable byefficient numerical methods. We introduce smoothing functions forthe stability functions and present a smoothing Newton methodfor solving the problems. Global and local quadratic convergence ofthe algorithm is established. Numerical examples from dynamicalsystems are also given to illustrate the efficiency of the newapproach.
This paper introduces a novel technique for nonlinear acceleration of first-order methods for constrained convex optimization. Previous studies of nonlinear acceleration have only been able to provide convergence guarantees for …
This paper introduces a novel technique for nonlinear acceleration of first-order methods for constrained convex optimization. Previous studies of nonlinear acceleration have only been able to provide convergence guarantees for unconstrained convex optimization. In contrast, our method is able to avoid infeasibility of the accelerated iterates and retains the theoretical performance guarantees of the unconstrained case. We focus on Anderson acceleration of the classical projected gradient descent (PGD) method, but our techniques can easily be extended to more sophisticated algorithms, such as mirror descent. Due to the presence of a constraint set, the relevant fixed-point mapping for PGD is not differentiable. However, we show that the convergence results for Anderson acceleration of smooth fixed-point iterations can be extended to the non-smooth case under certain technical conditions.
The discrete optimal transport (OT) problem, which offers an effective computational tool for comparing two discrete probability distributions, has recently attracted much attention and played essential roles in many modern …
The discrete optimal transport (OT) problem, which offers an effective computational tool for comparing two discrete probability distributions, has recently attracted much attention and played essential roles in many modern applications. This paper proposes to solve the discrete OT problem by applying a squared smoothing Newton method via the Huber smoothing function for solving the corresponding KKT system directly. The proposed algorithm admits appealing convergence properties and is able to take advantage of the solution sparsity to greatly reduce computational costs. Moreover, the algorithm can be extended to solve problems with similar structures, including the Wasserstein barycenter (WB) problem with fixed supports. To verify the practical performance of the proposed method, we conduct extensive numerical experiments to solve a large set of discrete OT and WB benchmark problems. Our numerical results show that the proposed method is efficient compared to state-of-the-art linear programming (LP) solvers. Moreover, the proposed method consumes less memory than existing LP solvers, which demonstrates the potential usage of our algorithm for solving large-scale OT and WB problems.
The nonlinear complementarity problem has been converted into a system of nonsmooth equations by means of Fischer-Burmeister functional, which may be called the Fischer-Burmeister equation. The local superlinear convergence of …
The nonlinear complementarity problem has been converted into a system of nonsmooth equations by means of Fischer-Burmeister functional, which may be called the Fischer-Burmeister equation. The local superlinear convergence of the generalized Newton method applied to the Fischer-Burmeister equation has been established under certain regularity assumptions. In contrast to the damped Newton method for systems of smooth equations, global convergence of the damped generalized Newton method for systems of nonsmooth equations cannot be proved in general. In this paper, we show that the natural globalization of the Newton method for smooth equations can be extended to the Fischer-Burmeister equation without any hybrid strategy. Moreover, we are also able to demonstrate that the damped modified Gauss-Newton method can be extended to the Fischer-Burmeister equation. This shows that the elegant convergence analysis of the traditional Newton, damped Newton and damped Gauss-Newton methods can be naturally generalized to the Fischer-Burmeister equation.
Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 6 April 2020Accepted: 16 February 2021Published online: 04 May 2021Keywordsnonsmooth optimization, generalized Newton …
Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 6 April 2020Accepted: 16 February 2021Published online: 04 May 2021Keywordsnonsmooth optimization, generalized Newton method, tilt-stable local minimizers, prox-regular functions, superlinear convergenceAMS Subject Headings90C31, 49J52, 49J53Publication DataISSN (print): 1052-6234ISSN (online): 1095-7189Publisher: Society for Industrial and Applied MathematicsCODEN: sjope8
This paper proposes and develops a new Newton-type algorithm to solve subdifferential inclusions defined by subgradients of extended real-valued prox-regular functions. The proposed algorithm is formulated in terms of the …
This paper proposes and develops a new Newton-type algorithm to solve subdifferential inclusions defined by subgradients of extended real-valued prox-regular functions. The proposed algorithm is formulated in terms of the second order subdifferential of such functions that enjoy extensive calculus rules and can be efficiently computed for broad classes of extended real-valued functions. Based on this and on the metric regularity and subregularity properties of subgradient mappings, we establish verifiable conditions ensuring the well-posedness of the proposed algorithm and its local superlinear convergence. The obtained results are also new for the class of equations defined by continuously differentiable functions with Lipschitzian gradients ([Formula: see text] functions), which is the underlying case of our consideration. The developed algorithms for prox-regular functions and their extension to a structured class of composite functions are formulated in terms of proximal mappings and forward–backward envelopes. Besides numerous illustrative examples and comparison with known algorithms for [Formula: see text] functions and generalized equations, the paper presents applications of the proposed algorithms to regularized least square problems arising in statistics, machine learning, and related disciplines. Funding: Research of P. D. Khanh is funded by Ho Chi Minh City University of Education Foundation for Science and Technology [Grant CS.2022.19.20TD]. Research of B. Mordukhovich and V. T. Phat was partly supported by the U.S. National Science Foundation [Grants DMS-1808978 and DMS-2204519]. The research of B. Mordukhovich was also supported by the Air Force Office of Scientific Research [Grant 15RT0462] and the Australian Research Council under Discovery Project DP-190100555. This work was supported by the Air Force Office of Scientific Research [Grant 15RT0462].
1. Introduction and Preview 2. Generalized Gradients 3. Differential Inclusions 4. The Calculus of Variations 5. Optimal Control 6. Mathematical Programming 7. Topics in Analysis.
1. Introduction and Preview 2. Generalized Gradients 3. Differential Inclusions 4. The Calculus of Variations 5. Optimal Control 6. Mathematical Programming 7. Topics in Analysis.
Clarke has given a robust definition of subgradients of arbitrary Lipschitz continuous functions f on R^n, but for purposes of minimization algorithms it seems essential that the subgradient multifunction partial …
Clarke has given a robust definition of subgradients of arbitrary Lipschitz continuous functions f on R^n, but for purposes of minimization algorithms it seems essential that the subgradient multifunction partial f have additional properties, such as certain special kinds of semicontinuity, which are not automatic consequences of f being Lipschitz continuous. This paper explores properties of partial f that correspond to f being subdifferentially regular, another concept of Clarke's, and to f being a pointwise supremum of functions that are k times continuously differentiable.
We present an implementable algorithm for solving constrained optmization problems defined by functions that are not everywhere differenliable. The method is based on combining, modifying and extending the nonsmooth optimization …
We present an implementable algorithm for solving constrained optmization problems defined by functions that are not everywhere differenliable. The method is based on combining, modifying and extending the nonsmooth optimization work of Wolfe, Leraarechal, Feuer, Poljak and Merrill. It can be thought of as a generalized reset conjugate gradient algorithm. We also introduce the class of weakly upper semismooth functions. These functions are locally Lipschitz and have a semicontinuous relationship between their generalized gradient sets and their directional derivatives. The algorithm is shown to converge to stationary points of the optimization problem if the objective and constraint functions are weakly upper semismooth. Such points are optimal points if the problem functions are also semiconvex and a constraint qualification is satisfied. Under stronger convexity assumptions, bounds on the deviation from optimally of the algorithm iterates are given.
Two fundamental classes of problems in large-scale linear and quadratic programming are described. Multistage problems covering a wide variety of models in dynamic programming and stochastic programming are represented in …
Two fundamental classes of problems in large-scale linear and quadratic programming are described. Multistage problems covering a wide variety of models in dynamic programming and stochastic programming are represented in a new way. Strong properties of duality are revealed which support the development of iterative approximate techniques of solution in terms of saddlepoints. Optimality conditions are derived in a form that emphasizes the possibilities of decomposition.
First- and second-order conditions are given which must necessarily be satisfied by local minimizers for certain finite-dimensional nonsmooth nonlinear programming problems. The problems considered are of standard form, having a …
First- and second-order conditions are given which must necessarily be satisfied by local minimizers for certain finite-dimensional nonsmooth nonlinear programming problems. The problems considered are of standard form, having a finite number of equality and inequality constraints. The principal result does not require a constraint qualification, but does require that the functions be semismooth at the minimizer. The necessary conditions are stated in terms of the generalized gradients of nonsmooth analysis and certain second-order directional derivatives.
The class of "lowwer-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C Superscript 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>C</mml:mi> <mml:mn>1</mml:mn> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{C^1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>" functions, that is functions which arise …
The class of "lowwer-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C Superscript 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>C</mml:mi> <mml:mn>1</mml:mn> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{C^1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>" functions, that is functions which arise by taking the maximum of a compactly indexed family of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C Superscript 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>C</mml:mi> <mml:mn>1</mml:mn> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{C^1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> functions, is characterized in terms of properties of the generalized subdifferential. A locally Lipschitz function is shown to be lower-<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C Superscript 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>C</mml:mi> <mml:mn>1</mml:mn> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{C^1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> if and only if its subdifferential is "strictly submonotone". Other properties of functions with "submonotone" subdifferentials are investigated.
We introduce semismooth and semiconvex functions and discuss their properties with respect to nonsmooth nonconvex constrained optimization problems. These functions are locally Lipschitz, and hence have generalized gradients. The author …
We introduce semismooth and semiconvex functions and discuss their properties with respect to nonsmooth nonconvex constrained optimization problems. These functions are locally Lipschitz, and hence have generalized gradients. The author has given an optimization algorithm that uses generalized gradients of the problem functions and converges to stationary points if the functions are semismooth. If the functions are semiconvex and a constraint qualification is satisfied, then we show that a stationary point is an optimal point. We show that the pointwise maximum or minimum over a compact family of continuously differentiable functions is a semismooth function and that the pointwise maximum over a compact family of semiconvex functions is a semiconvex function. Furthermore, we show that a semismooth composition of semismooth functions is semismooth and give a type of chain rule for generalized gradients.
Preface to the Classics Edition Preface Acknowledgments Glossary of Symbols Introduction Part I. Background Material. 1. Sample Problems 2. Linear Algebra 3. Analysis Part II. Nonconstructive Existence Theorems. 4. Gradient …
Preface to the Classics Edition Preface Acknowledgments Glossary of Symbols Introduction Part I. Background Material. 1. Sample Problems 2. Linear Algebra 3. Analysis Part II. Nonconstructive Existence Theorems. 4. Gradient Mappings and Minimization 5. Contractions and the Continuation Property 6. The Degree of a Mapping Part III. Iterative Methods. 7. General Iterative Methods 8. Minimization Methods Part IV. Local Convergence. 9. Rates of Convergence-General 10. One-Step Stationary Methods 11. Multistep Methods and Additional One-Step Methods Part V. Semilocal and Global Convergence. 12. Contractions and Nonlinear Majorants 13. Convergence under Partial Ordering 14. Convergence of Minimization Methods An Annotated List of Basic Reference Books Bibliography Author Index Subject Index.
The Clarke subgradients of a nonconvex function p on R n are characterized in terms of limits of “proximal subgradients.” In the case where p is the optimal value function …
The Clarke subgradients of a nonconvex function p on R n are characterized in terms of limits of “proximal subgradients.” In the case where p is the optimal value function in a nonlinear programming problem depending on parameters, proximal subgradients correspond to saddlepoints of the augmented Lagrangian. When the constraint and objective functions are sufficiently smooth, this leads to a characterization of marginal values for a given problem in terms of limits of Lagrange multipliers in “neighboring” problems for which the standard second-order sufficient conditions for optimality are satisfied at a unique point.
A generalized approach is taken to linear and quadratic programming in which dual as well as primal variables may be subjected to bounds, and constraints may be represented through penalties. …
A generalized approach is taken to linear and quadratic programming in which dual as well as primal variables may be subjected to bounds, and constraints may be represented through penalties. Corresponding problem models in optimal control related to continuous-time programming are then set up and theorems on duality and the existence of solutions are derived. Optimality conditions are obtained in the form of a global saddle point property which decomposes into an instantaneous saddle point condition on the primal and dual control vectors at each time, along with an endpoint condition.
In this paper, we extend the classical Newton method for solving continuously differentiable systems of nonlinear equations to B-differentiable systems. Such B-differentiable systems of equations provide a unified framework for …
In this paper, we extend the classical Newton method for solving continuously differentiable systems of nonlinear equations to B-differentiable systems. Such B-differentiable systems of equations provide a unified framework for the nonlinear complementarity, variational inequality and nonlinear programming problems. We establish the local and quadratic convergence of the method and propose a modification for global convergence. Applications of the theory to complementarity, variational inequality and optimization will be explained. In each of these contexts, the resulting method resembles the known Newton methods derived from Robinson's generalized equation formulation, but with a computational advantage. Namely, the new method incorporates a kind of active-set strategy in defining the subproblems. Unlike the previous methods which are only locally convergent, the modified version of the new method provides a descent algorithm which is globally convergent under some mild assumptions.
A function from one normed linear space to another is said to be Bouligand differentiable (B-differentiable) at a point if it is directionally differentiable there in every direction, and if …
A function from one normed linear space to another is said to be Bouligand differentiable (B-differentiable) at a point if it is directionally differentiable there in every direction, and if the directional derivative has a certain uniformity property. This is a weakening of the classical idea of Frechet (F-) differentiability, and it is useful in dealing with optimization problems and in other situations in which F-differentiability may be too strong.
In this paper we introduce a concept of strong B-derivative, and we employ this idea to prove an implicit-function theorem for B-differentiable functions. This theorem provides the same kinds of information as does the classical implicit-function theorem, but with B-differentiability in place of F-differentiability. Therefore it is applicable to a considerably wider class of functions than is the classical theorem.
This paper extends Newton and quasi-Newton methods to systems of PC^1 equations and establishes the quadratic convergence property of the extended Newton method and the Q-superlinear convergence property of the …
This paper extends Newton and quasi-Newton methods to systems of PC^1 equations and establishes the quadratic convergence property of the extended Newton method and the Q-superlinear convergence property of the extended quasi-Newton method.