Search

This paper introduces cutting planes that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set S ∩ P , where S is a closed set, and P is a polyhedron. Given an oracle that provides the distance from a point to S, we construct a pure cutting plane algorithm which is shown to converge if the initial relaxation is a polyhedron. These cuts are generated from convex forbidden zones, or S-free sets, derived from the oracle. We also consider the special case of polynomial optimization. Accordingly we develop a theory of outer-product-free sets, where S is the set of real, symmetric matrices of the form x x T . All maximal outer-product-free sets of full dimension are shown to be convex cones and we identify several families of such sets. These families are used to generate strengthened intersection cuts that can separate any infeasible extreme point of a linear programming relaxation efficiently. Computational experiments demonstrate the promise of our approach. [ABSTRACT FROM AUTHOR]

In this paper, we propose a first second-order scheme based on arbitrary non-Euclidean norms, incorporated by Bregman distances. They are introduced directly in the Newton iterate with regularization parameter proportional to the square root of the norm of the current gradient. For the basic scheme, as applied to the composite convex optimization problem, we establish the global convergence rate of the order O (k - 2) both in terms of the functional residual and in the norm of subgradients. Our main assumption on the smooth part of the objective is Lipschitz continuity of its Hessian. For uniformly convex functions of degree three, we justify global linear rate, and for strongly convex function we prove the local superlinear rate of convergence. Our approach can be seen as a relaxation of the Cubic Regularization of the Newton method (Nesterov and Polyak in Math Program 108(1):177–205, 2006) for convex minimization problems. This relaxation preserves the convergence properties and global complexities of the Cubic Newton in convex case, while the auxiliary subproblem at each iteration is simpler. We equip our method with adaptive search procedure for choosing the regularization parameter. We propose also an accelerated scheme with convergence rate O (k - 3) , where k is the iteration counter. [ABSTRACT FROM AUTHOR]

In this paper, a joint study of the behavior of solutions of the Heavy Ball ODE and Heavy Ball type algorithms is given. Since the pioneering work of Polyak (USSR Comput Math Math Phys 4(5):1–17, 1964), it is well known that such a scheme is very efficient for C 2 strongly convex functions with Lipschitz gradient. But much less is known when only growth conditions are considered. Depending on the geometry of the function to minimize, convergence rates for convex functions, with some additional regularity such as quasi-strong convexity, or strong convexity, were recently obtained in Aujol et al. (Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization, 2020). Convergence results with much weaker assumptions are given in the present paper: namely, linear convergence rates when assuming a growth condition (which amounts to a Łojasiewicz property in the convex case). This analysis is firstly performed in continuous time for the ODE, and then transposed for discrete optimization schemes. In particular, a variant of the Heavy Ball algorithm is proposed, which converges geometrically whatever the parameters choice, and which has the best state of the art convergence rate for first order methods to minimize composite non smooth convex functions satisfying a Łojasiewicz property. [ABSTRACT FROM AUTHOR]

The well known constant rank constraint qualification [Math. Program. Study 21:110–126, 1984] introduced by Janin for nonlinear programming has been recently extended to a conic context by exploiting the eigenvector structure of the problem. In this paper we propose a more general and geometric approach for defining a new extension of this condition to the conic context. The main advantage of our approach is that we are able to recast the strong second-order properties of the constant rank condition in a conic context. In particular, we obtain a second-order necessary optimality condition that is stronger than the classical one obtained under Robinson's constraint qualification, in the sense that it holds for every Lagrange multiplier, even though our condition is independent of Robinson's condition. [ABSTRACT FROM AUTHOR]

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

Classical trust region methods were designed to solve problems in which function and gradient information are exact. This paper considers the case when there are errors (or noise) in the above computations and proposes a simple modification of the trust region method to cope with these errors. The new algorithm only requires information about the size/standard deviation of the errors in the function evaluations and incurs no additional computational expense. It is shown that, when applied to a smooth (but not necessarily convex) objective function, the iterates of the algorithm visit a neighborhood of stationarity infinitely often, assuming errors in the function and gradient evaluations are bounded. It is also shown that, after visiting the above neighborhood for the first time, the iterates cannot stray too far from it, as measured by the objective value. Numerical results illustrate how the classical trust region algorithm may fail in the presence of noise, and how the proposed algorithm ensures steady progress towards stationarity in these cases. [ABSTRACT FROM AUTHOR]

The softmax policy gradient (PG) method, which performs gradient ascent under softmax policy parameterization, is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. For γ -discounted infinite-horizon tabular Markov decision processes (MDPs), remarkable progress has recently been achieved towards establishing global convergence of softmax PG methods in finding a near-optimal policy. However, prior results fall short of delineating clear dependencies of convergence rates on salient parameters such as the cardinality of the state space S and the effective horizon 1 1 - γ , both of which could be excessively large. In this paper, we deliver a pessimistic message regarding the iteration complexity of softmax PG methods, despite assuming access to exact gradient computation. Specifically, we demonstrate that the softmax PG method with stepsize η can take 1 η | S | 2 Ω (1 1 - γ ) iterations to converge, even in the presence of a benign policy initialization and an initial state distribution amenable to exploration (so that the distribution mismatch coefficient is not exceedingly large). This is accomplished by characterizing the algorithmic dynamics over a carefully-constructed MDP containing only three actions. Our exponential lower bound hints at the necessity of carefully adjusting update rules or enforcing proper regularization in accelerating PG methods. [ABSTRACT FROM AUTHOR]

Much recent research effort has been directed to the development of efficient algorithms for solving minimax problems with theoretical convergence guarantees due to the relevance of these problems to a few emergent applications. In this paper, we propose a unified single-loop alternating gradient projection (AGP) algorithm for solving smooth nonconvex-(strongly) concave and (strongly) convex–nonconcave minimax problems. AGP employs simple gradient projection steps for updating the primal and dual variables alternatively at each iteration. We show that it can find an ε -stationary point of the objective function in O ε - 2 (resp. O ε - 4 ) iterations under nonconvex-strongly concave (resp. nonconvex–concave) setting. Moreover, its gradient complexity to obtain an ε -stationary point of the objective function is bounded by O ε - 2 (resp., O ε - 4 ) under the strongly convex–nonconcave (resp., convex–nonconcave) setting. To the best of our knowledge, this is the first time that a simple and unified single-loop algorithm is developed for solving both nonconvex-(strongly) concave and (strongly) convex–nonconcave minimax problems. Moreover, the complexity results for solving the latter (strongly) convex–nonconcave minimax problems have never been obtained before in the literature. Numerical results show the efficiency of the proposed AGP algorithm. Furthermore, we extend the AGP algorithm by presenting a block alternating proximal gradient (BAPG) algorithm for solving more general multi-block nonsmooth nonconvex-(strongly) concave and (strongly) convex–nonconcave minimax problems. We can similarly establish the gradient complexity of the proposed algorithm under these four different settings. [ABSTRACT FROM AUTHOR]

This paper is devoted to studying an augmented Lagrangian method for solving a class of manifold optimization problems, which have nonsmooth objective functions and nonlinear constraints. Under the constant positive linear dependence condition on manifolds, we show that the proposed method converges to a stationary point of the nonsmooth manifold optimization problem. Moreover, we propose a globalized semismooth Newton method to solve the augmented Lagrangian subproblem on manifolds efficiently. The local superlinear convergence of the manifold semismooth Newton method is also established under some suitable conditions. We also prove that the semismoothness on submanifolds can be inherited from that in the ambient manifold. Finally, numerical experiments on compressed modes and (constrained) sparse principal component analysis illustrate the advantages of the proposed method. [ABSTRACT FROM AUTHOR]

There are many important practical optimization problems whose feasible regions are not known to be nonempty or not, and optimizers of the objective function with the least constraint violation prefer to be found. A natural way for dealing with these problems is to extend the nonlinear optimization problem as the one optimizing the objective function over the set of points with the least constraint violation. This leads to the study of the shifted problem. This paper focuses on the constrained convex optimization problem. The sufficient condition for the closedness of the set of feasible shifts is presented and the continuity properties of the optimal value function and the solution mapping for the shifted problem are studied. Properties of the conjugate dual of the shifted problem are discussed through the relations between the dual function and the optimal value function. The solvability of the dual of the optimization problem with the least constraint violation is investigated. It is shown that, if the least violated shift is in the domain of the subdifferential of the optimal value function, then this dual problem has an unbounded solution set. Under this condition, the optimality conditions for the problem with the least constraint violation are established in term of the augmented Lagrangian. It is shown that the augmented Lagrangian method has the properties that the sequence of shifts converges to the least violated shift and the sequence of multipliers is unbounded. Moreover, it is proved that the augmented Lagrangian method is able to find an approximate solution to the problem with the least constraint violation and it has linear rate of convergence under an error bound condition. The augmented Lagrangian method is applied to an illustrative convex second-order cone constrained optimization problem with least constraint violation and numerical results verify our theoretical results. [ABSTRACT FROM AUTHOR]

This paper is devoted to the theoretical and numerical investigation of an augmented Lagrangian method for the solution of optimization problems with geometric constraints. Specifically, we study situations where parts of the constraints are nonconvex and possibly complicated, but allow for a fast computation of projections onto this nonconvex set. Typical problem classes which satisfy this requirement are optimization problems with disjunctive constraints (like complementarity or cardinality constraints) as well as optimization problems over sets of matrices which have to satisfy additional rank constraints. The key idea behind our method is to keep these complicated constraints explicitly in the constraints and to penalize only the remaining constraints by an augmented Lagrangian function. The resulting subproblems are then solved with the aid of a problem-tailored nonmonotone projected gradient method. The corresponding convergence theory allows for an inexact solution of these subproblems. Nevertheless, the overall algorithm computes so-called Mordukhovich-stationary points of the original problem under a mild asymptotic regularity condition, which is generally weaker than most of the respective available problem-tailored constraint qualifications. Extensive numerical experiments addressing complementarity- and cardinality-constrained optimization problems as well as a semidefinite reformulation of MAXCUT problems visualize the power of our approach. [ABSTRACT FROM AUTHOR]

We study the convergence rate of the famous Symmetric Rank-1 (SR1) algorithm, which has wide applications in different scenarios. Although it has been extensively investigated, SR1 still lacks a non-asymptotic superlinear rate compared with other quasi-Newton methods such as DFP and BFGS. In this paper, we address the aforementioned issue to obtain the first explicit non-asymptotic rates of superlinear convergence for the vanilla SR1 methods with a correction strategy that is used to achieve numerical stability. Specifically, the vanilla SR1 with the correction strategy achieves the rate of the form 2 n ln (4 ϰ) k k / 2 for general smooth strongly-convex functions where k is the iteration counter, ϰ is the condition number of the objective function, and n is the dimensionality of the problem. Furthermore, the vanilla SR1 algorithm enjoys a little faster convergence rate and can find the optima of the quadratic objective function at most n steps. [ABSTRACT FROM AUTHOR]

In this paper, we present difference of convex algorithms for solving bilevel programs in which the upper level objective functions are difference of convex functions, and the lower level programs are fully convex. This nontrivial class of bilevel programs provides a powerful modelling framework for dealing with applications arising from hyperparameter selection in machine learning. Thanks to the full convexity of the lower level program, the value function of the lower level program turns out to be convex and hence the bilevel program can be reformulated as a difference of convex bilevel program. We propose two algorithms for solving the reformulated difference of convex program and show their convergence to stationary points under very mild assumptions. Finally we conduct numerical experiments to a bilevel model of support vector machine classification. [ABSTRACT FROM AUTHOR]

Due to their relation to the linear complementarity problem, absolute value equations have been intensively studied recently. In this paper, we present error bound conditions for absolute value equations. Along with the error bounds, we introduce a condition number. We consider general scaled matrix p-norms, as well as particular p-norms. We discuss basic properties of the condition number, including its computational complexity. We present various bounds on the condition number, and we give exact formulae for special classes of matrices. Moreover, we consider matrices that appear based on the transformation from the linear complementarity problem. Finally, we apply the error bound to convergence analysis of two methods for solving absolute value equations. [ABSTRACT FROM AUTHOR]

This paper proposes an accelerated proximal point method for maximally monotone operators. The proof is computer-assisted via the performance estimation problem approach. The proximal point method includes various well-known convex optimization methods, such as the proximal method of multipliers and the alternating direction method of multipliers, and thus the proposed acceleration has wide applications. Numerical experiments are presented to demonstrate the accelerating behaviors. [ABSTRACT FROM AUTHOR]

The paper is devoted to the existence of global optimal solutions for a general class of nonsmooth problems of constrained vector optimization without boundedness assumptions on constraint set. The main attention is paid to the two major notions of optimality in vector problems: Pareto efficiency and proper efficiency in the sense of Geoffrion. Employing adequate tools of variational analysis and generalized differentiation, we first establish relationships between the notions of properness, M-tameness, and the Palais–Smale conditions formulated for the restriction of the vector cost mapping on the constraint set. These results are instrumental to derive verifiable necessary and sufficient conditions for the existence of Pareto efficient solutions in vector optimization. Furthermore, the developed approach allows us to obtain new sufficient conditions for the existence of Geoffrion-properly efficient solutions to such constrained vector problems. [ABSTRACT FROM AUTHOR]

We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items and a set of metaitems. This problem generalizes the problem introduced by Ahmed S, Atamtürk A (Mathematical programming 128(1-2):149–169, 2011), and it can be modeled as a mixed integer nonlinear program involving binary decision variables associated with the items and metaitems. Its goal is to find a subset of metaitems that maximizes the total utility corresponding to the items it covers. It has applications to, among others, maximal covering location, and influence maximization problems. In the paper, we propose a double-hypograph decomposition which allows for projecting out the variables associated with the items by separately exploiting the structural properties of the utility function and of the set-union operator. Thanks to it, the utility function is linearized via an exact outer-approximation technique, whereas the set-union operator is linearized in two ways: either (i) via a reformulation based on submodular cuts, or (ii) via a Benders decomposition. We analyze from a theoretical perspective the strength of the inequalities of the resulting reformulations, and embed them into two branch-and-cut algorithms. We also show how to extend our reformulations to the case where the utility function is not necessarily increasing. We then experimentally compare our algorithms inter se, to a standard reformulation based on submodular cuts, to a state-of-the-art global-optimization solver, and to the greedy algorithm for the maximization of a submodular function. The results reveal that, on our testbed, the method based on combining an outer approximation with Benders cuts significantly outperforms the other ones. [ABSTRACT FROM AUTHOR]

In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with non-Lipschitzian value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MS-MINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a (T + 1) -stage stochastic MINLP satisfying L-exact Lipschitz regularization with d-dimensional state spaces, to obtain an ε -optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by O ((2 L T ε) d) , and is lower bounded by O ((LT 4 ε) d) for the general case or by O ((LT 8 ε) d / 2 - 1) for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity depends polynomially on the number of stages. We further show that the iteration complexity depends linearly on T, if all the state spaces are finite sets, or if we seek a (T ε) -optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale with T. To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixed-integer optimization. [ABSTRACT FROM AUTHOR]

The sparse nonlinear programming (SNP) problem has wide applications in signal and image processing, machine learning and finance, etc. However, the computational challenge posed by SNP has not yet been well resolved due to the nonconvex and discontinuous ℓ 0 -norm involved. In this paper, we resolve this numerical challenge by developing a fast Newton-type algorithm. As a theoretical cornerstone, we establish a first-order optimality condition for SNP based on the concept of strong β -Lagrangian stationarity via the Lagrangian function, and reformulate it as a system of nonlinear equations called the Lagrangian equations. The nonsingularity of the corresponding Jacobian is discussed, based on which the Lagrange–Newton algorithm (LNA) is then proposed. Under mild conditions, we establish the locally quadratic convergence and its iterative complexity estimation. To further demonstrate the efficiency and superiority of our proposed algorithm, we apply LNA to two specific problems arising from compressed sensing and sparse high-order portfolio selection, in which significant benefits accrue from the restricted Newton step. [ABSTRACT FROM AUTHOR]

Semidefinite programming (SDP) with diagonal constraints arise in many optimization problems, such as Max-Cut, community detection and group synchronization. Although SDPs can be solved to arbitrary precision in polynomial time, generic convex solvers do not scale well with the dimension of the problem. In order to address this issue, Burer and Monteiro (Math Program 95(2):329–357, 2003) proposed to reduce the dimension of the problem by appealing to a low-rank factorization and solve the subsequent non-convex problem instead. In this paper, we present coordinate ascent based methods to solve this non-convex problem with provable convergence guarantees. More specifically, we prove that the block-coordinate maximization algorithm applied to the non-convex Burer–Monteiro method globally converges to a first-order stationary point with a sublinear rate without any assumptions on the problem. We further show that this algorithm converges linearly around a local maximum provided that the objective function exhibits quadratic decay. We establish that this condition generically holds when the rank of the factorization is sufficiently large. Furthermore, incorporating Lanczos method to the block-coordinate maximization, we propose an algorithm that is guaranteed to return a solution that provides 1 - O 1 / r approximation to the original SDP without any assumptions, where r is the rank of the factorization. This approximation ratio is known to be optimal (up to constants) under the unique games conjecture, and we can explicitly quantify the number of iterations to obtain such a solution. [ABSTRACT FROM AUTHOR]

This paper concerns the worst-case complexity of cyclic coordinate descent (C-CD) for minimizing a convex quadratic function, which is equivalent to Gauss–Seidel method, Kaczmarz method and projection onto convex sets (POCS) in this simple setting. We observe that the known provable complexity of C-CD can be O (n 2) times slower than randomized coordinate descent (R-CD), but no example was proven to exhibit such a large gap. In this paper we show that the gap indeed exists. We prove that there exists an example for which C-CD takes at least O (n 4 κ CD log 1 ϵ) operations, where κ CD is related to Demmel's condition number and it determines the convergence rate of R-CD. It implies that in the worst case C-CD can indeed be O (n 2) times slower than R-CD, which has complexity O (n 2 κ CD log 1 ϵ) . Note that for this example, the gap exists for any fixed update order, not just a particular order. An immediate consequence is that for Gauss–Seidel method, Kaczmarz method and POCS, there is also an O (n 2) gap between the cyclic versions and randomized versions (for solving linear systems). One difficulty with the analysis is that the spectral radius of a non-symmetric iteration matrix does not necessarily constitute a lower bound for the convergence rate. Finally, we design some numerical experiments to show that the size of the off-diagonal entries is an important indicator of the practical performance of C-CD. [ABSTRACT FROM AUTHOR]

In this paper, we consider nonsmooth convex optimization problems with additive structure featuring independent oracles (black-boxes) working in parallel. Existing methods for solving these distributed problems in a general form are synchronous, in the sense that they wait for the responses of all the oracles before performing a new iteration. In this paper, we propose level bundle methods handling asynchronous oracles. These methods require original upper-bounds (using upper-models or scarce coordinations) to deal with asynchronicity. We prove their convergence using variational-analysis techniques and illustrate their practical performance on a Lagrangian decomposition problem. [ABSTRACT FROM AUTHOR]

In this paper, we propose and analyze a trust-region model-based algorithm for solving unconstrained stochastic optimization problems. Our framework utilizes random models of an objective function f(x), obtained from stochastic observations of the function or its gradient. Our method also utilizes estimates of function values to gauge progress that is being made. The convergence analysis relies on requirements that these models and these estimates are sufficiently accurate with high enough, but fixed, probability. Beyond these conditions, no assumptions are made on how these models and estimates are generated. Under these general conditions we show an almost sure global convergence of the method to a first order stationary point. In the second part of the paper, we present examples of generating sufficiently accurate random models under biased or unbiased noise assumptions. Lastly, we present some computational results showing the benefits of the proposed method compared to existing approaches that are based on sample averaging or stochastic gradients. [ABSTRACT FROM AUTHOR]

We study the local convergence of classical quasi-Newton methods for nonlinear optimization. Although it was well established a long time ago that asymptotically these methods converge superlinearly, the corresponding rates of convergence still remain unknown. In this paper, we address this problem. We obtain first explicit non-asymptotic rates of superlinear convergence for the standard quasi-Newton methods, which are based on the updating formulas from the convex Broyden class. In particular, for the well-known DFP and BFGS methods, we obtain the rates of the form (n L 2 μ 2 k) k / 2 and (nL μ k) k / 2 respectively, where k is the iteration counter, n is the dimension of the problem, μ is the strong convexity parameter, and L is the Lipschitz constant of the gradient. [ABSTRACT FROM AUTHOR]

In this paper we consider the minimization of a continuous function that is potentially not differentiable or not twice differentiable on the boundary of the feasible region. By exploiting an interior point technique, we present first- and second-order optimality conditions for this problem that reduces to classical ones when the derivative on the boundary is available. For this type of problems, existing necessary conditions often rely on the notion of subdifferential or become non-trivially weaker than the KKT condition in the (twice-)differentiable counterpart problems. In contrast, this paper presents a new set of first- and second-order necessary conditions that are derived without the use of subdifferential and reduce to exactly the KKT condition when (twice-)differentiability holds. As a result, these conditions are stronger than some existing ones considered for the discussed minimization problem when only non-negativity constraints are present. To solve for these optimality conditions in the special but important case of linearly constrained problems, we present two novel interior point trust-region algorithms and show that their worst-case computational efficiency in achieving the potentially stronger optimality conditions match the best known complexity bounds. Since this work considers a more general problem than those in the literature, our results also indicate that best known existing complexity bounds are actually held for a wider class of nonlinear programming problems. This new development is significant since optimality conditions play a fundamental role in computational optimization and more and more nonlinear and nonconvex problems need to be solved in practice. [ABSTRACT FROM AUTHOR]

This paper addresses the question of whether it can be beneficial for an optimization algorithm to follow directions of negative curvature. Although prior work has established convergence results for algorithms that integrate both descent and negative curvature steps, there has not yet been extensive numerical evidence showing that such methods offer consistent performance improvements. In this paper, we present new frameworks for combining descent and negative curvature directions: alternating two-step approaches and dynamic step approaches. The aspect that distinguishes our approaches from ones previously proposed is that they make algorithmic decisions based on (estimated) upper-bounding models of the objective function. A consequence of this aspect is that our frameworks can, in theory, employ fixed stepsizes, which makes the methods readily translatable from deterministic to stochastic settings. For deterministic problems, we show that instances of our dynamic framework yield gains in performance compared to related methods that only follow descent steps. We also show that gains can be made in a stochastic setting in cases when a standard stochastic-gradient-type method might make slow progress. [ABSTRACT FROM AUTHOR]

In this paper, we devise new relaxations for composite functions, which improve the prevalent factorable relaxations, without introducing additional variables, by exploiting the inner-function structure. We outer-approximate inner-functions using arbitrary under- and over-estimators and then convexify the outer-function over a polytope P, which models the ordering relationships between the inner-functions and their estimators and utilizes bound information on the inner-functions as well as on the estimators. We show that there is a subset Q of P, with significantly simpler combinatorial structure, such that the separation problem of the graph of the outer-function over P is polynomially equivalent, via a fast combinatorial algorithm, to that of its graph over Q. We specialize our study to consider the product of two inner-functions with one non-trivial underestimator for each inner-function. For the corresponding polytope P, we show that there are eight valid inequalities besides the four McCormick inequalities, which improve the factorable relaxation. Finally, we show that our results generalize to simultaneous convexification of a vector of outer-functions. [ABSTRACT FROM AUTHOR]

In this paper we will establish some necessary condition and sufficient condition respectively for a set-valued mapping to have the Lipschitz-like property relative to a closed set by employing regular normal cone and limiting normal cone of a restricted graph of the set-valued mapping. We will obtain a complete characterization for a set-valued mapping to have the Lipschitz-property relative to a closed and convex set by virtue of the projection of the coderivative onto a tangent cone. Furthermore, by introducing a projectional coderivative of set-valued mappings, we establish a verifiable generalized Mordukhovich criterion for the Lipschitz-like property relative to a closed and convex set. We will study the representation of the graphical modulus of a set-valued mapping relative to a closed and convex set by using the outer norm of the corresponding projectional coderivative value. For an extended real-valued function, we will apply the obtained results to investigate its Lipschitz continuity relative to a closed and convex set and the Lipschitz-like property of a level-set mapping relative to a half line. [ABSTRACT FROM AUTHOR]

Bilevel optimization problems have received a lot of attention in the last years and decades. Besides numerous theoretical developments there also evolved novel solution algorithms for mixed-integer linear bilevel problems and the most recent algorithms use branch-and-cut techniques from mixed-integer programming that are especially tailored for the bilevel context. In this paper, we consider MIQP-QP bilevel problems, i.e., models with a mixed-integer convex-quadratic upper level and a continuous convex-quadratic lower level. This setting allows for a strong-duality-based transformation of the lower level which yields, in general, an equivalent nonconvex single-level reformulation of the original bilevel problem. Under reasonable assumptions, we can derive both a multi- and a single-tree outer-approximation-based cutting-plane algorithm. We show finite termination and correctness of both methods and present extensive numerical results that illustrate the applicability of the approaches. It turns out that the proposed methods are capable of solving bilevel instances with several thousand variables and constraints and significantly outperform classical solution approaches. [ABSTRACT FROM AUTHOR]

A nonlinear stepsize control framework for unconstrained optimization was recently proposed by Toint (Optim Methods Softw 28:82-95, ), providing a unified setting in which the global convergence can be proved for trust-region algorithms and regularization schemes. The original analysis assumes that the Hessians of the models are uniformly bounded. In this paper, the global convergence of the nonlinear stepsize control algorithm is proved under the assumption that the norm of the Hessians can grow by a constant amount at each iteration. The worst-case complexity is also investigated. The results obtained for unconstrained smooth optimization are extended to some algorithms for composite nonsmooth optimization and unconstrained multiobjective optimization as well. [ABSTRACT FROM AUTHOR]

The problem of minimizing a polynomial over the standard simplex is one of the basic NP-hard nonlinear optimization problems-it contains the maximum clique problem in graphs as a special case. It is known that the problem allows a polynomial-time approximation scheme (PTAS) for polynomials of fixed degree, which is based on polynomial evaluations at the points of a sequence of regular grids. In this paper, we provide an alternative proof of the PTAS property. The proof relies on the properties of Bernstein approximation on the simplex. We also refine a known error bound for the scheme for polynomials of degree three. The main contribution of the paper is to provide new insight into the PTAS by establishing precise links with Bernstein approximation and the multinomial distribution. [ABSTRACT FROM AUTHOR]

This paper studies an extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with $$m$$ linear inequality constraints. When $$m=0,\,m = 1$$ , or $$m = 2$$ and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial time. However, it is also known that, when $$m \ge 2$$ and at least two of the linear constraints intersect within the ball, i.e., some feasible point of the eTRS satisfies both linear constraints at equality, then the same convex relaxation may admit a gap with eTRS. This paper shows that the convex relaxation has no gap for arbitrary $$m$$ as long as the linear constraints are non-intersecting. [ABSTRACT FROM AUTHOR]

Adjustable robust optimization (ARO) generally produces better worst-case solutions than static robust optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we provide conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that when the uncertainty is constraint-wise, the problem is convex with respect to the adjustable variables and concave with respect to the uncertain parameters, the adjustable variables lie in a convex and compact set and the uncertainty set is convex and compact, then robust solutions are also optimal for the corresponding ARO problem. Furthermore, we prove that if some of the uncertain parameters are constraint-wise and the rest are not, then under a similar set of assumptions there is an optimal decision rule for the ARO problem that does not depend on the constraint-wise uncertain parameters. Also, we show for a class of problems that using affine decision rules that depend on all of the uncertain parameters yields the same optimal objective value as when the rules depend solely on the non-constraint-wise uncertain parameters. Finally, we illustrate the usefulness of these results by applying them to convex quadratic and conic quadratic problems. [ABSTRACT FROM AUTHOR]

A strategy is proposed for characterizing the worst-case performance of algorithms for solving nonconvex smooth optimization problems. Contemporary analyses characterize worst-case performance by providing, under certain assumptions on an objective function, an upper bound on the number of iterations (or function or derivative evaluations) required until a pth-order stationarity condition is approximately satisfied. This arguably leads to conservative characterizations based on certain objectives rather than on ones that are typically encountered in practice. By contrast, the strategy proposed in this paper characterizes worst-case performance separately over regions comprising a search space. These regions are defined generically based on properties of derivative values. In this manner, one can analyze the worst-case performance of an algorithm independently from any particular class of objectives. Then, once given a class of objectives, one can obtain a tailored complexity analysis merely by delineating the types of regions that comprise the search spaces for functions in the class. Regions defined by first- and second-order derivatives are discussed in detail and example complexity analyses are provided for a few standard first- and second-order algorithms when employed to minimize convex and nonconvex objectives of interest. It is also explained how the strategy can be generalized to regions defined by higher-order derivatives and for analyzing the behavior of higher-order algorithms. [ABSTRACT FROM AUTHOR]

This paper studies high-order evaluation complexity for partially separable convexly-constrained optimization involving non-Lipschitzian group sparsity terms in a nonconvex objective function. We propose a partially separable adaptive regularization algorithm using a pth order Taylor model and show that the algorithm needs at most O (ϵ - (p + 1) / (p - q + 1)) evaluations of the objective function and its first p derivatives (whenever they exist) to produce an (ϵ , δ) -approximate qth-order stationary point. Our algorithm uses the underlying rotational symmetry of the Euclidean norm function to build a Lipschitzian approximation for the non-Lipschitzian group sparsity terms, which are defined by the group ℓ 2 – ℓ a norm with a ∈ (0 , 1) . The new result shows that the partially-separable structure and non-Lipschitzian group sparsity terms in the objective function do not affect the worst-case evaluation complexity order. [ABSTRACT FROM AUTHOR]

In this paper we consider a class of non-Lipschitz and non-convex minimization problems which generalize the $$L_2$$ - $$L_p$$ minimization problem. We propose an iterative algorithm that decides the next iteration based on the local convexity/concavity/sparsity of its current position. We show that our algorithm finds an $$\epsilon $$ -KKT point within $$O(\log {\epsilon ^{-1}})$$ iterations from certain initial points. The same result is also applied to the problem with general linear constraints under mild conditions. [ABSTRACT FROM AUTHOR]

This paper considers a class of stochastic second-order-cone complementarity problems (SSOCCP), which are generalizations of the noticeable stochastic complementarity problems and can be regarded as the Karush-Kuhn-Tucker conditions of some stochastic second-order-cone programming problems. Due to the existence of random variables, the SSOCCP may not have a common solution for almost every realization . In this paper, motivated by the works on stochastic complementarity problems, we present a deterministic formulation called the expected residual minimization formulation for SSOCCP. We present an approximation method based on the Monte Carlo approximation techniques and investigate some properties related to existence of solutions of the ERM formulation. Furthermore, we experiment some practical applications, which include a stochastic natural gas transmission problem and a stochastic optimal power flow problem in radial network. [ABSTRACT FROM AUTHOR]

This note provides a counterexample to a theorem announced in the last part of the paper (Vicente and Custódio Math Program 133:299–325, 2012). The counterexample involves an objective function f:R→R\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$f: \mathbb {R}\rightarrow \mathbb {R}$$\end{document} which satisfies all the assumptions required by the theorem but contradicts some of its conclusions. A corollary of this theorem is also affected by this counterexample. The main flaw revealed by the counterexample is the possibility that a directional direct search method (dDSM) generates a sequence of trial points (xk)k∈N\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(x_k)_{k \in \mathbb {N}}$$\end{document} converging to a point x∗\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$x_*$$\end{document} where f is discontinuous, lower semicontinuous and whose objective function value f(x∗)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$f(x_*)$$\end{document} is strictly less than limk→∞f(xk)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\lim _{k\rightarrow \infty } f(x_k)$$\end{document}. Moreover the dDSM generates trial points in only one of the continuity sets of f near x∗\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$x_*$$\end{document}. This note also investigates the proof of the theorem to highlight the inexact statements in the original paper. Finally this work introduces a modification of the dDSM that allows, in usual cases, to recover the properties broken by the counterexample. [ABSTRACT FROM AUTHOR]

We consider optimization algorithms that successively minimize simple Taylor-like models of the objective function. Methods of Gauss–Newton type for minimizing the composition of a convex function and a smooth map are common examples. Our main result is an explicit relationship between the step-size of any such algorithm and the slope of the function at a nearby point. Consequently, we (1) show that the step-sizes can be reliably used to terminate the algorithm, (2) prove that as long as the step-sizes tend to zero, every limit point of the iterates is stationary, and (3) show that conditions, akin to classical quadratic growth, imply that the step-sizes linearly bound the distance of the iterates to the solution set. The latter so-called error bound property is typically used to establish linear (or faster) convergence guarantees. Analogous results hold when the step-size is replaced by the square root of the decrease in the model's value. We complete the paper with extensions to when the models are minimized only inexactly. [ABSTRACT FROM AUTHOR]

Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables by introducing additional auxiliary variables. In this paper we initiate a systematic study of these quadratization approaches. We provide tight lower and upper bounds on the number of auxiliary variables needed in the worst-case for general objective functions, for bounded-degree functions, and for a restricted class of quadratizations. Our upper bounds are constructive, thus yielding new quadratization procedures. Finally, we completely characterize all 'minimal' quadratizations of negative monomials. [ABSTRACT FROM AUTHOR]

This paper considers optimization problems with cardinality constraints. Based on a recently introduced reformulation of this problem as a nonlinear program with continuous variables, we first define some problem-tailored constraint qualifications and then show how these constraint qualifications can be used to obtain suitable optimality conditions for cardinality constrained problems. Here, the (KKT-like) optimality conditions hold under much weaker assumptions than the corresponding result that is known for the somewhat related class of mathematical programs with complementarity constraints. [ABSTRACT FROM AUTHOR]

In this paper, we propose a class of block coordinate proximal gradient (BCPG) methods for solving large-scale nonsmooth separable optimization problems. The proposed BCPG methods are based on the Bregman functions, which may vary at each iteration. These methods include many well-known optimization methods, such as the quasi-Newton method, the block coordinate descent method, and the proximal point method. For the proposed methods, we establish their global convergence properties when the blocks are selected by the Gauss-Seidel rule. Further, under some additional appropriate assumptions, we show that the convergence rate of the proposed methods is R-linear. We also present numerical results for a new BCPG method with variable kernels for a convex problem with separable simplex constraints. [ABSTRACT FROM AUTHOR]

This paper is concerned with the minimization of an objective that is the sum of a convex function f and an $$\ell _1$$ regularization term. Our interest is in active-set methods that incorporate second-order information about the function f to accelerate convergence. We describe a semismooth Newton framework that can be used to generate a variety of second-order methods, including block active set methods, orthant-based methods and a second-order iterative soft-thresholding method. The paper proposes a new active set method that performs multiple changes in the active manifold estimate at every iteration, and employs a mechanism for correcting these estimates, when needed. This corrective mechanism is also evaluated in an orthant-based method. Numerical tests comparing the performance of three active set methods are presented. [ABSTRACT FROM AUTHOR]

At each iteration of the augmented Lagrangian algorithm, a nonlinear subproblem is being solved. The number of inner iterations (of some/any method) needed to obtain a solution of the subproblem, or even a suitable approximate stationary point, is in principle unknown. In this paper we show that to compute an approximate stationary point sufficient to guarantee local superlinear convergence of the augmented Lagrangian iterations, it is enough to solve two quadratic programming problems (or two linear systems in the equality-constrained case). In other words, two inner Newtonian iterations are sufficient. To the best of our knowledge, such results are not available even under the strongest assumptions (of second-order sufficiency, strict complementarity, and the linear independence constraint qualification). Our analysis is performed under second-order sufficiency only, which is the weakest assumption for obtaining local convergence and rate of convergence of outer iterations of the augmented Lagrangian algorithm. The structure of the quadratic problems in question is related to the stabilized sequential quadratic programming and to second-order corrections. [ABSTRACT FROM AUTHOR]

In optimal control, switching structures demanding at most one control to be active at any time instance appear frequently. Discretizing such problems, a so-called mathematical program with switching constraints is obtained. Although these problems are related to other types of disjunctive programs like optimization problems with complementarity or vanishing constraints, their inherent structure makes a separate consideration necessary. Since standard constraint qualifications are likely to fail at the feasible points of switching-constrained optimization problems, stationarity notions which are weaker than the associated Karush–Kuhn–Tucker conditions need to be investigated in order to find applicable necessary optimality conditions. Furthermore, appropriately tailored constraint qualifications need to be formulated. In this paper, we introduce suitable notions of weak, Mordukhovich-, and strong stationarity for mathematical programs with switching constraints and present some associated constraint qualifications. Our findings are exploited to state necessary optimality conditions for (discretized) optimal control problems with switching constraints. Furthermore, we apply our results to optimization problems with either-or-constraints. First, a novel reformulation of such problems using switching constraints is presented. Second, the derived surrogate problem is exploited to obtain necessary optimality conditions for the original program. [ABSTRACT FROM AUTHOR]

In this paper, we present two new methods for solving convex mixed-integer nonlinear programming problems based on the outer approximation method. The first method is inspired by the level method and uses a regularization technique to reduce the step size when choosing new integer combinations. The second method combines ideas from both the level method and the sequential quadratic programming technique and uses a second order approximation of the Lagrangean when choosing the new integer combinations. The main idea behind the methods is to choose the integer combination more carefully at each iteration, in order to obtain the optimal solution in fewer iterations compared to the original outer approximation method. We prove rigorously that both methods will find and verify the optimal solution in a finite number of iterations. Furthermore, we present a numerical comparison of the methods based on 109 test problems to illustrate their advantages. [ABSTRACT FROM AUTHOR]

Sequential optimality conditions have played a major role in unifying and extending global convergence results for several classes of algorithms for general nonlinear optimization. In this paper, we extend theses concepts for nonlinear semidefinite programming. We define two sequential optimality conditions for nonlinear semidefinite programming. The first is a natural extension of the so-called Approximate-Karush–Kuhn–Tucker (AKKT), well known in nonlinear optimization. The second one, called Trace-AKKT, is more natural in the context of semidefinite programming as the computation of eigenvalues is avoided. We propose an augmented Lagrangian algorithm that generates these types of sequences and new constraint qualifications are proposed, weaker than previously considered ones, which are sufficient for the global convergence of the algorithm to a stationary point. [ABSTRACT FROM AUTHOR]

We consider global efficiency of algorithms for minimizing a sum of a convex function and a composition of a Lipschitz convex function with a smooth map. The basic algorithm we rely on is the prox-linear method, which in each iteration solves a regularized subproblem formed by linearizing the smooth map. When the subproblems are solved exactly, the method has efficiency O (ε - 2) , akin to gradient descent for smooth minimization. We show that when the subproblems can only be solved by first-order methods, a simple combination of smoothing, the prox-linear method, and a fast-gradient scheme yields an algorithm with complexity O ~ (ε - 3) . We round off the paper with an inertial prox-linear method that automatically accelerates in presence of convexity. [ABSTRACT FROM AUTHOR]

This paper studies a general form problem in which a lower bounded continuously differentiable function is minimized over a block separable set incorporating a group sparsity expression as a constraint or a penalty (or both) in the group sparsity setting. This class of problems is generally hard to solve, yet highly applicable in numerous practical settings. Particularly, we study the proximal mapping that includes group-sparsity terms, and derive an efficient method to compute it. Necessary optimality conditions for the problem are devised, and a hierarchy between stationary-based and coordinate-wised based conditions is established. Methods that obtain points satisfying the optimality conditions are presented, analyzed and tested in applications from the fields of investment and graph theory. [ABSTRACT FROM AUTHOR]