One modification of the logarithmic barrier function method in linear and convex programming

A novel modification of the logarithmic barrier function method is introduced for solving problems of linear and convex programming. The modification is based on a parametric shifting of the constraints of the original problem, similarly to what was done in the method of Wierzbicki-Hestenes-Powell multipliers for the usual quadratic penalty function (this method is also known as the method of modified Lagrange functions). The new method is described, its convergence is proved, and results of numerical experiments are given.     

Asymptotic analysis of a path-following barrier method for linearly constrained convex problems *

In the present paper the logarithmic barrier method applied to the linearly constrained convex optimization problems is studied from the view point of classical path-following algorithms. In particular, the radius of convergence of Newton's method which depends on the barrier parameter itself is estimated in standard norms, being independent of the parameter, without explicitly using self-concordance properties. The obtained results establish a parameter selection rule which guarantees the overall convergence of a barrier technique with only one Newton step at each parameter level and the complexity of the method can be estimated.     

Proximal interior point approach in convex programming (ill-posed problems) * †

The paper deals with the theoretical analysis of a regularized logarithmic barrier method for solving ill-posed convex programming problems. In this method a multi-step proximal regularization of the auxiliary problems is performed in the framework of the interior point approach. The termination of the proximal terations for each auxiliary problem is controlled by means of estimates, characterizing the efficiency of the iterations. A special deleting rule permits to use only a part of the constraints of the original problem for constructing the auxiliary Problems.

Convergence and rate of convergence of the method suggested are studied as well as its stability with respect to data perturbations. An example is given showing the behavior of the classical barrier method in the case of ill-posed convex programming problems.     

Barrier function method and correction algorithms for improper convex programming problems

In the paper, convergence estimates are given for some generalization of the inverse barrier function method in convex programming. The significance of these estimates for constructing iterative algorithms is discussed. Regularizing properties of barrier functions and their application for optimal correction of improper convex programming problems are considered.     

Algorithm of Barrier Objective Penalty Function

In this paper, an algorithm of barrier objective penalty function for inequality constrained optimization is studied and a conception–the stability of barrier objective penalty function is presented. It is proved that an approximate optimal solution may be obtained by solving a barrier objective penalty function for inequality constrained optimization problem when the barrier objective penalty function is stable. Under some conditions, the stability of barrier objective penalty function is proved for convex programming. Specially, the logarithmic barrier function of convex programming is stable. Based on the barrier objective penalty function, an algorithm is developed for finding an approximate optimal solution to an inequality constrained optimization problem and its convergence is also proved under some conditions. Finally, numerical experiments show that the barrier objective penalty function algorithm has better convergence than the classical barrier function algorithm.     

A New Self-Dual Embedding Method for Convex Programming

In this paper we introduce a conic optimization formulation to solve constrained convex programming, and propose a self-dual embedding model for solving the resulting conic optimization problem. The primal and dual cones in this formulation are characterized by the original constraint functions and their corresponding conjugate functions respectively. Hence they are completely symmetric. This allows for a standard primal-dual path following approach for solving the embedded problem. Moreover, there are two immediate logarithmic barrier functions for the primal and dual cones. We show that these two logarithmic barrier functions are conjugate to each other. The explicit form of the conjugate functions are in fact not required to be known in the algorithm. An advantage of the new approach is that there is no need to assume an initial feasible solution to start with. To guarantee the polynomiality of the path-following procedure, we may apply the self-concordant barrier theory of Nesterov and Nemirovski. For this purpose, as one application, we prove that the barrier functions constructed this way are indeed self-concordant when the original constraint functions are convex and quadratic. We pose as an open question to find general conditions under which the constructed barrier functions are self-concordant.     

关于一些凸规划问题的复杂性研究结果

目前,已发表了大量研究各类不同凸规划的低复杂度的障碍函数方法的文章. 利用自和谐理论,对不同的几类凸规划问题构造相应的对数障碍函数,通过两个引理证明这些凸规划问题相应的对数障碍函数都满足自和谐,根据Nesterov 和Nemirovsky的工作证明了所给问题的内点算法具有多项式复杂性.     

A sufficient condition for self-concordance,with application to some classes of structured convex programming problems

Recently a number of papers were written that present low-complexity interior-point methods for different classes of convex programs. The goal of this article is to show that the logarithmic barrier function associated with these programs is self-concordant. Hence the polynomial complexity results for these convex programs can be derived from the theory of Nesterov and Nemirovsky on self-concordant barrier functions. We also show that the approach can be applied to some other known classes of convex programs.This author's research was supported by a research grant from SHELL.On leave from the Eötvös University, Budapest, Hungary. This author's research was partially supported by OTKA No. 2116.     

On the relations between two types of convergence for convex functions

Theory and applications have shown that there are two important types of convergence for convex functions: pointwise convergence and convergence in a topology induced by the convergence of their epigraphs. We show that these two types of convergence are equivalent on the class of convex functions which are equi-lower semicontinuous. This turns out to be maximal classes of convex functions for which this equivalence can be obtained. We also indicate a number of implications of these results to the convergence of convex sets and the corresponding support functions and to the convergence of the infima of sequences of convex minimization problems.     

Random variables,monotone relations,and convex analysis

Random variables can be described by their cumulative distribution functions, a class of nondecreasing functions on the real line. Those functions can in turn be identified, after the possible vertical gaps in their graphs are filled in, with maximal monotone relations. Such relations are known to be the subdifferentials of convex functions. Analysis of these connections yields new insights. The generalized inversion operation between distribution functions and quantile functions corresponds to graphical inversion of monotone relations. In subdifferential terms, it corresponds to passing to conjugate convex functions under the Legendre–Fenchel transform. Among other things, this shows that convergence in distribution for sequences of random variables is equivalent to graphical convergence of the monotone relations and epigraphical convergence of the associated convex functions. Measures of risk that employ quantiles (VaR) and superquantiles (CVaR), either individually or in mixtures, are illuminated in this way. Formulas for their calculation are seen from a perspective that reveals how they were discovered. The approach leads further to developments in which the superquantiles for a given distribution are interpreted as the quantiles for an overlying “superdistribution.” In this way a generalization of Koenker–Basset error is derived which lays a foundation for superquantile regression as a higher-order extension of quantile regression.     

Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization

Recently, the alternating direction method of multipliers (ADMM) has found many efficient applications in various areas; and it has been shown that the convergence is not guaranteed when it is directly extended to the multiple-block case of separable convex minimization problems where there are m ≥ 3 functions without coupled variables in the objective. This fact has given great impetus to investigate various conditions on both the model and the algorithm’s parameter that can ensure the convergence of the direct extension of ADMM (abbreviated as “e-ADMM”). Despite some results under very strong conditions (e.g., at least (m ? 1) functions should be strongly convex) that are applicable to the generic case with a general m, some others concentrate on the special case of m = 3 under the relatively milder condition that only one function is assumed to be strongly convex. We focus on extending the convergence analysis from the case of m = 3 to the more general case of m ≥ 3. That is, we show the convergence of e-ADMM for the case of m ≥ 3 with the assumption of only (m ? 2) functions being strongly convex; and establish its convergence rates in different scenarios such as the worst-case convergence rates measured by iteration complexity and the globally linear convergence rate under stronger assumptions. Thus the convergence of e-ADMM for the general case of m ≥ 4 is proved; this result seems to be still unknown even though it is intuitive given the known result of the case of m = 3. Even for the special case of m = 3, our convergence results turn out to be more general than the existing results that are derived specifically for the case of m = 3.     

Path-following barrier and penalty methods for linearly constrained problems

In the present paper some barrier and penalty methods (e.g. logarithmic barriers, SUMT, exponential penalties), which define a continuously differentiable primal and dual path, applied to linearly constrained convex problems are studied, in particular, the radius of convergence of Newton’s method depending on the barrier and penalty para-meter is estimated, Unlike using self-concordance properties the convergence bounds are derived by direct estimations of the solutions of the Newton equations. The obtained results establish parameter selection rules which guarantee the overall convergence of the considered barrier and penalty techniques with only a finite number of Newton steps at each parameter level. Moreover, the obtained estimates support scaling method which uses approximate dual multipliers as available in barrier and penalty methods     

一类线性乘积规划问题的分支定界缩减方法

提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的.     

Outer-approximation algorithms for nonsmooth convex MINLP problems

In this work, we combine outer-approximation (OA) and bundle method algorithms for dealing with mixed-integer non-linear programming (MINLP) problems with nonsmooth convex objective and constraint functions. As the convergence analysis of OA methods relies strongly on the differentiability of the involved functions, OA algorithms may fail to solve general nonsmooth convex MINLP problems. In order to obtain OA algorithms that are convergent regardless the structure of the convex functions, we solve the underlying OA’s non-linear subproblems by a specialized bundle method that provides necessary information to cut off previously visited (non-optimal) integer points. This property is crucial for proving (finite) convergence of OA algorithms. We illustrate the numerical performance of the given proposal on a class of hybrid robust and chance-constrained problems that involve a random variable with finite support.     

Remarks on the generalized Newton method

We give some convergence results for the generalized Newton method for the computation of zeros of nondifferentiable functions which we proposed in an earlier work. Our results show that the generalized method can converge quadratically when used to compute the zeros of the sum of a differentiable function and the (multivalued) subgradient of a lower semicontinuous proper convex function. The method is therefore effective for variational inequalities and can be used to find the minimum of a function which is the sum of a twice-differentiable convex function and a lower semicontinuous proper convex function. A numerical example is given.     

A Combined Homotopy Infeasible Interior-Point Method for Convex Nonlinear Programming

In this paper, on the basis of the logarithmic barrier function and KKT conditions , we propose a combined homotopy infeasible interior-point method (CHIIP) for convex nonlinear programming problems. For any convex nonlinear programming, without strict convexity for the logarithmic barrier function, we get different solutions of the convex programming in different cases by CHIIP method.     

A large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function

In this paper, we present a large-update interior-point algorithm for convex quadratic semi-definite optimization based on a new kernel function. The proposed function is strongly convex. It is not self-regular function and also the usual logarithmic function. The goal of this paper is to investigate such a kernel function and show that the algorithm has favorable complexity bound in terms of the elegant analytic properties of the kernel function. The complexity bound is shown to be $O\left( {\sqrt n \left( {\log n} \right)^2 \log \frac{n} {\varepsilon }} \right)$ . This bound is better than that by the classical primal-dual interior-point methods based on logarithmic barrier function and recent kernel functions introduced by some authors in optimization fields. Some computational results have been provided.     

Modified barrier functions (theory and methods)

The nonlinear rescaling principle employs monotone and sufficiently smooth functions to transform the constraints and/or the objective function into an equivalent problem, the classical Lagrangian which has important properties on the primal and the dual spaces.The application of the nonlinear rescaling principle to constrained optimization problems leads to a class of modified barrier functions (MBF's) and MBF Methods (MBFM's). Being classical Lagrangians (CL's) for an equivalent problem, the MBF's combine the best properties of the CL's and classical barrier functions (CBF's) but at the same time are free of their most essential deficiencies.Due to the excellent MBF properties, new characteristics of the dual pair convex programming problems have been found and the duality theory for nonconvex constrained optimization has been developed.The MBFM have up to a superlinear rate of convergence and are to the classical barrier functions (CBF's) method as the Multipliers Method for Augmented Lagrangians is to the Classical Penalty Function Method. Based on the dual theory associated with MBF, the method for the simultaneous solution of the dual pair convex programming problems with up to quadratic rates of convergence have been developed. The application of the MBF to linear (LP) and quadratic (QP) programming leads to a new type of multipliers methods which have a much better rate of convergence under lower computational complexity at each step as compared to the CBF methods.The numerical realization of the MBFM leads to the Newton Modified Barrier Method (NMBM). The excellent MBF properties allow us to discover that for any nondegenerate constrained optimization problem, there exists a hot start, from which the NMBM has a better rate of convergence, a better complexity bound, and is more stable than the interior point methods, which are based on the classical barrier functions.     

On the Existence and Convergence of the Central Path for Convex Programming and Some Duality Results

This paper gives several equivalent conditions which guarantee the existence of the weighted central paths for a given convex programming problem satisfying some mild conditions. When the objective and constraint functions of the problem are analytic, we also characterize the limiting behavior of these paths as they approach the set of optimal solutions. A duality relationship between a certain pair of logarithmic barrier problems is also discussed.     

Global optimization of bounded factorable functions with discontinuities

A deterministic global optimization method is developed for a class of discontinuous functions. McCormick’s method to obtain relaxations of nonconvex functions is extended to discontinuous factorable functions by representing a discontinuity with a step function. The properties of the relaxations are analyzed in detail; in particular, convergence of the relaxations to the function is established given some assumptions on the bounds derived from interval arithmetic. The obtained convex relaxations are used in a branch-and-bound scheme to formulate lower bounding problems. Furthermore, convergence of the branch-and-bound algorithm for discontinuous functions is analyzed and assumptions are derived to guarantee convergence. A key advantage of the proposed method over reformulating the discontinuous problem as a MINLP or MPEC is avoiding the increase in problem size that slows global optimization. Several numerical examples for the global optimization of functions with discontinuities are presented, including ones taken from process design and equipment sizing as well as discrete-time hybrid systems.