Convex underestimating relaxation techniques for nonconvex polynomial programming problems: computational overview
---
paper_title: Linear and Nonlinear Programming

paper_content:

This new edition covers the central concepts of practical optimization techniques, with an emphasis on methods that are both state-of-the-art and popular. One major insight is the connection between the purely analytical character of an optimization problem and the behavior of algorithms used to solve a problem. This was a major theme of the first edition of this book and the fourth edition expands and further illustrates this relationship. As in the earlier editions, the material in this fourth edition is organized into three separate parts. Part I is a self-contained introduction to linear programming. The presentation in this part is fairly conventional, covering the main elements of the underlying theory of linear programming, many of the most effective numerical algorithms, and many of its important special applications. Part II, which is independent of Part I, covers the theory of unconstrained optimization, including both derivations of the appropriate optimality conditions and an introduction to basic algorithms. This part of the book explores the general properties of algorithms and defines various notions of convergence. Part III extends the concepts developed in the second part to constrained optimization problems. Except for a few isolated sections, this part is also independent of Part I. It is possible to go directly into Parts II and III omitting Part I, and, in fact, the book has been used in this way in many universities.New to this edition is a chapter devoted to Conic Linear Programming, a powerful generalization of Linear Programming. Indeed, many conic structures are possible and useful in a variety of applications. It must be recognized, however, that conic linear programming is an advanced topic, requiring special study. Another important topic is an accelerated steepest descent method that exhibits superior convergence properties, and for this reason, has become quite popular. The proof of the convergence property for both standard and accelerated steepest descent methods are presented in Chapter 8. As in previous editions, end-of-chapter exercises appear for all chapters.From the reviews of the Third Edition: this very well-written book is a classic textbook in Optimization. It should be present in the bookcase of each student, researcher, and specialist from the host of disciplines from which practical optimization applications are drawn. (Jean-Jacques Strodiot, Zentralblatt MATH, Vol. 1207, 2011)
---
paper_title: ⋄ Convex Optimization,

paper_content:

Convex optimization problems arise frequently in many different fields. A comprehensive introduction to the subject, this book shows in detail how such problems can be solved numerically with great efficiency. The focus is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. The text contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance, and economics.
---
paper_title: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems

paper_content:

Preface. 1. Introduction. Part I: Discrete Nonconvex Programs. 2. RLT Hierarchy for Mixed-Integer Zero-One Problems. 3. Generalized Hierarchy for Exploiting Special Structures in Mixed-Integer Zero-One Problems. 4. RLT Hierarchy for General Discrete Mixed-Integer Problems. 5. Generating Valid Inequalities and Facets Using RLT. 6. Persistency in Discrete Optimization. Part II: Continuous Nonconvex Programs. 7. RLT-Based Global Optimization Algorithms for Nonconvex Polynomial Programming Problems. 8. Reformulation-Convexification Technique for Quadratic Programs and Some Convex Envelope Characterizations. 9. Reformulation-Convexification Technique for Polynomial Programs: Design and Implementation. Part III: Special Applications to Discrete and Continuous Nonconvex Programs. 10. Applications to Discrete Problems. 11. Applications to Continuous Problems. References.
---
paper_title: Handbook of semidefinite programming : theory, algorithms, and applications

paper_content:

Contributing Authors. List of Figures. List of Tables. Preface. 1. Introduction H. Wolkowicz, et al. Part I: Theory. 2. Convex Analysis on Symmetric Matrices F. Jarre. 3. The Geometry of Semidefinite Programming G. Pataki. 4. Duality and Optimality Conditions A. Shapiro, K. Scheinberg. 5. Self-Dual Embeddings E. de Klerk, et al. 6. Robustness A. Ben-Tal, et al. 7. Error Analysis Zhiquan Luo, J. Sturm. Part II: Algorithms. 8. Symmetric Cones, Potential Reduction Methods F. Alizadeh, S. Schmieta. 9. Potential Reduction and Primal-Dual Methods L. Tuncel. 10. Path-Following Methods R. Monteiro, M. Todd. 11. Bundle Methods and Eigenvalue Functions C. Helmberg, F. Oustry. Part III: Applications and Extensions. 12. Combinatorial Optimization M. Goemans, F. Rendl. 13. Nonconvex Quadratic Optimization Y. Nesterov, et al. 14. SDP in Systems and Control Theory V. Balakrishnan, Fan Wang. 15. Structural Design A. Ben-Tal, A. Nemirovski. 16. Moment Problems and Semidefinite Optimization D. Bertsimas, J. Sethuraman. 17. Design of Experiments in Statistics V. Fedorov, J. Lee. 18. Matrix Completion Problems A. Alfakih, H. Wolkowicz. 19. Eigenvalue Problems and Nonconvex Minimization F. Jarre. 20. General Nonlinear Programming S. Kruk, H. Wolkowicz. References. Appendix A-.1. Conclusion and Further Historical Notes. A-.2.Index.
---
paper_title: ⋄ Convex Optimization,

paper_content:

Convex optimization problems arise frequently in many different fields. A comprehensive introduction to the subject, this book shows in detail how such problems can be solved numerically with great efficiency. The focus is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. The text contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance, and economics.
---
paper_title: Nonlinear Programming: Theory, Algorithms and Applications

paper_content:

BASICS. The Nature of Optimization Problems. Analytical Background. Factorable Functions. UNCONSTRAINED PROBLEMS. Unconstrained Optimization Models. Minimizing a Function of a Single Variable. General Convergence Theory for Unconstrained Minimization Algorithms. Newton's Method With Variations. Conjugate Direction Algorithms. Quasi-Newton Methods. OPTIMALITY CONDITIONS FOR CONSTRAINED PROBLEMS. First- and Second-Order Optimality Conditions. Applications of Optimality Conditions. LINEARLY CONSTRAINED PROBLEMS. Models with Linear Constraints. Variable-Reduction Algorithms. NONLINEARLY CONSTRAINED PROBLEMS. Models with Nonlinear Constraints. Direct Algorithms for Nonlinearly Constrained Problems. Sequential Unconstrained Minimization Techniques. Sequential Constraint Linearization Techniques. OTHER TOPICS. Obtaining Global Solutions. Geometric Programming. References. Author and Subject Indexes.
---
paper_title: Convex Analysis and Global Optimization

paper_content:

This book presents state-of-the-art results and methodologies in modern global optimization, and has been a staple reference for researchers, engineers, advanced students (also in applied mathematics), and practitioners in various fields of engineering. The second edition has been brought up to date and continues to develop a coherent and rigorous theory of deterministic global optimization, highlighting the essential role of convex analysis. The text has been revised and expanded to meet the needs of research, education, and applications for many years to come. Updates for this new edition include: Discussion of modern approaches to minimax, fixed point, and equilibrium theorems, and to nonconvex optimization; Increased focus on dealing more efficiently with ill-posed problems of global optimization, particularly those with hard constraints; Important discussions of decomposition methods for specially structured problems; A complete revision of the chapter on nonconvex quadratic programming, in order to encompass the advances made in quadratic optimization since publication of the first edition. Additionally, this new edition contains entirely new chapters devoted to monotonic optimization, polynomial optimization and optimization under equilibrium constraints, including bilevel programming, multiobjective programming, and optimization with variational inequality constraint. From the reviews of the first edition: The book gives a good review of the topic. The text is carefully constructed and well written, the exposition is clear. It leaves a remarkable impression of the concepts, tools and techniques in global optimization. It might also be used as a basis and guideline for lectures on this subject. Students as well as professionals will profitably read and use it. Mathematical Methods of Operations Research, 49:3 (1999)
---
paper_title: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems

paper_content:

Preface. 1. Introduction. Part I: Discrete Nonconvex Programs. 2. RLT Hierarchy for Mixed-Integer Zero-One Problems. 3. Generalized Hierarchy for Exploiting Special Structures in Mixed-Integer Zero-One Problems. 4. RLT Hierarchy for General Discrete Mixed-Integer Problems. 5. Generating Valid Inequalities and Facets Using RLT. 6. Persistency in Discrete Optimization. Part II: Continuous Nonconvex Programs. 7. RLT-Based Global Optimization Algorithms for Nonconvex Polynomial Programming Problems. 8. Reformulation-Convexification Technique for Quadratic Programs and Some Convex Envelope Characterizations. 9. Reformulation-Convexification Technique for Polynomial Programs: Design and Implementation. Part III: Special Applications to Discrete and Continuous Nonconvex Programs. 10. Applications to Discrete Problems. 11. Applications to Continuous Problems. References.
---
paper_title: Nonlinear Programming -- Theory and Algorithms

paper_content:

Nonlinear Programming presents recent developments of key topics in nonlinear programming (NLP) using a logical and self-contained format. The volume is divided into three sections: convex analysis, optimality conditions, and dual computational techniques. Precise statements of algorithms are given along with convergence analysis. Each chapter contains detailed numerical examples, graphical illustrations, and numerous exercises to aid readers in understanding the concepts and methods discussed.
---
paper_title: Nonlinear Programming -- Theory and Algorithms

paper_content:

Nonlinear Programming presents recent developments of key topics in nonlinear programming (NLP) using a logical and self-contained format. The volume is divided into three sections: convex analysis, optimality conditions, and dual computational techniques. Precise statements of algorithms are given along with convergence analysis. Each chapter contains detailed numerical examples, graphical illustrations, and numerous exercises to aid readers in understanding the concepts and methods discussed.
---
paper_title: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems

paper_content:

Preface. 1. Introduction. Part I: Discrete Nonconvex Programs. 2. RLT Hierarchy for Mixed-Integer Zero-One Problems. 3. Generalized Hierarchy for Exploiting Special Structures in Mixed-Integer Zero-One Problems. 4. RLT Hierarchy for General Discrete Mixed-Integer Problems. 5. Generating Valid Inequalities and Facets Using RLT. 6. Persistency in Discrete Optimization. Part II: Continuous Nonconvex Programs. 7. RLT-Based Global Optimization Algorithms for Nonconvex Polynomial Programming Problems. 8. Reformulation-Convexification Technique for Quadratic Programs and Some Convex Envelope Characterizations. 9. Reformulation-Convexification Technique for Polynomial Programs: Design and Implementation. Part III: Special Applications to Discrete and Continuous Nonconvex Programs. 10. Applications to Discrete Problems. 11. Applications to Continuous Problems. References.
---
paper_title: ⋄ Convex Optimization,

paper_content:

Convex optimization problems arise frequently in many different fields. A comprehensive introduction to the subject, this book shows in detail how such problems can be solved numerically with great efficiency. The focus is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. The text contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance, and economics.
---
paper_title: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization

paper_content:

In the first part of this thesis, we introduce a specific class of Linear Matrix Inequalities (LMI) whose optimal solution can be characterized exactly. This family corresponds to the case where the associated linear operator maps the cone of positive semidefinite matrices onto itself. In this case, the optimal value equals the spectral radius of the operator. It is shown that some rank minimization problems, as well as generalizations of the structured singular value ($mu$) LMIs, have exactly this property. ::: ::: In the same spirit of exploiting structure to achieve computational efficiency, an algorithm for the numerical solution of a special class of frequency-dependent LMIs is presented. These optimization problems arise from robustness analysis questions, via the Kalman-Yakubovich-Popov lemma. The procedure is an outer approximation method based on the algorithms used in the computation of hinf norms for linear, time invariant systems. The result is especially useful for systems with large state dimension. ::: ::: The other main contribution in this thesis is the formulation of a convex optimization framework for semialgebraic problems, i.e., those that can be expressed by polynomial equalities and inequalities. The key element is the interaction of concepts in real algebraic geometry (Positivstellensatz) and semidefinite programming. ::: ::: To this end, an LMI formulation for the sums of squares decomposition for multivariable polynomials is presented. Based on this, it is shown how to construct sufficient Positivstellensatz-based convex tests to prove that certain sets are empty. Among other applications, this leads to a nonlinear extension of many LMI based results in uncertain linear system analysis. ::: ::: Within the same framework, we develop stronger criteria for matrix copositivity, and generalizations of the well-known standard semidefinite relaxations for quadratic programming. ::: ::: Some applications to new and previously studied problems are presented. A few examples are Lyapunov function computation, robust bifurcation analysis, structured singular values, etc. It is shown that the proposed methods allow for improved solutions for very diverse questions in continuous and combinatorial optimization.
---
paper_title: Nonlinear Programming: Theory, Algorithms and Applications

paper_content:

BASICS. The Nature of Optimization Problems. Analytical Background. Factorable Functions. UNCONSTRAINED PROBLEMS. Unconstrained Optimization Models. Minimizing a Function of a Single Variable. General Convergence Theory for Unconstrained Minimization Algorithms. Newton's Method With Variations. Conjugate Direction Algorithms. Quasi-Newton Methods. OPTIMALITY CONDITIONS FOR CONSTRAINED PROBLEMS. First- and Second-Order Optimality Conditions. Applications of Optimality Conditions. LINEARLY CONSTRAINED PROBLEMS. Models with Linear Constraints. Variable-Reduction Algorithms. NONLINEARLY CONSTRAINED PROBLEMS. Models with Nonlinear Constraints. Direct Algorithms for Nonlinearly Constrained Problems. Sequential Unconstrained Minimization Techniques. Sequential Constraint Linearization Techniques. OTHER TOPICS. Obtaining Global Solutions. Geometric Programming. References. Author and Subject Indexes.
---
paper_title: Handbook of semidefinite programming : theory, algorithms, and applications

paper_content:

Contributing Authors. List of Figures. List of Tables. Preface. 1. Introduction H. Wolkowicz, et al. Part I: Theory. 2. Convex Analysis on Symmetric Matrices F. Jarre. 3. The Geometry of Semidefinite Programming G. Pataki. 4. Duality and Optimality Conditions A. Shapiro, K. Scheinberg. 5. Self-Dual Embeddings E. de Klerk, et al. 6. Robustness A. Ben-Tal, et al. 7. Error Analysis Zhiquan Luo, J. Sturm. Part II: Algorithms. 8. Symmetric Cones, Potential Reduction Methods F. Alizadeh, S. Schmieta. 9. Potential Reduction and Primal-Dual Methods L. Tuncel. 10. Path-Following Methods R. Monteiro, M. Todd. 11. Bundle Methods and Eigenvalue Functions C. Helmberg, F. Oustry. Part III: Applications and Extensions. 12. Combinatorial Optimization M. Goemans, F. Rendl. 13. Nonconvex Quadratic Optimization Y. Nesterov, et al. 14. SDP in Systems and Control Theory V. Balakrishnan, Fan Wang. 15. Structural Design A. Ben-Tal, A. Nemirovski. 16. Moment Problems and Semidefinite Optimization D. Bertsimas, J. Sethuraman. 17. Design of Experiments in Statistics V. Fedorov, J. Lee. 18. Matrix Completion Problems A. Alfakih, H. Wolkowicz. 19. Eigenvalue Problems and Nonconvex Minimization F. Jarre. 20. General Nonlinear Programming S. Kruk, H. Wolkowicz. References. Appendix A-.1. Conclusion and Further Historical Notes. A-.2.Index.
---
paper_title: ⋄ Convex Optimization,

paper_content:

Convex optimization problems arise frequently in many different fields. A comprehensive introduction to the subject, this book shows in detail how such problems can be solved numerically with great efficiency. The focus is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. The text contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance, and economics.
---

Title: Convex Underestimating Relaxation Techniques for Nonconvex Polynomial Programming Problems: Computational Overview

Section 1: Introduction
Description 1: This section introduces the construction of convex relaxations for nonconvex optimization problems and highlights various techniques and their importance in global optimization.

Section 2: Convex Transforms
Description 2: This section describes convexification transformation methods that convert nonconvex problems into equivalent convex problems, focusing on concepts such as eigen-transformation, convex envelopes, nuclear norm, and conjugacy transformations.

Section 3: Convex Underestimators
Description 3: This section is dedicated to the determination of convex underestimators, including algorithms and methods to obtain relaxed dual functions, factorable relaxations, and relaxed lower bounds for complex terms.

Section 4: LP Relaxations for Quadratic Polynomial Programs
Description 4: This section details the Reformulation-Linearization Technique (RLT) and its application in creating LP relaxations for nonconvex quadratic problems, including the problem reformulation process and branch-and-bound algorithm.

Section 5: LMI Relaxations
Description 5: This section introduces LMI relaxations and their importance in solving nonconvex optimization problems, covering LMI feasibility sets, SDP formulations, and practical examples from engineering applications like truss topology design.

Section 6: Conclusion
Description 6: This section summarizes the main features of the relaxation techniques discussed, emphasizing the utility of relaxation methods in approximating difficult constrained optimization problems.

Appendix A: Branch-and-bound problem solving
Description A: This appendix provides a detailed example of the RLT process, illustrating the bounding and branching steps, and demonstrating the convergence of the solution.

Appendix B: Lagrange and SDP relaxations
Description B: This appendix explores the relationships between Lagrange and SDP relaxations with illustrative numerical examples.

Appendix C: Semidefinite Programming
Description C: This appendix discusses the interpretation of QP problems as SDP problems using Schur complements, covering various QP cases and their complexities.