Minimum principle sufficiency

We characterize the property of obtaining a solution to a convex program by minimizing over the feasible region a linearization of the objective function at any of its solution points (Minimum Principle Sufficiency). For the case of a monotone linear complementarity problem this MPS property is completely equivalent to the existence of a nondegenerate solution to the problem. For the case of a convex quadratic program, the MPS property is equivalent to the span of the Hessian of the objective function being contained in the normal cone to the feasible region at any solution point, plus the cone generated by the gradient of the objective function at any solution point. This in turn is equivalent to the quadratic program having a weak sharp minimum. An important application of the MPS property is that minimizing on the feasible region a linearization of the objective function at a point in a neighborhood of a solution point gives an exact solution of the convex program. This leads to finite termination of convergent algorithms that periodically minimize such a linearization.This material is based on research supported by National Science Foundation Grants DCR-8521228 and CCR-8723091, and Air Force Office of Scientific Research Grants AFOSR 86-0172 and AFOSR and AFOSR 89-0410.     

On Weak and Strong Convergence of the Projected Gradient Method for Convex Optimization in Real Hilbert Spaces

This work focuses on convergence analysis of the projected gradient method for solving constrained convex minimization problems in Hilbert spaces. We show that the sequence of points generated by the method employing the Armijo line search converges weakly to a solution of the considered convex optimization problem. Weak convergence is established by assuming convexity and Gateaux differentiability of the objective function, whose Gateaux derivative is supposed to be uniformly continuous on bounded sets. Furthermore, we propose some modifications in the classical projected gradient method in order to obtain strong convergence. The new variant has the following desirable properties: the sequence of generated points is entirely contained in a ball with diameter equal to the distance between the initial point and the solution set, and the whole sequence converges strongly to the solution of the problem that lies closest to the initial iterate. Convergence analysis of both methods is presented without Lipschitz continuity assumption.     

凸规划的新算法

对一般凸目标函数和一般凸集约束的凸规划问题新解法进行探讨,它是线性规划一种新算法的扩展和改进,此算法的基本思想是在规划问题的可行域中由所建－的一个切割面到另一个切割面的不断推进来求取最优的。文章对目标函数是二次的且约束是一般凸集和二次目标函数且约束是线性的情形,给出了更简单的算法。     

E凸规划问题解集的刻画

考虑一类重要的广义凸规划问题E凸规划. 在E凸集中定义了关于E凸函数的E-Gateaux微分概念, 证明了E凸函数 的E-Gateaux微分的几个特征性质,并利用这些特征性质,提出了E凸规划问题解集的等价刻画. 在赋范向量空间中,对于一个目标函数在最优解处E-Gateaux可微的E凸规划问题而言,它的解集是由位于超平面内的可行解组成的,这些可行解的法向量就是目标函数在给定最优解处的E-Gateaux微分.     

Optimization Over the Efficient Set of Multi-objective Convex Optimal Control Problems

We consider multi-objective convex optimal control problems. First we state a relationship between the (weakly or properly) efficient set of the multi-objective problem and the solution of the problem scalarized via a convex combination of objectives through a vector of parameters (or weights). Then we establish that (i) the solution of the scalarized (parametric) problem for any given parameter vector is unique and (weakly or properly) efficient and (ii) for each solution in the (weakly or properly) efficient set, there exists at least one corresponding parameter vector for the scalarized problem yielding the same solution. Therefore the set of all parametric solutions (obtained by solving the scalarized problem) is equal to the efficient set. Next we consider an additional objective over the efficient set. Based on the main result, the new objective can instead be considered over the (parametric) solution set of the scalarized problem. For the purpose of constructing numerical methods, we point to existing solution differentiability results for parametric optimal control problems. We propose numerical methods and give an example application to illustrate our approach.     

An approximation algorithm for convex multi-objective programming problems

In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and the feasible set are convex. This method is an extension of Benson’s outer approximation algorithm for multi-objective linear programming problems. We prove that this method provides a set of weakly ε-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable objectives or constraints.     

Lagrange Multiplier Conditions Characterizing the Optimal Solution Sets of Cone-Constrained Convex Programs

Various characterizations of optimal solution sets of cone-constrained convex optimization problems are given. The results are expressed in terms of subgradients and Lagrange multipliers. We establish first that the Lagrangian function of a convex program is constant on the optimal solution set. This elementary property is then used to derive various simple Lagrange multiplier-based characterizations of the solution set. For a finite-dimensional convex program with inequality constraints, the characterizations illustrate that the active constraints with positive Lagrange multipliers at an optimal solution remain active at all optimal solutions of the program. The results are applied to derive corresponding Lagrange multiplier characterizations of the solution sets of semidefinite programs and fractional programs. Specific examples are given to illustrate the nature of the results.     

On Extensions of the Frank-Wolfe Theorems

In this paper we consider optimization problems defined by a quadratic objective function and a finite number of quadratic inequality constraints. Given that the objective function is bounded over the feasible set, we present a comprehensive study of the conditions under which the optimal solution set is nonempty, thus extending the so-called Frank-Wolfe theorem. In particular, we first prove a general continuity result for the solution set defined by a system of convex quadratic inequalities. This result implies immediately that the optimal solution set of the aforementioned problem is nonempty when all the quadratic functions involved are convex. In the absence of the convexity of the objective function, we give examples showing that the optimal solution set may be empty either when there are two or more convex quadratic constraints, or when the Hessian of the objective function has two or more negative eigenvalues. In the case when there exists only one convex quadratic inequality constraint (together with other linear constraints), or when the constraint functions are all convex quadratic and the objective function is quasi-convex (thus allowing one negative eigenvalue in its Hessian matrix), we prove that the optimal solution set is nonempty.     

Solving Rectilinear Planar Location Problems with Barriers by a Polynomial Partitioning

This paper considers planar location problems with rectilinear distance and barriers where the objective function is any convex, nondecreasing function of distance. Such problems have a non-convex feasible region and a nonconvex objective function. Based on an equivalent problem with modified barriers, derived in a companion paper [3], the non convex feasible set is partitioned into a network and rectangular cells. The rectangular cells are further partitioned into a polynomial number of convex subcells, called convex domains, on which the distance function, and hence the objective function, is convex. Then the problem is solved over the network and convex domains for an optimal solution. Bounds are given that reduce the number of convex domains to be examined. The number of convex domains is bounded above by a polynomial in the size of the problem.     

An Outer Approximation Algorithm Guaranteeing Feasibility of Solutions and Approximate Accuracy of Optimality

We treat a concave programming problem with a compact convex feasible set. Assuming the differentiability of the convex functions which define the feasible set, we propose two solution methods. Those methods utilize the convexity of the feasible set and the property of the normal cone to the feasible set at each point over the boundary. Based on the proposed two methods, we propose a solution algorithm. This algorithm takes advantages over classical methods: (1) the obtained approximate solution is always feasible, (2) the error of such approximate value can be evaluated properly for the optimal value of such problem, (3) the algorithm does not have any redundant iterations.     

A proximal point algorithm for generalized fractional programs

In this paper, the problem of solving generalized fractional programs will be addressed. This problem has been extensively studied and several algorithms have been proposed. In this work, we propose an algorithm that combines the proximal point method with a continuous min–max formulation of discrete generalized fractional programs. The proposed method can handle non-differentiable convex problems with possibly unbounded feasible constraints set, and solves at each iteration a convex program with unique dual solution. It generates two sequences that approximate the optimal value of the considered problem from below and from above at each step. For a class of functions, including the linear case, the convergence rate is at least linear.     

Robust optimization revisited via robust vector Farkas lemmas

This paper provides characterizations of the weakly minimal elements of vector optimization problems and the global minima of scalar optimization problems posed on locally convex spaces whose objective functions are deterministic while the uncertain constraints are treated under the robust (or risk-averse) approach, i.e. requiring the feasibility of the decisions to be taken for any possible scenario. To get these optimality conditions we provide Farkas-type results characterizing the inclusion of the robust feasible set into the solution set of some system involving the objective function and possibly uncertain parameters. In the particular case of scalar convex optimization problems, we characterize the optimality conditions in terms of the convexity and closedness of an associated set regarding a suitable point.     

First order optimality conditions in vector optimization involving stable functions

We study a nonsmooth vector optimization problem with an arbitrary feasible set or a feasible set defined by a generalized inequality constraint and an equality constraint. We assume that the involved functions are nondifferentiable. First, we provide some calculus rules for the contingent derivative in which the stability (a local Lipschitz property at a point) of the functions plays a crucial role. Second, another calculus rules are established for steady functions. Third, necessary optimality conditions are stated using tangent cones to the feasible set and the contingent derivative of the objective function. Finally, some necessary and sufficient conditions are presented through Lagrange multiplier rules.     

Simplicial Branch-and-Reduce Algorithm for Convex Programs with a Multiplicative Constraint

Optimization problems that involve products of convex functions in the objective function or in the constraints arise in a variety of applications. These problems are difficult global optimization problems. During the past 15 years, however, a number of practical algorithms have been proposed for globally solving these types of problems. In this article, we present and validate a branch-and-reduce algorithm for finding a global optimal solution to a convex program that contains an additional constraint on the product of several convex functions. To globally solve this problem, the algorithm instead globally solves an equivalent master problem. At any stage of the algorithm, a disconnected set consisting of a union of simplices is constructed. This set is guaranteed to contain a portion of the boundary of the feasible region of the master problem where a global optimal solution lies. The algorithm uses a new branch-and-reduce scheme to iteratively reduce the sizes of these sets until a global optimal solution is found. Several potential computational advantages of the algorithm are explained, and a numerical example is solved.     

Unboundedness in reverse convex and concave integer programming

In this paper we are concerned with the problem of unboundedness and existence of an optimal solution in reverse convex and concave integer optimization problems. In particular, we present necessary and sufficient conditions for existence of an upper bound for a convex objective function defined over the feasible region contained in ${\mathbb{Z}^n}$ . The conditions for boundedness are provided in a form of an implementable algorithm, showing that for the considered class of functions, the integer programming problem is unbounded if and only if the associated continuous problem is unbounded. We also address the problem of boundedness in the global optimization problem of maximizing a convex function over a set of integers contained in a convex and unbounded region. It is shown in the paper that in both types of integer programming problems, the objective function is either unbounded from above, or it attains its maximum at a feasible integer point.     

Convergence for vector optimization problems with variable ordering structure

In this paper, we first discuss the Painlevé–Kuratowski set convergence of (weak) minimal point set for a convex set, when the set and the ordering cone are both perturbed. Next, we consider a convex vector optimization problem, and take into account perturbations with respect to the feasible set, the objective function and the ordering cone. For this problem, by assuming that the data of the approximate problems converge to the data of the original problem in the sense of Painlevé–Kuratowski convergence and continuous convergence, we establish the Painlevé–Kuratowski set convergence of (weak) minimal point and (weak) efficient point sets of the approximate problems to the corresponding ones of original problem. We also compare our main theorems with existing results related to the same topic.     

Approximation of Planar Convex Sets from Hyperplane Probes

This paper studies a geometric probing problem. Suppose that an unknown convex set in R ² can be probed by an oracle which, when given a unit vector, will return the position of the supporting hyperplane of the convex set that has the given vector as an outward normal. We present an on-line algorithm for choosing probing directions so that, after n probes, an inner and an outer estimate of the convex set are obtained that are within of each other in Hausdorff distance. This is optimal since there exist convex sets that, even if visible, cannot be approximated better than with n-sided polygons, for example, a circle. Received April 18, 1995, and in revised form March 28, 1996.     

Convergence Properties of a Conditional ε-Subgradient Method Applied to Linear Programs

We propose a new conditional ε-subgradient method intended for solving general convex programs, Convergence properties of the method are investigated. It is proved that for a linear program with a compact set of solutions, the method generates a sequence of feasible approximations whose objective function values converge to the optimal value at a rate that is at least linear.     

An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs

We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family implicitly induces a convex underestimator of the objective function on the feasible region of the quadratic program. This alternative perspective on convex relaxations enables us to establish several useful properties of the corresponding convex underestimators. In particular, if the recession cone of the feasible region of the quadratic program does not contain any directions of negative curvature, we show that the convex underestimator arising from the copositive relaxation is precisely the convex envelope of the objective function of the quadratic program, strengthening Burer’s well-known result on the exactness of the copositive relaxation in the case of nonconvex quadratic programs. We also present an algorithmic recipe for constructing instances of quadratic programs with a finite optimal value but an unbounded relaxation for a rather large family of convex relaxations including the doubly nonnegative relaxation.

     

Axiomatizations of the Euclidean compromise solution

A multicriteria optimization problem is one of choosing an alternative that optimizes several—possibly conflicting—objective functions simultaneously. The utopia point of a multicriteria optimization problem is the vector that specifies for each objective function the most favorable feasible value. The Euclidean compromise solution in multicriteria optimization is a solution that selects from a feasible set the alternative such that its vector of criteria values has minimal Euclidean distance to the utopia point. This paper provides several axiomatic characterizations of the Euclidean compromise solution that are based on consistency properties.