Search

The Griewank test function for global unconstrained optimization has multiple local minima clustered around the global minimum at the origin. A new version of this test function is proposed that has a similar structure, but whose behavior at the local minima and maxima is non-smooth. This piecewise smooth version of the Griewank function represents an abs-factorable test case of objective functions for global non-smooth optimization as, for example, observed in the training of neural networks. [ABSTRACT FROM AUTHOR]

We translate a multiobjective optimization problem into a single objective Lipschitz problem by using the hypervolume criterion of the Pareto set. Deterministic global optimization methods allow one to track the whole Pareto front rather than converging to a single non-dominated solution. We augmented an efficient hypervolume computation technique with hypervolume increment strategy, and established Lipschitzianity of the resulting objective function. We used two deterministic Lipschitz optimization methods together with the hypervolume objective and benchmarked them against some state-of-the-art alternative multiobjective optimization methods, establishing the competitiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

The aim of this paper is to present dual optimality conditions for the difference of two extended real valued increasing co-radiant functions. We do this by first characterizing dual optimality conditions for the difference of two nonpositive increasing co-radiant functions. Finally, we present dual optimality conditions for the difference of two extended real valued increasing co-radiant functions. Our approach is based on the Toland–Singer formula. [ABSTRACT FROM AUTHOR]

Trends over the past two decades indicate that much of the performance gains of commercial optimization solvers is due to improvements in x86 hardware. To continue making progress, it is critical to consider alternative/specialized massively parallel computing architectures. In this work, we detail the development of an open-source source code transformation approach built using Symbolics.jl to construct McCormick-based relaxations of functions that enables their effective parallelized evaluation. We then apply this approach in a novel parallelized branch-and-bound routine that offloads lower- and upper-bounding problems to a GPU. The effectiveness of this new approach is demonstrated on three nonconvex problems of interest, where it yields convergence time improvements of 22–118x compared to an equivalent serial CPU implementation and in two cases outperforms vanilla branch-and-bound versions of existing state-of-the-art solvers that use tighter bounding techniques. This work exemplifies how deterministic global optimizers using alternative hardware architectures can compete with—or eventually outclass—even the most powerful serial CPU implementations, and to the best of the authors' knowledge, represents the first successful demonstration of deterministic global optimization using a GPU. [ABSTRACT FROM AUTHOR]

In this study, we investigate a class of linear multiplicative programs with positive exponents. By introducing p additional variables, the original problem is reformulated into an equivalent problem (EP) within the output space. Subsequently, a novel global optimization algorithm is introduced to tackle EP. The algorithm primarily leverages two key techniques. One is the outer approximation technique, which tightens the relaxed feasible region of EP and improves the upper bound by carefully examining suitable feasible points. The other is the branch and bound technique to guarantee the global optimality of the solution. Numerical results confirm the effectiveness and practicality of the proposed algorithm, thereby underscoring its potential for real-world applications. [ABSTRACT FROM AUTHOR]

This article presents a self-adjustable branch-and-bound algorithm for globally solving a class of linear multiplicative programming problems (LMP). In this algorithm, a self-adjustable branching rule is introduced and it can continuously update the upper bound for the optimal value of LMP by selecting suitable branching point under certain conditions, which differs from the standard bisection rule. The proposed algorithm further integrates the linear relaxation program and the self-adjustable branching rule. The dependability and robustness of the proposed algorithm are demonstrated by establishing the global convergence. Furthermore, the computational complexity of the proposed algorithm is estimated. Finally, numerical results validate the effectiveness of the self-adjustable branching rule and demonstrate the feasibility of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We are considering differential-algebraic equations with embedded optimization criteria (DAEOs), in which the embedded optimization problem is solved by global optimization. This leads to differential inclusions for cases in which there are multiple global optimizers at the same time. Jump events from one global optimum to another result in nonsmooth DAEs and reduce the order of convergence of the numerical integrator to first-order. Implementation of event detection and location as introduced in this work preserves the higher-order convergence behaviour of the integrator. This allows the computation of discrete tangent and adjoint sensitivities for optimal control problems. [ABSTRACT FROM AUTHOR]

The problem of finding a globally optimal k-partition of a set A is a very intricate optimization problem for which in general, except in the case of one-dimensional data, i.e., for data with one feature ( A ⊂ R ), there is no method to solve. Only in the one-dimensional case, there are efficient methods based on the fact that the search for a globally optimal k-partition is equivalent to solving a global optimization problem for a symmetric Lipschitz-continuous function using the global optimization algorithm DIRECT. In the present paper, we propose a method for finding a globally optimal k-partition in the general case ( A ⊂ R n , n ≥ 1 ), generalizing an idea for solving the Lipschitz global optimization for symmetric functions. To do this, we propose a method that combines a global optimization algorithm with linear constraints and the k-means algorithm. The first of these two algorithms is used only to find a good initial approximation for the k-means algorithm. The method was tested on a number of artificial datasets and on several examples from the UCI Machine Learning Repository, and an application in spectral clustering for linearly non-separable datasets is also demonstrated. Our proposed method proved to be very efficient. [ABSTRACT FROM AUTHOR]

The strategy presented in this paper differs significantly from existing approaches as we formulate the problem as a standard optimization problem of difference of convex functions. We have developed the necessary and sufficient conditions for global solutions in this standard form. The main challenge in the standard form arises from a constraint of the form g (t) ≥ 1 , where g is a convex function. We utilize the classical inequality between the weighted arithmetic and harmonic means to overcome this challenge. This enables us to express the optimality conditions as a convex geometric programming problem and employ a predictor-corrector primal-dual interior point method for its solution, with weights updated during the predictor phase. The interior point method solves the dual problem of geometric programming and obtains the primal solution through exponential transformation. We have implemented the algorithm in Fortran 90 and validated it using a set of test problems from the literature. The proposed method successfully solved all the test problems, and the computational results are presented alongside the tested problems and the corresponding solutions found. [ABSTRACT FROM AUTHOR]

The aim of this paper is to deepen the study of solution methods for rank-two nonconvex problems with polyhedral feasible region, expressed by means of equality, inequality and box constraints, and objective function in the form of ϕ c T x + c 0 , d T x + d 0 b T x + b 0 or ϕ ¯ c ¯ T y + c ¯ 0 a T y + a 0 , d T y + d 0 b T y + b 0 . These problems arise in bicriteria programs, quantitative management science, data envelopment analysis, efficiency analysis and performance measurement. Theoretical results are proved and applied to propose a solution algorithm. Computational results are provided, comparing various splitting criteria. [ABSTRACT FROM AUTHOR]

This paper presents an efficient global optimization algorithm to solve a class of linear multiplicative problems (LMP). The algorithm first converts LMP into an equivalent problem (EP) via some variables transformation, and a convex relaxation problem is constructed to derive a lower bound to the optimal value of EP. Consequently, the process of solving LMP is transformed into tackling a series of convex programs. Additionally, a pruning rule is developed to offer a chance to remove the portion of the investigated space which does not contain the optimal solution of EP, and we propose a strategy which provides more choices of the feasible solution to update the upper bound for the optimal value of LMP. We also analyze the convergence of the algorithm and give its complexity result. Finally, our approach has been confirmed to be effective based on numerical results. [ABSTRACT FROM AUTHOR]

This work focuses on recovering images from various forms of corruption, for which a challenging non-smooth, non-convex optimization model is proposed. The model consists of a concave truncated data fidelity functional and a convex total-variational term. We introduce and study various novel equivalent mathematical models from the perspective of duality, leading to two new optimization frameworks in terms of two-stage and single-stage. The two-stage optimization approach follows a classical convex-concave optimization framework with an inner loop of convex optimization and an outer loop of concave optimization. In contrast, the single-stage optimization approach follows the proposed novel convex model, which boils down to the global optimization of all variables simultaneously. Moreover, the key step of both optimization frameworks can be formulated as linearly constrained convex optimization and efficiently solved by the augmented Lagrangian method. For this, two different implementations by projected-gradient and indefinite-linearization are proposed to build up their numerical solvers. The extensive experiments show that the proposed single-stage optimization algorithms, particularly with indefinite linearization implementation, outperform the multi-stage methods in numerical efficiency, stability, and recovery quality. [ABSTRACT FROM AUTHOR]

This paper aims to globally solve a generalized affine fractional program problem (GAFPP). Firstly, by introducing some outer space variables and performing equivalent transformations, we can derive the equivalence problem (EP) of the GAFPP. Secondly, by constructing a novel linear relaxation method, we can deduce the affine relaxation problem (ARP) of the EP. Next, by solving the ARP to compute the lower bound, we propose a new outer space branch-and-bound algorithm for tackling the GAFPP. Then, the global convergence of the algorithm is proved, and the computational complexity of the algorithm in the worst case is analyzed. Finally, numerical experimental results are reported to illustrate the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

Over the last three decades, many attempts have been made to improve the DIRECT (DIviding RECTangles) algorithm's efficiency. Various novel ideas and extensions have been suggested. The main two steps of DIRECT-type algorithms are selecting and partitioning potentially optimal rectangles. However, the most efficient combination of these two steps is an area that has not been investigated so far. This paper presents a study covering an extensive examination of various candidate selection and partitioning techniques within the same DIRECT algorithmic framework. Twelve DIRECT-type algorithmic variations are compared on 800 randomly generated GKLS-type test problems and 96 box-constrained global optimization problems from DIRECTGOLib v1.1 with varying complexity. Based on these studies, we have identified the most efficient selection and partitioning combinations leading to new, more efficient, DIRECT-type algorithms. All these algorithms are included in the latest version of DIRECTGO v1.1.0 and are publicly available. [ABSTRACT FROM AUTHOR]

Algorithm portfolios are multi-algorithmic schemes that combine a number of solvers into a joint framework for solving global optimization problems. A crucial part of such schemes is the resource allocation process that is responsible for assigning computational resources to the constituent algorithms. We propose a resource allocation process based on adaptive decision-making procedures. The proposed approach is incorporated in algorithm portfolios composed of three essential types of numerical optimization algorithms, namely gradient-based, direct search, and swarm intelligence algorithms. The designed algorithm portfolios are experimentally demonstrated on a challenging optimization problem for different dimensions and experimental settings. The accompanying statistical analysis offers interesting conclusions and insights on the performance of the algorithm portfolio compared to its constituent algorithms, as well as on the effect of its parameters. [ABSTRACT FROM AUTHOR]

We focus on deterministic global optimization (DGO) for nonconvex parameter estimation problems. Realistic and accurate solutions often require a fitting against very large measurement data sets, resulting in intractable size for DGO. Thus, we aim at accelerating the branch-and-bound algorithm by using reduced data sets for constructing valid bounds. We focus on fitting the equation of state for propane, which is of high interest for the chemical industry. The resulting estimation problem is a challenging nonconvex mixed-integer nonlinear optimization problem. We investigate the validity of using reduced data sets by comparing how the lower and upper bounds change when replacing the full data set with different reduced data sets. We account for regions with high and low quality fits by considering the results for the whole feasible region and 100 different subregions. Our results indicate that both regions containing solution candidates and regions containing only low quality fits can be identified based on reduced data sets. Moreover, we observe that the average CPU time per branch-and-bound iteration typically decreases if reduced data sets are used. [ABSTRACT FROM AUTHOR]

This paper is devoted to solving the one-dimensional global optimization problems where the objective function f satisfies a Hölder condition over a real interval [a, b]. We suggest two algorithms as an extended version of the Piyavskii's method. The first one is based on the use of the tangent at the midpoint of each subinterval of [a, b] of the parabolic lower bounding functions of f. The second one is a combination of two successive phases. In phase 1, we obtain with a few iterations, a subinterval which often contains the point of the global minimum using a K α -Lipschitz lower bounding functions with a tolerance δ much larger than the given accuracy ε . In phase 2, we apply the first algorithm on the interval obtained in phase 1. A convergence result is proved and compared with the existing methods. The numerical experiments of the two algorithms on some test functions are encouraging. [ABSTRACT FROM AUTHOR]

We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate between solving a master problem, which is a mixed-integer linear relaxation of the original problem, and a subproblem, which is designed to tighten the linear relaxation of the next master problem by using the Lipschitz information about the respective functions. By doing so, we follow the ideas of Schmidt, Sirvent, and Wollner (Math Program 178(1):449–483 (2019) and Optim Lett 16(5):1355-1372 (2022)) and improve the tackling of multivariate constraints. Although multivariate nonlinearities obviously increase modeling capabilities, their incorporation also significantly increases the computational burden of the proposed algorithm. We prove the correctness of our method and also derive a worst-case iteration bound. Finally, we show the generality of the addressed problem class and the proposed method by illustrating that both bilevel optimization problems with nonconvex and quadratic lower levels as well as nonlinear and mixed-integer models of gas transport can be tackled by our method. We provide the necessary theory for both applications and briefly illustrate the outcomes of the new method when applied to these two problems. [ABSTRACT FROM AUTHOR]

We present a method to solve a special class of parameter identification problems for an elliptic optimal control problem to global optimality. The bilevel problem is reformulated via the optimal-value function of the lower-level problem. The reformulated problem is nonconvex and standard regularity conditions like Robinson's CQ are violated. Via a relaxation of the constraints, the problem can be decomposed into a family of convex problems and this is the basis for a solution algorithm. The convergence properties are analyzed. It is shown that a penalty method can be employed to solve this family of problems while maintaining convergence speed. For an example problem, the use of the identity as penalty function allows for the solution by a semismooth Newton method. Numerical results are presented. Difficulties and limitations of our approach to solve a nonconvex problem to global optimality are discussed. [ABSTRACT FROM AUTHOR]

We investigate an inertial forward–backward algorithm in connection with the minimization of the sum of a non-smooth and possibly non-convex and a non-convex differentiable function. The algorithm is formulated in the spirit of the famous FISTA method; however, the setting is non-convex and we allow different inertial terms. Moreover, the inertial parameters in our algorithm can take negative values too. We also treat the case when the non-smooth function is convex, and we show that in this case a better step size can be allowed. Further, we show that our numerical schemes can successfully be used in DC-programming. We prove some abstract convergence results which applied to our numerical schemes allow us to show that the generated sequences converge to a critical point of the objective function, provided a regularization of the objective function satisfies the Kurdyka–Łojasiewicz property. Further, we obtain a general result that applied to our numerical schemes ensures convergence rates for the generated sequences and for the objective function values formulated in terms of the KL exponent of a regularization of the objective function. Finally, we apply our results to image restoration. [ABSTRACT FROM AUTHOR]

It is well known that bilevel optimization problems are hard to solve both in theory and practice. In this paper, we highlight a further computational difficulty when it comes to solving bilevel problems with continuous but nonconvex lower levels. Even if the lower-level problem is solved to ε -feasibility regarding its nonlinear constraints for an arbitrarily small but positive ε , the obtained bilevel solution as well as its objective value may be arbitrarily far away from the actual bilevel solution and its actual objective value. This result even holds for bilevel problems for which the nonconvex lower level is uniquely solvable, for which the strict complementarity condition holds, for which the feasible set is convex, and for which Slater's constraint qualification is satisfied for all feasible upper-level decisions. Since the consideration of ε -feasibility cannot be avoided when solving nonconvex problems to global optimality, our result shows that computational bilevel optimization with continuous and nonconvex lower levels needs to be done with great care. Finally, we illustrate that the nonlinearities in the lower level are the key reason for the observed bad behavior by showing that linear bilevel problems behave much better at least on the level of feasible solutions. [ABSTRACT FROM AUTHOR]

We propose a random-subspace algorithmic framework for global optimization of Lipschitz-continuous objectives, and analyse its convergence using novel tools from conic integral geometry. X-REGO randomly projects, in a sequential or simultaneous manner, the high-dimensional original problem into low-dimensional subproblems that can then be solved with any global, or even local, optimization solver. We estimate the probability that the randomly-embedded subproblem shares (approximately) the same global optimum as the original problem. This success probability is then used to show almost sure convergence of X-REGO to an approximate global solution of the original problem, under weak assumptions on the problem (having a strictly feasible global solution) and on the solver (guaranteed to find an approximate global solution of the reduced problem with sufficiently high probability). In the particular case of unconstrained objectives with low effective dimension, we propose an X-REGO variant that explores random subspaces of increasing dimension until finding the effective dimension of the problem, leading to X-REGO globally converging after a finite number of embeddings, proportional to the effective dimension. We show numerically that this variant efficiently finds both the effective dimension and an approximate global minimizer of the original problem. [ABSTRACT FROM AUTHOR]

We introduce a generalization of separability for global optimization, presented in the context of a simple branch and bound method. Our results apply to continuously differentiable objective functions implemented as computer programs. A significant search space reduction can be expected to yield an acceleration of any global optimization method. We show how to utilize interval derivatives calculated by adjoint algorithmic differentiation to examine the monotonicity of the objective with respect to so called structural separators and how to verify the latter automatically. [ABSTRACT FROM AUTHOR]

This paper investigates a class of linear fractional programming (LFP) problem, which minimizes the sum of a finite number of linear fractional functions over a polyhedral region. Firstly, the equivalence problem (EP) of the LFP problem is given by a new two-stage transformation method. Secondly, considering the characteristics that the branch-and-bound algorithm can guarantee the global optimality of the solution to an optimization problem, and then based on the EP, we discuss the bounding operation, branching operation, pruning operation and rectangle-region reduction technique of this algorithm. After that, the convergence of the algorithm is proved and its computational complexity is deduced from the worst case. Finally, some experiments are reported to verify the effectiveness, feasibility and other performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We show a connection between global unconstrained optimization of a continuous function f and weak KAM theory for an eikonal-type equation arising also in ergodic control. A solution v of the critical Hamilton–Jacobi equation is built by a small discount approximation as well as the long time limit of an associated evolutive equation. Then v is represented as the value function of a control problem with target, whose optimal trajectories are driven by a differential inclusion describing the gradient descent of v. Such trajectories are proved to converge to the set of minima of f, using tools in control theory and occupational measures. We prove also that in some cases the set of minima is reached in finite time. [ABSTRACT FROM AUTHOR]

In this paper, we deal with the class of unconstrained multi-objective optimization problems. In this setting we introduce, for the first time in the literature, a Limited Memory Quasi-Newton type method, which is well suited especially in large scale scenarios. The proposed algorithm approximates, through a suitable positive definite matrix, the convex combination of the Hessian matrices of the objectives; the update formula for the approximation matrix can be seen as an extension of the one used in the popular L-BFGS method for scalar optimization. Equipped with a Wolfe type line search, the considered method is proved to be well defined even in the nonconvex case. Furthermore, for twice continuously differentiable strongly convex problems, we state global and R-linear convergence to Pareto optimality of the sequence of generated points. The performance of the new algorithm is empirically assessed by a thorough computational comparison with state-of-the-art Newton and Quasi-Newton approaches from the multi-objective optimization literature. The results of the experiments highlight that the proposed approach is generally efficient and effective, outperforming the competitors in most settings. Moreover, the use of the limited memory method results to be beneficial within a global optimization framework for Pareto front approximation. [ABSTRACT FROM AUTHOR]

The quadratically constrained quadratic programming problem often appears in various fields such as engineering practice, management science and network communication. This paper mainly considers a non-convex quadratic programming problem with convex quadratic constraints. Firstly, the objective function of the problem is reconstructed into a form composed of only one convex function and several linear functions by using the eigenvalue decomposition technique of matrix. Then the reconstructed problem is converted to the equivalent problem with simple concave quadratic objective function in the outcome space by introducing appropriate auxiliary variables, and its feasible domain is convex. Based on the branch-and-bound framework which can guarantee the global optimality of the solution, a global optimization algorithm for solving the equivalent problem is proposed, which integrates the effective relaxation process and the branching process related to the outer approximation technique. Finally, the effectiveness and feasibility of the algorithm are illustrated by numerical experiments. [ABSTRACT FROM AUTHOR]

Deterministic nonconvex optimization solvers generate convex relaxations of nonconvex functions by making use of underlying factorable representations. One approach introduces auxiliary variables assigned to each factor that lifts the problem into a higher-dimensional decision space. In contrast, a generalized McCormick relaxation approach offers the significant advantage of constructing relaxations in the lower dimensionality space of the original problem without introducing auxiliary variables, often referred to as a "reduced-space" approach. Recent contributions illustrated how additional nontrivial inequality constraints may be used in factorable programming to tighten relaxations of the ubiquitous bilinear term. In this work, we exploit an analogous representation of McCormick relaxations and factorable programming to formulate tighter relaxations in the original decision space. We develop the underlying theory to generate necessarily tighter reduced-space McCormick relaxations when a priori convex/concave relaxations are known for intermediate bilinear terms. We then show how these rules can be generalized within a McCormick relaxation scheme via three different approaches: the use of a McCormick relaxations coupled to affine arithmetic, the propagation of affine relaxations implied by subgradients, and an enumerative approach that directly uses relaxations of each factor. The developed approaches are benchmarked on a library of optimization problems using the EAGO.jl optimizer. Two case studies are also considered to demonstrate the developments: an application in advanced manufacturing to optimize supply chain quality metrics and a global dynamic optimization application for rigorous model validation of a kinetic mechanism. The presented subgradient method leads to an improvement in CPU time required to solve the considered problems to ϵ -global optimality. [ABSTRACT FROM AUTHOR]

We consider the bound-constrained global optimization of functions with low effective dimensionality, that are constant along an (unknown) linear subspace and only vary over the effective (complement) subspace. We aim to implicitly explore the intrinsic low dimensionality of the constrained landscape using feasible random embeddings, in order to understand and improve the scalability of algorithms for the global optimization of these special-structure problems. A reduced subproblem formulation is investigated that solves the original problem over a random low-dimensional subspace subject to affine constraints, so as to preserve feasibility with respect to the given domain. Under reasonable assumptions, we show that the probability that the reduced problem is successful in solving the original, full-dimensional problem is positive. Furthermore, in the case when the objective's effective subspace is aligned with the coordinate axes, we provide an asymptotic bound on this success probability that captures its polynomial dependence on the effective and, surprisingly, ambient dimensions. We then propose X-REGO, a generic algorithmic framework that uses multiple random embeddings, solving the above reduced problem repeatedly, approximately and possibly, adaptively. Using the success probability of the reduced subproblems, we prove that X-REGO converges globally, with probability one, and linearly in the number of embeddings, to an ϵ -neighbourhood of a constrained global minimizer. Our numerical experiments on special structure functions illustrate our theoretical findings and the improved scalability of X-REGO variants when coupled with state-of-the-art global—and even local—optimization solvers for the subproblems. [ABSTRACT FROM AUTHOR]

Complex quadratic double-ratio minimax optimization (CQRMO) problem under a quadratic constraint has the potential to solve the total least squares problem. In order to solve it, a variant of S-Lemma is proposed and found to be interesting because it leads to a generalized linear conic fractional problem. Then, we achieve the global optimum of CQRMO problem with a quadratic constraint by using two algorithms for the generalized linear conic fractional problem. The efficiency of the proposed algorithms is evaluated by several numerical examples. [ABSTRACT FROM AUTHOR]

We study mixed-integer nonlinear optimization (MINLO) formulations of the disjunction x ∈ { 0 } ∪ [ ℓ , u ] , where z is a binary indicator for x ∈ [ ℓ , u ] ( 0 ≤ ℓ < u ), and y "captures" f(x), which is assumed to be convex and positive on its domain [ ℓ , u ] , but otherwise y = 0 when x = 0 . This model is very useful in nonlinear combinatorial optimization, where there is a fixed cost c for operating an activity at level x in the operating range [ ℓ , u ] , and then, there is a further (convex) variable cost f(x). So the overall cost is c z + f (x) . In applied situations, there can be N 4-tuples (f , ℓ , u , c) , and associated (x, y, z), and so, the combinatorial nature of the problem is that for any of the 2 N choices of the binary z-variables, the non-convexity associated with each of the (f , ℓ , u) goes away. We study relaxations related to the perspective transformation of a natural piecewise-linear under-estimator of f, obtained by choosing linearization points for f. Using 3-d volume (in (x, y, z)) as a measure of the tightness of a convex relaxation, we investigate relaxation quality as a function of f, ℓ , u, and the linearization points chosen. We make a detailed investigation for convex power functions f (x) : = x p , p > 1 . [ABSTRACT FROM AUTHOR]

We study conjugate and Lagrange dualities for composite optimization problems within the framework of abstract convexity. We provide conditions for zero duality gap in conjugate duality. For Lagrange duality, intersection property is applied to obtain zero duality gap. Connection between Lagrange dual and conjugate dual is also established. Examples related to convex and weakly convex functions are given. [ABSTRACT FROM AUTHOR]

We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the Reformulation-Linearization Technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added to tighten the relaxation, is vacuously satisfied and can thus be omitted, and (ii) the number of decision variables in the RLT relaxation can be reduced from O (n 2) to O (n) . Taken together, both observations allow us to reduce computation times by up to several orders of magnitude. Our results can be specialized to indefinite quadratic optimization problems over simplices and extended to non-convex optimization problems over the Cartesian product of two simplices as well as specific classes of polyhedral and non-convex feasible regions. Our numerical experiments illustrate the promising performance of the proposed framework. [ABSTRACT FROM AUTHOR]

A small polygon is a polygon of unit diameter. The maximal perimeter and the maximal width of a convex small polygon with n = 2 s vertices are not known when s ≥ 4 . In this paper, we construct a family of convex small n-gons, n = 2 s and s ≥ 3 , and show that the perimeters and the widths obtained cannot be improved for large n by more than a / n 6 and b / n 4 respectively, for certain positive constants a and b. In addition, assuming that a conjecture of Mossinghoff is true, we formulate the maximal perimeter problem as a nonlinear optimization problem involving trigonometric functions and, for n = 2 s with 3 ≤ s ≤ 7 , we provide global optimal solutions. [ABSTRACT FROM AUTHOR]

We propose a new decomposition method to solve multistage non-convex mixed-integer (stochastic) nonlinear programming problems (MINLPs). We call this algorithm non-convex nested Benders decomposition (NC-NBD). NC-NBD is based on solving dynamically improved mixed-integer linear outer approximations of the MINLP, obtained by piecewise linear relaxations of nonlinear functions. Those MILPs are solved to global optimality using an enhancement of nested Benders decomposition, in which regularization, dynamically refined binary approximations of the state variables and Lagrangian cut techniques are combined to generate Lipschitz continuous non-convex approximations of the value functions. Those approximations are then used to decide whether the approximating MILP has to be dynamically refined and in order to compute feasible solutions for the original MINLP. We prove that NC-NBD converges to an ε -optimal solution in a finite number of steps. We provide promising computational results for some unit commitment problems of moderate size. [ABSTRACT FROM AUTHOR]

The celebrated Motzkin–Straus formulation for the maximum clique problem provides a nontrivial characterization of the clique number of a graph in terms of the maximum value of a nonconvex quadratic function over a standard simplex. It was originally developed as a way of proving Turán's theorem in graph theory, but was later used to develop competitive algorithms for the maximum clique problem based on continuous optimization. Clique relaxations, such as s-defective clique and s-plex, emerged as attractive, more practical alternatives to cliques in network-based cluster detection models arising in numerous applications. This paper establishes continuous cubic formulations for the maximum s-defective clique problem and the maximum s-plex problem by generalizing the Motzkin–Straus formulation to the corresponding clique relaxations. The formulations are used to extend Turán's theorem and other known lower bounds on the clique number to the considered clique relaxations. Results of preliminary numerical experiments with the CONOPT solver demonstrate that the proposed formulations can be used to quickly compute high-quality solutions for the maximum s-defective clique problem and the maximum s-plex problem. The proposed formulations can also be used to generate interesting test instances for global optimization solvers. [ABSTRACT FROM AUTHOR]

We consider the global optimization of nonconvex mixed-integer quadratic programs with linear equality constraints. In particular, we present a new class of convex quadratic relaxations which are derived via quadratic cuts. To construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of specialized solution algorithms. Our quadratic cuts are nonconvex, but define a convex feasible set when intersected with the equality constraints. We show that our relaxations are an outer-approximation of a semi-infinite convex program which under certain conditions is equivalent to a well-known semidefinite program relaxation. The new relaxations are implemented in the global optimization solver BARON, and tested by conducting numerical experiments on a large collection of problems. Results demonstrate that, for our test problems, these relaxations lead to a significant improvement in the performance of BARON. [ABSTRACT FROM AUTHOR]