Sufficient optimality criteria in continuous time programming

Sufficient optimality conditions are obtained in the case of continuous time programming problems under the assumptions that (i) particular linear combinations of the components of the constraint function are quasiconvex and objective functional is pseudoconcave “almost everywhere,” (ii) a particular linear combination of constraint function and objective functional is pseudoconcave “almost everywhere”.     

An extension of proximal methods for quasiconvex minimization on the nonnegative orthant

In this paper we propose an extension of proximal methods to solve minimization problems with quasiconvex objective functions on the nonnegative orthant. Assuming that the function is bounded from below and lower semicontinuous and using a general proximal distance, it is proved that the iterations given by our algorithm are well defined and stay in the positive orthant. If the objective function is quasiconvex we obtain the convergence of the iterates to a certain set which contains the set of optimal solutions and convergence to a KKT point if the function is continuously differentiable and the proximal parameters are bounded. Furthermore, we introduce a sufficient condition on the proximal distance such that the sequence converges to an optimal solution of the problem.     

Second-order invex functions in nonlinear programming

We introduce a notion of a second-order invex function. A Fréchet differentiable invex function without any further assumptions is second-order invex. It is shown that the inverse claim does not hold. A Fréchet differentiable function is second-order invex if and only if each second-order stationary point is a global minimizer. Two complete characterizations of these functions are derived. It is proved that a quasiconvex function is second-order invex if and only if it is second-order pseudoconvex. Further, we study the nonlinear programming problem with inequality constraints whose objective function is second-order invex. We introduce a notion of second-order type I objective and constraint functions. This class of problems strictly includes the type I invex ones. Then we extend a lot of sufficient optimality conditions with generalized convex functions to problems with second-order type I invex objective function and constraints. Additional optimality results, which concern type I and second-order type I invex data are obtained. An answer to the question when a kernel, which is not identically equal to zero, exists is given.     

Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming

This paper presents a “standard form” variant of Karmarkar's algorithm for linear programming. The tecniques of using duality and cutting objective are combined in this variant to maintain polynomial-time complexity and to bypass the difficulties found in Karmarkar's original algorithm. The variant works with problems in standard form and simultaneously generates sequences of primal and dual feasible solutions whose objective function values converge to the unknown optimal value. Some computational results are also reported.     

Nonlinear programming without a penalty function

In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead, a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm compares favourably with LANCELOT and an implementation of Sl₁QP. Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001     

Steepest descent method with a generalized Armijo search for quasiconvex functions on Riemannian manifolds

This paper extends the full convergence of the steepest descent method with a generalized Armijo search and a proximal regularization to solve minimization problems with quasiconvex objective functions on complete Riemannian manifolds. Previous convergence results are obtained as particular cases and some examples in non-Euclidian spaces are given. In particular, our approach can be used to solve constrained minimization problems with nonconvex objective functions in Euclidian spaces if the set of constraints is a Riemannian manifold and the objective function is quasiconvex in this manifold.     

Sufficient optimality criteria in nonlinear programming for generalized equality-inequality constraints

Sufficient optimality criteria of the Kuhn-Tucker and Fritz John type in nonlinear programming are established in the presence of equality-inequality constraints. The constraint functions are assumed to be quasiconvex, and the objective function is taken to be pseudoconvex (or convex).     

Cutting Plane Algorithms and Approximate Lower Subdifferentiability

A notion of boundedly ε-lower subdifferentiable functions is introduced and investigated. It is shown that a bounded from below, continuous, quasiconvex function is locally boundedly ε-lower subdifferentiable for every ε>0. Some algorithms of cutting plane type are constructed to solve minimization problems with approximately lower subdifferentiable objective and constraints. In those algorithms an approximate minimizer on a compact set is obtained in a finite number of iterations provided some boundedness assumption be satisfied.     

An infeasible interior-point algorithm for solving primal and dual geometric programs

In this paper an algorithm is presented for solving the classical posynomial geometric programming dual pair of problems simultaneously. The approach is by means of a primal-dual infeasible algorithm developed simultaneously for (i) the dual geometric program after logarithmic transformation of its objective function, and (ii) its Lagrangian dual program. Under rather general assumptions, the mechanism defines a primal-dual infeasible path from a specially constructed, perturbed Karush-Kuhn-Tucker system.Subfeasible solutions, as described by Duffin in 1956, are generated for each program whose primal and dual objective function values converge to the respective primal and dual program values. The basic technique is one of a predictor-corrector type involving Newton’s method applied to the perturbed KKT system, coupled with effective techniques for choosing iterate directions and step lengths. We also discuss implementation issues and some sparse matrix factorizations that take advantage of the very special structure of the Hessian matrix of the logarithmically transformed dual objective function. Our computational results on 19 of the most challenging GP problems found in the literature are encouraging. The performance indicates that the algorithm is effective regardless of thedegree of difficulty, which is a generally accepted measure in geometric programming. Research supported in part by the University of Iowa Obermann Fellowship and by NSF Grant DDM-9207347.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

An ordering (enumerative) algorithm for nonlinear 0-1 programming

In this paper, a new algorithm to solve a general 0–1 programming problem with linear objective function is developed. Computational experiences are carried out on problems where the constraints are inequalities on polynomials. The solution of the original problem is equivalent with the solution of a sequence of set packing problems with special constraint sets. The solution of these set packing problems is equivalent with the ordering of the binary vectors according to their objective function value. An algorithm is developed to generate this order in a dynamic way. The main tool of the algorithm is a tree which represents the desired order of the generated binary vectors. The method can be applied to the multi-knapsack type nonlinear 0–1 programming problem. Large problems of this type up to 500 variables have been solved.     

A successive quadratic programming method for a class of constrained nonsmooth optimization problems

In this paper we present an algorithm for solving nonlinear programming problems where the objective function contains a possibly nonsmooth convex term. The algorithm successively solves direction finding subproblems which are quadratic programming problems constructed by exploiting the special feature of the objective function. An exact penalty function is used to determine a step-size, once a search direction thus obtained is judged to yield a sufficient reduction in the penalty function value. The penalty parameter is adjusted to a suitable value automatically. Under appropriate assumptions, the algorithm is shown to produce an approximate optimal solution to the problem with any desirable accuracy in a finite number of iterations.     

First Order Optimality Conditions for Generalized Semi-Infinite Programming Problems

We study first-order optimality conditions for the class of generalized semi-infinite programming problems (GSIPs). We extend various well-known constraint qualifications for finite programming problems to GSIPs and analyze the extent to which a corresponding Karush-Kuhn-Tucker (KKT) condition depends on these extensions. It is shown that in general the KKT condition for GSIPs takes a weaker form unless a certain constraint qualification is satisfied. In the completely convex case where the objective of the lower-level problem is concave and the constraint functions are quasiconvex, we show that the KKT condition takes a sharper form. The authors thank the anonymous referees for careful reading of the paper and helpful suggestions. The research of the first author was partially supported by NSERC.     

Quasiconvex Minimization on a Locally Finite Union of Convex Sets

Extending the approach initiated in Aussel and Hadjisavvas (SIAM J. Optim. 16:358–367, 2005) and Aussel and Ye (Optimization 55:433–457, 2006), we obtain the existence of a local minimizer of a quasiconvex function on the locally finite union of closed convex subsets of a Banach space. We apply the existence result to some difficult nonconvex optimization problems such as the disjunctive programming problem and the bilevel programming problem. Dedicated to Jean-Pierre Crouzeix on the occasion of his 65th birthday. The authors thank two anonymous referees for careful reading of the paper and helpful suggestions. The research of the second author was partially supported by NSERC/Canada.     

Some constraint qualifications for quasiconvex vector-valued systems

In this paper, we consider minimization problems with a quasiconvex vector-valued inequality constraint. We propose two constraint qualifications, the closed cone constraint qualification for vector-valued quasiconvex programming (the VQ-CCCQ) and the basic constraint qualification for vector-valued quasiconvex programming (the VQ-BCQ). Based on previous results by Benoist et al. (Proc Am Math Soc 13:1109–1113, 2002), and Suzuki and Kuroiwa (J Optim Theory Appl 149:554–563, 2011), and (Nonlinear Anal 74:1279–1285, 2011), we show that the VQ-CCCQ (resp. the VQ-BCQ) is the weakest constraint qualification for Lagrangian-type strong (resp. min–max) duality. As consequences of the main results, we study semi-definite quasiconvex programming problems in our scheme, and we observe the weakest constraint qualifications for Lagrangian-type strong and min–max dualities. Finally, we summarize the characterizations of the weakest constraint qualifications for convex and quasiconvex programming.     

A variation on Karmarkar’s algorithm for solving linear programming problems

The algorithm described here is a variation on Karmarkar’s algorithm for linear programming. It has several advantages over Karmarkar’s original algorithm. In the first place, it applies to the standard form of a linear programming problem and produces a monotone decreasing sequence of values of the objective function. The minimum value of the objective function does not have to be known in advance. Secondly, in the absence of degeneracy, the algorithm converges to an optimal basic feasible solution with the nonbasic variables converging monotonically to zero. This makes it possible to identify an optimal basis before the algorithm converges.     

An alternating iterative method and its application in statistical inference

This paper studies non-convex programming problems. It is known that, in statistical inference, many constrained estimation problems may be expressed as convex programming problems. However, in many practical problems, the objective functions are not convex. In this paper, we give a definition of a semi-convex objective function and discuss the corresponding non-convex programming problems. A two-step iterative algorithm called the alternating iterative method is proposed for finding solutions for such problems. The method is illustrated by three examples in constrained estimation problems given in Sasabuchi et al. （Biometrika, 72, 465472 （1983））, Shi N. Z. （J. Multivariate Anal., 50, 282-293 （1994）） and El Barmi H. and Dykstra R. （Ann. Statist., 26, 1878 1893 （1998））.     

拓扑向量空间中锥拟凸多目标规划锥有效解集的连通性

本文研究局部凸的Hausdorff拓扑向量空间中锥拟凸多目标规划锥有效解集的连通性问题。利用广义鞍点定理,证明了目标映射为一对一的锥拟凸多目标规划的锥有效解集是连通的。     

On sufficient optimality conditions for a quasiconvex programming problem

Some remarks are made on a paper by Bector, Chandra, and Bector (see Ref. 1) concerning the Fritz John and Kuhn-Tucker sufficient optmality conditions as well as duality theorems for a nonlinear programming problem with a quasiconvex objective function.This research was supported by the Italian Ministry of University Scientific and Technological Research.     

On ranking of feasible solutions of a bottleneck linear programming problem

Summary An algorithm for the ranking of the feasible solutions of a bottleneck linear programming problem in ascending order of values of a concave bottleneck objective function is developed in this paper. The “best” feasible solution for a given value of the bottleneck objective is obtained at each stage. It is established that only the extreme points of a convex polytope need to be examined for the proposed ranking. Another algorithm, involving partitioning of the nodes, to rank the feasible solutions of the bottleneck linear programming problem is proposed, and numerical illustrations for both are provided.