We propose a descent subgradient algorithm for minimizing a function $ f:\mathbb {R}n\to \mathbb {R} $ f:Rn -> R, assumed to be locally Lipschitz, but not necessarily smooth or convex. To find an effective descent ...
详细信息
We propose a descent subgradient algorithm for minimizing a function $ f:\mathbb {R}<^>n\to \mathbb {R} $ f:Rn -> R, assumed to be locally Lipschitz, but not necessarily smooth or convex. To find an effective descent direction, the Goldstein epsilon-subdifferential is approximated through an iterative process. The method enjoys a new two-point variant of Mifflin's line search in which the subgradients are arbitrary. Thus, the line search procedure is easy to implement. Moreover, in comparison to bundle methods, the quadratic subproblems have a simple structure, and to handle nonconvexity the proposed method requires no algorithmic modification. We study the global convergence of the method and prove that any accumulation point of the generated sequence is Clarke stationary, assuming that the objective f is weakly upper semismooth. We illustrate the efficiency and effectiveness of the proposed algorithm on a collection of academic and semi-academic test problems.
Deterministic nonconvex optimization solvers generate convex relaxations of noncon-vex functions by making use of underlying factorable representations. One approach introduces auxiliary variables assigned to each fac...
详细信息
Deterministic nonconvex optimization solvers generate convex relaxations of noncon-vex 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 under-lying 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 *** 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 is an element of-global optimality.
We propose a new variational model in Sobolev-Orlicz spaces with non-standard growth conditions of the objective functional and discuss its applications to image processing. The characteristic feature of the proposed ...
详细信息
We propose a new variational model in Sobolev-Orlicz spaces with non-standard growth conditions of the objective functional and discuss its applications to image processing. The characteristic feature of the proposed model is that the variable exponent, which is associated with non-standard growth, is unknown a priori and it depends on a particular function that belongs to the domain of objective functional. So, we deal with a constrained minimization problem that lives in variable Sobolev-Orlicz spaces. In view of this, we discuss the consistency of the proposed model, give the scheme for its regularization, derive the corresponding optimality system, and propose an iterative algorithm for practical implementations.
This paper considers general separable pseudoconvex optimization problems with continuous complicating variables in which primal and projected problems are both pseudoconvex problems. A novel decomposition method base...
详细信息
This paper considers general separable pseudoconvex optimization problems with continuous complicating variables in which primal and projected problems are both pseudoconvex problems. A novel decomposition method based on generalized Benders decomposition, named nonconvex sensitivity-based generalized Benders decomposition, is developed and proved strictly to obtain optimal solutions of general separable pseudoconvex optimization problems of interest without constructing surrogate models. By the use of a reformulation strategy (introducing an extra equality constraint and constructing several subproblems), the algorithm handles the nonconvexity by direct manipulations of consistent linear Benders cuts and the check of optimality conditions and approximating the feasible region of complicating variables by supporting hyperplanes. The master problems of the new algorithm are always linear programming problems and the solution of the algorithm contains sensitivity information about complicating variables. Moreover, the new algorithm could also be used as a tool to check the nonconvexity of an optimization problem. Two cases are given to confirm the validity and applicability of the proposed algorithm.
In convex optimization problems, characterizations of the solution set in terms of the classical subdifferentials have been investigated by Mangasarian. In quasiconvex optimization problems, characterizations of the s...
详细信息
In convex optimization problems, characterizations of the solution set in terms of the classical subdifferentials have been investigated by Mangasarian. In quasiconvex optimization problems, characterizations of the solution set for quasiconvex programming in terms of the Greenberg-Pierskalla subdifferentials were given by Suzuki and Kuroiwa. In this paper, our attention focuses on the class of tangentially convex functions. Indeed, we study characterizations of the solution set for tangentially convex optimization problems in terms of subdifferentials. For this purpose, we use tangential subdifferentials and the Greenberg-Pierskalla subdifferentials and present necessary and sufficient optimality conditions for tangentially convex optimization problems. As a consequence, we investigate characterizations of the solution set in terms of tangential subdifferentials and the Greenberg-Pierskalla subdifferentials for tangentially convex optimization problems. Moreover, we compare our results with previous ones.
In this paper, an efficient implementation of aggregate homotopy method for nonconvex nonlinear programming problems is proposed. Adopting truncated aggregate technique, only a small subset of the constraints is aggre...
详细信息
In this paper, an efficient implementation of aggregate homotopy method for nonconvex nonlinear programming problems is proposed. Adopting truncated aggregate technique, only a small subset of the constraints is aggregated at each iteration, hence the number of gradient and Hessian calculations is reduced dramatically. The subset is adaptively updated with some cheaply implementable truncating criterions, to guarantee the locally quadratic convergence of the correction process with as few computation cost as possible. Numerical tests with comparison to some other methods show that the new method is very efficient, especially for the problems with large amount of constraints and {computationally expensive} gradients or Hessians.
In this paper, we extend the concept of quasidifferential to a new notion called semi-quasidifferential. This generalization is motivated by the convexificator notion. Some important properties of semiquasidifferentia...
详细信息
In this paper, we extend the concept of quasidifferential to a new notion called semi-quasidifferential. This generalization is motivated by the convexificator notion. Some important properties of semiquasidifferentials are established. The relationship between semi-quasidifferentials and the Clarke sub differential is studied, and a mean value theorem in terms of semi-quasidifferentials is proved. It is shown that this notion is helpful to investigate nonsmooth optimization problems even when the objective and/or constraint functions are discontinuous. Considering a multiobjective optimization problem, a characterization of some cones related to the feasible set is provided. They are used for deriving necessary and sufficient optimality conditions. We close the paper by obtaining optimality conditions in multi objective optimization in terms of semi-quasidifferentials. Some outcomes of the current work generalize the related results existing in the literature. (c) 2021 Elsevier B.V. All rights reserved.
Cross-manifold clustering is an extreme challenge learning problem. Since the low-density hypothesis is not satisfied in cross-manifold problems, many traditional clustering methods failed to discover the cross-manifo...
详细信息
Cross-manifold clustering is an extreme challenge learning problem. Since the low-density hypothesis is not satisfied in cross-manifold problems, many traditional clustering methods failed to discover the cross-manifold structures. In this article, we propose multiple flat projections clustering (MFPC) for cross-manifold clustering. In our MFPC, the given samples are projected into multiple localized flats to discover the global structures of implicit manifolds. Thus, the intersected clusters are distinguished in various projection flats. In MFPC, a series of nonconvex matrix optimization problems is solved by a proposed recursive algorithm. Furthermore, a nonlinear version of MFPC is extended via kernel tricks to deal with a more complex cross-manifold learning situation. The synthetic tests show that our MFPC works on the cross-manifold structures well. Moreover, experimental results on the benchmark datasets and object tracking videos show excellent performance of our MFPC compared with some state-of-the-art manifold clustering methods.
An extensible open-source deterministic global optimizer (EAGO) programmed entirely in the Julia language is presented. EAGO was developed to serve the need for supporting higher-complexity user-defined functions (e.g...
详细信息
An extensible open-source deterministic global optimizer (EAGO) programmed entirely in the Julia language is presented. EAGO was developed to serve the need for supporting higher-complexity user-defined functions (e.g. functions defined implicitly via algorithms) within optimization models. EAGO embeds a first-of-its-kind implementation of McCormick arithmetic in an Evaluator structure allowing for the construction of convex/concave relaxations using a combination of source code transformation, multiple dispatch, and context-specific approaches. Utilities are included to parse user-defined functions into a directed acyclic graph representation and perform symbolic transformations enabling dramatically improved solution speed. EAGO is compatible with a wide variety of local optimizers, the most exhaustive library of transcendental functions, and allows for easy accessibility through the JuMP modelling language. Together with Julia's minimalist syntax and competitive speed, these powerful features make EAGO a versatile research platform enabling easy construction of novel meta-solvers, incorporation and utilization of new relaxations, and extension to advanced problem formulations encountered in engineering and operations research (e.g. multilevel problems, user-defined functions). The applicability and flexibility of this novel software is demonstrated on a diverse set of examples. Lastly, EAGO is demonstrated to perform comparably to state-of-the-art commercial optimizers on a benchmarking test set.
This work builds upon the theoretical and numerical results of the recently proposed Penalized Algorithm for Constrained Nonsmooth Optimization (PACNO). Our contribution is threefold. Instead of resting upon approxima...
详细信息
This work builds upon the theoretical and numerical results of the recently proposed Penalized Algorithm for Constrained Nonsmooth Optimization (PACNO). Our contribution is threefold. Instead of resting upon approximate stationary points of the subproblems, approximate local minimizers are assumed to be computed. Consequently, a stronger convergence result is obtained, based on a new sequential optimality condition. Moreover, using a blackbox minimization framework and hard-sphere instances, the intrinsic parameters of PACNO have been adjusted, improving outcomes from the literature for the kissing problem, which consists of determining the maximum number of non-overlapping and equal spheres that can touch simultaneously a given sphere of the same size. Finally, the so-called double-kissing problem has been modeled: two equal and touching spheres are provided, and one aims at finding the maximum number of non-overlapping spheres, having the same radius of the given pair, which can be arranged so that each of them touches at least one of the stated spheres. A nonsmooth formulation for the double-kissing problem is devised, and the solutions of bi-, three-, and four-dimensional instances are successfully achieved.
暂无评论