Lower level duality and the global solution of generalized semi-infinite programs

The reformulation of generalized semi-infinite programs (GSIP) to simpler problems is considered. These reformulations are achieved under the assumption that a duality property holds for the lower level program (LLP). Lagrangian duality is used in the general case to establish the relationship between the GSIP and a related semi-infinite program (SIP). Practical aspects of this reformulation, including how to bound the duality multipliers, are also considered. This SIP reformulation result is then combined with recent advances for the global, feasible solution of SIP to develop a global, feasible point method for the solution of GSIP. Reformulations to finite nonlinear programs, and the practical aspects of solving these reformulations globally, are also discussed. When the LLP is a linear program or second-order cone program, specific duality results can be used that lead to stronger results. Numerical examples demonstrate that the global solution of GSIP is computationally practical via the solution of these duality-based reformulations.     

Global solution of semi-infinite programs

Optimization problems involving a finite number of decision variables and an infinite number of constraints are referred to as semi-infinite programs (SIPs). Existing numerical methods for solving nonlinear SIPs make strong assumptions on the properties of the feasible set, e.g., convexity and/or regularity, or solve a discretized approximation which only guarantees a lower bound to the true solution value of the SIP. Here, a general, deterministic algorithm for solving semi-infinite programs to guaranteed global optimality is presented. A branch-and-bound (B&B) framework is used to generate convergent sequences of upper and lower bounds on the SIP solution value. The upper-bounding problem is generated by replacing the infinite number of real-valued constraints with a finite number of constrained inclusion bounds; the lower-bounding problem is formulated as a convex relaxation of a discretized approximation to the SIP. The SIP B&B algorithm is shown to converge finitely to –optimality when the subdivision and discretization procedures used to formulate the node subproblems are known to retain certain convergence characteristics. Other than the properties assumed by globally-convergent B&B methods (for finitely-constrained NLPs), this SIP algorithm makes only one additional assumption: For every minimizer x* of the SIP there exists a sequence of Slater points x_n for which (cf. Section 5.4). Numerical results for test problems in the SIP literature are presented. The exclusion test and a modified upper-bounding problem are also investigated as heuristic approaches for alleviating the computational cost of solving a nonlinear SIP to guaranteed global optimality.     

A hybrid discretization algorithm with guaranteed feasibility for the global solution of semi-infinite programs

A discretization-based algorithm for the global solution of semi-infinite programs (SIPs) is proposed, which is guaranteed to converge to a feasible, \(\varepsilon \)-optimal solution finitely under mild assumptions. The algorithm is based on the hybridization of two existing algorithms. The first algorithm (Mitsos in Optimization 60(10–11):1291–1308, 2011) is based on a restriction of the right-hand side of the constraints of a discretized SIP. The second algorithm (Tsoukalas and Rustem in Optim Lett 5(4):705–716, 2011) employs a discretized oracle problem and a binary search in the objective space. Hybridization of the approaches yields an algorithm, which leverages the strong convergence guarantees and the relatively tight upper bounding problem of the first approach while employing an oracle problem adapted from the second approach to generate cheap lower bounds and adaptive updates to the restriction of the first approach. These adaptive updates help in avoiding a dense population of the discretization. The hybrid algorithm is shown to be superior to its predecessors both theoretically and computationally. A proof of finite convergence is provided under weaker assumptions than the assumptions in the references. Numerical results from established SIP test cases are presented.     

Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs

A rigorous decomposition approach to solve separable mixed-integer nonlinear programs where the participating functions are nonconvex is presented. The proposed algorithms consist of solving an alternating sequence of Relaxed Master Problems (mixed-integer linear program) and two nonlinear programming problems (NLPs). A sequence of valid nondecreasing lower bounds and upper bounds is generated by the algorithms which converge in a finite number of iterations. A Primal Bounding Problem is introduced, which is a convex NLP solved at each iteration to derive valid outer approximations of the nonconvex functions in the continuous space. Two decomposition algorithms are presented in this work. On finite termination, the first yields the global solution to the original nonconvex MINLP and the second finds a rigorous bound to the global solution. Convergence and optimality properties, and refinement of the algorithms for efficient implementation are presented. Finally, numerical results are compared with currently available algorithms for example problems, illuminating the potential benefits of the proposed algorithm.     

Global solution of nonlinear mixed-integer bilevel programs

An algorithm for the global optimization of nonlinear bilevel mixed-integer programs is presented, based on a recent proposal for continuous bilevel programs by Mitsos et al. (J Glob Optim 42(4):475–513, 2008). The algorithm relies on a convergent lower bound and an optional upper bound. No branching is required or performed. The lower bound is obtained by solving a mixed-integer nonlinear program, containing the constraints of the lower-level and upper-level programs; its convergence is achieved by also including a parametric upper bound to the optimal solution function of the lower-level program. This lower-level parametric upper bound is based on Slater-points of the lower-level program and subsets of the upper-level host sets for which this point remains lower-level feasible. Under suitable assumptions the KKT necessary conditions of the lower-level program can be used to tighten the lower bounding problem. The optional upper bound to the optimal solution of the bilevel program is obtained by solving an augmented upper-level problem for fixed upper-level variables. A convergence proof is given along with illustrative examples. An implementation is described and applied to a test set comprising original and literature problems. The main complication relative to the continuous case is the construction of the parametric upper bound to the lower-level optimal objective value, in particular due to the presence of upper-level integer variables. This challenge is resolved by performing interval analysis over the convex hull of the upper-level integer variables.     

Conic approximation to quadratic optimization with linear complementarity constraints

This paper proposes a conic approximation algorithm for solving quadratic optimization problems with linear complementarity constraints.We provide a conic reformulation and its dual for the original problem such that these three problems share the same optimal objective value. Moreover, we show that the conic reformulation problem is attainable when the original problem has a nonempty and bounded feasible domain. Since the conic reformulation is in general a hard problem, some conic relaxations are further considered. We offer a condition under which both the semidefinite relaxation and its dual problem become strictly feasible for finding a lower bound in polynomial time. For more general cases, by adaptively refining the outer approximation of the feasible set, we propose a conic approximation algorithm to identify an optimal solution or an \(\epsilon \)-optimal solution of the original problem. A convergence proof is given under simple assumptions. Some computational results are included to illustrate the effectiveness of the proposed algorithm.     

Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method

Let be a 0-1 quadratic program which consists in minimizing a quadratic function subject to linear equality constraints. In this paper, we present QCR, a general method to reformulate into an equivalent 0-1 program with a convex quadratic objective function. The reformulated problem can then be efficiently solved by a classical branch-and-bound algorithm, based on continuous relaxation. This idea is already present in the literature and used in standard solvers such as CPLEX. Our objective in this work was to find a convex reformulation whose continuous relaxation bound is, moreover, as tight as possible. From this point of view, we show that QCR is optimal in a certain sense. State-of-the-art reformulation methods mainly operate a perturbation of the diagonal terms and are valid for any {0,1} vector. The innovation of QCR comes from the fact that the reformulation also uses the equality constraints and is valid on the feasible solution domain only. Hence, the superiority of QCR holds by construction. However, reformulation by QCR requires the solution of a semidefinite program which can be costly from the running time point of view. We carry out a computational experience on three different combinatorial optimization problems showing that the costly computational time of reformulation by QCR can however result in a drastically more efficient branch-and-bound phase. Moreover, our new approach is competitive with very specific methods applied to particular optimization problems.     

A one-phase algorithm for semi-infinite linear programming

We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.     

A new smoothing Newton-type algorithm for semi-infinite programming

We consider a semismooth reformulation of the KKT system arising from the semi-infinite programming (SIP) problem. Based upon this reformulation, we present a new smoothing Newton-type method for the solution of SIP problem. The main properties of this method are: (a) it is globally convergent at least to a stationary point of the SIP problem, (b) it is locally superlinearly convergent under a certain regularity condition, (c) the feasibility is ensured via the aggregated constraint, and (d) it has to solve just one linear system of equations at each iteration. Preliminary numerical results are reported.     

Global Convergence of a Robust Smoothing SQP Method for Semi-Infinite Programming

The semi-infinite programming (SIP) problem is a program with infinitely many constraints. It can be reformulated as a nonsmooth nonlinear programming problem with finite constraints by using an integral function. Due to the nondifferentiability of the integral function, gradient-based algorithms cannot be used to solve this nonsmooth nonlinear programming problem. To overcome this difficulty, we present a robust smoothing sequential quadratic programming (SQP) algorithm for solving the nonsmooth nonlinear programming problem. At each iteration of the algorthm, we need to solve only a quadratic program that is always feasible and solvable. The global convergence of the algorithm is established under mild conditions. Numerical results are given. Communicated by F. Giannessi His work was supported by the Hong Kong Research Grant Council His work was supported by the Australian Research Council.     

First-order inertial algorithms involving dry friction damping

We present a Branch-and-Cut algorithm for a class of nonlinear chance-constrained mathematical optimization problems with a finite number of scenarios. Unsatisfied scenarios can enter a recovery mode. This class corresponds to problems that can be reformulated as deterministic convex mixed-integer nonlinear programming problems with indicator variables and continuous scenario variables, but the size of the reformulation is large and quickly becomes impractical as the number of scenarios grows. The Branch-and-Cut algorithm is based on an implicit Benders decomposition scheme, where we generate cutting planes as outer approximation cuts from the projection of the feasible region on suitable subspaces. The size of the master problem in our scheme is much smaller than the deterministic reformulation of the chance-constrained problem. We apply the Branch-and-Cut algorithm to the mid-term hydro scheduling problem, for which we propose a chance-constrained formulation. A computational study using data from ten hydroplants in Greece shows that the proposed methodology solves instances faster than applying a general-purpose solver for convex mixed-integer nonlinear programming problems to the deterministic reformulation, and scales much better with the number of scenarios.

     

Rounding-based heuristics for nonconvex MINLPs

We propose two primal heuristics for nonconvex mixed-integer nonlinear programs. Both are based on the idea of rounding the solution of a continuous nonlinear program subject to linear constraints. Each rounding step is accomplished through the solution of a mixed-integer linear program. Our heuristics use the same algorithmic scheme, but they differ in the choice of the point to be rounded (which is feasible for nonlinear constraints but possibly fractional) and in the linear constraints. We propose a feasibility heuristic, that aims at finding an initial feasible solution, and an improvement heuristic, whose purpose is to search for an improved solution within the neighborhood of a given point. The neighborhood is defined through local branching cuts or box constraints. Computational results show the effectiveness in practice of these simple ideas, implemented within an open-source solver for nonconvex mixed-integer nonlinear programs.     

Generalized semi-infinite programming: Theory and methods

Generalized semi-infinite optimization problems (GSIP) are considered. The difference between GSIP and standard semi-infinite problems (SIP) is illustrated by examples. By applying the `Reduction Ansatz', optimality conditions for GSIP are derived. Numerical methods for solving GSIP are considered in comparison with methods for SIP. From a theoretical and a practical point of view it is investigated, under which assumptions a GSIP can be transformed into an SIP.     

A homotopy interior point method for semi-infinite programming problems

This paper presents a homotopy interior point method for solving a semi-infinite programming (SIP) problem. For algorithmic purpose, based on bilevel strategy, first we illustrate appropriate necessary conditions for a solution in the framework of standard nonlinear programming (NLP), which can be solved by homotopy method. Under suitable assumptions, we can prove that the method determines a smooth interior path from a given interior point to a point w ^*, at which the necessary conditions are satisfied. Numerical tracing this path gives a globally convergent algorithm for the SIP. Lastly, several preliminary computational results illustrating the method are given.     

Exact and approximation algorithms for a soft rectangle packing problem

We consider the problem of finding an arrangement of rectangles with given areas that minimizes the total length of all inner and outer border lines. We present a polynomial time approximation algorithm and derive an upper bound estimation on its approximation ratio. Furthermore, we give a formulation of the problem as mixed-integer nonlinear program and show that it can be approximatively reformulated as linear mixed-integer program. On a test set of problem instances, we compare our approximation algorithm with another one from the literature. Using a standard numerical mixed-integer linear solver, we show that adding the solutions from the approximation algorithm as advanced starter helps to reduce the overall solution time for proven global optimality, or gives better primal and dual bounds if a certain time-limit is reached before.     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

Convex Semi-Infinite Programming: Implicit Optimality Criterion Based on the Concept of Immobile Indices

We state a new implicit optimality criterion for convex semi-infinite programming (SIP) problems. This criterion does not require any constraint qualification and is based on concepts of immobile index and immobility order. Given a convex SIP problem with a continuum of constraints, we use an information about its immobile indices to construct a nonlinear programming (NLP) problem of a special form. We prove that a feasible point of the original infinite SIP problem is optimal if and only if it is optimal in the corresponding finite NLP problem. This fact allows us to obtain new efficient optimality conditions for convex SIP problems using known results of the optimality theory of NLP. To construct the NLP problem, we use the DIO algorithm. A comparison of the optimality conditions obtained in the paper with known results is provided.     

Generalized Convex Disjunctive Programming: Nonlinear Convex Hull Relaxation

Generalized Disjunctive Programming (GDP) has been introduced recently as an alternative to mixed-integer programming for representing discrete/continuous optimization problems. The basic idea of GDP consists of representing these problems in terms of sets of disjunctions in the continuous space, and logic propositions in terms of Boolean variables. In this paper we consider GDP problems involving convex nonlinear inequalities in the disjunctions. Based on the work by Stubbs and Mehrotra [21] and Ceria and Soares [6], we propose a convex nonlinear relaxation of the nonlinear convex GDP problem that relies on the convex hull of each of the disjunctions that is obtained by variable disaggregation and reformulation of the inequalities. The proposed nonlinear relaxation is used to formulate the GDP problem as a Mixed-Integer Nonlinear Programming (MINLP) problem that is shown to be tighter than the conventional big-M formulation. A disjunctive branch and bound method is also presented, and numerical results are given for a set of test problems.     

A relaxation method for solving systems with infinitely many linear inequalities

The problem of finding a feasible solution to a linear inequality system arises in numerous contexts. We consider solving linear semi-infinite inequality systems via an extension of the relaxation method for finite linear inequality systems. The difficulties are discussed and a convergence result is derived under fairly general assumptions on a large class of linear semi-infinite inequality systems.     

Generalized semi-infinite programming: numerical aspects

Generalized semi-infinite optimization problems (GSIP) are considered. It is investigated how the numerical methods for standard semi-infinite programming (SIP) can be extended to GSIP. Newton methods can be extended immediately. For discretization methods the situation is more complicated. These difficulties are discussed and convergence results for a discretization- and an exchange method are derived under fairly general assumptions on GSIP. The question is answered under which conditions GSIP represents a convex problem.