Facial reduction in partially finite convex programming

We consider the problem of minimizing an extended-valued convex function on a locally convex space subject to a finite number of linear (in)equalities. When the standard constraint qualification fails a reduction technique is needed to derive necessary optimality conditions. Facial reduction is usually applied in the range of the constraints. In this paper it is applied in the domain space, thus maintaining any structure (and in particular lattice properties) of the underlying domain. Applications include constrained approximation and best entropy estimation.Research partially supported by the Natural Sciences and Engineering Research Council of Canada.     

Adaptive constraint reduction for convex quadratic programming

We propose an adaptive, constraint-reduced, primal-dual interior-point algorithm for convex quadratic programming with many more inequality constraints than variables. We reduce the computational effort by assembling, instead of the exact normal-equation matrix, an approximate matrix from a well chosen index set which includes indices of constraints that seem to be most critical. Starting with a large portion of the constraints, our proposed scheme excludes more unnecessary constraints at later iterations. We provide proofs for the global convergence and the quadratic local convergence rate of an affine-scaling variant. Numerical experiments on random problems, on a data-fitting problem, and on a problem in array pattern synthesis show the effectiveness of the constraint reduction in decreasing the time per iteration without significantly affecting the number of iterations. We note that a similar constraint-reduction approach can be applied to algorithms of Mehrotra’s predictor-corrector type, although no convergence theory is supplied.     

Potential reduction method for harmonically convex programming

In this paper, we introduce a potential reduction method for harmonically convex programming. We show that, if the objective function and them constraint functions are allk-harmonically convex in the feasible set, then the number of iterations needed to find an -optimal solution is bounded by a polynomial inm, k, and log(1/). The method requires either the optimal objective value of the problem or an upper bound of the harmonic constantk as a working parameter. Moreover, we discuss the relation between the harmonic convexity condition used in this paper and some other convexity and smoothness conditions used in the literature.The authors like to thank Dr. Hans Nieuwenhuis for carefully reading this paper and the anonymous referees for the worthy suggestions.     

解线约束凸规划的势下降算法

A potential reduction algorithm is proposed for optimization of a convex function subject to linear constraints. At each step of the algorithm,a system of linear equations is solved toget a search direction and the Armijo‘s rule is used to determine a stepsize. It is proved that thealgorithm is globally convergent. Computational results are reported.     

Reverse convex programming

Reverse convex programs generally have disconnected feasible regions. Basic solutions are defined and properties of the latter and of the convex hull of the feasible region are derived. Solution procedures are discussed and a cutting plane algorithm is developed.Research supported by NSF Grant ENG76-12250     

An unconstrained convex programming approach to solving convex quadratic programming problems

In this paper, we derive an unconstrained convex programming approach to solving convex quadratic programming problems in standard form. Related duality theory is established by using two simple inequalities. An ?-optimal solution is obtained by solving an unconstrained dual convex program. A dual-to-primal conversion formula is also provided. Some preliminary computational results of using a curved search method is included     

Method of orthogonal simplexes and its applications to convex programming

Numerical methods for solving a convex programming problem are considered whose guaranteed convergence rate depends only on the space dimension. On average, the ratio of the corresponding geometric progression is better than that in the basis model of ellipsoids or simplexes. Results of numerical experiments are presented.     

Duality gap in convex programming

In this paper, we consider general convex programming problems and give a sufficient condition for the equality of the infimum of the original problem and the supremum of its ordinary dual. This condition may be seen as a continuity assumption on the constraint sets (i.e. on the sublevel sets of the constraint function) under linear perturbation. It allows us to generalize as well as treat previous results in a unified framework. Our main result is in fact based on a quite general constraint qualification result for quasiconvex programs involving a convex objective function proven in the setting of a real normed vector space.Mathematics Subject Classification (2000):90C25, 90C26, 90C30, 90C31     

Unconstrained convex programming approach to linear programming

Recently, Fang proposed approximating a linear program in the Karmarkar standard form by adding an entropic barrier function to the objective function and derived an unconstrained dual concave program. We present in this note a necessary and sufficient condition for the existence of a dual optimal solution to the perturbed problem. In addition, a sharp upper bound of error estimation in this approximation scheme is provided.     

Bilevel convex programming models

Bilevel convex models are studied after being cast into a parametric programming form. This form has a lexicographic inner-outer structure where the optimal value of the outer model is optimized on the set of optimal solutions of the inner model. Optimal solutions are characterized using a Lagrangian saddle-point approach and a marginal value formula is given for the outer model. These are used to formulate a general method for finding an optimal solution by input optimization.     

Discrepancy and convex programming

Summary The pertinence of convexity arguments in the study of discrepancy of sequences is exhibited. The usefulness of this viewpoint can be twofold. Firstly, it allows the interpretation of the problem of estimating the discrepancy as a problem in convex programming in important cases. Secondly, it helps to restrict the family of sets which have to be considered when evaluating the usual (or extreme) discrepancy and the isotrope discrepancy of sequences. In particular, in the latter case it suffices to look at a rather special class of convex polytopes. Entrata in Redazione il 27 maggio 1971. Some results of this paper were presented in an address delivered at the Conference on Analytic Number Theory, Carbondale, Ill., October 22–24, 1970.     

An unconstrained convex programming view of linear programming

The major interest of this paper is to show that, at least in theory, a pair of primal and dual -optimal solutions to a general linear program in Karmarkar's standard form can be obtained by solving an unconstrained convex program. Hence unconstrained convex optimization methods are suggested to be carefully reviewed for this purpose.     

A convex analysis approach for convex multiplicative programming

Global optimization problems involving the minimization of a product of convex functions on a convex set are addressed in this paper. Elements of convex analysis are used to obtain a suitable representation of the convex multiplicative problem in the outcome space, where its global solution is reduced to the solution of a sequence of quasiconcave minimizations on polytopes. Computational experiments illustrate the performance of the global optimization algorithm proposed.      

Feasible partition problem in reverse convex and convex mixed-integer programming

In this paper we consider the consistent partition problem in reverse convex and convex mixed-integer programming. In particular we will show that for the considered classes of convex functions, both integer and relaxed systems can be partitioned into two disjoint subsystems, each of which is consistent and defines an unbounded region. The polynomial time algorithm to generate the partition will be proposed and the algorithm for a maximal partition will also be provided.     

Inequalities in completely convex stochastic programming

A two-stage stochastic programming problem in which the random variable enters in a convex manner is called completely convex. For such problems we give a sequence of inequalities and equalities showing the equivalence of optimality over plans and optimality of a two-stage procedure related to dynamic programming and giving upper bounds on the expected value of perfect information. Our assumptions are the weakest possible to guarantee the results in the completely convex case and supersede previous related results which have received erroneous proofs or have been established under highly restrictive conditions. In the course of our argument we exhibit a new measurable selection theorem and a rather general form of Jensen's inequality. We also present a multistage generalization of our central theorem.     

On optimality in abstract convex programming

A concept of uniform convergence for cone-convex functions is introduced and a number of ensuing properties are derived. Characterizations of optimality, without requiring the usual constraint qualification, are then given for abstract convex programs with constraints satisfying certain mean value and uniformly decreasing properties. The optimality conditions are stated in terms of the inconsistency of cone inclusions and the solutions to associated simpler programs.

---

Zusammenfassung Für verallgemeinert konvexe Functionen wird ein Begriff der gleichmäßigen Konvergenz eingeführt, und es werden einige daraus sich ergebende Eigenschaften hergeleitet. Für abstrakte konvexe Programme werden Optimalitätsbedingungen angegeben, die ohne die übliche Regularitätsvoraussetzung an die Nebenbedingungen auskommen. Die Nebenbedingungen müssen hierbei nur einer gewissen Mittelwertbedingung oder einer gleichmäßigen Abnahmebedingung genügen. Bei der Formulierung dieser Optimalitätsbedingungen verwendet man die Unlösbarkeit eines Systems von Inklusionen und die Lösungen von zugeordneten einfacheren Programmen.

     

Direct theorems in semi-infinite convex programming

We show that a semi-infinite quasi-convex program with certain regularity conditions possesses finitely constrained subprograms with the same optimal value. This result is applied to various problems.Research partially funded by NSERC A4493.     

Nonlinear programming in locally convex spaces

Farkas' lemma is generalized both to nonlinear functions and to infinite-dimensional spaces; the version for linear maps is less restricted than Hurwicz's result. A generalization of F. John's necessary condition for constrained minima is deduced for infinite dimension and cone constraints. Some theorems on converse and symmetric duality in nonlinear programming are obtained, which extend the known results, even in the finite-dimensional case.Communicated by P. P. Varayia     

Logarithmic SUMT limits in convex programming

The limits of a class of primal and dual solution trajectories associated with the Sequential Unconstrained Minimization Technique (SUMT) are investigated for convex programming problems with non-unique optima. Logarithmic barrier terms are assumed. For linear programming problems, such limits – of both primal and dual trajectories – are strongly optimal, strictly complementary, and can be characterized as analytic centers of, loosely speaking, optimality regions. Examples are given, which show that those results do not hold in general for convex programming problems. If the latter are weakly analytic (Bank et al. [3]), primal trajectory limits can be characterized in analogy to the linear programming case and without assuming differentiability. That class of programming problems contains faithfully convex, linear, and convex quadratic programming problems as strict subsets. In the differential case, dual trajectory limits can be characterized similarly, albeit under different conditions, one of which suffices for strict complementarity. Received: November 13, 1997 / Accepted: February 17, 1999?Published online February 22, 2001