Search

This paper develops and analyzes an accelerated proximal descent method for finding stationary points of nonconvex composite optimization problems. The objective function is of the form f + h, where h is a proper closed convex function, f is a differentiable function on the domain of h, and ∇f is Lipschitz continuous on the domain of h. The main advantage of this method is that it is "parameter-free"" in the sense that it does not require knowledge of the Lipschitz constant of ∇f or of any global topological properties of f. It is shown that the proposed method can obtain an ε-approximate stationary point with iteration complexity bounds that are optimal, up to logarithmic terms over ε, in both the convex and nonconvex settings. Some discussion is also given about how the proposed method can be leveraged in other existing optimization frameworks, such as min-max smoothing and penalty frameworks for constrained programming, to create more specialized parameter-free methods. Finally, numerical experiments are presented to support the practical viability of the method. [ABSTRACT FROM AUTHOR]

In this work, we propose an outer approximation algorithm for solving bounded convex vector optimization problems (CVOPs). The scalarization model solved iteratively within the algorithm is a modification of the norm-minimizing scalarization proposed in [Ç. Ararat, F. Ulus, and M. Umer, J. Optim. Theory Appl., 194 (2022), pp. 681--712]. For a predetermined tolerance ε > 0, we prove that the algorithm terminates after finitely many iterations, and it returns a polyhedral outer approximation to the upper image of the CVOP such that the Hausdorff distance between the two is less than ε. We show that for an arbitrary norm used in the scalarization models, the approximation error after k iterations decreases by the order of O(k1/1-q)), where q is the dimension of the objective space. An improved convergence rate of O(k2/(1-q)) is proved for the special case of using the Euclidean norm. [ABSTRACT FROM AUTHOR]

In this paper, we present a variant of the circumcenter method for the convex feasibility problem (CFP), ensuring finite convergence under a Slater assumption. The method replaces exact projections onto the convex sets with projections onto separating half-spaces, perturbed by positive exogenous parameters that decrease to zero along the iterations. If the perturbation parameters decrease slowly enough, such as the terms of a diverging series, finite convergence is achieved. To the best of our knowledge, this is the first circumcenter method for CFP that guarantees finite convergence. [ABSTRACT FROM AUTHOR]

The Frank--Wolfe method has become increasingly useful in statistical and machine learning applications due to the structure-inducing properties of the iterates and especially in settings where linear minimization over the feasible set is more computationally efficient than projection. In the setting of empirical risk minimization--one of the fundamental optimization problems in statistical and machine learning--the computational effectiveness of Frank--Wolfe methods typically grows linearly in the number of data observations n. This is in stark contrast to the case for typical stochastic projection methods. In order to reduce this dependence on n, we look to second-order smoothness of typical smooth loss functions (least squares loss and logistic loss, for example), and we propose amending the Frank--Wolfe method with Taylor series--approximated gradients, including variants for both deterministic and stochastic settings. Compared with current state-of-the-art methods in the regime where the optimality tolerance\varepsilon is sufficiently small, our methods are able to simultaneously reduce the dependence on large n while obtaining optimal convergence rates of Frank--Wolfe methods in both convex and nonconvex settings. We also propose a novel adaptive step-size approach for which we have computational guarantees. Finally, we present computational experiments which show that our methods exhibit very significant speedups over existing methods on real-world datasets for both convex and nonconvex binary classification problems. [ABSTRACT FROM AUTHOR]

We consider optimal control problems for partial differential equations where the controls take binary values but vary over the time horizon; they can thus be seen as dynamic switches. The switching patterns may be sub ject to combinatorial constraints such as, e.g., an upper bound on the total number of switchings or a lower bound on the time between two switchings. In a companion paper [C. Buchheim, A. Gruütering, and C. Meyer, SIAM J. Optim., arXiv:2203.07121, 2024], we describe the Lp -closure of the convex hull of feasible switching patterns as the intersection of convex sets derived from finite-dimensional pro jections. In this paper, the resulting outer description is used for the construction of an outer approximation algorithm in function space, whose iterates are proven to converge strongly in L² to the global minimizer of the convexified optimal control problem. The linear-quadratic subproblems arising in each iteration of the outer approximation algorithm are solved by means of a semismooth Newton method. A numerical example in two spatial dimensions illustrates the efficiency of the overall algorithm. [ABSTRACT FROM AUTHOR]

The Douglas--Rachford (DR) method is a widely used method for finding a point in the intersection of two closed convex sets (feasibility problem). However, the method converges weakly, and the associated rate of convergence is hard to analyze in general. In addition, the direct extension of the DR method for solving more-than-two-sets feasibility problems, called the -sets-DR method, is not necessarily convergent. To improve the efficiency of the optimization algorithms, the introduction of randomization and the momentum technique has attracted increasing attention. In this paper, we propose the randomized -sets-DR (RrDR) method for solving the feasibility problem derived from linear systems, showing the benefit of the randomization as it brings linear convergence in expectation to the otherwise divergent -sets-DR method. Furthermore, the convergence rate does not depend on the dimension of the coefficient matrix. We also study RrDR with heavy ball momentum and establish its accelerated rate. Numerical experiments are provided to confirm our results and demonstrate the notable improvements in accuracy and efficiency of the DR method brought by the randomization and the momentum technique. [ABSTRACT FROM AUTHOR]

Given closed convex sets Ci, i=1, ... l, and some nonzero linear maps Ai, i=1, ... l, of suitable dimensions, the multiset split feasibility problem aims at finding a point in ... based on computing projections onto Ci and multiplications by Ai and AiT. In this paper, we consider the associated best approximation problem, i.e., the problem of computing projections onto ...; we refer to this problem as the best approximation problem in multiset split feasibility settings (BA-MSF). We adapt the Dykstra's projection algorithm, which is classical for solving the BA-MSF in the special case when all Ai - I, to solve the general BA-MSF. Our Dykstra-type projection algorithm is derived by applying (proximal) coordinate gradient descent to the Lagrange dual problem, and it only requires computing projections onto Ci and multiplications by Ai and AiT in each iteration. Under a standard relative interior condition and a genericity assumption on the point we need to project, we show that the dual objective satisfies the Kurdyka-Łojasiewicz property with an explicitly computable exponent on a neighborhood of the (typically unbounded) dual solution set when each Ci is C1,α.-cone reducible for some α∈ (0,1]: this class of sets covers the class of C²-cone reducible sets, which include all polyhedrons, second-order cone, and the cone of positive semidefinite matrices as special cases. Using this, explicit convergence rate (linear or sublinear) of the sequence generated by the Dykstra-type projection algorithm is derived. Concrete examples are constructed to illustrate the necessity of some of our assumptions. [ABSTRACT FROM AUTHOR]

The separation of two sets (or more specific of two cones) plays an important role in different fields of mathematics such as variational analysis, convex analysis, convex geometry, and optimization. In the paper, we derive some new results for the separation of two not necessarily convex cones by a (convex) cone/conical surface in real (topological) linear spaces. Basically, we follow the separation approach by Kasimbeyli [SIAM J. Optim., 20 (2010), pp. 1591-1619] based on augmented dual cones and Bishop--Phelps type (normlinear) separating functions. Classical separation theorems for convex sets are the key tool for proving our main nonlinear cone separation theorems. [ABSTRACT FROM AUTHOR]

We leverage path differentiability and a recent result on nonsmooth implicit differentiation calculus to give sufficient conditions ensuring that the solution to a monotone inclusion problem will be path differentiable, with formulas for computing its generalized gradient. A direct consequence of our result is that these solutions happen to be differentiable almost everywhere. Our approach is fully compatible with automatic differentiation and comes with the following assumptions which are easy to check (roughly speaking): semialgebraicity and strong monotonicity. We illustrate the scope of our results by considering the following three fundamental composite problem settings: strongly convex problems, dual solutions to convex minimization problems, and primal-dual solutions to min-max problems. [ABSTRACT FROM AUTHOR]

Given a graph, the shortest-path problem requires finding a sequence of edges with minimum cumulative length that connects a source vertex to a target vertex. We consider a variant of this classical problem in which the position of each vertex in the graph is a continuous decision variable constrained in a convex set, and the length of an edge is a convex function of the position of its endpoints. Problems of this form arise naturally in many areas, from motion planning of autonomous vehicles to optimal control of hybrid systems. The price for such a wide applicability is the complexity of this problem, which is easily seen to be NP-hard. Our main contribution is a strong and lightweight mixed-integer convex formulation based on perspective operators, that makes it possible to efficiently find globally optimal paths in large graphs and in high-dimensional spaces. [ABSTRACT FROM AUTHOR]

We study properties of the convex hull of a set S described by quadratic inequalities. A simple way of generating inequalities valid on S is to take a nonnegative linear combinations of the defining inequalities of S. We call such inequalities aggregations. Special aggregations naturally contain the convex hull of S, and we give sufficient conditions for such aggregations to define the convex hull. We introduce the notion of hidden hyperplane convexity (HHC), which is related to the classical notion of hidden convexity of quadratic maps. We show that if the quadratic map associated with S satisfies HHC, then the convex hull of S is defined by special aggregations. To the best of our knowledge, this result generalizes all known results regarding aggregations defining convex hulls. Using this sufficient condition, we are able to recognize previously unknown classes of sets where aggregations lead to convex hull. We show that the condition known as positive definite linear combination together with hidden hyerplane convexity is a sufficient condition for finitely many aggregations to define the convex hull. All the above results are for sets defined using open quadratic inequalities. For closed quadratic inequalities, we prove a new result regarding aggregations giving the convex hull, without topological assumptions on S. [ABSTRACT FROM AUTHOR]

This corrigendum provides a variant of the Brondsted-Rockafellar theorem, which helps to correct an error in the proof of the sufficiency part of Theorem 2.8 in [X. Y. Zheng, SIAM J. Optim., 33 (2023), pp. 338-359] and to establish the correct characterization for a closed convex set to be Cp-differentiable. In particular, in the original paper, Theorem 2.8 holds with εp 1+p replacing εp2, and Theorem 3.2 holds with "1+pp-order-well-posed solvable" replacing"2 p -order-well-posed solvable." All other results remain true. [ABSTRACT FROM AUTHOR]

In this paper we consider large-scale composite optimization problems having the objective function formed as a sum of two terms (possibly nonconvex); one has a (block) coordinatewise Lipschitz continuous gradient and the other is differentiable but nonseparable. Under these general settings we derive and analyze two new coordinate descent methods. The first algorithm, referred to as the coordinate proximal gradient method, considers the composite form of the objective function, while the other algorithm disregards the composite form of the objective and uses the partial gradient of the full objective, yielding a coordinate gradient descent scheme with novel adaptive stepsize rules. We prove that these new stepsize rules make the coordinate gradient scheme a descent method, provided that additional assumptions hold for the second term in the objective function. We present a complete worst-case complexity analysis for these two new methods in both convex and nonconvex settings, provided that the (block) coordinates are chosen random or cyclic. Preliminary numerical results also confirm the efficiency of our two algorithms for practical problems. [ABSTRACT FROM AUTHOR]

This note is concerned with a class of nonmonotone descent methods for minimizing a proper lower semicontinuous Kurdyka-Łojasiewicz (KL) function Φ, which generates a sequence satisfying a nonmonotone decrease condition and a relative error tolerance. Under suitable assumptions, we prove that the whole sequence converges to a limiting critical point of Φ, and, when Φ is a KL function of exponent θ∈[0,1), the convergence admits a linear rate if θ∈[0,1/2] and a sublinear rate associated to θ if θ∈(1/2,1). These assumptions are shown to be sufficient and necessary if in addition Φ is weakly convex on a neighborhood of the set of critical points. Our results not only extend the convergence results of monotone descent methods for KL optimization problems but also resolve the convergence problem on the iterate sequence generated by a class of nonmonotone line search algorithms for nonconvex and nonsmooth problems. [ABSTRACT FROM AUTHOR]

Given a closed convex set A in a Banach space X, motivated by the continuity and Fréchet differentiability of A introduced, respectively, in [D. Gale and V. Klee, Math. Scand., 7 (1959), pp. 379-391] and [X. Y. Zheng, SIAM J. Optim., 30 (2020), pp. 490-512], this paper considers the Cp-differentiability, subdifferentiability, and G\^ateaux differentiability of A. Using the technique of variational analysis, it is proved that A is Cp-differentiable (resp., subdifferentiable or G\^ateaux differentiable) if and only if for every continuous convex function f : X → R with infx∈A f(x) > infx∈X f(x) the corresponding constrained optimization problem PA(f) is 2/p-order-well-posed solvable (resp., generalized well-posed solvable or weak well-posed solvable). It is also proved that if the conjugate function f* of a continuous convex function f on X is Cp-differentiable on dom(f*), then for every closed convex set A in X with infx∈A f(x) > -∞ the corresponding optimization problem PA(f) is 2/p-order-well-posed solvable. As a byproduct, every constrained convex optimization problem with a strongly convex quadratic objective function is proved to be globally second-order-well-posed solvable. Our main results are new even in the case of finite dimensional spaces. [ABSTRACT FROM AUTHOR]

This paper deals with error bound characterizations of the conical constraint qualification (CCQ) for convex inequality systems in a Banach space X. We establish necessary and sufficient conditions for a closed convex set S defined by a convex function g to have CCQ. These conditions are expressed in terms of the notion of error bound. Our results show that these characterizations hold in the following special cases: 1. g is the maximum of a finite number of differentiable convex functions. 2. S is closed convex and polyhedral. 3. The dimension of the subspace span(S) is less than 2 and g is positively homogeneous. We construct technical examples showing that these characterizations are limited to the three situations above. We introduce a new condition in terms of the gauge function which allows us to give an error bound characterization of convex nondifferentiable systems and to obtain as a direct consequence different characterizations of the concept of the strong conical hull intersection property for a finite collection of convex sets. [ABSTRACT FROM AUTHOR]

Amenability is a geometric property of convex cones that is stronger than facial exposedness and assists in the study of error bounds for conic feasibility problems. In this paper we establish numerous properties of amenable cones and investigate the relationships between amenability and other properties of convex cones, such as niceness and projectional exposure. We show that the amenability of a compact slice of a closed convex cone is equivalent to the amenability of the cone, and we prove several results on the preservation of amenability under intersections and other convex operations. It then follows that homogeneous, doubly nonnegative, and other cones that can be represented as slices of the cone of positive semidefinite matrices are amenable. It is known that projectionally exposed cones are amenable and that amenable cones are nice; however, the converse statements have been open questions. We construct an example of a four-dimensional cone that is nice but not amenable. We also show that amenable cones are projectionally exposed in dimensions up to and including four. We conclude with a discussion on open problems related to facial structure of convex sets that we came across in the course of this work but were not able to fully resolve. [ABSTRACT FROM AUTHOR]

This paper combines two ingredients in order to get a rather surprising result on one of the most studied, elegant, and powerful tools for solving convex feasibility problems, the method of alternating projections (MAP). Going back to names such as Kaczmarz and von Neumann, MAP has the ability to track a pair of points realizing minimum distance between two given closed convex sets. Unfortunately, MAP may suffer from arbitrarily slow convergence, and sublinear rates are essentially only surpassed in the presence of some Lipschitzian error bound, which is our first ingredient. The second one is a seemingly unfavorable and unexpected condition, namely, infeasibility. For two nonintersecting closed convex sets satisfying an error bound, we establish finite convergence of MAP. In particular, MAP converges in finitely many steps when applied to a polyhedron and a hyperplane in the case in which they have empty intersection. Moreover, the farther the target sets lie from each other, fewer are the iterations needed by MAP for finding a best approximation pair. Insightful examples and further theoretical and algorithmic discussions accompany our results, including the investigation of finite termination of other projection methods. [ABSTRACT FROM AUTHOR]

This paper presents a proximal bundle variant, namely, the relaxed proximal bundle (RPB) method, for solving convex nonsmooth composite optimization problems. Like other proximal bundle variants, RPB solves a sequence of prox bundle subproblems whose objective functions are regularized composite cutting-plane models. Moreover, RPB uses a novel condition to decide whether to perform a serious or null iteration which does not necessarily yield a function value decrease. Optimal iteration-complexity bounds for RPB are established for a large range of prox stepsizes, in both convex and strongly convex settings. To the best of our knowledge, this is the first time that a proximal bundle variant is shown to be optimal for a large range of prox stepsizes. Finally, iterationcomplexity results for RPB to obtain iterates satisfying practical termination criteria, rather than near optimal solutions, are also derived. [ABSTRACT FROM AUTHOR]

In this paper, we study the sequential convex programming method with monotone line search (SCPls) in [Z. Lu, Sequential Convex Programming Methods for a Class of Structured Nonlinear Programming, https://arxiv.org/abs/1210.3039, 2012] for a class of difference-of-convex optimization problems with multiple smooth inequality constraints. The SCPls is a representative variant of moving-ball-approximation-type algorithms [A. Auslender, R. Shefi, and M. Teboulle, SIAM J. Optim., 20 (2010), pp. 3232-3259; J. Bolte, Z. Chen, and E. Pauwels, Math. Program., 182 (2020) pp. 1-36; J. Bolte and E. Pauwels, Math. Oper. Res., 41 (2016), pp. 442-465; R. Shefi and M. Teboulle, Math. Program., 159 (2016), pp. 137-164] for constrained optimization problems. We analyze the convergence rate of the sequence generated by SCPls in both nonconvex and convex settings by imposing suitable Kurdyka--Löjasiewicz (KL) assumptions. Specifically, in the nonconvex settings, we assume that a special potential function related to the ob jective and the constraints is a KL function, while in the convex settings we impose KL assumptions directly on the extended ob jective function (i.e., sum of the ob jective and the indicator function of the constraint set). A relationship between these two different KL assumptions is established in the convex settings under additional differentiability assumptions. We also discuss how to deduce the KL exponent of the extended ob jective function from its Lagrangian in the convex settings, under additional assumptions on the constraint functions. Thanks to this result, the extended ob jectives of some constrained optimization models such as minimizing\ell1 sub ject to logistic/Poisson loss are found to be KL functions with exponent 1 under mild assumptions. To illustrate how our results can be applied, we consider SCPs for minimizing 1-2 [P-Yin, Y. Lou, Q. He, and J. Xin, SIAM J. Sci. Comput., 37 (2015), pp. A536--A563] subject to residual error measured by norm/Lorentzian norm [R. E. Carrillo, A. B. Ramirez, G. R. Arce, K. E. Barner, and B. M. Sadler, EURASIP J. Adv. Signal Process. (2016), 108]. We first discuss how the various conditions required in our analysis can be verified, and then perform numerical experiments to illustrate the convergence behaviors of SCPls. [ABSTRACT FROM AUTHOR]

In this paper, through an intuitive vanil la proximal method perspective, we derive a concise unified acceleration framework (UAF) for minimizing a convex function that has H\"older continuous derivatives with respect to general (non-Euclidean) norms. The UAF reconciles two different high-order acceleration approaches, one by Nesterov [Math. Program., 112 (2008), pp. 159-181] and one by Monteiro and Svaiter [SIAM J. Optim., 23 (2013), pp. 1092-1125]. As a result, the UAF unifies the high-order acceleration instances of the two approaches by only two problem-related parameters and two additional parameters for framework design. Meanwhile, the UAF (and its analysis) is the first approach to make high-order methods applicable for high-order smoothness conditions with respect to non-Euclidean norms. Furthermore, the UAF is the first approach that can match the existing lower bound of iteration complexity for minimizing a convex function with H\"older continuous derivatives. For practical implementation, we introduce a new and effective heuristic that significantly simplifies the binary search procedure required by the framework. We use experiments on logistic regression to verify the effectiveness of the heuristic. Finally, the UAF is proposed directly in the general composite convex setting and shows that the existing high-order algorithms can be naturally extended to the general composite convex setting. [ABSTRACT FROM AUTHOR]

For an inequality system defined by an infinite family of proper lower semicontinuous convex functions in normed linear space, we consider the Farkas--Minkowski (FM for short) type qualification and the basic constraint qualification (BCQ for short). By employing a new approach based on some new results established here on the SECQ (sum of epigraphs constraint qualification) for families of closed convex sets, some sufficient conditions involving further relaxing Slater type conditions for ensuring the FM qualification are provided. As applications, new sufficient conditions for ensuring the BCQ are given. These results significantly improve the corresponding ones in [C. Li and K. F. Ng, SIAM J. Optim., 15 (2005), pp. 488-512] and [C. Li, X. P. Zhao, and Y. H. Hu, SIAM J. Optim., 23 (2013), pp. 2208-2230], and they are obtained without the key continuity assumption on the sup-function of the inequality system which the previous works depend heavily on. Some examples are also presented to illustrate the applicability of our results. [ABSTRACT FROM AUTHOR]

Stochastic gradient descent (SGD) is one of the most widely used algorithms for largescale optimization problems. While classical theoretical analysis of SGD for convex problems studies (suffix) averages of iterates and obtains information theoretically optimal bounds on suboptimality, the last point of SGD is, by far, the most preferred choice in practice. The best known results for the last point of SGD [O. Shamir and T. Zhang, Proceedings of the 30th International Conference on Machine Learning, 2013, pp. 71-79] however, are suboptimal compared to information theoretic lower bounds by a log T factor, where T is the number of iterations. Harvey, Liaw, Plan, and Randhawa [Conference on Learning Theory, PMLR, 2019, pp. 1579-1613] shows that in fact, this additional log T factor is tight for standard step size sequences of Θ (1√t ) and Θa (1√t) for non-strongly convex and strongly convex settings, respectively. Similarly, even for subgradient descent (GD) when applied to nonsmooth, convex functions, the best known step size sequences still lead to O(log T)-suboptimal convergence rates (on the final iterate). The main contribution of this work is to design new step size sequences that enjoy information theoretically optimal bounds on the suboptimality of the last point of SGD as well as GD. We achieve this by designing a modification scheme that converts one sequence of step sizes to another so that the last point of SGD/GD with modified sequence has the same suboptimality guarantees as the average of SGD/GD with original sequence. We also show that our result holds with high probability. We validate our results through simulations which demonstrate that the new step size sequence indeed improves the final iterate significantly compared to the standard step size sequences. [ABSTRACT FROM AUTHOR]

We take a Hamiltonian-based perspective to generalize Nesterov's accelerated gradient descent and Polyak's heavy ball method to a broad class of momentum methods in the setting of (possibly) constrained minimization in Euclidean and non-Euclidean normed vector spaces. Our perspective leads to a generic and unifying nonasymptotic analysis of convergence of these methods in both the function value (in the setting of convex optimization) and in the norm of the gradient (in the setting of unconstrained, possibly nonconvex, optimization). Our approach relies upon a time-varying Hamiltonian that produces generalized momentum methods as its equations of motion. The convergence analysis for these methods is intuitive and is based on the conserved quantities of the time-dependent Hamiltonian. [ABSTRACT FROM AUTHOR]

We consider a generalization of the Bauer maximum principle. We work with tensorial products of convex measures set that are not necessarily compact but generated by their extreme points. We show that the maximum of a quasi-convex lower semicontinuous function on this product space is reached on the tensorial product of finite mixtures of extreme points. Our work is an extension of the Bauer maximum principle in three different aspects. First, we only assume that the objective functional is quasi-convex. Secondly, the optimization is performed over a space built as a product of measure sets. Finally, the usual compactness assumption is replaced with the existence of an integral representation on the extreme points. We focus on the product of two different types of measure sets, called the moment class and the unimodal moment class. The elements of these classes are probability measures (respectively, unimodal probability measures) satisfying generalized moment constraints. We show that an integral representation on the extreme points is available for such spaces and that it extends to their tensorial product. We give several applications of the theorem, going from robust Bayesian analysis to the optimization of a quantile of a computer code output. [ABSTRACT FROM AUTHOR]

Smooth convex minimization over the unit trace-norm ball is an important optimization problem in machine learning, signal processing, statistics, and other fields that underlies many tasks in which one wishes to recover a low-rank matrix given certain measurements. While first-order methods for convex optimization enjoy optimal convergence rates, they require in the worst-case to compute a full-rank SVD on each iteration, in order to compute the Euclidean projection onto the trace-norm ball. These full-rank SVD computations, however, prohibit the application of such methods to large-scale problems. A simple and natural heuristic to reduce the computational cost of such methods is to approximate the Euclidean projection using only a low-rank SVD. This raises the question if, and under what conditions, this simple heuristic can indeed result in provable convergence to the optimal solution. In this paper we show that any optimal solution is a center of a Euclidean ball inside which the projected-gradient mapping admits a rank that is at most the multiplicity of the largest singular value of the gradient vector at this optimal point. Moreover, the radius of the ball scales with the spectral gap of this gradient vector. We show how this readily implies the local convergence (i.e., from a "warm-start" initialization) of standard first-order methods such as the projected-gradient method and accelerated gradient methods, using only low-rank SVD computations. We also quantify the effect of "over-parameterization," i.e., using SVD computations with higher rank, on the radius of this ball, showing it can increase dramatically with moderately larger rank. We extend our results also to the setting of smooth convex minimization with trace-norm regularization and smooth convex optimization over bounded-trace positive semidefinite matrices. Our theoretical investigation is supported by concrete empirical evidence that demonstrates the correct convergence of first-order methods with low-rank projections for the matrix completion task on real-world datasets. [ABSTRACT FROM AUTHOR]

We consider a linear problem over a finite set of integer vectors and assume that there is a verification oracle, which is an algorithm being able to verify whether a given vector optimizes a given linear function over the feasible set. Given an initial solution, the algorithm proposed in this paper finds an optimal solution of the problem together with a path, in the 1-skeleton of the convex hull of the feasible set, from the initial solution to the optimal solution found. The length of this path is bounded by the sum of distinct values which can be taken by the components of feasible solutions, minus the dimension of the problem. In particular, in the case when the feasible set is a set of binary vectors, the length of the constructed path is bounded by the number of variables, independently of the objective function. [ABSTRACT FROM AUTHOR]

In this paper, we compare the definitions of convex sets and convex functions in finite dimensional integer spaces introduced by Adivar and Fang, Borwein, and Giladi, respectively. We show that their definitions of convex sets and convex functions are equivalent. We also provide exact formulations for convex sets, convex cones, affine sets, and convex functions and we analyze the separation between convex sets in finite dimensional integer spaces. As an application, we consider an integer linear programming problem with linear inequality constraints and obtain some necessary or sufficient optimality conditions by employing the image space analysis. We finally provide some computational results based on the above-mentioned optimality conditions. [ABSTRACT FROM AUTHOR]

In this paper we propose a splitting scheme which hybridizes the generalized conditional gradient with a proximal step and which we call the CGALP algorithm for minimizing the sum of three proper convex and lower-semicontinuous functions in real Hilbert spaces. The minimization is subject to an affine constraint, that, in particular, allows one to deal with composite problems (a sum of more than three functions) in a separable way by the usual product space technique. While classical conditional gradient methods require Lipschitz continuity of the gradient of the differentiable part of the objective, CGALP needs only differentiability (on an appropriate subset) and hence circumvents the intricate question of Lipschitz continuity of gradients. For the two remaining functions in the objective, we do not require any additional regularity assumption. The second function, possibly nonsmooth, is assumed simple; i.e., the associated proximal mapping is easily computable. For the third function, again nonsmooth, we just assume that its domain is weakly compact and that a linearly perturbed minimization oracle is accessible. In particular, this last function can be chosen to be the indicator of a nonempty bounded closed convex set in order to deal with additional constraints. Finally, the affine constraint is addressed by the augmented Lagrangian approach. Our analysis is carried out for a wide choice of algorithm parameters satisfying so-called open loop rules. As main results, under mild conditions, we show asymptotic feasibility with respect to the affine constraint, weak convergence of the dual multipliers, and convergence of the Lagrangian values to the saddle-point optimal value. We also provide pointwise and ergodic rates of convergence for both the feasibility gap and the Lagrangian values. [ABSTRACT FROM AUTHOR]

A multiobjective optimization problem is simplicial if the Pareto set and front are homeomorphic to a simplex and, under the homeomorphisms, each face of the simplex corresponds to the Pareto set and front of a subproblem that treats a subset of objective functions. In this paper, we show that strongly convex problems are simplicial under a mild assumption on the ranks of the differentials of the objective mappings. We further prove that one can make any strongly convex problem satisfy the assumption by a generic linear perturbation, provided that the dimension of the source is sufficiently larger than that of the target. We demonstrate that the location problems, a biological modeling, and the ridge regression can be reduced to multiobjective strongly convex problems via appropriate transformations preserving the Pareto ordering and the topology. [ABSTRACT FROM AUTHOR]

We study stability properties of a given solution of a constrained equation, where the constraint has the form of the inclusion into an arbitrary closed convex set. We are mostly interested in those cases when Robinson's regularity condition does not hold, and we obtain weaker conditions ensuring stability of a given solution subject to wide classes of perturbations, or, in other words, ensuring covering of a ``large"" set. Unlike previous developments of this kind, here we do not employ any necessary conicity assumptions on the constraint set, thus allowing for a much wider area of potential applications. [ABSTRACT FROM AUTHOR]

In this paper, we provide the first provable linear-time (in terms of the number of nonzero entries of the input) algorithm for approximately solving the generalized trust region subproblem (GTRS) of minimizing a quadratic function over a quadratic constraint under some regularity condition. Our algorithm is motivated by and extends a recent linear-time algorithm for the trust region subproblem by Hazan and Koren [Math. Program., 158 (2016), pp. 363–381]. However, due to the nonconvexity and noncompactness of the feasible region, such an extension is nontrivial. Our main contribution is to demonstrate that under some regularity condition, the optimal solution is in a compact and convex set and lower and upper bounds of the optimal value can be computed in linear time. Using these properties, we develop a linear-time algorithm for the GTRS. [ABSTRACT FROM AUTHOR]

For deterministic optimization, line search methods augment algorithms by providing stability and improved efficiency. Here we adapt a classical backtracking Armijo line search to the stochastic optimization setting. While traditional line search relies on exact computations of the gradient and values of the objective function, our method assumes that these values are available up to some dynamically adjusted accuracy which holds with some sufficiently large, but fixed, probability. We bound the expected number of iterations to reach a desired first-order accuracy in the nonconvex, convex, and strongly convex cases and show that this bound matches the complexity bound of deterministic gradient descent up to constants. [ABSTRACT FROM AUTHOR]

In this paper we study sufficient conditions for metric subregularity of a set-valued map which is the sum of a single-valued continuous map and a locally closed subset. First we derive a sufficient condition for metric subregularity which is weaker than the so-called first-order sufficient condition for metric subregularity (FOSCMS) by adding an extra sequential condition. Then we introduce directional versions of quasi-normality and pseudo-normality which are stronger than the new weak sufficient condition for metric subregularity but weaker than classical quasi-normality and pseudo-normality. Moreover we introduce a nonsmooth version of the second-order sufficient condition for metric subregularity and show that it is a sufficient condition for the new sufficient condition for metric subregularity to hold. An example is used to illustrate that directional pseudo-normality can be weaker than FOSCMS. For the class of set-valued maps where the single-valued mapping is affine and the abstract set is the union of finitely many convex polyhedral sets, we show that pseudo-normality and hence directional pseudo-normality holds automatically at each point oft he graph. Finally we apply our results to complementarity and Karush–Kuhn–Tucker systems. [ABSTRACT FROM AUTHOR]

In this paper we develop a family of randomized projection methods (RPM) for solving the convex feasibility problem. Our approach is based on several new ideas and tools, including stochastic approximation of convex sets, stochastic reformulations, and conditioning of the convex feasibility problem. In particular, we propose four equivalent stochastic reformulations: stochastic smooth and nonsmooth optimization problems, the stochastic fixed point problem, and the stochastic feasibility problem. The last reformulation asks for a point which belongs to a certain random set with probability one. In this case, RPM can be interpreted as follows: we sample a batch of random sets in an independently and identically distributed fashion, perform projections of the current iterate on all sampled sets, and then combine these projections by averaging with a carefully designed extrapolation step. We prove that under stochastic linear regularity, RPM converges linearly, with a rate that has a natural interpretation as a condition number of the stochastic optimization reformulation and that depends explicitly on the number of sets sampled. In doing so, we extend the concept of condition number to general convex feasibility problems. This condition number depends on the linear regularity constant and an additional key constant which can be interpreted as a Lipschitz constant of the gradient of the stochastic optimization reformulation. Besides providing a general framework for the design and analysis of randomized projection schemes, our results resolve an open problem in the literature related to the theoretical understanding of observed practical efficiency of extrapolated parallel projection methods. In addition, we prove that our method converges sublinearly in the case when the stochastic linear regularity condition is not satisfied. Preliminary numerical results also show a better performance of our extrapolated step-size scheme over its constant step-size counterpart. [ABSTRACT FROM AUTHOR]

The second-order tangent set is an important concept in describing the curvature of the set involved. Due to the existence of the complementarity condition, the second-order cone (SOC) complementarity set is a nonconvex set. Moreover, unlike the vector complementarity set, the SOC complementarity set is not even the union of finitely many polyhedral convex sets. Despite these difficulties, we succeed in showing that like the vector complementarity set, the SOC complementarity set is second-order directionally differentiable and an exact formula for the second-order tangent set of the SOC complementarity set can be given. We derive these results by establishing the relationship between the second-order tangent set of the SOC complementarity set and the second-order directional derivative of the projection operator over the SOC, and calculating the second-order directional derivative of the projection operator over the SOC. As an application, we derive second-order necessary optimality conditions for the mathematical program with SOC complementarity constraints [ABSTRACT FROM AUTHOR]

In this paper, we show that the subadditive dual of a feasible conic mixed-integer program (MIP) is a strong dual whenever it is feasible. Moreover, we show that this dual feasibility condition is equivalent to feasibility of the conic dual of the continuous relaxation of the conic MIP. In addition, we prove that all known conditions and other \natural" conditions for strong duality, such as strict mixed-integer feasibility, boundedness of the feasible set, or essentially strict feasibility, imply that the subadditive dual is feasible. As an intermediate result, we extend the so-called finiteness property" from full-dimensional convex sets to intersections of full-dimensional convex sets and Dirichlet convex sets. [ABSTRACT FROM AUTHOR]

We study the boundary structure of closed convex cones, with a focus on facially dual complete (nice) cones. These cones form a proper subset of facially exposed convex cones, and they behave well in the context of duality theory for convex optimization. Using the well-known and commonly used concept of tangent cones in nonlinear optimization, we introduce some new notions for exposure of faces of convex sets. Based on these new notions, we obtain a necessary condition and a sufficient condition for a cone to be facially dual complete. In our sufficient condition, we utilize a new notion called lexicographic tangent cones (these are a family of cones obtained from a recursive application of the tangent cone concept). Lexicographic tangent cones are related to Nesterov's lexicographic derivatives and to the notion of subtrans versality in the context of variational analysis. [ABSTRACT FROM AUTHOR]

Making cut-generating functions (CGFs) computationally viable is a central question in modern integer programming research. One would like to find CGFs that are simultaneously good, i.e., there are good guarantees for the cutting planes they generate, and efficient, meaning that the values of the CGFs can be computed cheaply (with procedures that have some hope of being implemented in current solvers). We investigate in this paper to what extent this balance can be struck. We propose a family of CGFs which, in a sense, achieves this harmony between good and efficient. In particular, we provide a parameterized family of (b + ... Zn)-free sets to derive CGFs from and show that our proposed CGFs give a good approximation of the closure given by CGFs obtained from all maximal (b + ... Zn)-free sets and their so-called trivial liftings, and simultaneously show that these CGFs can be computed with explicit, efficient procedures. We provide a constructive framework to identify these sets and also compute their trivial lifting. We then follow up with computational experiments to demonstrate this and to evaluate their practical use. Our proposed family of cuts seem to give some tangible improvement on randomly generated instances compared to GMI cuts; however, in MIPLIB 3.0 instances and vertex cover and stable problems on random graph instances, their performance is poor. [ABSTRACT FROM AUTHOR]

We consider a family of algorithms that successively sample and minimize simple stochastic models of the objective function. We show that under reasonable conditions on approximation quality and regularity of the models, any such algorithm drives a natural stationarity measure to zero at the rate O(k-1/4) As a consequence, we obtain the first complexity guarantees for the stochastic proximal point, proximal subgradient, and regularized Gauss{Newton methods for minimizing compositions of convex functions with smooth maps. The guiding principle, underlying the complexity guarantees, is that all algorithms under consideration can be interpreted as approximate descent methods on an implicit smoothing of the problem, given by the Moreau envelope. Specializing to classical circumstances, we obtain the long-sought convergence rate of the stochastic projected gradient method, without batching, for minimizing a smooth function on a closed convex set. [ABSTRACT FROM AUTHOR]

An adaptive regularization algorithm using high-order models is proposed for solving partially separable convexly constrained nonlinear optimization problems whose objective function contains non-Lipschitzian ℓq-norm regularization terms for q ∈ (0, 1). It is shown that the algorithm using a $p$th-order Taylor model for p odd needs in general at most $(ε-(p+1)/p) evaluations of the objective function and its derivatives (at points where they are defined) to produce an ε-approximate first-order critical point. This result is obtained either with Taylor models, at the price of requiring the feasible set to be "kernel centered" (which includes bound constraints and many other cases of interest), or with non-Lipschitz models, at the price of passing the difficulty to the computation of the step. Since this complexity bound is identical in order to that already known for purely Lipschitzian minimization subject to convex constraints [C. Cartis, N. I. M. Gould, and Ph. L. Toint, IMA J. Numer. Anal., 32 (2012), pp. 1662--1695], the new result shows that introducing non-Lipschitzian singularities in the objective function may not affect the worst-case evaluation complexity order. The result also shows that using the problem's partially separable structure (if present) does not affect the complexity order either. A final (worse) complexity bound is derived for the case where Taylor models are used with a general convex feasible set. [ABSTRACT FROM AUTHOR]

In general, multistage stochastic optimization problems are formulated on the basis of continuous distributions describing the uncertainty. Such "infinite" problems are practically impossible to solve as they are formulated, and finite tree approximations of the underlying stochastic processes are used as proxies. In this paper, we demonstrate how one can find guaranteed bounds, i.e., finite tree models, for which the optimal values give upper and lower bounds for the optimal value of the original infinite problem. Typically, there is a gap between the two bounds. However, this gap can be made arbitrarily small by making the approximating trees bushier. We consider approximations in the first-order stochastic sense, in the convex-order sense, and based on subgradient approximations. Their use is shown in a multistage risk-averse production problem. [ABSTRACT FROM AUTHOR]

We propose a distributed version of a stochastic approximation scheme constrained to remain in the intersection of a finite family of convex sets. The projection to the intersection of these sets is also computed in a distributed manner and a "gossip" mechanism is employed to blend the projection iterations with the stochastic approximation using multiple time scales. [ABSTRACT FROM AUTHOR]

The projection onto the intersection of sets generally does not allow for a closed form even when the individual projection operators have explicit descriptions. In this work, we systematically analyze the projection onto the intersection of a cone with either a ball or a sphere. Several cases are provided where the projector is available in closed form. Various examples based on finitely generated cones, the Lorentz cone, and the cone of positive semidefinite matrices are presented. The usefulness of our formulae is illustrated by numerical experiments for determining copositivity of real symmetric matrices. [ABSTRACT FROM AUTHOR]

This paper is meant to prove the consistency of the scenario approach à la Calafiore, Campi, and Garatti with convex constraints. Scenario convex problems are usually stated in two equivalent forms: first, as the minimum of a linear function over the intersection of a finite random sample of independent and identically distributed convex sets, or second, as the min-max of a finite random sample of independent and identically distributed convex functions. The paper shows that, under fairly general assumptions, as the size of the sample increases the minimum attained by the solution of a problem of the first kind converges almost surely to the minimum attained by a suitably defined "essential" robust problem (or diverges if such a robust problem is infeasible), and that the minimum attained by the solution of a scenario problem of the second kind converges almost surely to the minimum of the pointwise essential supremum taken over all the possible convex functions (or diverges if such essential supremum takes the only value +∞). In both cases, if the solution of the essential problem exists and is unique, the solution of the scenario problem converges to it almost surely. [ABSTRACT FROM AUTHOR]

The paper deals with some theoretical and numerical aspects for an optimal matching problem with constraints. It is known that the uniqueness of the optimal matching measure does not hold even with Lp sources and targets. In this paper, the uniqueness is proven under geometric conditions. On the other hand, we also introduce a dual formulation with a linear cost functional on a convex set and show that its Fenchel{Rockafellar dual formulation gives the right solution to the optimal matching problem. Basing on our formulations, a numerical approximation is given via an augmented Lagrangian method. We compute at the same time the optimal matching measure, optimal ows, and Kantorovich potentials. The convergence of the discretization is also studied in detail. [ABSTRACT FROM AUTHOR]

In this paper we study genericity for the class of semialgebraic optimization problems with equality and inequality constraints, in which every problem of the class is obtained by linear perturbations of the objective function, while the \core" objective function and the constraint functions are kept fixed. Assume that the linear independence constraint qualification is satisfied at every point in the constraint set. It is shown that almost all problems in the class are such that (i) the restriction of the objective function on the constraint set is coercive and regular at infinity; (ii) there is a unique optimal solution, lying on a unique active manifold, at which the strict complementarity and second order sufficiency conditions, the quadratic growth condition, and the Hölder type global error bound hold, and (iii) all minimizing sequences converge. Furthermore, the active manifold is constant, and the optimal solution and the optimal value function depend analytically under local perturbations of the objective function. These results are combined with a standard result about the existence of sums of squares certificates to prove that we can build a sequence of semidefinite programs whose solutions give rise to a sequence of points converging to the optimal solution of the original problem in finitely many steps. It is worth emphasizing that the results of this study hold globally and we do not require the problem to be convex or the constraint set to be compact. [ABSTRACT FROM AUTHOR]

We present a provably convergent distributed analog of Han's algorithm for computing the projection of a point on the intersection of a finite collection of convex sets. [ABSTRACT FROM AUTHOR]

In this article we consider a consistent convex feasibility problem in a real Hilbert space defined by a finite family of sets Ci. We are interested, in particular, in the case where for each i, Ci = FixUi = {z ∈ H ∣ pi(z) = 0}, Ui : H → H is a cutter and pi : H → [0,∞) is a proximity function. Moreover, we make the following assumption: the computation of pi is at most as difficult as the evaluation of Ui and this is at most as difficult as projecting onto Ci. We study a double-layer fixed point algorithm which applies two types of controls in every iteration step. The first one—the outer control—is assumed to be almost cyclic. The second one—the inner control—determines the most important sets from those offered by the first one. The selection is made in terms of proximity functions. The convergence results presented in this manuscript depend on the conditions which, first, bind together the sets, the operators, and the proximity functions and, second, connect the inner and outer controls. In particular, weak regularity (demi-closedness principle), bounded regularity, and bounded linear regularity imply weak, strong, and linear convergence of our algorithm, respectively. The framework presented in this paper covers many known (subgradient) projection algorithms already existing in the literature, for example, those applied with (almost) cyclic, remotest-set, maximum displacement, most-violated constraint, and simultaneous controls. In addition, we provide several new examples, where the double-layer approach indeed accelerates the convergence speed as we demonstrate numerically. [ABSTRACT FROM AUTHOR]

We study the extension of the Chambolle–Pock primal-dual algorithm to nonsmooth optimization problems involving nonlinear operators between function spaces. Local convergence is shown under technical conditions including metric regularity of the corresponding primal-dual optimality conditions. We also show convergence for a Nesterov-type accelerated variant, provided one part of the functional is strongly convex. We show the applicability of the accelerated algorithm to examples of inverse problems with L¹ and L∞fitting terms as well as of state-constrained optimal control problems, where convergence can be guaranteed after introducing an (arbitrarily small, still nonsmooth) Moreau–Yosida regularization. This is verified in numerical examples. [ABSTRACT FROM AUTHOR]