From a Nonlinear, Nonconvex Variational Problem to a Linear, Convex Formulation

   Abstract. We propose a general approach to deal with nonlinear, nonconvex variational problems based on a reformulation of the problem resulting in an optimization problem with linear cost functional and convex constraints. As a first step we explicitly explore these ideas to some one-dimensional variational problems and obtain specific conclusions of an analytical and numerical nature.     

On generalized geometric programming problems with non-positive variables

Generalized geometric programming (GGP) problems occur frequently in engineering design and management. Some exponential-based decomposition methods have been developed for solving global optimization of GGP problems. However, the use of logarithmic/exponential transformations restricts these methods to handle the problems with strictly positive variables. This paper proposes a technique for treating non-positive variables with integer powers in GGP problems. By means of variable transformation, the GGP problem with non-positive variables can be equivalently solved with another one having positive variables. In addition, we present some computationally efficient convexification rules for signomial terms to enhance the efficiency of the optimization approach. Numerical examples are presented to demonstrate the usefulness of the proposed method in GGP problems with non-positive variables.     

A unified framework for constructing globally convergent algorithms for multidimensional coefficient inverse problems

We present a unified framework for constructing the globally convergent algorithms for a broad class of multidimensional coefficient inverse problems arising in natural science and industry. Based on the convexification approach, the unified framework substantiates the numerical solution of the corresponding problem of nonconvex optimization. A globally convergent iterative algorithm for an inverse problem of diffuse optical mammography is constructed. It utilizes the contraction property of a nonlinear operator resulting from applying the convexification approach. The effectiveness of this algorithm is demonstrated in computational experiments.     

A class of convexification and concavification methods for non-monotone optimization problems

A class of convexification and concavification methods are proposed for solving some classes of non-monotone optimization problems. It is shown that some classes of non-monotone optimization problems can be converted into better structured optimization problems, such as, concave minimization problems, reverse convex programming problems, and canonical D.C. programming problems by the proposed convexification and concavification methods. The equivalence between the original problem and the converted better structured optimization problem is established.     

A STRONG OPTIMIZATION THEOREM IN LOCALLY CONVEX SPACES

This paper presents a geometric characterization of convex sets in locally convex spaces on which a strong optimization theorem of the Stegall-type holds, and gives Collier's theorem of w Asplund spaces a localized setting.     

The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables

In this paper, we compare the strength of the optimal perspective relaxation and Shor's SDP relaxation for convex quadratic optimization problems with indicator variables and prove that they are equivalent.     

On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables

In this paper, we propose a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having mixed-integer first- and second-stage variables. A modified Benders' decomposition method is developed, where the Benders' subproblems define lower bounding second-stage value functions of the first-stage variables that are derived by constructing a certain partial convex hull representation of the two-stage solution space. This partial convex hull is sequentially generated using a convexification scheme such as the Reformulation-Linearization Technique (RLT) or lift-and-project process, which yields valid inequalities that are reusable in the subsequent subproblems by updating the values of the first-stage variables. A branch-and-bound algorithm is designed based on a hyperrectangular partitioning process, using the established property that any resulting lower bounding Benders' master problem defined over a hyperrectangle yields the same objective value as the original stochastic program over that region if the first-stage variable solution is an extreme point of the defining hyperrectangle or the second-stage solution satisfies the binary restrictions. We prove that this algorithm converges to a global optimal solution. Some numerical examples and computational results are presented to demonstrate the efficacy of this approach.     

Hidden Convex Minimization

A class of nonconvex minimization problems can be classified as hidden convex minimization problems. A nonconvex minimization problem is called a hidden convex minimization problem if there exists an equivalent transformation such that the equivalent transformation of it is a convex minimization problem. Sufficient conditions that are independent of transformations are derived in this paper for identifying such a class of seemingly nonconvex minimization problems that are equivalent to convex minimization problems. Thus, a global optimality can be achieved for this class of hidden convex optimization problems by using local search methods. The results presented in this paper extend the reach of convex minimization by identifying its equivalent with a nonconvex representation.     

Global optimization of signomial geometric programming problems

This paper presents a global optimization approach for solving signomial geometric programming problems. In most cases nonconvex optimization problems with signomial parts are difficult, NP-hard problems to solve for global optimality. But some transformation and convexification strategies can be used to convert the original signomial geometric programming problem into a series of standard geometric programming problems that can be solved to reach a global solution. The tractability and effectiveness of the proposed successive convexification framework is demonstrated by seven numerical experiments. Some considerations are also presented to investigate the convergence properties of the algorithm and to give a performance comparison of our proposed approach and the current methods in terms of both computational efficiency and solution quality.     

A polyhedral branch-and-cut approach to global optimization

A variety of nonlinear, including semidefinite, relaxations have been developed in recent years for nonconvex optimization problems. Their potential can be realized only if they can be solved with sufficient speed and reliability. Unfortunately, state-of-the-art nonlinear programming codes are significantly slower and numerically unstable compared to linear programming software.In this paper, we facilitate the reliable use of nonlinear convex relaxations in global optimization via a polyhedral branch-and-cut approach. Our algorithm exploits convexity, either identified automatically or supplied through a suitable modeling language construct, in order to generate polyhedral cutting planes and relaxations for multivariate nonconvex problems. We prove that, if the convexity of a univariate or multivariate function is apparent by decomposing it into convex subexpressions, our relaxation constructor automatically exploits this convexity in a manner that is much superior to developing polyhedral outer approximators for the original function. The convexity of functional expressions that are composed to form nonconvex expressions is also automatically exploited.Root-node relaxations are computed for 87 problems from globallib and minlplib, and detailed computational results are presented for globally solving 26 of these problems with BARON 7.2, which implements the proposed techniques. The use of cutting planes for these problems reduces root-node relaxation gaps by up to 100% and expedites the solution process, often by several orders of magnitude.The research was supported in part by ExxonMobil Upstream Research Company, the National Science Foundation under awards DMII 0115166 and CTS 0124751, and the Joint NSF/NIGMS Initiative to Support Research in the Area of Mathematical Biology under NIH award GM072023.