Global minimization by reducing the duality gap
The authors discuss nonlinear optimization problems of the form \[ (P_ Q)\qquad \min_{x,q} \bigl\{f_ 0(q,x): q\in Q,\;f_ j(q,x)\leq 0,\;j= 1,\dots,m\bigr\}, \] where \(Q\) is a nonempty set. The aim is to find lower bounds for the global minimum of \((P_ Q)\). One of the most important ways is based on the introduction of the Lagrange dual problem \((D_ Q)\) but in general no strict duality relations hold. To reduce the duality gap the authors provide an interesting approach by partitioning the set \(Q\). If \(Q= \bigcup_{i\in I} Q_ i\) then it is easy to show that \[ \min(P_ Q)= \min_{i\in I}\{\min (P_{Q_ i})\}\geq \min_{i\in I} \{\max(D_{Q_ i})\}\geq \max(D_ Q). \] So the value \(\min_{i\in I} \{\max(D_{Q_ i})\}\) is a better estimation for the optimal value of \((P_ Q)\). Moreover, one can guess that the gap will be smaller if the partition is taken finer i.e. if the radius of the partition (the radius of the smallest ball containing the sets \(Q_ i\)) tends to zero. Naturally, suitable convexity and regularity conditions for the partial problems \((P_{Q_ i})\) must be assumed. For ``partially linear problems (here all functions are linear in the variable \(x\) and \(Q\) is a polytop) the authors provide sufficient conditions that for any \(\varepsilon> 0\) there exists a partition of \(Q\) with the duality gap smaller than \(\varepsilon\). It is worthy to state that for such problems all dual problems reduce to linear semi-infinite problems which can simplified by additional convexity assumptions for the variable \(q\). At the end of the paper a branch-and-bound type algorithm and first results by solving a special two-stage process are presented.
- Lagrange duality and partitioning techniques in nonconvex global optimization
- On solving nonconvex optimization problems by reducing the duality gap
- Estimates of the duality gap for optimum partition problems
- On the Duality Gap in Nonconvex Optimization
- Convergence and application of a decomposition method using duality bounds for nonconvex global optimization
- A collection of test problems for constrained global optimization algorithms
- A Decomposition Strategy for Global Optimum Search in the Pooling Problem
- A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
- scientific article; zbMATH DE number 3791104 (Why is no real title available?)
- scientific article; zbMATH DE number 125254 (Why is no real title available?)
- scientific article; zbMATH DE number 3894826 (Why is no real title available?)
- Primal-relaxed dual global optimization approach
- State Constraints in Convex Control Problems of Bolza
- A new Lagrangean approach to the pooling problem
- New properties and computational improvement of the GOP algorithm for problems with quadratic objective functions and constraints
- Lagrange duality and partitioning techniques in nonconvex global optimization
- Active set strategies in an ellipsoid algorithm for nonlinear programming
- Integrated planning for design and production in two-stage recycling operations
- A numerical evaluation of the bounded degree sum-of-squares hierarchy of Lasserre, Toh, and Yang on the pooling problem
- Complexity analysis and algorithm design of pooling problem
- Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness
- Convergence-order analysis of branch-and-bound algorithms for constrained problems
- Decomposition-based inner- and outer-refinement algorithms for global optimization
- Modeling and design of global logistics systems: a review of integrated strategic and tactical models and design algorithms
- \(\alpha BB\): A global optimization method for general constrained nonconvex problems
- Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations
- Decision-dependent probabilities in stochastic programs with recourse
- Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods
- Comparison of mixed-integer relaxations with linear and logarithmic partitioning schemes for quadratically constrained problems
- Tightening methods based on nontrivial bounds on bilinear terms
- Feasibility and cost minimisation for a lithium extraction problem
- Natural gas production network infrastructure development under uncertainty
- Large-scale standard pooling problems with constrained pools and fixed demands
- A multi-commodity flow formulation for the generalized pooling problem
- Strong formulations for the pooling problem
- On a decomposition method for nonconvex global optimization
- On solving nonconvex optimization problems by reducing the duality gap
- Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints
- The convergence of partitioning dual bounds for partial convex optimization problems
- Estimates of the duality gap for optimum partition problems
- A generalized global optimization formulation of the pooling problem with processing facilities and composite quality constraints
- Pooling problems with polynomial-time algorithms
- Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO
- Analysis of MILP techniques for the pooling problem
- Methods for optimizing over the efficient and weakly efficient sets of an affine fractional vector optimization program
- GLOMIQO: global mixed-integer quadratic optimizer
- A cost minimization heuristic for the pooling problem
- Strong convex nonlinear relaxations of the pooling problem
- A polynomially solvable case of the pooling problem
- Relaxations and discretizations for the pooling problem
- New multi-commodity flow formulations for the pooling problem
- Simultaneous convexification of bilinear functions over polytopes with application to network interdiction
- Duality bound method for the general quadratic programming problem with quadratic constraints
- A global supply chain model with transfer pricing and transportation cost allocation
- The computational complexity of the pooling problem
- On the effectiveness of sequential linear programming for the pooling problem
- Comparison of MINLP formulations for global superstructure optimization
- Tightening discretization-based MILP models for the pooling problem using upper bounds on bilinear terms
- A new model and algorithm design of pooling problem
- Convergence and application of a decomposition method using duality bounds for nonconvex global optimization
- Extended duality for nonlinear programming
- Improved rank-one-based relaxations and bound tightening techniques for the pooling problem
- An exact reformulation algorithm for large nonconvex nLPs involving bilinear terms
- A new global optimization algorithm for signomial geometric programming via Lagrangian relaxation
This page was built for publication: Global minimization by reducing the duality gap
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1322556)
