An algorithm for nonlinear optimization problems with binary variables

One of the challenging optimization problems is determining the minimizer of a nonlinear programming problem that has binary variables. A vexing difficulty is the rate the work to solve such problems increases as the number of discrete variables increases. Any such problem with bounded discrete variables, especially binary variables, may be transformed to that of finding a global optimum of a problem in continuous variables. However, the transformed problems usually have astronomically large numbers of local minimizers, making them harder to solve than typical global optimization problems. Despite this apparent disadvantage, we show that the approach is not futile if we use smoothing techniques. The method we advocate first convexifies the problem and then solves a sequence of subproblems, whose solutions form a trajectory that leads to the solution. To illustrate how well the algorithm performs we show the computational results of applying it to problems taken from the literature and new test problems with known optimal solutions.     

αBB: A global optimization method for general constrained nonconvex problems

A branch and bound global optimization method,BB, for general continuous optimization problems involving nonconvexities in the objective function and/or constraints is presented. The nonconvexities are categorized as being either of special structure or generic. A convex relaxation of the original nonconvex problem is obtained by (i) replacing all nonconvex terms of special structure (i.e. bilinear, fractional, signomial) with customized tight convex lower bounding functions and (ii) by utilizing the parameter as defined in [17] to underestimate nonconvex terms of generic structure. The proposed branch and bound type algorithm attains finite-convergence to the global minimum through the successive subdivision of the original region and the subsequent solution of a series of nonlinear convex minimization problems. The global optimization method,BB, is implemented in C and tested on a variety of example problems.     

An improved hybrid global optimization method for protein tertiary structure prediction

First principles approaches to the protein structure prediction problem must search through an enormous conformational space to identify low-energy, near-native structures. In this paper, we describe the formulation of the tertiary structure prediction problem as a nonlinear constrained minimization problem, where the goal is to minimize the energy of a protein conformation subject to constraints on torsion angles and interatomic distances. The core of the proposed algorithm is a hybrid global optimization method that combines the benefits of the αBB deterministic global optimization approach with conformational space annealing. These global optimization techniques employ a local minimization strategy that combines torsion angle dynamics and rotamer optimization to identify and improve the selection of initial conformations and then applies a sequential quadratic programming approach to further minimize the energy of the protein conformations subject to constraints. The proposed algorithm demonstrates the ability to identify both lower energy protein structures, as well as larger ensembles of low-energy conformations.     

An adaptive nonmonotone global Barzilai–Borwein gradient method for unconstrained optimization

The Barzilai–Borwein (BB) gradient method has received many studies due to its simplicity and numerical efficiency. By incorporating a nonmonotone line search, Raydan (SIAM J Optim. 1997;7:26–33) has successfully extended the BB gradient method for solving general unconstrained optimization problems so that it is competitive with conjugate gradient methods. However, the numerical results reported by Raydan are poor for very ill-conditioned problems because the effect of the degree of nonmonotonicity may be noticeable. In this paper, we focus more on the nonmonotone line search technique used in the global Barzilai–Borwein (GBB) gradient method. We improve the performance of the GBB gradient method by proposing an adaptive nonmonotone line search based on the morphology of the objective function. We also prove the global convergence and the R-linear convergence rate of the proposed method under reasonable assumptions. Finally, we give some numerical experiments made on a set of unconstrained optimization test problems of the CUTEr collection. The results show the efficiency of the proposed method in the sense of the performance profile introduced (Math Program. 2002;91:201–213) by Dolan and Moré.     

On the continuity of the minima for a family of constrained optimization problems ∗

We consider a family of problems Py dealing with the minimization of a given function on a constraint set, both depending on a parameter y. We study continuity properties, with respect to a parameter, of the value and of the solution set of the problems. Working with convex functions and convex constraint sets, we show how the well-posedness of the problem allows to avoid compactness hypotheses usually requested to get the same stability results.     

Adaptive methods for solvings minimax problems ∗

We consider finite-dimensional minimax problems for two traditional models: firstly,with box constraints at variables and,secondly,taking into account a finite number of tinear inequalities. We present finite exact primal and dual methods. These methods are adapted to a great extent to the specific structure of the cost function which is formed by a finite number of linear functions. During the iterations of the primal method we make use of the information from the dual problem, thereby increasing effectiveness. To improve the dual method we use the “long dual step” rule (the principle of ullrelaxation).The results are illustrated by numerical experiments.     

An Eulerian–Lagrangian method for optimization problems governed by multidimensional nonlinear hyperbolic PDEs

We present a numerical method for solving tracking-type optimal control problems subject to scalar nonlinear hyperbolic balance laws in one and two space dimensions. Our approach is based on the formal optimality system and requires numerical solutions of the hyperbolic balance law forward in time and its nonconservative adjoint equation backward in time. To this end, we develop a hybrid method, which utilizes advantages of both the Eulerian finite-volume central-upwind scheme (for solving the balance law) and the Lagrangian discrete characteristics method (for solving the adjoint transport equation). Experimental convergence rates as well as numerical results for optimization problems with both linear and nonlinear constraints and a duct design problem are presented.     

Generalized Benders’ Decomposition for topology optimization problems

This article considers the non-linear mixed 0–1 optimization problems that appear in topology optimization of load carrying structures. The main objective is to present a Generalized Benders’ Decomposition (GBD) method for solving single and multiple load minimum compliance (maximum stiffness) problems with discrete design variables to global optimality. We present the theoretical aspects of the method, including a proof of finite convergence and conditions for obtaining global optimal solutions. The method is also linked to, and compared with, an Outer-Approximation approach and a mixed 0–1 semi definite programming formulation of the considered problem. Several ways to accelerate the method are suggested and an implementation is described. Finally, a set of truss topology optimization problems are numerically solved to global optimality.     

Computing global minima to polynomial optimization problems using Gröbner bases

The local optimality conditions to polynomial optimization problems are a set of polynomial equations (plus some inequality conditions). With the recent techniques of Gröbner bases one can find all solutions to such systems, and hence also find global optima. We give a short survey of these methods. We also apply them to a set of problems termed with exact solutions unknown in the problem sets of Hock and Schittkowski. To these problems we give exact solutions.     

Forward–backward quasi-Newton methods for nonsmooth optimization problems

The forward–backward splitting method (FBS) for minimizing a nonsmooth composite function can be interpreted as a (variable-metric) gradient method over a continuously differentiable function which we call forward–backward envelope (FBE). This allows to extend algorithms for smooth unconstrained optimization and apply them to nonsmooth (possibly constrained) problems. Since the FBE can be computed by simply evaluating forward–backward steps, the resulting methods rely on a similar black-box oracle as FBS. We propose an algorithmic scheme that enjoys the same global convergence properties of FBS when the problem is convex, or when the objective function possesses the Kurdyka–?ojasiewicz property at its critical points. Moreover, when using quasi-Newton directions the proposed method achieves superlinear convergence provided that usual second-order sufficiency conditions on the FBE hold at the limit point of the generated sequence. Such conditions translate into milder requirements on the original function involving generalized second-order differentiability. We show that BFGS fits our framework and that the limited-memory variant L-BFGS is well suited for large-scale problems, greatly outperforming FBS or its accelerated version in practice, as well as ADMM and other problem-specific solvers. The analysis of superlinear convergence is based on an extension of the Dennis and Moré theorem for the proposed algorithmic scheme.     

Characterizing switch-setting problems ∗

Algebraic conditions and algorithmic procedures are given to determine whether an m × n rectangular configuration of switches can be transformed so that all switches are in the off position, regardless of initial configuration. However, when any switch is toggled, it and its rectilinearly adjacent neighbors change state. Using linear algebra, a finite field representation of the problem, and an analysis of Fibonacci polynomials, conditions on m and n are given which characterize when the m × n problem can be solved.     

Inertial forward–backward methods for solving vector optimization problems

Abstract

We propose two forward–backward proximal point type algorithms with inertial/memory effects for determining weakly efficient solutions to a vector optimization problem consisting in vector-minimizing with respect to a given closed convex pointed cone the sum of a proper cone-convex vector function with a cone-convex differentiable one, both mapping from a Hilbert space to a Banach one. Inexact versions of the algorithms, more suitable for implementation, are provided as well, while as a byproduct one can also derive a forward–backward method for solving the mentioned problem. Numerical experiments with the proposed methods are carried out in the context of solving a portfolio optimization problem.     

Barzilai and Borwein’s method for multiobjective optimization problems

The present study is an attempt to extend Barzilai and Borwein’s method for dealing with unconstrained single objective optimization problems to multiobjective ones. As compared with Newton, Quasi-Newton and steepest descent multi-objective optimization methods, Barzilai and Borwein multiobjective optimization (BBMO) method requires simple and quick calculations in that it makes no use of the line search methods like the Armijo rule that necessitates function evaluations at each iteration. It goes without saying that the innovative aspect of the current study is due to the use of no function evaluations in comparison with other multi-objective optimization non-parametric methods (e.g. Newton, Quasi-Newton and steepest descent methods, to name a few) that have been investigated so far. Also, the convergence of the BBMO method for the objective functions assumed to be twice continuously differentiable has been proved. MATLAB software was utilized to implement the BBMO method, and the results were compared with the other methods mentioned earlier. Using some performance assessment, the quality of nondominated frontier of BBMO was analogized to above mentioned methods. In addition, the approximate nondominated frontiers gained from the methods were compared with the exact nondominated frontier for some problems. Also, performance profiles are considered to visualize numerical results presented in tables.     

Levitin–Polyak well-posedness for constrained quasiconvex vector optimization problems

In this paper, a notion of Levitin–Polyak (LP in short) well-posedness is introduced for a vector optimization problem in terms of minimizing sequences and efficient solutions. Sufficient conditions for the LP well-posedness are studied under the assumptions of compactness of the feasible set, closedness of the set of minimal solutions and continuity of the objective function. The continuity assumption is then weakened to cone lower semicontinuity for vector-valued functions. A notion of LP minimizing sequence of sets is studied to establish another set of sufficient conditions for the LP well-posedness of the vector problem. For a quasiconvex vector optimization problem, sufficient conditions are obtained by weakening the compactness of the feasible set to a certain level-boundedness condition. This in turn leads to the equivalence of LP well-posedness and compactness of the set of efficient solutions. Some characterizations of LP well-posedness are given in terms of the upper Hausdorff convergence of the sequence of sets of approximate efficient solutions and the upper semicontinuity of an approximate efficient map by assuming the compactness of the set of efficient solutions, even when the objective function is not necessarily quasiconvex. Finally, a characterization of LP well-posedness in terms of the closedness of the approximate efficient map is provided by assuming the compactness of the feasible set.     

On $$epsilon $$ ϵ -solutions for robust semi-infinite optimization problems

Positivity - In this paper, we consider semi-infinite optimization problems involving a convex objective function and infinitely many convex constraint functions with data uncertainty, and give its...     

Alternating forward–backward splitting for linearly constrained optimization problems

Optimization Letters - We present an alternating forward–backward splitting method for solving linearly constrained structured optimization problems. The algorithm takes advantage of the...     

Characterizations of ɛ-duality gap statements for constrained optimization problems

In this paper we present different regularity conditions that equivalently characterize various ?-duality gap statements (with ? ≥ 0) for constrained optimization problems and their Lagrange and Fenchel-Lagrange duals in separated locally convex spaces, respectively. These regularity conditions are formulated by using epigraphs and ?-subdifferentials. When ? = 0 we rediscover recent results on stable strong and total duality and zero duality gap from the literature.     

An inexact modified subgradient algorithm for nonconvex optimization

We propose and analyze an inexact version of the modified subgradient (MSG) algorithm, which we call the IMSG algorithm, for nonsmooth and nonconvex optimization over a compact set. We prove that under an approximate, i.e. inexact, minimization of the sharp augmented Lagrangian, the main convergence properties of the MSG algorithm are preserved for the IMSG algorithm. Inexact minimization may allow to solve problems with less computational effort. We illustrate this through test problems, including an optimal bang-bang control problem, under several different inexactness schemes.