Constrained Nonlinear Optimization

Strengthening the SDP Relaxation of AC Power Flows with Convex Envelopes, Bound Tightening, and Lifted Nonlinear Cuts

  • Carleton Coffrin
  • Hassan L. Hijazi
  • Pascal Van Hentenryck
    • Categories Applications - OR and Management Sciences, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , ,

    This paper considers state-of-the-art convex relaxations for the AC power flow equations and introduces new valid cuts based on convex envelopes and lifted nonlinear constraints. These valid linear inequalities strengthen existing semidefinite and quadratic programming relaxations and dominate existing cuts proposed in the litterature. Together with model intersections and bound tightening, the new linear cuts … Read more

    Solutions of a constrained Hermitian matrix-valued function optimization problem with applications

  • Yongge Tian
    • Categories Constrained Nonlinear Optimization Tags

    Let $f(X) =\left( XC + D\right)M\left(XC + D \right)^{*} – G$ be a given nonlinear Hermitian matrix-valued function with $M = M^*$ and $G = G^*$, and assume that the variable matrix $X$ satisfies the consistent linear matrix equation $XA = B$. This paper shows how to characterize the semi-definiteness of $f(X)$ subject to all … Read more

    Global Convergence of ADMM in Nonconvex Nonsmooth Optimization

  • Yu Wang
  • Wotao Yin
  • Jinshan Zeng
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, $\phi(x_1,\ldots,x_p,y)$, subject to linear equality constraints that couple $x_1,\ldots,x_p,y$, where $p\ge 1$ is an integer. Our ADMM sequentially updates the primal variables in the order $x_1,\ldots,x_p,y$, followed by updating the dual … Read more

    Strict Constraint Qualifications and Sequential Optimality Conditions for Constrained Optimization

  • Roberto Andreani
  • José Mario Martínez
  • Alberto Ramos
  • Paulo J. S. Silva
    • Categories Constrained Nonlinear Optimization Tags , , , , , ,

    Sequential optimality conditions for constrained optimization are necessarily satisfied by local minimizers, independently of the fulfillment of constraint qualifications. These conditions support the employment of different stopping criteria for practical optimization algorithms. On the other hand, when an appropriate strict constraint qualification associated with some sequential optimality condition holds at a point that satisfies the … Read more

    hBcnorm regularization algorithms for optimization over permutation matrices

  • Bo Jiang
  • Ya-Feng Liu
  • Zaiwen Wen
    • Categories 0-1 Programming, Constrained Nonlinear Optimization Tags , , , , , ,

    Optimization problems over permutation matrices appear widely in facility layout, chip design, scheduling, pattern recognition, computer vision, graph matching, etc. Since this problem is NP-hard due to the combinatorial nature of permutation matrices, we relax the variable to be the more tractable doubly stochastic matrices and add an $L_p$-norm ($0 < p < 1$) regularization ... Read more

    Relationships between constrained and unconstrained multi-objective optimization and application in location theory

  • Christian Günther
  • Christiane Tammer
    • Categories Constrained Nonlinear Optimization, Generalized Convexity/Monoticity, Multi-Criteria Optimization

    This article deals with constrained multi-objective optimization problems. The main purpose of the article is to investigate relationships between constrained and unconstrained multi-objective optimization problems. Under suitable assumptions (e.g., generalized convexity assumptions) we derive a characterization of the set of (strictly, weakly) efficient solutions of a constrained multi-objective optimization problem using characterizations of the sets … Read more

    Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of $O(\epsilon^{-3/2})$ proved by Cartis, Gould and Toint (IMAJNA 32(4) 2012, pp.1662-1695) for computing an $\epsilon$-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are … Read more

    Polynomial SDP Cuts for Optimal Power Flow

  • Carleton Coffrin
  • Hassan L. Hijazi
  • Pascal Van Hentenryck
    • Categories Applications - OR and Management Sciences, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    The use of convex relaxations has lately gained considerable interest in Power Systems. These relaxations play a major role in providing quality guarantees for non-convex optimization problems. For the Optimal Power Flow (OPF) prob- lem, the semidefinite programming (SDP) relaxation is known to produce tight lower bounds. Unfortunately, SDP solvers still suffer from a lack … Read more

    On the convergence rate of grid search for polynomial optimization over the simplex

  • Etienne de Klerk
  • Monique Laurent
  • Zhao Sun
  • Juan C. Vera
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory Tags ,

    We consider the approximate minimization of a given polynomial on the standard simplex, obtained by taking the minimum value over all rational grid points with given denominator ${r} \in \mathbb{N}$. It was shown in [De Klerk, E., Laurent, M., Sun, Z.: An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric … Read more

    Algorithms for the power-$ Steiner tree problem in the Euclidean plane

  • Christina Burt
  • Alysson Machado Costa
  • Charl Ras
    • Categories Combinatorial Optimization, Constrained Nonlinear Optimization Tags , ,

    We study the problem of constructing minimum power-$p$ Euclidean $k$-Steiner trees in the plane. The problem is to find a tree of minimum cost spanning a set of given terminals where, as opposed to the minimum spanning tree problem, at most $k$ additional nodes (Steiner points) may be introduced anywhere in the plane. The cost … Read more