Nonlinear Optimization

A Relaxed-Projection Splitting Algorithm for Variational Inequalities in Hilbert Spaces

  • Yunier Bello-Cruz
  • R. Diaz Millan
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    We introduce a relaxed-projection splitting algorithm for solving variational inequalities in Hilbert spaces for the sum of nonsmooth maximal monotone operators, where the feasible set is defined by a nonlinear and nonsmooth continuous convex function inequality. In our scheme, the orthogonal projections onto the feasible set are replaced by projections onto separating hyperplanes. Furthermore, each … Read more

    Lagrangean Decomposition for Mean-Variance Combinatorial Optimization

  • Frank Baumann
  • Christoph Buchheim
  • Anna Ilyina
    • Categories Combinatorial Optimization, Constrained Nonlinear Optimization, Robust Optimization Tags , ,

    We address robust versions of combinatorial optimization problems, focusing on the uncorrelated ellipsoidal uncertainty case, which corresponds to so-called mean-variance optimization. We present a branch and bound-algorithm for such problems that uses lower bounds obtained from Lagrangean decomposition. This approach allows to separate the uncertainty aspect in the objective function from the combinatorial structure of … Read more

    Active Set Methods with Reoptimization for Convex Quadratic Integer Programming

  • Christoph Buchheim
  • Long Trieu
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Quadratic Programming Tags , ,

    We present a fast branch-and-bound algorithm for solving convex quadratic integer programs with few linear constraints. In each node, we solve the dual problem of the continuous relaxation using an infeasible active set method proposed by Kunisch and Rendl to get a lower bound; this active set algorithm is well suited for reoptimization. Our algorithm … Read more

    Penalty Methods with Stochastic Approximation for Stochastic Nonlinear Programming

  • Shiqian Ma
  • Xiao Wang
  • Ya-xiang Yuan
    • Categories Nonlinear Optimization, Stochastic Programming

    In this paper, we propose a class of penalty methods with stochastic approximation for solving stochastic nonlinear programming problems. We assume that only noisy gradients or function values of the objective function are available via calls to a stochastic first-order or zeroth-order oracle. In each iteration of the proposed methods, we minimize an exact penalty … Read more

    A Revisit to Quadratic Programming with One Inequality Quadratic Constraint via Matrix Pencil

  • Lin Gang-Xuan
  • Sheu Ruey-Lin
  • Hsia Yong
    • Categories Global Optimization Theory, Quadratic Programming Tags , , , , ,

    The quadratic programming over one inequality quadratic constraint (QP1QC) is a very special case of quadratically constrained quadratic programming (QCQP) and attracted much attention since early 1990’s. It is now understood that, under the primal Slater condition, (QP1QC) has a tight SDP relaxation (PSDP). The optimal solution to (QP1QC), if exists, can be obtained by … Read more

    Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity

  • Sheu Ruey-Lin
  • Hsia Yong
    • Categories Global Optimization Theory, Quadratic Programming

    The trust region subproblem with a fixed number m additional linear inequality constraints, denoted by (T_m), have drawn much attention recently. The question as to whether Problem ( T_m) is in Class P or Class NP remains open. So far, the only affirmative general result is that (T_1) has an exact SOCP/SDP reformulation and thus … Read more

    Updating constraint preconditioners for KKT systems in quadratic programming via low-rank corrections

  • Stefania Bellavia
  • Valentina De Simone
  • Daniela di Serafino
  • Benedetta Morini
    • Categories Quadratic Programming Tags , , , ,

    This work focuses on the iterative solution of sequences of KKT linear systems arising in interior point methods applied to large convex quadratic programming problems. This task is the computational core of the interior point procedure and an efficient preconditioning strategy is crucial for the efficiency of the overall method. Constraint preconditioners are very effective … Read more

    On Efficiently Combining Limited Memory and Trust-Region Techniques

  • Oleg Burdakov
  • Lujin Gong
  • Ya-xiang Yuan
  • Spartak Zikrin
    • Categories Unconstrained Optimization

    Limited memory quasi-Newton methods and trust-region methods represent two efficient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited memory methods are usually combined with a line search. We show how to efficiently … Read more

    A Primal Heuristic for MINLP based on Dual Information

  • Armin Fügenschuh
  • Jesco Humpola
  • Thomas Lehmann
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Meta Heuristics

    We present a novel heuristic algorithm to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network’s capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the … Read more

    Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs

  • Immanuel M. Bomze
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , ,

    We study non-convex quadratic minimization problems under (possibly non-convex) quadratic and linear constraints, and characterize both Lagrangian and Semi-Lagrangian dual bounds in terms of conic optimization. While the Lagrangian dual is equivalent to the SDP relaxation (which has been known for quite a while, although the presented form, incorporating explicitly linear constraints, seems to be … Read more