检索结果-内蒙古大学图书馆

On Vaidya's volumetric cutting plane method for convex programming

MATHEMATICS OF OPERATIONS RESEARCH 1997年第1期22卷 63-89页

作者： Anstreicher, KM Department of Management Sciences University of Iowa Iowa City IA 52242 United States

We describe a simplified and strengthened version of Vaidya's volumetric cutting plane method for finding a point in a convex set C subset of R(n). At each step the algorithm has a system of linear inequality constraints which defines a polyhedron P superset of C, and an interior point x is an element of P. The algorithm then either drops one constraint, or calls an oracle to check if x is an element of C, and, if not, obtain a new constraint that separates x from C. Following the addition or deletion of a constraint, the algorithm takes a small number of Newton steps for the volumetric barrier V(.). Progress of the algorithm is measured in terms of changes in V(.). The algorithm is terminated when either it is discovered that x is an element of C, or V(.) becomes large enough to demonstrate that the volume of C must be below some prescribed amount. The complexity of the algorithm compares favorably with that of the ellipsoid method, especially in terms of the number of calls to the separation oracle. Compared to Vaidya's original analysis, we decrease the total number of Newton steps required for termination by a factor of about 1.3 million, white at the same time decreasing the maximum number of constraints used to define P from 10(7)n to 200n.

关键词： linear programming convex programming interior point algorithm volumetric barrier cutting plane method ellipsoid algorithm

来源：评论

学校读者我要写书评

暂无评论

Self-scaled barriers and interior-point methods for convex programming

引用

MATHEMATICS OF OPERATIONS RESEARCH 1997年第1期22卷 1-42页

作者： Nesterov, YE Todd, MJ CORNELL UNIV SCH OPERAT RES & IND ENGNITHACANY 14853 CORNELL CTR APPL MATH ITHACANY

This paper provides a theoretical foundation for efficient interior-point algorithms for convex programming problems expressed in conic form, when the cone and its associated barrier are self-scaled. For such problems we devise long-step and symmetric primal-dual methods. Because of the special properties of these cones and barriers, our algorithms can take steps that go typically a large fraction of the way to the boundary of the feasible region, rather than being confined to a ball of unit radius in the local norm defined by the Hessian of the barrier.

关键词： convex programming conical form interior point algorithms self-concordant barrier self-scaled cone self-scaled barrier path-following algorithms potential-reduction algorithms

来源：评论

学校读者我要写书评

暂无评论

Penalty/barrier multiplier methods for convex programming problems

引用

SIAM JOURNAL ON OPTIMIZATION 1997年第2期7卷 347-366页

作者： BenTal, A Zibulevsky, M Fac. of Indust. Eng. and Management Technion - Israel Inst. of Technol. Haifa 32000 Israel

We study a class of methods for solving convex programs, which are based on non-quadratic augmented Lagrangians for which the penalty parameters are functions of the multipliers. This gives rise to Lagrangians which are nonlinear in the multipliers. Each augmented Lagrangian is specified by a choice of a penalty function phi and a penalty-updating function pi. The requirements on pi are mild and allow for the inclusion of most of the previously suggested augmented Lagrangians. More importantly, a new type of penalty/barrier function (having a logarithmic branch glued to a quadratic branch) is introduced and used to construct an efficient algorithm. Convergence of the algorithms is proved for the case of pi being a sublinear function of the dual multipliers. The algorithms are tested on large-scale quadratically constrained problems arising in structural optimization.

关键词： convex programming augmented Lagrangian

来源：评论

学校读者我要写书评

暂无评论

A note on error bounds for convex and nonconvex programs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 1999年第1-3期12卷 41-51页

作者： Bertsekas, DP MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA

Given a single feasible solution x(F) and a single infeasible solution x(I) of a mathematical program, we provide an upper bound to the optimal dual value. We assume that x(F) satisfies a weakened form of the Slater condition. We apply the bound to convex programs and we discuss its relation to Hoffman-like bounds. As a special case, we recover a bound due to Mangasarian [11] on the distance of a point to a convex set specified by inequalities.

关键词： convex programming optimization duality error bounds

来源：评论

学校读者我要写书评

暂无评论

Exterior minimum-penalty path-following methods in semidefinite programming

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1999年第2期100卷 327-348页

作者： Fan, MKH Gong, Y Georgia Inst Technol Sch Elect & Comp Engn Atlanta GA 30332 USA

A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable but convex. It covers several standard problems, such as linear and quadratic programming, and has many applications in engineering. In this paper, we introduce the notion of minimal-penalty path, which is defined as the collection of minimizers for a family of convex optimization problems, and propose two methods for solving the problem by following the minimal-penalty path from the exterior of the feasible set. Our first method, which is also a constraint-aggregation method, achieves the solution by solving a sequence of linear programs, but exhibits a zigzagging behavior around the minimal-penalty path. Our second method eliminates the above drawback by following efficiently the minimum-penalty path through the centering and ascending steps. The global convergence of the methods is proved and their performance is illustrated by means of an example.

关键词： convex programming semidefinite programming linear matrix inequalities linear programming constraint-aggregation method minimum-penalty path exterior path-following methods

来源：评论

学校读者我要写书评

暂无评论

On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions

引用

DISCRETE APPLIED MATHEMATICS 1999年 97卷 363-373页

作者： Gurvich, V Khachiyan, L Rutgers State Univ Dept Comp Sci Hill Ctr New Brunswick NJ 08903 USA Rutgers State Univ RUTCOR New Brunswick NJ 08903 USA

Let f : {0, 1}(n) --> {0, 1} be a monotone Boolean function whose value at any point x is an element of {0, 1}(n) can be determined in time t. Denote by c = boolean AND(i is an element of C) boolean ORi is an element of I x(i) the irredundant CNF of f, where C is the set of the prime implicates of f. Similarly, let d = boolean ORJ is an element of D boolean AND(j is an element of J) x(j) be the irredundant DNF of the same function, where D is the set of the prime implicants of f. We show that given subsets C' subset of or equal to C and D' subset of or equal to D such that (C', D') not equal (C, D), a new term in (C\C')boolean OR(D\D') can be found in time O(n(t + n))+ m(o(log m)), where m = \C'\ + \D'\. In particular, if f(x) can be evaluated for every x is an element of {0, 1}(n) in polynomial time, then the forms c and d can be jointly generated in incremental quasi-polynomial time. On the other hand, even for the class of boolean AND, boolean OR-formulae f of depth 2, i.e., for CNFs or DNFs, it is unlikely that uniform sampling from within the set of the prime implicates and implicants of f can be carried out in time bounded by a quasi-polynomial 2(polylog(.)) in the input size of f. We also show that for some classes of polynomial-time computable monotone Boolean functions it is NP-hard to test either of the conditions D' = D or C' = C. This provides evidence that for each of these classes neither conjunctive nor disjunctive irredundant normal forms can be generated in total (or incremental) quasi-polynomial time. Such classes of monotone Boolean functions naturally arise in game theory, networks and relay contact circuits, convex programming, and include a subset of boolean AND, boolean OR-formulae of depth 3. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： incremental polynomial time quasi-polynomial time dualization NP-hardness monotone Boolean function monotone Boolean formula conjunctive normal form disjunctive normal form prime implicate prime implicant relay contact circuit positional game convex programming

来源：评论

学校读者我要写书评

暂无评论

Continuous-time state-feedback H₂-control of Markovian jump linear systems via convex analysis

引用

AUTOMATICA 1999年第2期35卷 259-268页

作者： Costa, OLV do Val, JBR Geromel, JC Univ Sao Paulo Dept Elect Engn BR-05508900 Sao Paulo Brazil UNICAMP Fac Elect Engn LAC DT BR-13081970 Campinas SP Brazil

Continuous-time H-2-control problem for the class of linear systems with Markovian jumps (MJLS) using convex analysis is considered in this paper. The definition of the H-2-norm for continuous-time MJLS is presented and related to the appropriate observability and controllability Gramians. A convex programming formulation for the H-2-control problem of MJLS is developed. That enables us to tackle the optimization problem of MJLS under the assumption that the transition rate matrix Pi = [pi(ij)] for the Markov chain may not be exactly known, but belongs to an appropriate convex set. An equivalence between the convex formulation when Pi is exactly known and the usual dynamic programming approach of quadratic optimal control of MJLS is established. It is shown that there exists a solution for the convex programming problem if and only if there exists the mean-square stabilizing solution for a set of coupled algebraic Riccati equations. These results are compared with other related works in the current literature. (C) 1999 Elsevier Science Ltd. All rights reserved.

关键词： convex programming linear systems Markov parameters jump process quadratic control parameter uncertainty

来源：评论

学校读者我要写书评

暂无评论

Constrained quadratic state feedback control of discrete-time Markovian jump linear systems

引用

AUTOMATICA 1999年第4期35卷 617-626页

作者： Costa, OLV Assumpcao, EO Boukas, EK Marques, RP Univ Sao Paulo Dept Elect Engn BR-05508900 Sao Paulo SP Brazil Ecole Polytech Dept Mech Engn Montreal PQ H3C 3A7 Canada

In this paper we consider the quadratic optimal control problem of a discrete-time Markovian jump linear system, subject to constraints on the state and control variables. It is desired to find a state feedback controller, which may also depend on the jump variable, that minimizes a quadratic cost and satisfies some upper bounds on the norms of some random variables, related to the state and control variables of the system. The transition probability of the Markov chain and initial condition of the system may belong to appropriate convex sets. We obtain an approximation for the optimal solution of this problem in terms of linear matrices inequalities, so that convex programming can be used for numerical calculations. Examples are presented to illustrate the usefulness of the developed results. (C) 1999 Elsevier Science Ltd. All rights reserved.

关键词： quadratic control constraints jump processes Markov parameters convex programming

来源：评论

学校读者我要写书评

暂无评论

Central paths, generalized proximal point methods, and Cauchy trajectories in Riemannian manifolds

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 1999年第2期37卷 566-588页

作者： Iusem, AN Svaiter, BF Neto, JXD Inst Matemat Pura & Aplicada BR-22460320 Rio De Janeiro Brazil Univ Fed Piaui CNN Dept Matemat BR-6400000 Teresina PI Brazil

We study the relationships between three concepts which arise in connection with variational inequality problems: central paths defined by arbitrary barriers, generalized proximal point methods (where a Bregman distance substitutes for the Euclidean one), and Cauchy trajectory in Riemannian manifolds. First we prove that under rather general hypotheses the central path defined by a general barrier for a monotone variational inequality problem is well defined, bounded, and continuous and converges to the analytic center of the solution set (with respect to the given barrier), thus generalizing results which deal only with complementarity problems and with the logarithmic barrier. Next we prove that a sequence generated by the proximal point method with the Bregman distance naturally induced by the barrier function converges precisely to the same point. Furthermore, for a certain class of problems (including linear programming), such a sequence is contained in the central path, making the concepts of central path and generalized proximal point sequence virtually equivalent. Finally we prove that for this class of problems the central path also coincides with the Cauchy trajectory in the Riemannian manifold defined on the positive orthant by a metric given by the Hessian of the barrier (i.e., a curve whose direction at each point is the negative gradient of the objective function at that point in the Riemannian metric).

关键词： convex programming linear programming variational inequalities complementarity problems interior point methods central path generalized distances proximal point method Riemannian manifolds

来源：评论

学校读者我要写书评

暂无评论

Exceptional families and existence theorems for variational inequality problems

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1999年第2期101卷 475-495页

作者： Zhao, YB Han, JY Qi, HD Chinese Acad Sci Inst Appl Math Beijing Peoples R China Chinese Acad Sci Inst Computat Math & Sci Engn Comp Beijing Peoples R China

This paper introduces the concept of exceptional family for nonlinear variational inequality problems. Among other things, we show that the nonexistence of an exceptional family is a sufficient condition for the existence of a solution to variational inequalities. This sufficient condition is weaker than many known solution conditions and it is also necessary for pseudomonotone variational inequalities. From the results in this paper, we believe that the concept of exceptional families of variational inequalities provides a new powerful tool for the study of the existence theory for variational inequalities.

关键词： variational inequalities convex programming complementarity problems exceptional families existence theorems

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：