A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming

In this paper we propose a new iterative method for solving a class of linear complementarity problems:u 0,Mu + q 0, u^T(Mu + q)=0, where M is a givenl ×l positive semidefinite matrix (not necessarily symmetric) andq is a givenl-vector. The method makes two matrix-vector multiplications and a trivial projection onto the nonnegative orthant at each iteration, and the Euclidean distance of the iterates to the solution set monotonously converges to zero. The main advantages of the method presented are its simplicity, robustness, and ability to handle large problems with any start point. It is pointed out that the method may be used to solve general convex quadratic programming problems. Preliminary numerical experiments indicate that this method may be very efficient for large sparse problems.On leave from the Department of Mathematics, University of Nanjing, Nanjing, People's Republic of China.     

Constrained l1 estimation via geometric programming

The l₁ and constrained l₁ estimation problems are viewed in the light of extended geometric programming. As a result of this point of view we are able to establish an equivalence between geometric and linear programming duality results for these classes of problems. In addition, the duality results provide some useful insights into the properties of the l₁ estimation problems. Finally we establish an equivalence between the l_∞ norm problem and a class of constrained l₁ estimation problems.     

On ℓp programming

Our paper treats the primal and dual program of ?_p programming. ?_p programming is a generalization of ?_p approximation problems. There is a strict connection between ?_p programming and geometrical programming, because in both of them geometrical inequality plays a fundamental role. The structure of our paper follows that of Klafszkys [1].In the first Sections duality theorems are proved, which play an important role in mathematical programming. Most of these results can be found in Petersons and Eckers [3,4,5], but our proofs are much more simple and we show these fundamental properties more detailed.Afterwards the relation between the Lagrange function and the optimal solution pair is investigated. Regularity is investigated as well and we show the marginal value of ?_p programming. In the end linear programming ?_p constrained ?_p approximation problems, the quadratically constrained quadratic programming and compromise programming are shown as special cases of ?_p programming.     

线性多级规划的最优性条件和基本性质

本文研究的线性多级规划模型比较一般化，容许集可以是无界的，每级的目标函数可以与各下级控制的决策变量有关．我们得到了这类多级规划的一组最优性充要条件，利用这组条件推导了各级可行集的弱拟凸性、连通性等几何性质．作为应用订正了Bard的一个例题．     

New formulations of the multiple sequence alignment problem

A well known formulation of the multiple sequence alignment (MSA) problem is the maximum weight trace (MWT), a 0–1 linear programming problem. In this paper, we propose a new integer quadratic programming formulation of the MSA. The number of constraints and variables in the problem are only of the order of kL ², where, k is the number of sequences and L is the total length of the sequences, that is, L = ?_i=1^kl_i{L= \sum_{i=1}^{k}l_{i}} , where l _i is the length of sequence i. Based on this formulation we introduce an equivalent linear constrained 0–1 quadratic programming problem. We also propose a 0–1 linear programming formulation of the MWT problem, with polynomially many constraints. Our formulation provides the first direct compact formulation that ensures that the critical circuit inequalities (which are exponentially many) are all met.     

Inverse optimization for linearly constrained convex separable programming problems

In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with ℓ₁ and ℓ₂ norms. These inverse optimization problems are either linear programming when ℓ₁ norm is used in the formulation, or convex quadratic separable programming when ℓ₂ norm is used.     

Discrete linear bilevel programming problem

In this paper, we analyze some properties of the discrete linear bilevel program for different discretizations of the set of variables. We study the geometry of the feasible set and discuss the existence of an optimal solution. We also establish equivalences between different classes of discrete linear bilevel programs and particular linear multilevel programming problems. These equivalences are based on concave penalty functions and can be used to design penalty function methods for the solution of discrete linear bilevel programs.Support of this work has been provided by the INIC (Portugal) under Contract 89/EXA/5, by INVOTAN, FLAD, and CCLA (Portugal), and by FCAR (Québec), NSERC, and DND-ARP (Canada).     

Controlled dual perturbations for l p -programming

l _p -programming is a common generalization of linear programming, quadratically constrained quadratic programming,l _p -constrainedl _p -approximation, and multiple criteria compromise programming. It is a type of convex programming with objective function and inequality constraints expressed by means ofl _p -norms. The dual program established by Peterson and Ecker is a maximization problem with a concave, upper-semicontinuous objective function over a set of constraints that are essentially linear. In developing a dual method for this problem, we face two major difficulties. One is the non-differentiability of the dual objective function and the other one is an efficient dual-to-primal conversion.In this paper, we introduce a mechanism to construct a suitably perturbed dual program with a differentiable concave objective function over linear constraints. Solving this well-constructed perturbed dual program, we can obtain an-optimal dual solution for an arbitrarily small number. Moreover, we show a way of constructing a linear program based on this dual solution. Then an-optimal primal solution can be obtained by solving the dual of this simple linear program.

---

Zusammenfassung Diel _p -Optimierung ist eine Verallgemeinerung, die die lineare Optimierung, quadratische Optimierung mit quadratischen Restriktionen,l _p -Approximation mitl _p -Restriktionen, wie auch Vektoroptimierung umfaßt. Es handelt sich dabei um konvexe Optimierungsaufgaben, bei denen Zielfunktions- und Ungleichungsrestriktionen mittelsl _p -Normen ausgedrückt werden. Das duale Problem nach Peterson and Eckert ist ein Maximierungsproblem mit einer konkaven oberhalb-halbstetigen Zielfunktion über einer Menge von im wesentlichen linearen Restrictionen. Bei der Entwicklung einer dualen Lösungsmethode treten zwei Hauptschwierigkeiten auf: Die eine ist die Nicht-Differenzierbarkeit der dualen Zielfunktion, die andere besteht darin, eine effiziente Übertragung der dualen Lösung in eine primale zu finden.In dieser Arbeit führen wir eine Methode ein, die es gestattet, ein entsprechendes gestörtes duales Programm mit differenzierbarer konkaver Zielfunktion und linearen Restriktion aufzustellen. Bei der Lösung dieses wohl-strukturierten, gestörten dualen Problems erhalten wir eine-optimale Duallösung für beliebig kleines. Ferner zeigen wir einen Weg auf, wie, basierend auf dieser Duallösung, ein lineares Programm formuliert werden kann. Löst man das Dualproblem dieses einfachen linearen Programms, so erhält man eine-optimale Lösung für das Ausgangsproblem.

     

Discontinuous piecewise linear optimization

A theoretical framework and a practical algorithm are presented to solve discontinuous piecewise linear optimization problems dealing with functions for which theridges are known. A penalty approach allows one to consider such problems subject to a wide range of constraints involving piecewise linear functions. Although the theory is expounded in detail in the special case of discontinuous piecewiselinear functions, it is straightforwardly extendable, using standard nonlinear programming techniques, tononlinear (discontinuous piecewise differentiable) functions.The descent algorithm which is elaborated uses active-set and projected gradient approaches. It is a generalization of the ideas used by Conn to deal with nonsmoothness in thel ₁ exact penalty function, and it is based on the notion ofdecomposition of a function into a smooth and a nonsmooth part. The constrained case is reduced to the unconstrained minimization of a (piecewise linear)l ₁ exact penalty function. We also discuss how the algorithm is modified when it encounters degenerate points. Preliminary numerical results are presented: the algorithm is applied to discontinuous optimization problems from models in industrial engineering. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by the Natural Sciences and Engineering Council of Canada and the Centre de Recherches Mathématiques, Université de Montréal.This research was supported in part by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No. F49620-91-C-0079. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.     

Efficient Sequential Quadratic Programming Implementations for Equality-Constrained Discrete-Time Optimal Control

Efficient sequential quadratic programming (SQP) implementations are presented for equality-constrained, discrete-time, optimal control problems. The algorithm developed calculates the search direction for the equality-based variant of SQP and is applicable to problems with either fixed or free final time. Problem solutions are obtained by solving iteratively a series of constrained quadratic programs. The number of mathematical operations required for each iteration is proportional to the number of discrete times N. This is contrasted by conventional methods in which this number is proportional to N ³. The algorithm results in quadratic convergence of the iterates under the same conditions as those for SQP and simplifies to an existing dynamic programming approach when there are no constraints and the final time is fixed. A simple test problem and two application problems are presented. The application examples include a satellite dynamics problem and a set of brachistochrone problems involving viscous friction.     

并行求解约束优化问题的QP-free型算法

针对约束块可分的最优化问题,引入序列线性方程组方法和有效集策略,提出了一个求解约束块可分优化问题的QP-free型并行变量分配（PVD）算法.算法中用三个系数具有对称结构的线性方程组来代替PVD算法中的二次规划问题以求解线搜索方向,避免了约束不相容,减小了计算量.并且算法不要求约束是凸的.最后证明了QP-free型PVD算法的全局收敛性.     

关于<用初等行变换解一类线性规划问题>一文的注记

本指出，在献[1]提出的求解线性规划的方法中，对于初始可行基、最优解和零解的存在性问题所得出的某些结论是错误的，特殊是如果含n个变量的约束条件的增广矩阵经初等行变换后，其中某行的前n个分量非正，而最后一个分量为0时，应认为该线性规划问题可能有非零解，且不一定存在零解，而非[1]所述的结论。     

On the structure and properties of a linear multilevel programming problem

Many decision-making situations involve multiple planners with different, and sometimes conflicting, objective functions. One type of model that has been suggested to represent such situations is the linear multilevel programming problem. However, it appears that theoretical and algorithmic results for linear multilevel programming have been limited, to date, to the bounded case or the case of when only two levels exist. In this paper, we investigate the structure and properties of a linear multilevel programming problem that may be unbounded. We study the geometry of the problem and its feasible region. We also give necessary and sufficient conditions for the problem to be unbounded, and we show how the problem is related to a certain parametric concave minimization problem. The algorithmic implications of the results are also discussed.This research was supported by National Science Foundation Grant No. ECS-85-15231.     

On the resolution and optimization of a system of fuzzy relational equations with sup-T composition

This paper provides a thorough investigation on the resolution of a finite system of fuzzy relational equations with sup-T composition, where T is a continuous triangular norm. When such a system is consistent, although we know that the solution set can be characterized by a maximum solution and finitely many minimal solutions, it is still a challenging task to find all minimal solutions in an efficient manner. Using the representation theorem of continuous triangular norms, we show that the systems of sup-T equations can be divided into two categories depending on the involved triangular norm. When the triangular norm is Archimedean, the minimal solutions correspond one-to-one to the irredundant coverings of a set covering problem. When it is non-Archimedean, they only correspond to a subset of constrained irredundant coverings of a set covering problem. We then show that the problem of minimizing a linear objective function subject to a system of sup-T equations can be reduced into a 0–1 integer programming problem in polynomial time. This work generalizes most, if not all, known results and provides a unified framework to deal with the problem of resolution and optimization of a system of sup-T equations. Further generalizations and related issues are also included for discussion.     

An application of the Lovász–Schrijver <Emphasis Type="Italic">M</Emphasis>(<Emphasis Type="Italic">K</Emphasis>, <Emphasis Type="Italic">K</Emphasis>) operator to the stable set problem

Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.      

一类二层多目标规划的若干性质

本文对于下层为线性多目标规划的二层规划问题,在约束域非空有界的条件下证明了可行集的弱拟凸性、连通性,为算法设计提供了理论依据．     

A linear programming formulation for the maximum complete multipartite subgraph problem

Let G be a simple undirected graph with node set V(G) and edge set E(G). We call a subset independent if F is contained in the edge set of a complete multipartite (not necessarily induced) subgraph of G, F is dependent otherwise. In this paper we characterize the independents and the minimal dependents of G. We note that every minimal dependent of G has size two if and only if G is fan and prism-free. We give a 0-1 linear programming formulation of the following problem: find the maximum weight of a complete multipartite subgraph of G, where G has nonnegative edge weights. This formulation may have an exponential number of constraints with respect to |V(G)| but we show that the continuous relaxation of this 0-1 program can be solved in polynomial time.     

The <Emphasis Type="Italic">K</Emphasis>th-Best Approach for Linear Bilevel Multi-follower Programming

The majority of research on bilevel programming has centered on the linear version of the problem in which only one leader and one follower are involved. This paper addresses linear bilevel multi-follower programming (BLMFP) problems in which there is no sharing information among followers. It explores the theoretical properties of linear BLMFP, extends the Kth-best approach for solving linear BLMFP problems and gives a computational test for this approach.     

Controllability properties of constrained linear systems

In this paper, we present results on constrained controllability for linear control systems. The controls are constrained to take values in a compact set containing the origin. We use the results on reachability properties discussed in Ref. 1.We prove that controllability of an arbitrary pointp inR ⁿ is equivalent to an inclusion property of the reachable sets at certain positive times. We also develop geometric properties ofG, the set of all nonnegative times at whichp is controllable, and ofC, the set of all controllable points. We characterize the setC for the given system and provide additional spectrum-dependent structure.We show that, for the given linear system, several notions of constrained controllability of the pointp are the same, and thus the setC is open. We also provide a necessary condition for small-time (differential or local) constrained controllability ofp.This work was supported in part by NSF Grant ECS-86-09586.