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.     

Multiple subgradient descent bundle method for convex nonsmooth multiobjective optimization

The aim of this paper is to propose a new multiple subgradient descent bundle method for solving unconstrained convex nonsmooth multiobjective optimization problems. Contrary to many existing multiobjective optimization methods, our method treats the objective functions as they are without employing a scalarization in a classical sense. The main idea of this method is to find descent directions for every objective function separately by utilizing the proximal bundle approach, and then trying to form a common descent direction for every objective function. In addition, we prove that the method is convergent and it finds weakly Pareto optimal solutions. Finally, some numerical experiments are considered.     

Duality Principles for Optimization Problems Dealing with the Difference of Vector-Valued Convex Mappings

Using the concept of a subdifferential of a vector-valued convex mapping, we provide duality formulas for the minimization of nonconvex composite functions and related optimization problems such as the minimization of a convex function over a vectorial DC constraint.     

A Fast Space-decomposition Scheme for Nonconvex Eigenvalue Optimization

In this paper, a nonsmooth bundle algorithm to minimize the maximum eigenvalue function of a nonconvex smooth function is presented. The bundle method uses an oracle to compute separately the function and subgradient information for a convex function, and the function and derivative values for the smooth mapping. Using this information, in each iteration, we replace the smooth inner mapping by its Taylor-series linearization around the current serious step. To solve the convex approximate eigenvalue problem with affine mapping faster, we adopt the second-order bundle method based on ????-decomposition theory. Through the backtracking test, we can make a better approximation for the objective function. Quadratic convergence of our special bundle method is given, under some additional assumptions. Then we apply our method to some particular instance of nonconvex eigenvalue optimization, specifically: bilinear matrix inequality problems.     

A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes

In this paper, we develop a version of the bundle method to solve unconstrained difference of convex (DC) programming problems. It is assumed that a DC representation of the objective function is available. Our main idea is to utilize subgradients of both the first and second components in the DC representation. This subgradient information is gathered from some neighborhood of the current iteration point and it is used to build separately an approximation for each component in the DC representation. By combining these approximations we obtain a new nonconvex cutting plane model of the original objective function, which takes into account explicitly both the convex and the concave behavior of the objective function. We design the proximal bundle method for DC programming based on this new approach and prove the convergence of the method to an \(\varepsilon \)-critical point. The algorithm is tested using some academic test problems and the preliminary numerical results have shown the good performance of the new bundle method. An interesting fact is that the new algorithm finds nearly always the global solution in our test problems.     

Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations

We introduce a proximal bundle method for the numerical minimization of a nonsmooth difference-of-convex (DC) function. Exploiting some classic ideas coming from cutting-plane approaches for the convex case, we iteratively build two separate piecewise-affine approximations of the component functions, grouping the corresponding information in two separate bundles. In the bundle of the first component, only information related to points close to the current iterate are maintained, while the second bundle only refers to a global model of the corresponding component function. We combine the two convex piecewise-affine approximations, and generate a DC piecewise-affine model, which can also be seen as the pointwise maximum of several concave piecewise-affine functions. Such a nonconvex model is locally approximated by means of an auxiliary quadratic program, whose solution is used to certify approximate criticality or to generate a descent search-direction, along with a predicted reduction, that is next explored in a line-search setting. To improve the approximation properties at points that are far from the current iterate a supplementary quadratic program is also introduced to generate an alternative more promising search-direction. We discuss the main convergence issues of the line-search based proximal bundle method, and provide computational results on a set of academic benchmark test problems.     

A reformulation framework for global optimization

In this paper, we present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions two versions of the so-called αBB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem will form a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems.     

On generalized trade-off directions in nonconvex multiobjective optimization

Trade-off information related to Pareto optimal solutions is important in multiobjective optimization problems with conflicting objectives. Recently, the concept of trade-off directions has been introduced for convex problems. These trade-offs are characterized with the help of tangent cones. Generalized trade-off directions for nonconvex problems can be defined by replacing convex tangent cones with nonconvex contingent cones. Here we study how the convex concepts and results can be generalized into a nonconvex case. Giving up convexity naturally means that we need local instead of global analysis. Received: December 2000 / Accepted: October 2001?Published online February 14, 2002     

Convergence analysis of a proximal point algorithm for minimizing differences of functions

Several optimization schemes have been known for convex optimization problems. However, numerical algorithms for solving nonconvex optimization problems are still underdeveloped. A significant progress to go beyond convexity was made by considering the class of functions representable as differences of convex functions. In this paper, we introduce a generalized proximal point algorithm to minimize the difference of a nonconvex function and a convex function. We also study convergence results of this algorithm under the main assumption that the objective function satisfies the Kurdyka–?ojasiewicz property.     

On duality in multiobjective semi-infinite optimization

Abstract

In this paper, we consider multiobjective semi-infinite optimization problems which are defined in a finite-dimensional space by finitely many objective functions and infinitely many inequality constraints. We present duality results both for the convex and nonconvex case. In particular, we show weak, strong and converse duality with respect to both efficiency and weak efficiency. Moreover, the property of being a locally properly efficient point plays a crucial role in the nonconvex case.     

Duality for multiobjective optimization problems with convex objective functions and D.C. constraints

In this paper we provide a duality theory for multiobjective optimization problems with convex objective functions and finitely many D.C. constraints. In order to do this, we study first the duality for a scalar convex optimization problem with inequality constraints defined by extended real-valued convex functions. For a family of multiobjective problems associated to the initial one we determine then, by means of the scalar duality results, their multiobjective dual problems. Finally, we consider as a special case the duality for the convex multiobjective optimization problem with convex constraints.     

A dynamic gradient approach to Pareto optimization with nonsmooth convex objective functions

In a general Hilbert framework, we consider continuous gradient-like dynamical systems for constrained multiobjective optimization involving nonsmooth convex objective functions. Based on the Yosida regularization of the subdifferential operators involved in the system, we obtain the existence of strong global trajectories. We prove a descent property for each objective function, and the convergence of trajectories to weak Pareto minima. This approach provides a dynamical endogenous weighting of the objective functions, a key property for applications in cooperative games, inverse problems, and numerical multiobjective optimization.     

An efficient DC programming approach for portfolio decision with higher moments

Portfolio selection with higher moments is a NP-hard nonconvex polynomial optimization problem. In this paper, we propose an efficient local optimization approach based on DC (Difference of Convex functions) programming—called DCA (DC Algorithm)—that consists of solving the nonconvex program by a sequence of convex ones. DCA will construct, in each iteration, a suitable convex quadratic subproblem which can be easily solved by explicit method, due to the proposed special DC decomposition. Computational results show that DCA almost always converges to global optimal solutions while comparing with the global optimization methods (Gloptipoly, Branch-and-Bound) and it outperforms several standard local optimization algorithms.     

Inner and outer estimates for the solution sets and their asymptotic cones in vector optimization

We use asymptotic analysis to develop finer estimates for the efficient, weak efficient and proper efficient solution sets (and for their asymptotic cones) to convex/quasiconvex vector optimization problems. We also provide a new representation for the efficient solution set without any convexity assumption, and the estimates involve the minima of the linear scalarization of the original vector problem. Some new necessary conditions for a point to be efficient or weak efficient solution for general convex vector optimization problems, as well as for the nonconvex quadratic multiobjective optimization problem, are established.     

An interior proximal linearized method for DC programming based on Bregman distance or second-order homogeneous kernels

Abstract

We present an interior proximal method for solving constrained nonconvex optimization problems where the objective function is given by the difference of two convex function (DC function). To this end, we consider a linearized proximal method with a proximal distance as regularization. Convergence analysis of particular choices of the proximal distance as second-order homogeneous proximal distances and Bregman distances are considered. Finally, some academic numerical results are presented for a constrained DC problem and generalized Fermat–Weber location problems.     

The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation

We propose an inexact proximal bundle method for constrained nonsmooth nonconvex optimization problems whose objective and constraint functions are known through oracles which provide inexact information. The errors in function and subgradient evaluations might be unknown, but are merely bounded. To handle the nonconvexity, we first use the redistributed idea, and consider even more difficulties by introducing inexactness in the available information. We further examine the modified improvement function for a series of difficulties caused by the constrained functions. The numerical results show the good performance of our inexact method for a large class of nonconvex optimization problems. The approach is also assessed on semi-infinite programming problems, and some encouraging numerical experiences are provided.     

Generalized asymptotic functions in nonconvex multiobjective optimization problems

In this paper, we use generalized asymptotic functions and second-order asymptotic cones to develop a general existence result for the nonemptiness of the proper efficient solution set and a sufficient condition for the domination property in nonconvex multiobjective optimization problems. A new necessary condition for a point to be efficient or weakly efficient solution is given without any convexity assumption. We also provide a finer outer estimate for the asymptotic cone of the weakly efficient solution set in the quasiconvex case. Finally, we apply our results to the linear fractional multiobjective optimization problem.     

Diagonal discrete gradient bundle method for derivative free nonsmooth optimization

Typically, practical nonsmooth optimization problems involve functions with hundreds of variables. Moreover, there are many practical problems where the computation of even one subgradient is either a difficult or an impossible task. In such cases, the usual subgradient-based optimization methods cannot be used. However, the derivative free methods are applicable since they do not use explicit computation of subgradients. In this paper, we propose an efficient diagonal discrete gradient bundle method for derivative-free, possibly nonconvex, nonsmooth minimization. The convergence of the proposed method is proved for semismooth functions, which are not necessarily differentiable or convex. The method is implemented using Fortran 95, and the numerical experiments confirm the usability and efficiency of the method especially in case of large-scale problems.     

A sequential parametric convex approximation method with applications to nonconvex truss topology design problems

We describe a general scheme for solving nonconvex optimization problems, where in each iteration the nonconvex feasible set is approximated by an inner convex approximation. The latter is defined using an upper bound on the nonconvex constraint functions. Under appropriate conditions, a monotone convergence to a KKT point is established. The scheme is applied to truss topology design (TTD) problems, where the nonconvex constraints are associated with bounds on displacements and stresses. It is shown that the approximate convex problem solved at each inner iteration can be cast as a conic quadratic programming problem, hence large scale TTD problems can be efficiently solved by the proposed method.     

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.