共查询到20条相似文献,搜索用时 78 毫秒
1.
M. Ben-Daya 《The Journal of the Operational Research Society》1995,46(3):332-338
In this paper, we propose a line-search procedure for the logarithmic barrier function in the context of an interior point algorithm for convex quadratic programming. Preliminary testing shows that the proposed procedure is superior to some other line-search methods developed specifically for the logarithmic barrier function in the literature. 相似文献
2.
On the implementation of a log-barrier progressive hedging method for multistage stochastic programs
A progressive hedging method incorporated with self-concordant barrier for solving multistage stochastic programs is proposed recently by Zhao [G. Zhao, A Lagrangian dual method with self-concordant barrier for multistage stochastic convex nonlinear programming, Math. Program. 102 (2005) 1-24]. The method relaxes the nonanticipativity constraints by the Lagrangian dual approach and smoothes the Lagrangian dual function by self-concordant barrier functions. The convergence and polynomial-time complexity of the method have been established. Although the analysis is done on stochastic convex programming, the method can be applied to the nonconvex situation. We discuss some details on the implementation of this method in this paper, including when to terminate the solution of unconstrained subproblems with special structure and how to perform a line search procedure for a new dual estimate effectively. In particular, the method is used to solve some multistage stochastic nonlinear test problems. The collection of test problems also contains two practical examples from the literature. We report the results of our preliminary numerical experiments. As a comparison, we also solve all test problems by the well-known progressive hedging method. 相似文献
3.
Villalobos C. Tapia R. Zhang Y. 《Journal of Optimization Theory and Applications》2002,112(2):239-263
Newton's method is a fundamental technique underlying many numerical methods for solving systems of nonlinear equations and optimization problems. However, it is often not fully appreciated that Newton's method can produce significantly different behavior when applied to equivalent systems, i.e., problems with the same solution but different mathematical formulations. In this paper, we investigate differences in the local behavior of Newton's method when applied to two different but equivalent systems from linear programming: the optimality conditions of the logarithmic barrier function formulation and the equations in the so-called perturbed optimality conditions. Through theoretical analysis and numerical results, we provide an explanation of why Newton's method performs more effectively on the latter system. 相似文献
4.
This paper deals with regularized penalty-barrier methods for convex programming problems. In the spirit of an iterative proximal regularization approach, an interior-point method is constructed, in which at each step a strongly convex function has to be minimized and the prox-term can be scaled by a variable scaling factor. The convergence of the method is studied for an axiomatically given class of barrier functions. According to the results, a wide class of barrier functions (in particular, logarithmic and exponential functions) can be applied to design special algorithms. For the method with a logarithmic barrier, the rate of convergence is investigated and assumptions that ensure linear convergence are given. 相似文献
5.
6.
Rui Shen Zhiqing Meng Chuangyin Dang Min Jiang 《Numerical Functional Analysis & Optimization》2017,38(11):1473-1489
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. 相似文献
7.
In contrast to stochastic differential equation models used for the calculation of the term structure of interest rates, we
develop an approach based on linear dynamical systems under non-stochastic uncertainty with perturbations. The uncertainty
is described in terms of known feasible sets of varying parameters. Observations are used in order to estimate these parameters
by minimizing the maximum of the absolute value of measurement errors, which leads to a linear or nonlinear semi-infinite
programming problem. A regularized logarithmic barrier method for solving (ill-posed) convex semi-infinite programming problems
is suggested. In this method a multi-step proximal regularization is coupled with an adaptive discretization strategy in the
framework of an interior point approach. A special deleting rule permits one to use only a part of the constraints of the
discretized problems. Convergence of the method and its stability with respect to data perturbations in the cone of convexC
1-functions are studied. On the basis of the solutions of the semi-infinite programming problems a technical trading system
for future contracts of the German DAX is suggested and developed.
Supported by the Stiftung Rheinland/Pfalz für Innovation, No. 8312-386261/307. 相似文献
8.
L. D. Popov 《Proceedings of the Steklov Institute of Mathematics》2008,263(2):108-119
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. 相似文献
9.
Nonlinear Proximal Decomposition Method for Convex Programming 总被引:2,自引:0,他引:2
In this paper, we propose a new decomposition method for solving convex programming problems with separable structure. The proposed method is based on the decomposition method proposed by Chen and Teboulle and the nonlinear proximal point algorithm using the Bregman function. An advantage of the proposed method is that, by a suitable choice of the Bregman function, each subproblem becomes essentially the unconstrained minimization of a finite-valued convex function. Under appropriate assumptions, the method is globally convergent to a solution of the problem. 相似文献
10.
This paper extends prior work by the authors on solving nonlinear least squares unconstrained problems using a factorized
quasi-Newton technique. With this aim we use a primal-dual interior-point algorithm for nonconvex nonlinear programming. The
factorized quasi-Newton technique is now applied to the Hessian of the Lagrangian function for the transformed problem which
is based on a logarithmic barrier formulation. We emphasize the importance of establishing and maintaining symmetric quasi-definiteness
of the reduced KKT system. The algorithm then tries to choose a step size that reduces a merit function, and to select a penalty
parameter that ensures descent directions along the iterative process. Computational results are included for a variety of
least squares constrained problems and preliminary numerical testing indicates that the algorithm is robust and efficient
in practice. 相似文献
11.
《Optimization》2012,61(1-4):117-147
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. 相似文献
12.
《Journal of Complexity》1999,15(2):282-293
We study the complexity of a barrier method for linear-inequality constrained optimization problems where the objective function is only assumed to be analytic and convex. As a special case, we obtain the usual complexity bounds for the linear programming problem and for when the objective function is convex and quadratic. 相似文献
13.
It was recently shown that modified barrier methods are not only theoretically but also computationally superior to classic barrier methods when applied to general nonlinear problems. In this paper, a penalty-barrier function is presented that was designed to overcome particular problems associated with modified log-barrier functions. A quadratic extrapolation of logarithmic terms as well as handling simple bounds separately are utilized. The resulting penalty-barrier method is outlined and compared to previous methods. The conclusion drawn from the computational tests is that the revised method exhibits superior performance on the test set of this study and consequently holds promise as a viable technique for general nonlinear programming. 相似文献
14.
Computing exact solution to nonlinear integer programming: Convergent Lagrangian and objective level cut method 总被引:3,自引:0,他引:3
In this paper, we propose a convergent Lagrangian and objective level cut method for computing exact solution to two classes
of nonlinear integer programming problems: separable nonlinear integer programming and polynomial zero-one programming. The
method exposes an optimal solution to the convex hull of a revised perturbation function by successively reshaping or re-confining
the perturbation function. The objective level cut is used to eliminate the duality gap and thus to guarantee the convergence
of the Lagrangian method on a revised domain. Computational results are reported for a variety of nonlinear integer programming
problems and demonstrate that the proposed method is promising in solving medium-size nonlinear integer programming problems. 相似文献
15.
Consider a linear programming problem in Karmarkar's standard form. By perturbing its linear objective function with an entropic barrier function and applying generalized geometric programming theory to it, Fang recently proposed an unconstrained convex programming approach to finding an epsilon-optimal solution. In this paper, we show that Fang's derivation of an unconstrained convex dual program can be greatly simplified by using only one simple geometric inequality. In addition, a system of nonlinear equations, which leads to a pair of primal and dual epsilon-optimal solutions, is proposed for further investigation.This work was partially supported by the North Carolina Supercomputing Center and a 1990 Cray Research Grant. The authors are indebted to Professors E. L. Peterson and R. Saigal for stimulating discussions. 相似文献
16.
V. D. Skarin 《Proceedings of the Steklov Institute of Mathematics》2008,263(2):120-134
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. 相似文献
17.
A New Self-Dual Embedding Method for Convex Programming 总被引:5,自引:0,他引:5
Shuzhong Zhang 《Journal of Global Optimization》2004,29(4):479-496
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. 相似文献
18.
In this paper, we study the search directions of three important interior-point algorithms, namely, the primal-affine scaling method (with logarithmic barrier function), the dual-affine scaling method (with logarithmic barrier function), and the primal-dual interior point method. From an algebraic point of view, we show that the search directions of these three algorithms are merely Newton directions along three different paths that lead to a solution of the Karush-Kuhn-Tucker conditions of a given linear programming problem. From a geometric point of view, we show that these directions can be obtained by solving certain well-defined subproblems. Both views provide a general platform for studying the existing interior-point methods and deriving new interior-point algorithms. We illustrate the derivation of new interior-point algorithms by replacing the logarithmic barrier function with an entropic barrier function. The results have been generalized and discussed.This work is partially supported by the North Carolina Supercomputing Center 1990 Cray Grant Program sponsored by Cray Research. 相似文献
19.
We propose a primal-dual continuation approach for the capacitated multi-facility Weber problem (CMFWP) based on its nonlinear
second-order cone program (SOCP) reformulation. The main idea of the approach is to reformulate the CMFWP as a nonlinear SOCP
with a nonconvex objective function, and then introduce a logarithmic barrier term and a quadratic proximal term into the
objective to construct a sequence of convexified subproblems. By this, this class of nondifferentiable and nonconvex optimization
problems is converted into the solution of a sequence of nonlinear convex SOCPs. In this paper, we employ the semismooth Newton
method proposed in Kanzow et al. (SIAM Journal of Optimization 20:297–320, 2009) to solve the KKT system of the resulting convex SOCPs. Preliminary numerical results are reported for eighteen test instances,
which indicate that the continuation approach is promising to find a satisfying suboptimal solution, even a global optimal
solution for some test problems. 相似文献
20.
On the classical logarithmic barrier function method for a class of smooth convex programming problems 总被引:6,自引:0,他引:6
In this paper, we describe a natural implementation of the classical logarithmic barrier function method for smooth convex programming. It is assumed that the objective and constraint functions fulfill the so-called relative Lipschitz condition, with Lipschitz constantM>0.In our method, we do line searches along the Newton direction with respect to the strictly convex logarithmic barrier function if we are far away from the central trajectory. If we are sufficiently close to this path, with respect to a certain metric, we reduce the barrier parameter. We prove that the number of iterations required by the algorithm to converge to an -optimal solution isO((1+M
2)
log) orO((1+M
2)nlog), depending on the updating scheme for the lower bound.on leave from Eötvös University, Budapest, Hungary. 相似文献