Convex analysis and minimization algorithms II: Advanced theory and bundle methods
Convexity of real functions of several variables, generalizations (26B25) Research exposition (monographs, survey articles) pertaining to calculus of variations and optimal control (49-02) Nonsmooth analysis (49J52) Convex functions and convex programs in convex geometry (52A41) Numerical optimization and variational techniques (65K10) Convex programming (90C25)
As the second book in a two-volume series, this text retains the notation and organization of Volume I. In particular, its chapters are numbered 9- 15.Three of these deal with advanced topics in ``pure convex analysis in finite-dimensional spaces -- the Legendre-Fenchel conjugate (Chap. 10), the theory of the \(\epsilon\)-subdifferential (Chap. 11), and abstract duality in convex programming (Chap. 12). The other four build toward a selection of implementable algorithms for the numerical minimization of nondifferentiable convex functions, including bundle methods, cutting plane methods, trust region ideas, and other refinements. All of these algorithms use only the following information about the minimand \(f\): there is some ``black box (U1) which takes as input a point \(x\), and returns the number \(f(x)\) and a vector \(s(x)\) lying somewhere in the subdifferential \(\partial f(x)\). The development starts in Chapter 9, with a description of how, given a point \(x\), repeated calls to (U1) can be used to build up a convex polyhedron inside \(\partial f(x)\). Either this polyhedron eventually contains a descent direction for \(f\) based at \(x\), or else \(0\) lies in \(\partial f(x)\) and hence \(x\) gives the desired minimum. The authors describe a descent method built around this iteration, taking care to point out that it is ``bad but basic. Likewise, \(\epsilon\)-descent methods built around inner constructions of the \(\epsilon\)-subgradient (the topic of Chap. 13) turn out to be as impractical for real computing as they are essential for explaining how the useful methods set out later actually work. Chapters 14 and 15 contain several algorithms for practical nonsmooth convex programming. The highlight of Chapter 14 is a bundle method in dual form, complete with thorough discussions of direction-finding, line- search, and convergence properties. In Chapter 15, the simplest form of the cutting-plane algorithm is shown to be inadequate, and a variety of remedies is proposed. Three of these work in the primal space, and can be motivated by the basic method's inherent instability; a fourth works in the dual space, and is proposed to overcome the slow convergence of the basic steepest descent algorithm. One primal variant, ``stabilization by penalty is singled out for deeper analysis: here the cutting plane function \(\check f_ k\) underestimating the minimand \(f\) is augmented with a quadratic penalty term to produce a quadratic function whose minimum defines the next point of interest. This selection is motivated by the method's intimate relation to the procedure of Moreau-Yosida regularization, which is clearly explained; its convergence properties are analysed in detail. Throughout this work, the emphasis is on the mathematical principles underlying the effective design of convex programming algorithms. Some details concerning implementation are present, and the results of some numerical experiments appear, but there is no simple appendix listing (for example) a FORTRAN program capable of minimizing any convex function. This is not so much an oversight as an understated expression of the philosophy implicit in both volumes: numerical methods should be chosen with care and implemented with understanding. Any reader who has understood Chapters 14 and 15 (and who has access to a standard subroutine that can minimize convex quadratic functions subject to linear constraints) will be in an excellent position not only to write computer code in the language of his/her choice, but also to claim real expertise in its theoretical foundations. The bibliography is excellent; it is the same in both volumes.
- Minimizers of Dirichlet functionals on the \(n\)-torus and the weak KAM theory
- Hybrid conjugate gradient method for a convex optimization problem over the fixed-point set of a nonexpansive mapping
- Direct approach to the minimization of the maximal stress over an arch structure
- Stabilized column generation
- Maximal closure on a graph with resource constraints
- A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics.
- Constraint qualifications and stationary conditions for mathematical programming with non-differentiable vanishing constraints
- A free boundary approach to the Rosensweig instability of ferrofluids
- A note on computing the smallest conic singular value
- Epi-convergence: the Moreau envelope and generalized linear-quadratic functions
- Best practices for comparing optimization algorithms
- Lagrangian relaxation for SVM feature selection
- A note on the Morozov principle via Lagrange duality
- Sparse estimation of high-dimensional correlation matrices
- An approximate redistributed proximal bundle method with inexact data for minimizing nonsmooth nonconvex functions
- Extremality of convex sets with some applications
- A method for convex minimization based on translated first-order approximations
- On some geometric conditions for minimality of DCH-functions via DC-duality approach
- On the computational efficiency of subgradient methods: a case study with Lagrangian bounds
- A proximal bundle method for constrained nonsmooth nonconvex optimization with inexact information
- Formulae for the conjugate and the subdifferential of the supremum function
- Subdifferential calculus for set-valued mappings and optimality conditions for multiobjective optimization problems
- Proximal bundle algorithms for nonlinearly constrained convex minimax fractional programs
- A conceptual conjugate epi-projection algorithm of convex optimization: superlinear, quadratic and finite convergence
- A new multi-step iterative algorithm for approximating common fixed points of a finite family of multi-valued Bregman relatively nonexpansive mappings
- The general split equality problem for Bregman quasi-nonexpansive mappings in Banach spaces
- Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations
- Two approaches to stochastic optimal control problems with a final-time expectation constraint
- Templates for convex cone problems with applications to sparse signal recovery
- A steepest descent method for vector optimization
- Lagrangian decomposition of block-separable mixed-integer all-quadratic programs
- Necessary and sufficient conditions for (weakly) efficient of non-differentiable multi-objective semi-infinite programming problems
- An effective adaptive trust region algorithm for nonsmooth minimization
- Bounded and almost periodic solutions of convex Lagrangian systems.
- A quasi-second-order proximal bundle algorithm
- An effective nonsmooth optimization algorithm for locally Lipschitz functions
- Error bound results for convex inequality systems via conjugate duality
- Global error bounds for piecewise convex polynomials
- On -optimality conditions for multiobjective fractional optimization problems
- A new infeasible proximal bundle algorithm for nonsmooth nonconvex constrained optimization
- Noisy Euclidean distance matrix completion with a single missing node
- Inexact proximal \(\epsilon\)-subgradient methods for composite convex optimization problems
- Visualization of the \(\varepsilon \)-subdifferential of piecewise linear-quadratic functions
- A filter proximal bundle method for nonsmooth nonconvex constrained optimization
- A multistage stochastic programming approach for preventive maintenance scheduling of GENCOs with natural gas contract
- Modified inertial subgradient extragradient method in reflexive Banach spaces
- Comparison principle for Hamilton-Jacobi-Bellman equations via a bootstrapping procedure
- Management of wind power variations in electricity system investment models. A parallel computing strategy
- Qualification conditions-free characterizations of the \(\varepsilon \)-subdifferential of convex integral functions
- Linearization of McCormick relaxations and hybridization with the auxiliary variable method
- On Bayesian posterior mean estimators in imaging sciences and Hamilton-Jacobi partial differential equations
- A feasibility-ensured Lagrangian heuristic for general decomposable problems
- Differential stability properties in convex scalar and vector optimization
- Efficient proximal mapping computation for low-rank inducing norms
- A strong convergence theorem for solving an equilibrium problem and a fixed point problem using the Bregman distance
- Outer approximation for mixed-integer nonlinear robust optimization
- Revisiting augmented Lagrangian duals
- Optimality and duality in nonsmooth semi-infinite optimization, using a weak constraint qualification
- On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton-Jacobi partial differential equations
- A convergence theorem for solving generalized mixed equilibrium problems and finding fixed points of a weak Bregman relatively nonexpansive mappings in Banach spaces
- On \(n\)-polynomial \(p\)-convex functions and some related inequalities
- On Hamilton-Jacobi PDEs and image denoising models with certain nonadditive noise
- Optimal rates of estimation for multi-reference alignment
- Random moment problems under constraints
- Mathematical programming formulations for piecewise polynomial functions
- Communication-efficient distributed multi-task learning with matrix sparsity regularization
- Multivariate coherent risk measures induced by multivariate convex risk measures
- A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
- Bundle methods for sum-functions with ``easy components: applications to multicommodity network design
- Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality
- Halpern's iteration for Bregman strongly nonexpansive multi-valued mappings in reflexive Banach spaces with application
- High-order total variation regularization approach for axially symmetric object tomography from a single radiograph
- Proximal bundle methods for nonsmooth DC programming
- Smoothing algorithms for computing the projection onto a Minkowski sum of convex sets
- New global optimality conditions for nonsmooth DC optimization problems
- Iterative approximations of attractive point of a new generalized Bregman nonspreading mapping in Banach spaces
- Computation of the epsilon-subdifferential of convex piecewise linear-quadratic functions in optimal worst-case time
- Continuous outer subdifferentials in nonsmooth optimization
- Strong convergence theorems for quasi-Bregman nonexpansive mappings in reflexive Banach spaces
- Improved local convergence analysis of the Gauss-Newton method under a majorant condition
- A new nonsmooth trust region algorithm for locally Lipschitz unconstrained optimization problems
- Support vector machine polyhedral separability in semisupervised learning
- An illumination problem with tradeoff between coverage of a dataset and aperture angle of a conic light beam
- Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation
- The stable duality of DC programs for composite convex functions
- Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities
- Tuning strategy for the proximity parameter in convex minimization
- A subgradient method for multiobjective optimization
- Aubin property and uniqueness of solutions in cone constrained optimization
- Optimal production and pricing strategies in a dynamic model of monopolistic firm
- Convergence results for a common solution of a finite family of equilibrium problems and quasi-Bregman nonexpansive mappings in Banach space
- Convergence theorem for common fixed points of a finite family of multi-valued Bregman relatively nonexpansive mappings
- On the penalized maximum likelihood estimation of high-dimensional approximate factor model
- A simple version of bundle method with linear programming
- Projective method of multipliers for linearly constrained convex minimization
- On the risk of convex-constrained least squares estimators under misspecification
- Differential stability of convex optimization problems with possibly empty solution sets
- Proximal bundle methods based on approximate subgradients for solving Lagrangian duals of minimax fractional programs
- A stabilized column generation scheme for the traveling salesman subtour problem
- On parallelizing dual decomposition in stochastic integer programming
This page was built for publication: Convex analysis and minimization algorithms II: Advanced theory and bundle methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4273942)