Lecture

Convexifying Nonconvex Problems: SDP and SOCP Relaxations

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

MGT-418: Convex optimization

This course introduces the theory and application of modern convex optimization from an engineering perspective. ...

Description

This lecture by the instructor covers the concept of convexifying nonconvex problems using semidefinite programming (SDP) and second-order cone programming (SOCP) relaxations. The lecture starts by introducing the interpretation of problems as convex relaxations, focusing on the convex-cardinality problem and continuous relaxations. It then delves into examples of total variation reconstruction in 1D and 2D, illustrating the application of convex approximations. The lecture further explores convex-rank problems, lift-and-project methods, and the semidefinite relaxation of quadratically constrained quadratic programs (QCQPs). Finally, it discusses optimal power flow (OPF) in power systems, detailing the formulation, constraints, and the highly nonconvex nature of the OPF problem.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Daniel Kuhn

Official source

Related concepts (22)

Cutting-plane method

In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are commonly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory.

Linear programming relaxation

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are of the form The relaxation of the original integer program instead uses a collection of linear constraints The resulting relaxation is a linear program, hence the name.

Convex optimization

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

Duality (optimization)

In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then the dual is a maximization problem (and vice versa). Any feasible solution to the primal (minimization) problem is at least as large as any feasible solution to the dual (maximization) problem.

Mathematical optimization

Mathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Related lectures (64)

Optimization Methods: Theory Discussion

Explores optimization methods, including unconstrained problems, linear programming, and heuristic approaches.

Energy Conversion Systems Optimization

Explores energy conversion systems optimization through heat recovery and mixed integer linear programming.

Linear Programming: Weighted Bipartite Matching

Covers linear programming, weighted bipartite matching, and vertex cover problems in optimization.

Linear Programming Duality

Explores Linear Programming Duality, covering weak duality, strong duality, Lagrange multipliers interpretation, and optimization constraints.

Approximation Algorithms