Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization

Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c ^T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations. Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000     

Inner Approximation Method for a Reverse Convex Programming Problem

In this paper, we consider a reverse convex programming problem constrained by a convex set and a reverse convex set, which is defined by the complement of the interior of a compact convex set X. We propose an inner approximation method to solve the problem in the case where X is not necessarily a polytope. The algorithm utilizes an inner approximation of X by a sequence of polytopes to generate relaxed problems. It is shown that every accumulation point of the sequence of optimal solutions of the relaxed problems is an optimal solution of the original problem.     

Geometrical characterization of weakly efficient points

In this note, we present a geometrical characterization of the set of weakly efficient points in constrained convex multiobjective optimization problems, valid for a compact set of objectives.     

Iteration-complexity of first-order penalty methods for convex programming

This paper considers a special but broad class of convex programming problems whose feasible region is a simple compact convex set intersected with the inverse image of a closed convex cone under an affine transformation. It studies the computational complexity of quadratic penalty based methods for solving the above class of problems. An iteration of these methods, which is simply an iteration of Nesterov’s optimal method (or one of its variants) for approximately solving a smooth penalization subproblem, consists of one or two projections onto the simple convex set. Iteration-complexity bounds expressed in terms of the latter type of iterations are derived for two quadratic penalty based variants, namely: one which applies the quadratic penalty method directly to the original problem and another one which applies the latter method to a perturbation of the original problem obtained by adding a small quadratic term to its objective function.     

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.     

Successive search methods for solving a canonical DC programming problem

In this article, we propose two successive search methods for solving a canonical DC programming problem constrained by the difference set between two compact convex sets in the case where the dimension number is greater than or equal to three. In order to find feasible solutions, the algorithms generate the directions based on a branch and bound procedure, successively. By exploring the provisional solutions throughout the intersection of the boundaries of two compact convex sets, both algorithms calculate an approximate solution.     

Generating Sum-of-Ratios Test Problems in Global Optimization

A method is presented for the construction of test problems involving the minimization over convex sets of sums of ratios of affine functions. Given a nonempty, compact convex set, the method determines a function that is the sum of linear fractional functions and attains a global minimum over the set at a point that can be found by convex programming and univariate search. Generally, the function will have also local minima over the set that are not global minima.     

On the stability of inner and outer approximations of a convex compact set by a ball

The finite-dimensional problems of outer and inner estimation of a convex compact set by a ball of some norm (circumscribed and inscribed ball problems) are considered. The stability of the solution with respect to the error in the specification of the estimated compact set is generally characterized. A new solution criterion for the outer estimation problem is obtained that relates the latter to the inner estimation problem for the lower Lebesgue set of the distance function to the most distant point of the estimated compact set. A quantitative estimate for the stability of the center of an inscribed ball is given under the additional assumption that the compact set is strongly convex. Assuming that the used norm is strongly quasi-convex, a quantitative stability estimate is obtained for the center of a circumscribed ball.     

Newton-like methods for solving vector optimization problems

In the context of Euclidean spaces, we present an extension of the Newton-like method for solving vector optimization problems, with respect to the partial orders induced by a pointed, closed and convex cone with a nonempty interior. We study both exact and inexact versions of the Newton-like method. Under reasonable hypotheses, we prove stationarity of accumulation points of the sequences produced by Newton-like methods. Moreover, assuming strict cone-convexity of the objective map to the vector optimization problem, we establish convergence of the sequences to an efficient point whenever the initial point is in a compact level set.     

An Exact Reformulation Algorithm for Large Nonconvex NLPs Involving Bilinear Terms

Many nonconvex nonlinear programming (NLP) problems of practical interest involve bilinear terms and linear constraints, as well as, potentially, other convex and nonconvex terms and constraints. In such cases, it may be possible to augment the formulation with additional linear constraints (a subset of Reformulation-Linearization Technique constraints) which do not affect the feasible region of the original NLP but tighten that of its convex relaxation to the extent that some bilinear terms may be dropped from the problem formulation. We present an efficient graph-theoretical algorithm for effecting such exact reformulations of large, sparse NLPs. The global solution of the reformulated problem using spatial Branch-and Bound algorithms is usually significantly faster than that of the original NLP. We illustrate this point by applying our algorithm to a set of pooling and blending global optimization problems.     

基于投影算子的回归神经网络模型及其在最优化问题中的应用

研究了一种基于投影算子的神经网络模型．与以前研究投影算子的值域一般是n维欧氏空间中的紧凸子集不同,而是n维欧氏空间中未必有界的闭凸子集,同时目标函数也是一般的连续可微函数,未必为凸函数．证明了所研究的神经网络模型具有整体解轨道,以及当目标函数满足某些条件时解轨道的整体收敛性．此外,还将所研究的模型应用于闭凸约束极小化问题以及非线性互补问题和隐互补问题中,并通过数值模拟说明了该神经网络方法的有效性．     

Nonadaptive methods for polyhedral approximation of the Edgeworth—Pareto hull using suboptimal coverings on the direction sphere

For multicriteria convex optimization problems, new nonadaptive methods are proposed for polyhedral approximation of the multidimensional Edgeworth-Pareto hull (EPH), which is a maximal set having the same Pareto frontier as the set of feasible criteria vectors. The methods are based on evaluating the support function of the EPH for a collection of directions generated by a suboptimal covering on the unit sphere. Such directions are constructed in advance by applying an asymptotically effective adaptive method for the polyhedral approximation of convex compact bodies, namely, by the estimate refinement method. Due to the a priori definition of the directions, the proposed EPH approximation procedure can easily be implemented with parallel computations. Moreover, the use of nonadaptive methods considerably simplifies the organization of EPH approximation on the Internet. Experiments with an applied problem (from 3 to 5 criteria) showed that the methods are fairly similar in characteristics to adaptive methods. Therefore, they can be used in parallel computations and on the Internet.     

带约束条件集值优化问题近似Henig有效解集的连通性

研究了带约束条件集值优化问题近似Henig有效解集的连通性.在实局部凸Hausdorff空间中,讨论了可行域为弧连通紧的,目标函数为C-弧连通的条件下,带约束条件集值优化问题近似Henig有效解集的存在性和连通性.并给出了带约束条件集值优化问题近似Henig有效解集的连通性定理.     

Motzkin decomposition of closed convex sets

Theodore Motzkin proved, in 1936, that any polyhedral convex set can be expressed as the (Minkowski) sum of a polytope and a polyhedral convex cone. This paper provides five characterizations of the larger class of closed convex sets in finite dimensional Euclidean spaces which are the sum of a compact convex set with a closed convex cone. These characterizations involve different types of representations of closed convex sets as the support functions, dual cones and linear systems whose relationships are also analyzed in the paper. The obtaining of information about a given closed convex set F and the parametric linear optimization problem with feasible set F from each of its different representations, including the Motzkin decomposition, is also discussed.     

Affine-inscribed and affine-circumscribed polygons and polytopes

Five theorems on polygons and polytopes inscribed in (or circumscribed about) a convex compact set in the plane or space are proved by topological methods. In particular, it is proved that for every interior point O of a convex compact set in ℝ³, there exists a two-dimensional section through O circumscribed about an affine image of a regular octagon. It is also proved that every compact convex set in ℝ³ (except the cases listed below) is circumscribed about an affine image of a cube-octahedron (the convex hull of the midpoints of the edges of a cube). Possible exceptions are provided by the bodies containing a parallelogram P and contained in a cylinder with directrix P. Bibliography: 29 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 231, 1995, pp. 286–298. Translated by B. M. Bekker.     

Regularization of ill-posed constrained minimization problems by iteration methods

The ill-posed minimization problems in Hilbert space with quadratic objective function and closed convex constraint set are considered. For the compact set the regularization methods for such problems are well understood [1, 2] The regularizing properties of some Iteration projection methods for noncompact constraint set are the main issues of this paper. We are looking the gradient projection method for the sphere.     

On certain optimization methods with finite-step inner algorithms for convex finite-dimensional problems with inequality constraints

Numerical methods are proposed for solving finite-dimensional convex problems with inequality constraints satisfying the Slater condition. A method based on solving the dual to the original regularized problem is proposed and justified for problems having a strictly uniformly convex sum of the objective function and the constraint functions. Conditions for the convergence of this method are derived, and convergence rate estimates are obtained for convergence with respect to the functional, convergence with respect to the argument to the set of optimizers, and convergence to the g-normal solution. For more general convex finite-dimensional minimization problems with inequality constraints, two methods with finite-step inner algorithms are proposed. The methods are based on the projected gradient and conditional gradient algorithms. The paper is focused on finite-dimensional problems obtained by approximating infinite-dimensional problems, in particular, optimal control problems for systems with lumped or distributed parameters.     

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.     

New variants of the generalized level method for minimization of convex nondifferentiable functions taking infinite values

New variants of the generalized level method for minimization of convex Lipschitz functions on a compact set with a nonempty interior are proposed. These variants include the well-known generalized and classical level methods. For the new variants, an estimate of the convergence rate is found, including the variants in which the auxiliary problems are solved approximately.     

Primal-dual subgradient methods for convex problems

In this paper we present a new approach for constructing subgradient schemes for different types of nonsmooth problems with convex structure. Our methods are primal-dual since they are always able to generate a feasible approximation to the optimum of an appropriately formulated dual problem. Besides other advantages, this useful feature provides the methods with a reliable stopping criterion. The proposed schemes differ from the classical approaches (divergent series methods, mirror descent methods) by presence of two control sequences. The first sequence is responsible for aggregating the support functions in the dual space, and the second one establishes a dynamically updated scale between the primal and dual spaces. This additional flexibility allows to guarantee a boundedness of the sequence of primal test points even in the case of unbounded feasible set (however, we always assume the uniform boundedness of subgradients). We present the variants of subgradient schemes for nonsmooth convex minimization, minimax problems, saddle point problems, variational inequalities, and stochastic optimization. In all situations our methods are proved to be optimal from the view point of worst-case black-box lower complexity bounds.