Search

This work attempts to combine the strengths of two major technologies that have matured over the last three decades: global mixed-integer nonlinear optimization and branch-and-price. We consider a class of generally nonconvex mixed-integer nonlinear programs (MINLPs) with linear complicating constraints and integer linking variables. If the complicating constraints are removed, the problem becomes easy to solve, e.g. due to decomposable structure. Integrality of the linking variables allows us to apply a discretization approach to derive a Dantzig-Wolfe reformulation and solve the problem to global optimality using branch-and-price. It is a remarkably simple idea; but to our surprise, it has barely found any application in the literature. In this work, we show that many relevant problems directly fall or can be reformulated into this class of MINLPs. We present the branch-and-price algorithm and demonstrate its effectiveness (and sometimes ineffectiveness) in an extensive computational study considering multiple large-scale problems of practical relevance, showing that, in many cases, orders-of-magnitude reductions in solution time can be achieved.

This paper presents a novel partially distributed outer approximation algorithm, named PaDOA, for solving a class of structured mixed integer convex programming problems to global optimality. The proposed scheme uses an iterative outer approximation method for coupled mixed integer optimization problems with separable convex objective functions, affine coupling constraints, and compact domain. PaDOA proceeds by alternating between solving large-scale structured mixed-integer linear programming problems and partially decoupled mixed-integer nonlinear programming subproblems that comprise much fewer integer variables. We establish conditions under which PaDOA converges to global minimizers after a finite number of iterations and verify these properties with an application to thermostatically controlled loads and to mixed-integer regression.

We study the problem of minimizing a convex function on a nonempty, finite subset of the integer lattice when the function cannot be evaluated at noninteger points. We propose a new underestimator that does not require access to (sub)gradients of the objective; such information is unavailable when the objective is a blackbox function. Rather, our underestimator uses secant linear functions that interpolate the objective function at previously evaluated points. These linear mappings are shown to underestimate the objective in disconnected portions of the domain. Therefore, the union of these conditional cuts provides a nonconvex underestimator of the objective. We propose an algorithm that alternates between updating the underestimator and evaluating the objective function. We prove that the algorithm converges to a global minimum of the objective function on the feasible set. We present two approaches for representing the underestimator and compare their computational effectiveness. We also compare implementations of our algorithm with existing methods for minimizing functions on a subset of the integer lattice. We discuss the difficulty of this problem class and provide insights into why a computational proof of optimality is challenging even for moderate problem sizes.

In this paper, we concentrate on generating cutting planes for the unsplittable capacitated network design problem. We use the unsplittable flow arc-set polyhedron of the considered problem as a substructure and generate cutting planes by solving the separation problem over it. To relieve the computational burden, we show that, in some special cases, a closed form of the separation problem can be derived. For the general case, a brute-force algorithm, called exact separation algorithm, is employed in solving the separation problem of the considered polyhedron such that the constructed inequality guarantees to be facet-defining. Furthermore, a new technique is presented to accelerate the exact separation algorithm, which significantly decreases the number of iterations in the algorithm. Finally, a comprehensive computational study on the unsplittable capacitated network design problem is presented to demonstrate the effectiveness of the proposed algorithm., 35 pages, 1 figure, accepted for publication in Journal of Global Optimization

The $\ell_p$ regularization problem with $0< p< 1$ has been widely studied for finding sparse solutions of linear inverse problems and gained successful applications in various mathematics and applied science fields. The proximal gradient algorithm is one of the most popular algorithms for solving the $\ell_p$ regularisation problem. In the present paper, we investigate the linear convergence issue of one inexact descent method and two inexact proximal gradient algorithms (PGA). For this purpose, an optimality condition theorem is explored to provide the equivalences among a local minimum, second-order optimality condition and second-order growth property of the $\ell_p$ regularization problem. By virtue of the second-order optimality condition and second-order growth property, we establish the linear convergence properties of the inexact descent method and inexact PGAs under some simple assumptions. Both linear convergence to a local minimal value and linear convergence to a local minimum are provided. Finally, the linear convergence results of the inexact numerical methods are extended to the infinite-dimensional Hilbert spaces., 28 pages

In this paper, we give a new penalized semidefinite programming approach for non-convex quadratically-constrained quadratic programs (QCQPs). We incorporate penalty terms into the objective of convex relaxations in order to retrieve feasible and near-optimal solutions for non-convex QCQPs. We introduce a generalized linear independence constraint qualification (GLICQ) criterion and prove that any GLICQ regular point that is sufficiently close to the feasible set can be used to construct an appropriate penalty term and recover a feasible solution. Inspired by these results, we develop a heuristic sequential procedure that preserves feasibility and aims to improve the objective value at each iteration. Numerical experiments on large-scale system identification problems as well as benchmark instances from the library of quadratic programming (QPLIB) demonstrate the ability of the proposed penalized semidefinite programs in finding near-optimal solutions for non-convex QCQP.

Relaxed constant positive linear dependence constraint qualification (RCPLD) for a system of smooth equalities and inequalities is a constraint qualification that is weaker than the usual constraint qualifications such as Mangasarian Fromovitz constraint qualification and the linear constraint qualification. Moreover RCPLD is known to induce an error bound property. In this paper we extend RCPLD to a very general feasibility system which may include Lipschitz continuous inequality constraints, complementarity constraints and abstract constraints. We show that this RCPLD for the general system is a constraint qualification for the optimality condition in terms of limiting subdifferential and limiting normal cone and it is a sufficient condition for the error bound property under the strict complementarity condition for the complementarity system and Clarke regularity conditions for the inequality constraints and the abstract constraint set. Moreover we introduce and study some sufficient conditions for RCPLD including the relaxed constant rank constraint qualification (RCRCQ). Finally we apply our results to the bilevel program.

We study the equivalence among a nonconvex QOP, its CPP and DNN relaxations under the assumption that the aggregated and correlative sparsity of the data matrices of the CPP relaxation is represented by a block-clique graph $G$. By exploiting the correlative sparsity, we decompose the CPP relaxation problem into a clique-tree structured family of smaller subproblems. Each subproblem is associated with a node of a clique tree of $G$. The optimal value can be obtained by applying an algorithm that we propose for solving the subproblems recursively from leaf nodes to the root node of the clique-tree. We establish the equivalence between the QOP and its DNN relaxation from the equivalence between the reduced family of subproblems and their DNN relaxations by applying the known results on: (i) CPP and DNN reformulation of a class of QOPs with linear equality, complementarity and binary constraints in 4 nonnegative variables. (ii) DNN reformulation of a class of quadratically constrained convex QOPs with any size. (iii) DNN reformulation of LPs with any size. As a result, we show that a QOP whose subproblems are the QOPs mentioned in (i), (ii) and (iii) is equivalent to its DNN relaxation, if the subproblems form a clique-tree structured family induced from a block-clique graph., Comment: 25 pages, 4 figures

It is well known that the convex hull of $$\{{(x,y,xy)}\}$$ , where (x, y) is constrained to lie in a box, is given by the reformulation-linearization technique (RLT) constraints. Belotti et al. (Electron Notes Discrete Math 36:805–812, 2010) and Miller et al. (SIAG/OPT Views News 22(1):1–8, 2011) showed that if there are additional upper and/or lower bounds on the product $$z=xy$$ , then the convex hull can be represented by adding an infinite family of inequalities, requiring a separation algorithm to implement. Nguyen et al. (Math Progr 169(2):377–415, 2018) derived convex hulls for $$\{(x,y,z)\}$$ with bounds on $$z=xy^b$$ , $$b\ge 1$$ . We focus on the case where $$b=1$$ and show that the convex hull with either an upper bound or lower bound on the product is given by RLT constraints, the bound on z and a single second-order cone (SOC) constraint. With both upper and lower bounds on the product, the convex hull can be represented using no more than three SOC constraints, each applicable on a subset of (x, y) values. In addition to the convex hull characterizations, volumes of the convex hulls with either an upper or lower bound on z are calculated and compared to the relaxation that imposes only the RLT constraints. As an application of these volume results, we show how spatial branching can be applied to the product variable so as to minimize the sum of the volumes for the two resulting subproblems.

Tight convex and concave relaxations are of high importance in deterministic global optimization. We present a method to tighten relaxations obtained by the McCormick technique. We use the McCormick subgradient propagation (Mitsos et al. in SIAM J Optim 20(2):573–601, 2009) to construct simple affine under- and overestimators of each factor of the original factorable function. Then, we minimize and maximize these affine relaxations in order to obtain possibly improved range bounds for every factor resulting in possibly tighter final McCormick relaxations. We discuss the method and its limitations, in particular the lack of guarantee for improvement. Subsequently, we provide numerical results for benchmark cases found in the MINLPLib2 library and case studies presented in previous works, where the McCormick technique appears to be advantageous, and discuss computational efficiency. We see that the presented algorithm provides a significant improvement in tightness and decrease in computational time, especially in the case studies using the reduced space formulation presented in (Bongartz and Mitsos in J Glob Optim 69:761–796, 2017).

In this paper, we present new convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP) problems. While recent research has focused on strengthening convex relaxations of QCQP using the reformulation-linearization technique (RLT), the state-of-the-art methods lose their effectiveness when dealing with (multiple) nonconvex quadratic constraints in QCQP, except for direct lifting and linearization. In this research, we decompose and relax each nonconvex constraint to two second order cone (SOC) constraints and then linearize the products of the SOC constraints and linear constraints to construct some new effective valid constraints. Moreover, we extend the reach of the RLT-like techniques for almost all different types of constraint-pairs (including valid inequalities by linearizing the product of a pair of SOC constraints, and the Hadamard product or the Kronecker product of two respective valid linear matrix inequalities), examine dominance relationships among different valid inequalities, and explore almost all possibilities of gaining benefits from generating valid constraints. We also successfully demonstrate that applying RLT-like techniques to additional redundant linear constraints could reduce the relaxation gap significantly. We demonstrate the efficiency of our results with numerical experiments.

We focus on finding sparse and least-$\ell_1$-norm solutions for unconstrained nonlinear optimal control problems. Such optimization problems are non-convex and non-smooth, nevertheless recent versions of Newton method for under-determined equations can be applied successively for such problems., Author version with errata after (15) at page 6 (missing formula for $\bar{v}$ is restored). J Glob Optim (2019)

In 2016 Aussel, Sultana and Vetrivel developed the concept of projected solution for quasi-variational inequality problems and projected Nash equilibrium. We introduce a new concept of solution for quasi-equilibrium problems and we study the existence of such solutions. Additionally, as a consequence of our results, we give existence results of projected solutions for quasi-optimization problems, quasi-variational inequalities problems and generalized Nash equilibrium problems., 24 pages. arXiv admin note: substantial text overlap with arXiv:1801.08581

The Douglas--Rachford algorithm is a popular algorithm for solving both convex and nonconvex feasibility problems. While its behaviour is settled in the convex inconsistent case, the general nonconvex inconsistent case is far from being fully understood. In this paper, we focus on the most simple nonconvex inconsistent case: when one set is a hyperplane and the other a doubleton (i.e., a two-point set). We present a characterization of cycling in this case which --- somewhat surprisingly --- depends on whether the ratio of the distance of the points to the hyperplane is rational or not. Furthermore, we provide closed-form expressions as well as several concrete examples which illustrate the dynamical richness of this algorithm.

We investigate how to partition a rectangular region of length $$L_1$$ and height $$L_2$$ into n rectangles of given areas $$(a_1, \dots , a_n)$$ using two-stage guillotine cuts, so as to minimize either (i) the sum of the perimeters, (ii) the largest perimeter, or (iii) the maximum aspect ratio of the rectangles. These problems play an important role in the ongoing Vietnamese land-allocation reform, as well as in the optimization of matrix multiplication algorithms. We show that the first problem can be solved to optimality in $${{\mathcal {O}}}(n \log n)$$ , while the two others are NP-hard. We propose mixed integer linear programming formulations and a binary search-based approach for solving the NP-hard problems. Experimental analyses are conducted to compare the solution approaches in terms of computational efficiency and solution quality, for different objectives.

The complexity of Pareto fronts imposes a great challenge on the convergence analysis of multi-objective optimization methods. While most theoretical convergence studies have addressed finite-set and/or discrete problems, others have provided probabilistic guarantees, assumed a total order on the solutions, or studied their asymptotic behaviour. In this paper, we revisit the Tchebycheff weighted method in a hierarchical bandits setting and provide a finite-time bound on the Pareto-compliant additive $\epsilon$-indicator. To the best of our knowledge, this paper is one of few that establish a link between weighted sum methods and quality indicators in finite time., Comment: submitted to Journal of Global Optimization. This article's notation and terminology is based on arXiv:1612.08412

This paper continues our recent effort in applying continuous optimization techniques to study optimal multicast communication networks modeled as bilevel hierarchical clustering problems. Given a finite number of nodes, we consider two different models of multicast networks by identifying a certain number of nodes as cluster centers, and at the same time, locating a particular node that serves as a total center so as to minimize the total transportation cost throughout the network. The fact that the cluster centers and the total center have to be among the given nodes makes these problems discrete optimization problems. Our approach is to reformulate the discrete problems as continuous ones and to apply Nesterov's smoothing approximation techniques on the Minkowski gauges that are used as distance measures. This approach enables us to propose two implementable DCA-based algorithms for solving the problems. Numerical results and practical applications are provided to illustrate our approach.

There are different solution concepts for convex vector optimization problems (CVOPs) and a recent one, which is motivated from a set optimization point of view, consists of finitely many efficient solutions that generate polyhedral inner and outer approximations to the Pareto frontier. A CVOP with compact feasible region is known to be bounded and there exists a solution of this sense to it. However, it is not known if it is possible to generate polyhedral inner and outer approximations to the Pareto frontier of a CVOP if the feasible region is not compact. This study shows that not all CVOPs are tractable in that sense and gives a characterization of tractable problems in terms of the well known weighted sum scalarization problems.

In Speakman and Lee (Math Oper Res 42(4):1230–1253, 2017), we analytically developed the idea of using volume as a measure for comparing relaxations in the context of spatial branch-and-bound. Specifically, for trilinear monomials, we analytically compared the three possible “double-McCormick relaxations” with the tight convex-hull relaxation. Here, again using volume as a measure, for the convex-hull relaxation of trilinear monomials, we establish simple rules for determining the optimal branching variable and optimal branching point. Additionally, we compare our results with current software practice.

In the article we present a general theory of augmented Lagrangian functions for cone constrained optimization problems that allows one to study almost all known augmented Lagrangians for cone constrained programs within a unified framework. We develop a new general method for proving the existence of global saddle points of augmented Lagrangian functions, called the localization principle. The localization principle unifies, generalizes and sharpens most of the known results on existence of global saddle points, and, in essence, reduces the problem of the existence of saddle points to a local analysis of optimality conditions. With the use of the localization principle we obtain first necessary and sufficient conditions for the existence of a global saddle point of an augmented Lagrangian for cone constrained minimax problems via both second and first order optimality conditions. In the second part of the paper, we present a general approach to the construction of globally exact augmented Lagrangian functions. The general approach developed in this paper allowed us not only to sharpen most of the existing results on globally exact augmented Lagrangians, but also to construct first globally exact augmented Lagrangian functions for equality constrained optimization problems, for nonlinear second order cone programs and for nonlinear semidefinite programs. These globally exact augmented Lagrangians can be utilized in order to design new superlinearly (or even quadratically) convergent optimization methods for cone constrained optimization problems., This is a preprint of an article published by Springer in Journal of Global Optimization (2018). The final authenticated version is available online at: http://dx.doi.org/10.1007/s10898-017-0603-0

We treat uncertain linear programming problems by utilizing the notion of weighted analytic centers and notions from the area of multi-criteria decision making. After introducing our approach, we develop interactive cutting-plane algorithms for robust optimization, based on concave and quasi-concave utility functions. In addition to practical advantages, due to the flexibility of our approach, we prove that under a theoretical framework proposed by Bertsimas and Sim (Oper Res 52:35–53, 2004), which establishes the existence of certain convex formulation of robust optimization problems, the robust optimal solutions generated by our algorithms are at least as desirable to the decision maker as any solution generated by many other robust optimization algorithms in the theoretical framework. We present some probabilistic bounds for feasibility of robust solutions and evaluate our approach by means of computational experiments.

DIviding RECTangles (DIRECT) is an efficient and popular method in dealing with bound constrained optimization problems. However, DIRECT suffers from dimension curse, since its computational complexity soars when dimension increases. Besides, DIRECT also converges slowly when the objective function is flat. In this paper, we propose a coordinate DIRECT algorithm, which coincides with the spirits of other coordinate update algorithms. We transform the original problem into a series of sub-problems, where only one or several coordinates are selected to optimize and the rest keeps fixed. For each sub-problem, coordinately dividing the feasible domain enjoys low computational burden. Besides, we develop adaptive schemes to keep the efficiency and flexibility to tackle different functions. Specifically, we use block coordinate update, of which the size could be adaptively selected, and we also employ sequential quadratic programming (SQP) to conduct the local search to efficiently accelerate the convergence even when the objective function is flat. With these techniques, the proposed algorithm achieves promising performance on both efficiency and accuracy in numerical experiments.

In the context of global optimization and mixed-integer non-linear programming, generalizing a technique of D’Ambrosio, Fampa, Lee and Vigerske for handling the square-root function, we develop a virtuous smoothing method, using cubics, aimed at functions having some limited non-smoothness. Our results pertain to root functions ( $$w^p$$ with $$0

A class of non-convex optimization problems with DC objective function is studied, where DC stands for being representable as the difference $f=g-h$ of two convex functions $g$ and $h$. In particular, we deal with the special case where one of the two convex functions $g$ or $h$ is polyhedral. In case $g$ is polyhedral, we show that a solution of the DC program can be obtained from a solution of an associated polyhedral projection problem. In case $h$ is polyhedral, we prove that a solution of the DC program can be obtained by solving a polyhedral projection problem and finitely many convex programs. Since polyhedral projection is equivalent to multiple objective linear programming (MOLP), a MOLP solver (in the second case together with a convex programming solver) can be used to solve instances of DC programs with polyhedral component. Numerical examples are provided, among them an application to locational analysis., Comment: 2nd version: some typos corrected, some remarks added, update of references

The decomposition of a matrix, as a product of factors with particular properties, is a much used tool in numerical analysis. Here we develop methods for decomposing a matrix $C$ into a product $X Y$, where the factors $X$ and $Y$ are required to minimize their distance from an arbitrary pair $X_0$ and $Y_0$. This type of decomposition, a projection to a matrix product constraint, in combination with projections that impose structural properties on $X$ and $Y$, forms the basis of a general method of decomposing a matrix into factors with specified properties. Results are presented for the application of these methods to a number of hard problems in exact factorization., Comment: 37 pages, 8 figures

Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomial time by solving a polynomial number of linear programs of polynomial size. We also give an overview of known complexity results and remaining open problems to further characterize the border between (strongly) NP-hard and polynomially solvable cases of the pooling problem., updated references

In this paper, the concepts of Pareto $H$-eigenvalue and Pareto $Z$-eigenvalue are introduced for studying constrained minimization problem and the necessary and sufficient conditions of such eigenvalues are given. It is proved that a symmetric tensor has at least one Pareto $H$-eigenvalue (Pareto $Z$-eigenvalue). Furthermore, the minimum Pareto $H$-eigenvalue (or Pareto $Z$-eigenvalue) of a symmetric tensor is exactly equal to the minimum value of constrained minimization problem of homogeneous polynomial deduced by such a tensor, which gives an alternative methods for solving the minimum value of constrained minimization problem. In particular, a symmetric tensor $\mathcal{A}$ is copositive if and only if every Pareto $H$-eigenvalue ($Z-$eigenvalue) of $\mathcal{A}$ is non-negative., Comment: 14 pages. arXiv admin note: text overlap with arXiv:1302.6084

In this paper we analyze several new methods for solving nonconvex optimization problems with the objective function consisting of a sum of two terms: one is nonconvex and smooth, and another is convex but simple and its structure is known. Further, we consider both cases: unconstrained and linearly constrained nonconvex problems. For optimization problems of the above structure, we propose random coordinate descent algorithms and analyze their convergence properties. For the general case, when the objective function is nonconvex and composite we prove asymptotic convergence for the sequences generated by our algorithms to stationary points and sublinear rate of convergence in expectation for some optimality measure. Additionally, if the objective function satisfies an error bound condition we derive a local linear rate of convergence for the expected values of the objective function. We also present extensive numerical experiments for evaluating the performance of our algorithms in comparison with state-of-the-art methods.

International audience; A small polygon is a convex polygon of unit diameter. We are interested in small polygons which have the largest area for a given number of vertices $n$. Many instances are already solved in the literature, namely for all odd $n$, and for $n=4, 6$ and $8$. Thus, for even $n\geq 10$, instances of this problem remain open. Finding those largest small polygons can be formulated as nonconvex quadratic programming problems which can challenge state-of-the-art global optimization algorithms. We show that a recently developed technique for global polynomial optimization, based on a semidefinite programming approach to the generalized problem of moments and implemented in the public-domain Matlab package GloptiPoly, can successfully find largest small polygons for $n=10$ and $n=12$. Therefore this significantly improves existing results in the domain. When coupled with accurate convex conic solvers, GloptiPoly can provide numerical guarantees of global optimality, as well as rigorous guarantees relying on interval arithmetic.