Set Containment Characterization

Characterization of the containment of a polyhedral set in a closed halfspace, a key factor in generating knowledge-based support vector machine classifiers [7], is extended to the following: (i) containment of one polyhedral set in another; (ii) containment of a polyhedral set in a reverse-convex set defined by convex quadratic constraints; (iii) Containment of a general closed convex set, defined by convex constraints, in a reverse-convex set defined by convex nonlinear constraints. The first two characterizations can be determined in polynomial time by solving m linear programs for (i) and m convex quadratic programs for (ii), where m is the number of constraints defining the containing set. In (iii), m convex programs need to be solved in order to verify the characterization, where again m is the number of constraints defining the containing set. All polyhedral sets, like the knowledge sets of support vector machine classifiers, are characterized by the intersection of a finite number of closed halfspaces.     

Mixed Duality without Constraint Qualification for Nonsmooth Fractional Programming

A class of nonsmooth multiobjective fractional programming is formulated. We establish the necessary and sufficient optimality conditions without the need of a constraint qualification. Then a mixed dual is introduced for a class of nonsmooth fractional programming problems, and various duality theorems are established without a constraint qualification.     

Duality Without a Constraint Qualification for Minimax Fractional Programming

Using a parametric approach, we establish the necessary and sufficient conditions for generalized fractional programming without the need of a constraint qualification. Subsequently, these optimality criteria are utilized as a basis for constructing a parametric dual model and two other parameter-free dual models. Several duality theorems are established.     

Restricted Robinson Constraint Qualification and Optimality for Cardinality-Constrained Cone Programming

In this paper, optimality conditions are presented and analyzed for the cardinality-constrained cone programming arising from finance, statistical regression, signal processing, etc. By introducing a restricted form of (strict) Robinson constraint qualification, the first-order optimality conditions for the cardinality-constrained cone programming are established based upon the properties of the normal cone. After characterizing further the second-order tangent set to the cardinality-constrained system, the second-order optimality conditions are also presented under some mild conditions. These proposed optimality conditions, to some extent, enrich the optimization theory for noncontinuous and nonconvex programming problems.     

Level Function Method for Quasiconvex Programming

In this paper, we introduce the notion of level function for a continuous real-valued quasiconvex function. The existence, construction, and application of level functions are discussed. Further, we propose a numerical method based on level functions for the solution of quasiconvex minimization problems. Several versions of the algorithms are presented. Also, we apply the idea of the level function method to the solution of a class of variational inequality problems. Finally, the results of numerical experiments on the proposed algorithms are reported.     

Characterization of Nonsmooth Semistrictly Quasiconvex and Strictly Quasiconvex Functions

New concepts of semistrict quasimonotonicity and strict quasimonotonicity for multivalued maps are introduced. It is shown that a locally Lipschitz map is (semi)strictly quasiconvex if and only if its Clarke subdifferential is (semi)strictly quasimonotone. Finally, an existence result for the corresponding variational inequality problem is obtained.     

Necessary and Sufficient Constraint Qualification for Surrogate Duality

In mathematical programming, constraint qualifications are essential elements for duality theory. Recently, necessary and sufficient constraint qualifications for Lagrange duality results have been investigated. Also, surrogate duality enables one to replace the problem by a simpler one in which the constraint function is a scalar one. However, as far as we know, a necessary and sufficient constraint qualification for surrogate duality has not been proposed yet. In this paper, we propose necessary and sufficient constraint qualifications for surrogate duality and surrogate min–max duality, which are closely related with ones for Lagrange duality.     

解非线性约束拟凸规划的一个梯度投影法

目前国内外所流行的梯度投影法(包括Rosen的原有算法和一些修正算法)还存在以下几个问题:一、要增加Polak程序以保证算法的收僉性。二、在计算投影梯度时,每步一般要作两次投影。三、对于非线性约束问题,负梯度投影方向是不可行的,因此必须在此方向的基础上构造出能保证算法收歛的新可行下降方向。而目前为构造出这个新方向所作的计算都比较复杂。 1981年[5]提出了一个处理线性约束条件的梯度投影法,基本上解决了线     

Constant-Rank Condition and Second-Order Constraint Qualification

The constant-rank condition for feasible points of nonlinear programming problems was defined by Janin (Math. Program. Study 21:127–138, 1984). In that paper, the author proved that the constant-rank condition is a first-order constraint qualification. In this work, we prove that the constant-rank condition is also a second-order constraint qualification. We define other second-order constraint qualifications.     

On Constraint Qualification in Multiobjective Optimization Problems: Semidifferentiable Case

Some versions of constraint qualifications in the semidifferentiable case are considered for a multiobjective optimization problem with inequality constraints. A Maeda-type constraint qualification is given and Kuhn–Tucker-type necessary conditions for efficiency are obtained. In addition, some conditions that ensure the Maeda-type constraint qualification are stated.     

Interior Proximal Algorithm for Quasiconvex Programming Problems and Variational Inequalities with Linear Constraints

In this paper, we propose two interior proximal algorithms inspired by the logarithmic-quadratic proximal method. The first method we propose is for general linearly constrained quasiconvex minimization problems. For this method, we prove global convergence when the regularization parameters go to zero. The latter assumption can be dropped when the function is assumed to be pseudoconvex. We also obtain convergence results for quasimonotone variational inequalities, which are more general than monotone ones.     

A New Abadie-Type Constraint Qualification for General Optimization Problems

Journal of Optimization Theory and Applications - A non-Lipschitz version of the Abadie constraint qualification is introduced for a nonsmooth and nonconvex general optimization problem. The...     

Abadie-Type Constraint Qualification for Mathematical Programs with Equilibrium Constraints

Mathematical programs with equilibrium constraints (MPEC) are nonlinear programs which do not satisfy any of the common constraint qualifications (CQ). In order to obtain first-order optimality conditions, constraint qualifications tailored to the MPECs have been developed and researched in the past. In this paper, we introduce a new Abadie-type constraint qualification for MPECs. We investigate sufficient conditions for this new CQ, discuss its relationship to several existing MPEC constraint qualifications, and introduce a new Slater-type constraint qualifications. Finally, we prove a new stationarity concept to be a necessary optimality condition under our new Abadie-type CQ.Communicated by Z. Q. Luo     

On the Relation between Constant Positive Linear Dependence Condition and Quasinormality Constraint Qualification

The constant positive linear dependence (CPLD) condition for feasible points of nonlinear programming problems was introduced by Qi and Wei (Ref. 1) and used in the analysis of SQP methods. In that paper, the authors conjectured that the CPLD could be a constraint qualification. This conjecture is proven in the present paper. Moreover, it is shown that the CPLD condition implies the quasinormality constraint qualification, but that the reciprocal is not true. Relations with other constraint qualifications are given.This research has been supported by PRONEX-Optimization Grant 76.79.1008-00, by FAPESP Grants 01-04597-4 and 02-00832-1, and by CNPq. The authors are indebted to two anonymous referees for useful comments and to Prof. Liqun Qi for encouragement.     

Infinite Alternative Theorems and Nonsmooth Constraint Qualification Conditions

In this paper, some infinite alternative theorems in locally convex vector spaces are proved and some applications of these theorems in optimization theory are addressed. Extensions of constraint qualification conditions, in the absence of differentiability using Clarke??s generalized gradient and Mordukhovich??s subdifferential, in Banach and Asplund spaces are introduced; and relationships between them are established. Some of these relations, are proved using the provided alternative theorems.     

The Generalized Mangasarian-Fromowitz Constraint Qualification and Optimality Conditions for Bilevel Programs

We consider the optimal value reformulation of the bilevel programming problem. It is shown that the Mangasarian-Fromowitz constraint qualification in terms of the basic generalized differentiation constructions of Mordukhovich, which is weaker than the one in terms of Clarke’s nonsmooth tools, fails without any restrictive assumption. Some weakened forms of this constraint qualification are then suggested, in order to derive Karush-Kuhn-Tucker type optimality conditions for the aforementioned problem. Considering the partial calmness, a new characterization is suggested and the link with the previous constraint qualifications is analyzed.     

关于双层规划约束规格的一个注记

本文表明了非线性规划中常见的约束规格对一般双层规划不成立,并对双层规划可以满足的较弱的约束规格“部分平静”,给出了使其成立的充分条件．     

New Constraint Qualification and Conjugate Duality for Composed Convex Optimization Problems

The approach to optimal control problems based on a purely variational reformulation may lead to new existence results by using fine, general existence theorems for variational problems without convexity assumptions. We illustrate this perspective here for autonomous one-dimensional problems and defer the study of more complex situations to later work. This research was supported by Project MTM2004-07114 from Ministerio de Educación y Ciencia (Spain) and by Grant PAI05-029 from JCCM (Castilla-La Mancha).     

Constraint Programming and Hybrid Formulations for Three Life Designs

Conway's game of Life provides an interesting testbed for exploring issues in formulation, symmetry, and optimization with constraint programming and hybrid constraint programming/integer programming methods. We consider three Life pattern-creation problems: finding maximum density still-Lifes, finding smallest immediate predecessor patterns, and finding period-2 oscillators. For the first two problems, integrating integer programming and constraint programming approaches provides a much better solution procedure than either individually. For the final problem, the constraint programming formulation provides the better approach.     

机组排班的混合集合规划方法研究

机组成本是仅次于燃料成本的第二大直接运营成本,合理的进行机组人员排班对降低航空公司运营成本有着重要意义。然而,机组排班问题是复杂性非常高的组合优化问题,属于NP难题。本文在分析机组排班问题研究进展的基础上,采用混合集合规划方法,综合考虑多种约束,建立了更具有实用性的机组排班优化模型。本文将运筹学理论与业务逻辑相结合,设计了高效的求解策略。利用多组航空公司真实数据对模型进行测试,测试结果表明,模型可以在较短时间内有效求解达到实际应用规模的机组排班问题。