In this paper, we develop an enhanced intersection cutting-plane algorithm for solving a mixed integer 0-1 bilinear programming formulation of the linear complementarity problem (LCP). The matrix M associated with the...
详细信息
In this paper, we develop an enhanced intersection cutting-plane algorithm for solving a mixed integer 0-1 bilinear programming formulation of the linear complementarity problem (LCP). The matrix M associated with the LCP is not assumed to possess any special structure, except that the corresponding feasible region is assumed to be bounded. A procedure is described to generate cuts that are deeper versions of the Tuy intersection cuts, based on a relaxation of the usual polar set. The proposed algorithm then attempts to find an LCP solution in the process of generating either a single or a pair of such strengthened intersection cuts. The process of generating these cuts involves a vertex-ranking scheme that either finds an LCP solution, or else these cuts eliminate the entire feasible region leading to the conclusion that no LCP solution exists. Computational experience on various test problems is provided.
A nonconvex variational model is introduced which contains the l(q)-"norm," q is an element of (0, 1), of the gradient of the underlying image in the regularization part together with a least squares-type da...
详细信息
A nonconvex variational model is introduced which contains the l(q)-"norm," q is an element of (0, 1), of the gradient of the underlying image in the regularization part together with a least squares-type data fidelity term which may depend on a possibly spatially dependent weighting parameter. Hence, the regularization term in this functional is a nonconvex compromise between the minimization of the support of the reconstruction and the classical convex total variation model. In the discrete setting, existence of a minimizer is proved, and a Newton-type solution algorithm is introduced and its global as well as local superlinear convergence toward a stationary point of a locally regularized version of the problem is established. The potential nonpositive definiteness of the Hessian of the objective during the iteration is handled by a trust-region-based regularization scheme. The performance of the new algorithm is studied by means of a series of numerical tests. For the associated infinite dimensional model an existence result based on the weakly lower semicontinuous envelope is established, and its relation to the original problem is discussed.
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.
Low-rank representation (LRR) intends to find the representation with lowest rank of a given data set, which can be formulated as a rank-minimisation problem. Since the rank operator is non-convex and discontinuous, m...
详细信息
Low-rank representation (LRR) intends to find the representation with lowest rank of a given data set, which can be formulated as a rank-minimisation problem. Since the rank operator is non-convex and discontinuous, most of the recent works use the nuclear norm as a convex relaxation. It is theoretically shown that, under some conditions, the Frobenius-norm-based optimisation problem has a unique solution that is also a solution of the original LRR optimisation problem. In other words, it is feasible to apply the Frobenius norm as a surrogate of the non-convex matrix rank function. This replacement will largely reduce the time costs for obtaining the lowest-rank solution. Experimental results show that the method (i.e. fast LRR (fLRR)) performs well in terms of accuracy and computation speed in image clustering and motion segmentation compared with nuclear-norm-based LRR algorithm.
作者：
FULOP, JHUNGARIAN ACAD SCI
INST COMP & AUTOMAT DEPT OPERAT RES KENDE U 13-17 H-1502 BUDAPEST HUNGARY
The paper deals with linear programs with an additional reverse convex constraint. If the feasible region of this problem is nonempty and the objective function to be minimized is bounded below on it, then the problem...
详细信息
The paper deals with linear programs with an additional reverse convex constraint. If the feasible region of this problem is nonempty and the objective function to be minimized is bounded below on it, then the problem has a finite minimum obtained on an at most one-dimensional face of the polyhedron as well. This paper presents a finite cutting plane method using convexity and disjunctive cuts for solving the considered problem. The method is based upon a procedure which, for a given nonnegative integer q, either finds such an at most q-dimensional face of the original polyhedron which has a point feasible to the cuts generated previously or proves that there exists no such a face. Computational experience is also provided. [ABSTRACT FROM AUTHOR]
Recently [ 1, 2] the new convexity principle has been validated. It states that a nonlinear image of a small ball in a Hilbert space is convex, provided that the map is C-1.1 and the center of the ball is a regular po...
详细信息
Recently [ 1, 2] the new convexity principle has been validated. It states that a nonlinear image of a small ball in a Hilbert space is convex, provided that the map is C-1.1 and the center of the ball is a regular point of the map. This result has numerous applications in linear algebra, optimization and control.
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.
Our aim is twofold: first, we want to introduce a partial quasiordering in cone uniform spaces with generalized pseudodistances for giving the general maximality principle in these spaces. Second, we want to show how ...
详细信息
Our aim is twofold: first, we want to introduce a partial quasiordering in cone uniform spaces with generalized pseudodistances for giving the general maximality principle in these spaces. Second, we want to show how this maximality principle can be used to obtain new and general results of Ekeland and Caristi types without lower semicontinuity assumptions, which was not done in the previous publications on this subject.
A method of constructing test problems for linear bilevel programming problems is presented. The method selects a vertex of the feasible region, 'far away' from the solution of the relaxed linear programming p...
详细信息
A method of constructing test problems for linear bilevel programming problems is presented. The method selects a vertex of the feasible region, 'far away' from the solution of the relaxed linear programming problem, as the global solution of the bilevel problem. A predetermined number of constraints are systematically selected to be assigned to the lower problem. The proposed method requires only local vertex search and solutions to linear programs.
A nonconvex programming problem, which arises in the context of application of Benders' decomposition procedure to a class of network optimization problems, is considered. Conditions which are both necessary and s...
详细信息
A nonconvex programming problem, which arises in the context of application of Benders' decomposition procedure to a class of network optimization problems, is considered. Conditions which are both necessary and sufficient for a local maximum are derived. The concept of a basic local maximum is introduced, and it is shown that there is a finite number of basic local maxima and at least one such local maximum is optimal.
暂无评论