A geometric framework for nonconvex optimization duality using augmented lagrangian functions

We provide a unifying geometric framework for the analysis of general classes of duality schemes and penalty methods for nonconvex constrained optimization problems. We present a separation result for nonconvex sets via general concave surfaces. We use this separation result to provide necessary and sufficient conditions for establishing strong duality between geometric primal and dual problems. Using the primal function of a constrained optimization problem, we apply our results both in the analysis of duality schemes constructed using augmented Lagrangian functions, and in establishing necessary and sufficient conditions for the convergence of penalty methods.     

A Branch-and-Bound Approach for Solving a Class of Generalized Semi-infinite Programming Problems

A nonconvex generalized semi-infinite programming problem is considered, involving parametric max-functions in both the objective and the constraints. For a fixed vector of parameters, the values of these parametric max-functions are given as optimal values of convex quadratic programming problems. Assuming that for each parameter the parametric quadratic problems satisfy the strong duality relation, conditions are described ensuring the uniform boundedness of the optimal sets of the dual problems w.r.t. the parameter. Finally a branch-and-bound approach is suggested transforming the problem of finding an approximate global minimum of the original nonconvex optimization problem into the solution of a finite number of convex problems.     

Lagrange Duality and Partitioning Techniques in Nonconvex Global Optimization

It is shown that, for very general classes of nonconvex global optimization problems, the duality gap obtained by solving a corresponding Lagrangian dual in reduced to zero in the limit when combined with suitably refined partitioning of the feasible set. A similar result holds for partly convex problems where exhaustive partitioning is applied only in the space of nonconvex variables. Applications include branch-and-bound approaches for linearly constrained problems where convex envelopes can be computed, certain generalized bilinear problems, linearly constrained optimization of the sum of ratios of affine functions, and concave minimization under reverse convex constraints.     

Improve-and-Branch Algorithm for the Global Optimization of Nonconvex NLP Problems

A new algorithm to solve nonconvex NLP problems is presented. It is based on the solution of two problems. The reformulated problem RP is a suitable reformulation of the original problem and involves convex terms and concave univariate terms. The main problem MP is a nonconvex NLP that outer-approximates the feasible region and underestimate the objective function. MP involves convex terms and terms which are the products of concave univariate functions and new variables. Fixing the variables in the concave terms, a convex NLP that overestimates the feasible region and underestimates the objective function is obtained from the MP. Like most of the deterministic global optimization algorithms, bounds on all the variables in the nonconvex terms must be provided. MP forces the objective value to improve and minimizes the difference of upper and lower bound of all the variables either to zero or to a positive value. In the first case, a feasible solution of the original problem is reached and the objective function is improved. In general terms, the second case corresponds to an infeasible solution of the original problem due to the existence of gaps in some variables. A branching procedure is performed in order to either prove that there is no better solution or reduce the domain, eliminating the local solution of MP that was found. The MP solution indicates a key point to do the branching. A bound reduction technique is implemented to accelerate the convergence speed. Computational results demonstrate that the algorithm compares very favorably to other approaches when applied to test problems and process design problems. It is typically faster and it produces very accurate results.     

Global Solution Approach for a Nonconvex MINLP Problem in Product Portfolio Optimization

The rigorous and efficient determination of the global solution of a nonconvex MINLP problem arising from product portfolio optimization introduced by Kallrath (2003) is addressed. The objective of the optimization problem is to determine the optimal number and capacity of reactors satisfying the demand and leading to a minimal total cost. Based on the model developed by Kallrath (2003), an improved formulation is proposed, which consists of a concave objective function and linear constraints with binary and continuous variables. A variety of techniques are developed to tighten the model and accelerate the convergence to the optimal solution. A customized branch and bound approach that exploits the special mathematical structure is proposed to solve the model to global optimality. Computational results for two case studies are presented. In both case studies, the global solutions are obtained and proved optimal very efficiently in contrast to available commercial MINLP solvers.     

DC approach to weakly convex optimization and nonconvex quadratic optimization problems

Motivated by weakly convex optimization and quadratic optimization problems, we first show that there is no duality gap between a difference of convex (DC) program over DC constraints and its associated dual problem. We then provide certificates of global optimality for a class of nonconvex optimization problems. As an application, we derive characterizations of robust solutions for uncertain general nonconvex quadratic optimization problems over nonconvex quadratic constraints.     

Solutions to quadratic minimization problems with box and integer constraints

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.     

Global minimization of a generalized convex multiplicative function

This paper discusses an algorithm for generalized convex multiplicative programming problems, a special class of nonconvex minimization problems in which the objective function is expressed as a sum ofp products of two convex functions. It is shown that this problem can be reduced to a concave minimization problem with only 2p variables. An outer approximation algorithm is proposed for solving the resulting problem.     

Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.     

Unconstrained and constrained global optimization of polynomial functions in one variable

In Floudas and Visweswaran (1990), a new global optimization algorithm (GOP) was proposed for solving constrained nonconvex problems involving quadratic and polynomial functions in the objective function and/or constraints. In this paper, the application of this algorithm to the special case of polynomial functions of one variable is discussed. The special nature of polynomial functions enables considerable simplification of the GOP algorithm. The primal problem is shown to reduce to a simple function evaluation, while the relaxed dual problem is equivalent to the simultaneous solution of two linear equations in two variables. In addition, the one-to-one correspondence between the x and y variables in the problem enables the iterative improvement of the bounds used in the relaxed dual problem. The simplified approach is illustrated through a simple example that shows the significant improvement in the underestimating function obtained from the application of the modified algorithm. The application of the algorithm to several unconstrained and constrained polynomial function problems is demonstrated.     

Solving dual problems using a coevolutionary optimization algorithm

In solving certain optimization problems, the corresponding Lagrangian dual problem is often solved simply because in these problems the dual problem is easier to solve than the original primal problem. Another reason for their solution is the implication of the weak duality theorem which suggests that under certain conditions the optimal dual function value is smaller than or equal to the optimal primal objective value. The dual problem is a special case of a bilevel programming problem involving Lagrange multipliers as upper-level variables and decision variables as lower-level variables. Another interesting aspect of dual problems is that both lower and upper-level optimization problems involve only box constraints and no other equality of inequality constraints. In this paper, we propose a coevolutionary dual optimization (CEDO) algorithm for co-evolving two populations—one involving Lagrange multipliers and other involving decision variables—to find the dual solution. On 11 test problems taken from the optimization literature, we demonstrate the efficacy of CEDO algorithm by comparing it with a couple of nested smooth and nonsmooth algorithms and a couple of previously suggested coevolutionary algorithms. The performance of CEDO algorithm is also compared with two classical methods involving nonsmooth (bundle) optimization methods. As a by-product, we analyze the test problems to find their associated duality gap and classify them into three categories having zero, finite or infinite duality gaps. The development of a coevolutionary approach, revealing the presence or absence of duality gap in a number of commonly-used test problems, and efficacy of the proposed coevolutionary algorithm compared to usual nested smooth and nonsmooth algorithms and other existing coevolutionary approaches remain as the hallmark of the current study.     

非凸集值优化问题严有效解的强对偶定理

本文研究了非凸集值向量优化的严有效解在两种对偶模型的强对偶问题.利用Lagrange对偶和Mond-Weir对偶原理,获得了如下结果：原集值优化问题的严有效解,在一些条件下是对偶问题的强有效解,并且原问题和对偶问题的目标函数值相等;推广了集值优化对偶理论在锥-凸假设下的相应结果.     

Multiobjective Control Approximation Problems: Duality and Optimality

A general convex multiobjective control approximation problem is considered with respect to duality. The single objectives contain linear functionals and powers of norms as parts, measuring the distance between linear mappings of the control variable and the state variables. Moreover, linear inequality constraints are included. A dual problem is established, and weak and strong duality properties as well as necessary and sufficient optimality conditions are derived. Point-objective location problems and linear vector optimization problems turn out to be special cases of the problem investigated. Therefore, well-known duality results for linear vector optimization are obtained as special cases.     

Some Farkas-type results for fractional programming problems with DC functions

For a kind of fractional programming problem that the objective functions are the ratio of two DC (difference of convex) functions with finitely many convex constraints, in this paper, its dual problems are constructed, weak and strong duality assertions are given, and some sufficient and necessary optimality conditions which characterize their optimal solutions are obtained. Some recently obtained Farkas-type results for fractional programming problems that the objective functions are the ratio of a convex function to a concave function with finitely many convex constraints are the special cases of the general results of this paper.     

A Global Optimization Method,QBB, for Twice-Differentiable Nonconvex Optimization Problem

A global optimization method, QBB, for twice-differentiable NLPs (Non-Linear Programming) is developed to operate within a branch-and-bound framework and require the construction of a relaxed convex problem on the basis of the quadratic lower bounding functions for the generic nonconvex structures. Within an exhaustive simplicial division of the constrained region, the rigorous quadratic underestimation function is constructed for the generic nonconvex function structure by virtue of the maximal eigenvalue analysis of the interval Hessian matrix. Each valid lower bound of the NLP problem with the division progress is computed by the convex programming of the relaxed optimization problem obtained by preserving the convex or linear terms, replacing the concave term with linear convex envelope, underestimating the special terms and the generic terms by using their customized tight convex lower bounding functions or the valid quadratic lower bounding functions, respectively. The standard convergence properties of the QBB algorithm for nonconvex global optimization problems are guaranteed. The preliminary computation studies are presented in order to evaluate the algorithmic efficiency of the proposed QBB approach.     

Proper efficiency and duality for a class of multiobjective fractional variational problems containing arbitrary norms

Necessary and sufficient conditions are established for properly efficient solutions of a class of nonsmooth nonconvex variational problems with multiple fractional objective functions and nonlinear inequality constraints. Based on these proper efficiency criteria. two multiobjective dual problems are constructed and appropriate duality theorems are proved. These proper efficiency and duality results also contain as special cases similar rcsults fer constrained variational problems with multiplei fractional. and conventional objective functions, which are particular cases of the main variational problem considered in this paper     

Nonlinear Lagrangian Theory for Nonconvex Optimization

The Lagrangian function in the conventional theory for solving constrained optimization problems is a linear combination of the cost and constraint functions. Typically, the optimality conditions based on linear Lagrangian theory are either necessary or sufficient, but not both unless the underlying cost and constraint functions are also convex.We propose a somewhat different approach for solving a nonconvex inequality constrained optimization problem based on a nonlinear Lagrangian function. This leads to optimality conditions which are both sufficient and necessary, without any convexity assumption. Subsequently, under appropriate assumptions, the optimality conditions derived from the new nonlinear Lagrangian approach are used to obtain an equivalent root-finding problem. By appropriately defining a dual optimization problem and an alternative dual problem, we show that zero duality gap will hold always regardless of convexity, contrary to the case of linear Lagrangian duality.     

A convergent decomposition algorithm for support vector machines

In this work we consider nonlinear minimization problems with a single linear equality constraint and box constraints. In particular we are interested in solving problems where the number of variables is so huge that traditional optimization methods cannot be directly applied. Many interesting real world problems lead to the solution of large scale constrained problems with this structure. For example, the special subclass of problems with convex quadratic objective function plays a fundamental role in the training of Support Vector Machine, which is a technique for machine learning problems. For this particular subclass of convex quadratic problem, some convergent decomposition methods, based on the solution of a sequence of smaller subproblems, have been proposed. In this paper we define a new globally convergent decomposition algorithm that differs from the previous methods in the rule for the choice of the subproblem variables and in the presence of a proximal point modification in the objective function of the subproblems. In particular, the new rule for sequentially selecting the subproblems appears to be suited to tackle large scale problems, while the introduction of the proximal point term allows us to ensure the global convergence of the algorithm for the general case of nonconvex objective function. Furthermore, we report some preliminary numerical results on support vector classification problems with up to 100 thousands variables.     

A primal-dual trust region algorithm for nonlinear optimization

This paper concerns general (nonconvex) nonlinear optimization when first and second derivatives of the objective and constraint functions are available. The proposed method is based on finding an approximate solution of a sequence of unconstrained subproblems parameterized by a scalar parameter. The objective function of each unconstrained subproblem is an augmented penalty-barrier function that involves both primal and dual variables. Each subproblem is solved using a second-derivative Newton-type method that employs a combined trust region and line search strategy to ensure global convergence. It is shown that the trust-region step can be computed by factorizing a sequence of systems with diagonally-modified primal-dual structure, where the inertia of these systems can be determined without recourse to a special factorization method. This has the benefit that off-the-shelf linear system software can be used at all times, allowing the straightforward extension to large-scale problems. Numerical results are given for problems in the COPS test collection.Mathematics Subject Classification (2000): 49M37, 65F05, 65K05, 90C30This paper is dedicated to Roger Fletcher on the occasion of his 65th birthday     

SOP: parallel surrogate global optimization with Pareto center selection for computationally expensive single objective problems

This paper presents a canonical dual approach for solving a nonconvex global optimization problem governed by a sum of 4th-order polynomial and a log-sum-exp function. Such a problem arises extensively in engineering and sciences. Based on the canonical duality–triality theory, this nonconvex problem is transformed to an equivalent dual problem, which can be solved easily under certain conditions. We proved that both global minimizer and the biggest local extrema of the primal problem can be obtained analytically from the canonical dual solutions. As two special cases, a quartic polynomial minimization and a minimax problem are discussed. Existence conditions are derived, which can be used to classify easy and relative hard instances. Applications are illustrated by several nonconvex and nonsmooth examples.