Convex Optimization

Author: Stephen P. Boyd,Lieven Vandenberghe

Publisher: Cambridge University Press

ISBN: 9780521833783

Category: Business & Economics

Page: 716

View: 5720

A comprehensive introduction to the tools, techniques and applications of convex optimization.

Convex Optimization & Euclidean Distance Geometry

Author: Jon Dattorro

Publisher: Meboo Publishing USA

ISBN: 0976401304

Category: Mathematics

Page: 570

View: 662

The study of Euclidean distance matrices (EDMs) fundamentally asks what can be known geometrically given onlydistance information between points in Euclidean space. Each point may represent simply locationor, abstractly, any entity expressible as a vector in finite-dimensional Euclidean space.The answer to the question posed is that very much can be known about the points;the mathematics of this combined study of geometry and optimization is rich and deep.Throughout we cite beacons of historical accomplishment.The application of EDMs has already proven invaluable in discerning biological molecular conformation.The emerging practice of localization in wireless sensor networks, the global positioning system (GPS), and distance-based pattern recognitionwill certainly simplify and benefit from this theory.We study the pervasive convex Euclidean bodies and their various representations.In particular, we make convex polyhedra, cones, and dual cones more visceral through illustration, andwe study the geometric relation of polyhedral cones to nonorthogonal bases biorthogonal expansion.We explain conversion between halfspace- and vertex-descriptions of convex cones,we provide formulae for determining dual cones,and we show how classic alternative systems of linear inequalities or linear matrix inequalities and optimality conditions can be explained by generalized inequalities in terms of convex cones and their duals.The conic analogue to linear independence, called conic independence, is introducedas a new tool in the study of classical cone theory; the logical next step in the progression:linear, affine, conic.Any convex optimization problem has geometric interpretation.This is a powerful attraction: the ability to visualize geometry of an optimization problem.We provide tools to make visualization easier.The concept of faces, extreme points, and extreme directions of convex Euclidean bodiesis explained here, crucial to understanding convex optimization.The convex cone of positive semidefinite matrices, in particular, is studied in depth.We mathematically interpret, for example,its inverse image under affine transformation, and we explainhow higher-rank subsets of its boundary united with its interior are convex.The Chapter on "Geometry of convex functions",observes analogies between convex sets and functions:The set of all vector-valued convex functions is a closed convex cone.Included among the examples in this chapter, we show how the real affinefunction relates to convex functions as the hyperplane relates to convex sets.Here, also, pertinent results formultidimensional convex functions are presented that are largely ignored in the literature;tricks and tips for determining their convexityand discerning their geometry, particularly with regard to matrix calculus which remains largely unsystematizedwhen compared with the traditional practice of ordinary calculus.Consequently, we collect some results of matrix differentiation in the appendices.The Euclidean distance matrix (EDM) is studied,its properties and relationship to both positive semidefinite and Gram matrices.We relate the EDM to the four classical axioms of the Euclidean metric;thereby, observing the existence of an infinity of axioms of the Euclidean metric beyondthe triangle inequality. We proceed byderiving the fifth Euclidean axiom and then explain why furthering this endeavoris inefficient because the ensuing criteria (while describing polyhedra)grow linearly in complexity and number.Some geometrical problems solvable via EDMs,EDM problems posed as convex optimization, and methods of solution arepresented;\eg, we generate a recognizable isotonic map of the United States usingonly comparative distance information (no distance information, only distance inequalities).We offer a new proof of the classic Schoenberg criterion, that determines whether a candidate matrix is an EDM. Our proofrelies on fundamental geometry; assuming, any EDM must correspond to a list of points contained in some polyhedron(possibly at its vertices) and vice versa.It is not widely known that the Schoenberg criterion implies nonnegativity of the EDM entries; proved here.We characterize the eigenvalues of an EDM matrix and then devisea polyhedral cone required for determining membership of a candidate matrix(in Cayley-Menger form) to the convex cone of Euclidean distance matrices (EDM cone); \ie,a candidate is an EDM if and only if its eigenspectrum belongs to a spectral cone for EDM^N.We will see spectral cones are not unique.In the chapter "EDM cone", we explain the geometric relationship betweenthe EDM cone, two positive semidefinite cones, and the elliptope.We illustrate geometric requirements, in particular, for projection of a candidate matrixon a positive semidefinite cone that establish its membership to the EDM cone. The faces of the EDM cone are described,but still open is the question whether all its faces are exposed as they are for the positive semidefinite cone.The classic Schoenberg criterion, relating EDM and positive semidefinite cones, isrevealed to be a discretized membership relation (a generalized inequality, a new Farkas''''''''-like lemma)between the EDM cone and its ordinary dual. A matrix criterion for membership to the dual EDM cone is derived thatis simpler than the Schoenberg criterion.We derive a new concise expression for the EDM cone and its dual involvingtwo subspaces and a positive semidefinite cone."Semidefinite programming" is reviewedwith particular attention to optimality conditionsof prototypical primal and dual conic programs,their interplay, and the perturbation method of rank reduction of optimal solutions(extant but not well-known).We show how to solve a ubiquitous platonic combinatorial optimization problem from linear algebra(the optimal Boolean solution x to Ax=b)via semidefinite program relaxation.A three-dimensional polyhedral analogue for the positive semidefinite cone of 3X3 symmetricmatrices is introduced; a tool for visualizing in 6 dimensions.In "EDM proximity"we explore methods of solution to a few fundamental and prevalentEuclidean distance matrix proximity problems; the problem of finding that Euclidean distance matrix closestto a given matrix in the Euclidean sense.We pay particular attention to the problem when compounded with rank minimization.We offer a new geometrical proof of a famous result discovered by Eckart \& Young in 1936 regarding Euclideanprojection of a point on a subset of the positive semidefinite cone comprising all positive semidefinite matriceshaving rank not exceeding a prescribed limit rho.We explain how this problem is transformed to a convex optimization for any rank rho.

Nonsmooth Mechanics and Convex Optimization

Author: Yoshihiro Kanno

Publisher: CRC Press

ISBN: 1420094238

Category: Science

Page: 445

View: 6253

"This book concerns matter that is intrinsically difficult: convex optimization, complementarity and duality, nonsmooth analysis, linear and nonlinear programming, etc. The author has skillfully introduced these and many more concepts, and woven them into a seamless whole by retaining an easy and consistent style throughout. The book is not all theory: There are many real-life applications in structural engineering, cable networks, frictional contact problems, and plasticity... I recommend it to any reader who desires a modern, authoritative account of nonsmooth mechanics and convex optimization." — Prof. Graham M.L. Gladwell, Distinguished Professor Emeritus, University of Waterloo, Fellow of the Royal Society of Canada "... reads very well—the structure is good, the language and style are clear and fluent, and the material is rendered accessible by a careful presentation that contains many concrete examples. The range of applications, particularly to problems in mechanics, is admirable and a valuable complement to theoretical and computational investigations that are at the forefront of the areas concerned." — Prof. B. Daya Reddy, Department of Mathematics and Applied Mathematics, Director of Centre for Research in Computational and Applied Mechanics, University of Cape Town, South Africa "Many materials and structures (e.g., cable networks, membrane) involved in practical engineering applications have complex responses that cannot be described by smooth constitutive relations. ... The author shows how these difficult problems can be tackled in the framework of convex analysis by arranging the carefully chosen materials in an elegant way. Most of the contents of the book are from the original contributions of the author. They are both mathematically rigorous and readable. This book is a must-read for anyone who intends to get an authoritative and state-of-art description for the analysis of nonsmooth mechanics problems with theory and tools from convex analysis." — Prof. Xu Guo, State Key Laboratory of Structural Analysis for Industrial Equipment, Department of Engineering Mechanics, Dalian University of Technology

Lectures on Modern Convex Optimization

Analysis, Algorithms, and Engineering Applications

Author: Aharon Ben-Tal,Arkadi Nemirovski

Publisher: SIAM

ISBN: 0898714915

Category: Technology & Engineering

Page: 488

View: 5228

Here is a book devoted to well-structured and thus efficiently solvable convex optimization problems, with emphasis on conic quadratic and semidefinite programming. The authors present the basic theory underlying these problems as well as their numerous applications in engineering, including synthesis of filters, Lyapunov stability analysis, and structural design. The authors also discuss the complexity issues and provide an overview of the basic theory of state-of-the-art polynomial time interior point methods for linear, conic quadratic, and semidefinite programming. The book's focus on well-structured convex problems in conic form allows for unified theoretical and algorithmical treatment of a wide spectrum of important optimization problems arising in applications.

Introductory Lectures on Convex Optimization

A Basic Course

Author: Y. Nesterov

Publisher: Springer Science & Business Media

ISBN: 144198853X

Category: Mathematics

Page: 236

View: 5783

It was in the middle of the 1980s, when the seminal paper by Kar markar opened a new epoch in nonlinear optimization. The importance of this paper, containing a new polynomial-time algorithm for linear op timization problems, was not only in its complexity bound. At that time, the most surprising feature of this algorithm was that the theoretical pre diction of its high efficiency was supported by excellent computational results. This unusual fact dramatically changed the style and direc tions of the research in nonlinear optimization. Thereafter it became more and more common that the new methods were provided with a complexity analysis, which was considered a better justification of their efficiency than computational experiments. In a new rapidly develop ing field, which got the name "polynomial-time interior-point methods", such a justification was obligatory. Afteralmost fifteen years of intensive research, the main results of this development started to appear in monographs [12, 14, 16, 17, 18, 19]. Approximately at that time the author was asked to prepare a new course on nonlinear optimization for graduate students. The idea was to create a course which would reflect the new developments in the field. Actually, this was a major challenge. At the time only the theory of interior-point methods for linear optimization was polished enough to be explained to students. The general theory of self-concordant functions had appeared in print only once in the form of research monograph [12].

Convex Optimization Theory

Author: Dimitri P. Bertsekas

Publisher: N.A

ISBN: 9781886529311

Category: Mathematics

Page: 246

View: 476

An insightful, concise, and rigorous treatment of the basic theory of convex sets and functions in finite dimensions, and the analytical/geometrical foundations of convex optimization and duality theory. Convexity theory is first developed in a simple accessible manner, using easily visualized proofs. Then the focus shifts to a transparent geometrical line of analysis to develop the fundamental duality between descriptions of convex sets and functions in terms of points and in terms of hyperplanes. Finally, convexity theory and abstract duality are applied to problems of constrained optimization, Fenchel and conic duality, and game theory to develop the sharpest possible duality results within a highly visual geometric framework.

Optimality Conditions in Convex Optimization

A Finite-Dimensional View

Author: Anulekha Dhara,Joydeep Dutta

Publisher: CRC Press

ISBN: 1439868220

Category: Business & Economics

Page: 444

View: 8894

Optimality Conditions in Convex Optimization explores an important and central issue in the field of convex optimization: optimality conditions. It brings together the most important and recent results in this area that have been scattered in the literature—notably in the area of convex analysis—essential in developing many of the important results in this book, and not usually found in conventional texts. Unlike other books on convex optimization, which usually discuss algorithms along with some basic theory, the sole focus of this book is on fundamental and advanced convex optimization theory. Although many results presented in the book can also be proved in infinite dimensions, the authors focus on finite dimensions to allow for much deeper results and a better understanding of the structures involved in a convex optimization problem. They address semi-infinite optimization problems; approximate solution concepts of convex optimization problems; and some classes of non-convex problems which can be studied using the tools of convex analysis. They include examples wherever needed, provide details of major results, and discuss proofs of the main results.

Convex Optimization

Algorithms and Complexity

Author: Sébastien Bubeck

Publisher: N.A

ISBN: 9781601988607

Category: Convex domains

Page: 142

View: 7424

This monograph presents the main complexity theorems in convex optimization and their corresponding algorithms. It begins with the fundamental theory of black-box optimization and proceeds to guide the reader through recent advances in structural optimization and stochastic optimization. The presentation of black-box optimization, strongly influenced by the seminal book by Nesterov, includes the analysis of cutting plane methods, as well as (accelerated) gradient descent schemes. Special attention is also given to non-Euclidean settings (relevant algorithms include Frank-Wolfe, mirror descent, and dual averaging), and discussing their relevance in machine learning. The text provides a gentle introduction to structural optimization with FISTA (to optimize a sum of a smooth and a simple non-smooth term), saddle-point mirror prox (Nemirovski's alternative to Nesterov's smoothing), and a concise description of interior point methods. In stochastic optimization it discusses stochastic gradient descent, mini-batches, random coordinate descent, and sublinear algorithms. It also briefly touches upon convex relaxation of combinatorial problems and the use of randomness to round solutions, as well as random walks based methods.

Convex Optimization in Signal Processing and Communications

Author: Daniel P. Palomar,Yonina C. Eldar

Publisher: Cambridge University Press

ISBN: 0521762227

Category: Computers

Page: 498

View: 5516

Leading experts provide the theoretical underpinnings of the subject plus tutorials on a wide range of applications, from automatic code generation to robust broadband beamforming. Emphasis on cutting-edge research and formulating problems in convex form make this an ideal textbook for advanced graduate courses and a useful self-study guide.

Selected Applications of Convex Optimization

Author: Li Li

Publisher: Springer

ISBN: 3662463563

Category: Business & Economics

Page: 140

View: 3109

This book focuses on the applications of convex optimization and highlights several topics, including support vector machines, parameter estimation, norm approximation and regularization, semi-definite programming problems, convex relaxation, and geometric problems. All derivation processes are presented in detail to aid in comprehension. The book offers concrete guidance, helping readers recognize and formulate convex optimization problems they might encounter in practice.

Convex Optimization in Normed Spaces

Theory, Methods and Examples

Author: Juan Peypouquet

Publisher: Springer

ISBN: 3319137107

Category: Mathematics

Page: 124

View: 2592

This work is intended to serve as a guide for graduate students and researchers who wish to get acquainted with the main theoretical and practical tools for the numerical minimization of convex functions on Hilbert spaces. Therefore, it contains the main tools that are necessary to conduct independent research on the topic. It is also a concise, easy-to-follow and self-contained textbook, which may be useful for any researcher working on related fields, as well as teachers giving graduate-level courses on the topic. It will contain a thorough revision of the extant literature including both classical and state-of-the-art references.

Code Generation for Embedded Convex Optimization

Author: N.A

Publisher: Stanford University



Page: N.A

View: 708

Convex optimization is widely used, in many fields, but is nearly always constrained to problems solved in a few minutes or seconds, and even then, nearly always with a human in the loop. The advent of parser-solvers has made convex optimization simpler and more accessible, and greatly increased the number of people using convex optimization. Most current applications, however, are for the design of systems or analysis of data. It is possible to use convex optimization for real-time or embedded applications, where the optimization solver is a part of a larger system. Here, the optimization algorithm must find solutions much faster than a generic solver, and often has a hard, real-time deadline. Use in embedded applications additionally means that the solver cannot fail, and must be robust even in the presence of relatively poor quality data. For ease of embedding, the solver should be simple, and have minimal dependencies on external libraries. Convex optimization has been successfully applied in such settings in the past. However, they have usually necessitated a custom, hand-written solver. This requires signficant time and expertise, and has been a major factor preventing the adoption of convex optimization in embedded applications. This work describes the implementation and use of a prototype code generator for convex optimization, CVXGEN, that creates high-speed solvers automatically. Using the principles of disciplined convex programming, CVXGEN allows the user to describe an optimization problem in a convenient, high-level language, then receive code for compilation into an extremely fast, robust, embeddable solver.

Introduction to Online Convex Optimization

Author: Elad Hazan

Publisher: N.A

ISBN: 9781680831702

Category: Mathematics

Page: 190

View: 529

This book serves as a reference for a self-contained course on online convex optimization and the convex optimization approach to machine learning for the educated graduate student in computer science/electrical engineering/ operations research/statistics and related fields. An ideal reference.

Conjugate Duality in Convex Optimization

Author: Radu Ioan-Bot

Publisher: Springer Science & Business Media

ISBN: 9783642049002

Category: Business & Economics

Page: 164

View: 3406

The results presented in this book originate from the last decade research work of the author in the ?eld of duality theory in convex optimization. The reputation of duality in the optimization theory comes mainly from the major role that it plays in formulating necessary and suf?cient optimality conditions and, consequently, in generatingdifferent algorithmic approachesfor solving mathematical programming problems. The investigations made in this work prove the importance of the duality theory beyond these aspects and emphasize its strong connections with different topics in convex analysis, nonlinear analysis, functional analysis and in the theory of monotone operators. The ?rst part of the book brings to the attention of the reader the perturbation approach as a fundamental tool for developing the so-called conjugate duality t- ory. The classical Lagrange and Fenchel duality approaches are particular instances of this general concept. More than that, the generalized interior point regularity conditions stated in the past for the two mentioned situations turn out to be p- ticularizations of the ones given in this general setting. In our investigations, the perturbationapproachrepresentsthestartingpointforderivingnewdualityconcepts for several classes of convex optimization problems. Moreover, via this approach, generalized Moreau–Rockafellar formulae are provided and, in connection with them, a new class of regularity conditions, called closedness-type conditions, for both stable strong duality and strong duality is introduced. By stable strong duality we understand the situation in which strong duality still holds whenever perturbing the objective function of the primal problem with a linear continuous functional.