[PDF] Introduction to Convex Optimization - The Hong Kong University of PDF slides_cvxopt

A set C ∈ Rn is said to be convex if the line segment between any two points is in the set: for any x,y ∈ C and 0 ≤ θ ≤ 1, θx + (1 − θ)y ∈ C Polyhedron: C = {x Ax ≤ b, Cx = d} where A ∈ Rm×n, C ∈ Rp×n, b ∈ Rm, d ∈ Rp

Convex Optimization / Stephen Boyd Lieven Vandenberghe p cm In this introduction we give an overview of mathematical optimization, focusing on

[PDF] Introduction to Convex Optimization for Machine Learning - People

Introduction to Convex Optimization for Machine Learning John Duchi Definition A set C ⊆ Rn is convex if for x, y ∈ C and any α ∈ [0,1], αx + (1 − α)y ∈ C

[PDF] Introduction to Convex Optimization - The Hong Kong University of

[PDF] Introduction to convex optimization I - The University of Edinburgh

Special classes of convex problems 1 Linear programming 2 Convex quadratic programming Sergio García Introduction to convex optimization I June 2018

[PDF] A Tutorial on Convex Optimization - UBC ECE

In some sense, convex optimization is providing new indispens- able computational tools today, which naturally extend our ability to solve problems such as least squares and linear programming to a much larger and richer class of problems

[PDF] 6079 Introduction to Convex Optimization, Lecture 1 - MIT

Convex Optimization — Boyd Vandenberghe 1 Introduction • mathematical optimization • least-squares and linear programming • convex optimization

[PDF] Lecture 1: Introduction to Convex Optimization

Lecture 1: Introduction to Convex Optimization Gan Zheng University of Luxembourg SnT Course: Convex Optimization with Applications Fall 2012

[PDF] An Introduction to Convex Optimization for Communications and

Index Terms—Convex optimization, digital communications, duality, second- order cone programming (SOCP), semidefinite programming (SDP), signal processing

[PDF] Lecture: Introduction to Convex Optimization - BICMR

Lecture: Introduction to Convex Optimization “Convex optimization”, Stephen Boyd and Lieven Vandenberghe solving convex optimization problems

[PDF] Introduction to Convex Constrained Optimization - ResearchGate

Introduction to Convex Constrained Optimization March 4, 2004 Solving Separable Convex Optimization via Linear Optimization • Optimality Conditions for

Introduction to Convex Optimization

Prof. Daniel P. Palomar

The Hong Kong University of Science and Technology (HKUST)

MAFS5310 - Portfolio Optimization with R

MSc in Financial Mathematics

Fall 2020-21, HKUST, Hong Kong

Outline

1Optimization Problems

2Convex Sets

3Convex Functions

4Convex Problems

Outline

1Optimization Problems

2Convex Sets

3Convex Functions

4Convex Problems

Optimization Problem

General optimization problem in standard form:

minimize xf0(x) subject tofi(x)0i=1;:::;m h i(x) =0i=1;:::;p where x= (x1;:::;xn)is the optimization variable f

0:Rn!Ris the objective function

f i:Rn!R;i=1;:::;mare inequality constraint functions h i:Rn!R;i=1;:::;pare equality constraint functions.Goal: find an optimal solutionx?that minimizesf0while satisfying all the constraints.

D. PalomarIntro to Convex Optimization4 / 52

Examples

Convex optimization is currently used in many different areas:circuit design (start-up named Barcelona in Silicon Valley)

signal processing (e.g., filter design) communication systems (e.g., transceiver design, beamforming design,

ML detection, power control in wireless)financial engineering (e.g., portfolio design, index tracking)

image proc. (e.g., deblurring, compressive sensing, blind separation) robust designs under uncertainty sparse and low-rank optimization machine learning graph learning from data biomedical applications (e.g., analysis of DNA)

D. PalomarIntro to Convex Optimization5 / 52

Examples: Elements in the Formulation

An optimization problem has three basic elements:

1variables,

2constraints, and

3objective.

Example: device sizing in electronic circuits:

variables: device widths and lengths constraints: manufacturing limits, timing requirements, max area objective: power consumption

Example: portfolio optimization:

variables: amounts invested in different assets constraints: budget, max investments per asset, min return objective: overall risk or return variance.

D. PalomarIntro to Convex Optimization6 / 52

Example: Power Control in Wireless Networks

Consider a wireless network withnlogical transmitter/receiver pairs: Goal: design the power allocation so that each receiver receives minimum interference from the other links.

D. PalomarIntro to Convex Optimization7 / 52

Example: Power Control in Wireless Networks

The signal-to-inerference-plus-noise-ratio (SINR) at theith receiver is sinr i=piGiiP j6=ipjGij+2i where p iis the power used by theith transmitter G ijis the path gain from transmitterjto receiveri

2iis the noise power at theith receiver.Problem: maximize the weakest SINR subject to power constraints

0pipmaxi:

maximize pmini=1;:::;np iGiiP j6=ipjGij+2i subject to 0pipmaxii=1;:::;n:D. PalomarIntro to Convex Optimization8 / 52

Solving Optimization Problems

General optimization problems are very difficult to solve (either long

computation time or not finding the best solution).Exceptions: least-squares problems, linear programming problems, and

convex optimization problems.Least-squares (LS)[Gauss, 1795]: minimize xkAxbk2

2solving LS problems: closed-form solutionx?=ATA1ATbfor

which there are reliable and efficient algorithms; mature technologyusing LS: easy to recognize

D. PalomarIntro to Convex Optimization9 / 52

Solving Optimization Problems

Linear Programming (LP):

minimize xcTx subject toaTixbi;i=1;:::;msolving LP problems: no closed-form solution, but reliable and efficient

algorithms and software; mature technologyusing LP: not as easy to recognize as LS problems, a few standard

tricks to convert problems into LPsConvex optimization: minimize xf0(x) subject tofi(x)bi;i=1;:::;msolving convex problems: no closed-form solution, but still reliable and

efficient algorithms and software; almost a technologyusing convex optimization: often difficult to recognize, many tricks for

transforming problems into convex form.

D. PalomarIntro to Convex Optimization10 / 52

Nonconvex Optimization

Nonconvex optimization problems are generally very difficult to solve,

although there are some rare exceptions.In general, they require either a long computation time or the

compromise of not always finding the optimal solution:local optimization: fast algorithms, but no guarantee of global

optimality, only local solution around the initial pointglobal optimization: worst-case complexity grows exponentially with

problem size, but finds global solution.

D. PalomarIntro to Convex Optimization11 / 52

Example: Lamp Illumination Problem

Considermlamps illuminatingnsmall flat patches:

Goal: achieve a desired illuminationIdeson all patches with bounded lamp powers.

D. PalomarIntro to Convex Optimization12 / 52

Example: Lamp Illumination Problem

The intensityIkat patchkdepends linearly on the lamp powerspj: I k=mX j=1a kjpj

where the coefficientsakjare given byakj= coskj=r2kj.Problem formulation: since the illumination is perceived

logarithmically by the eye, a good formulation of the problem is minimize I

1;:::;In;p1;:::;pmmaxkjlogIklogIdesj

subject to 0pjpmax;j=1;:::;m I k=Pm j=1akjpj;k=1;:::;n:How to solve the problem? Answer: It depends on how much you know about optimization.

D. PalomarIntro to Convex Optimization13 / 52

Example: Lamp Illumination Problem

1If you don"t know anything, then you just take a heuristic guess like

using a uniform powerpj=p, perhaps trying different values ofp.

2If you know about least-squares, then approximate the problem as

minimize I

1;:::;In;p1;:::;pmP

n k=1(IkIdes)2 subject toIk=Pm j=1akjpj;k=1;:::;n: and then clippjifpj>pmaxorpj<0.

3If you know about linear programming, then approximate the problem

asminimizeI

1;:::;In;p1;:::;pmmaxkjIkIdesj

subject to 0pjpmax;j=1;:::;m I k=Pm j=1akjpj;k=1;:::;n; which may not look as an LP but it is!

D. PalomarIntro to Convex Optimization14 / 52

Example: Lamp Illumination Problem

1If you don"t know anything, then you just take a heuristic guess like

using a uniform powerpj=p, perhaps trying different values ofp.2If you know about least-squares, then approximate the problem as

minimize I

1;:::;In;p1;:::;pmP

n k=1(IkIdes)2 subject toIk=Pm j=1akjpj;k=1;:::;n: and then clippjifpj>pmaxorpj<0.3If you know about linear programming, then approximate the problem asminimizeI

1;:::;In;p1;:::;pmmaxkjIkIdesj

subject to 0pjpmax;j=1;:::;m I k=Pm j=1akjpj;k=1;:::;n; which may not look as an LP but it is!

D. PalomarIntro to Convex Optimization14 / 52

Example: Lamp Illumination Problem

1If you don"t know anything, then you just take a heuristic guess like

using a uniform powerpj=p, perhaps trying different values ofp.2If you know about least-squares, then approximate the problem as

minimize I

1;:::;In;p1;:::;pmP

n k=1(IkIdes)2 subject toIk=Pm j=1akjpj;k=1;:::;n: and then clippjifpj>pmaxorpj<0.3If you know about linear programming, then approximate the problem asminimizeI

1;:::;In;p1;:::;pmmaxkjIkIdesj

subject to 0pjpmax;j=1;:::;m I k=Pm j=1akjpj;k=1;:::;n; which may not look as an LP but it is!

D. PalomarIntro to Convex Optimization14 / 52

Example: Lamp Illumination Problem

4If you know about convex optimization, after staring at the problem

long enough, you may realize that you can actually reformulate the original problem in convex form and then find the global solution: minimize I

1;:::;In;p1;:::;pmmaxkh(Ik=Ides)

subject to 0pjpmax;j=1;:::;m I k=Pm j=1akjpj;k=1;:::;n; whereh(u) = maxfu;1=ug.D. PalomarIntro to Convex Optimization15 / 52

Example: Lamp Illumination Problem

Additional constraints: does adding the constraints below complicate the problem? (a)no more than half of total power is in any 10 lamps (b)no more than half of the lamps are on (pj>0).Answer: (a)does not complicate the problem, whereas

(b)makes the problem extremely difficult.Moral: untrained intuition doesn"t always work; one needs to obtain

the proper background and develop the right intuition to discern between difficult and easy problems.

D. PalomarIntro to Convex Optimization16 / 52

Example: Lamp Illumination Problem

Additional constraints: does adding the constraints below complicate the problem? (a)no more than half of total power is in any 10 lamps (b)no more than half of the lamps are on (pj>0).Answer:

(a)does not complicate the problem, whereas(b)makes the problem extremely difficult.Moral: untrained intuition doesn"t always work; one needs to obtain

the proper background and develop the right intuition to discern between difficult and easy problems.

D. PalomarIntro to Convex Optimization16 / 52

Example: Lamp Illumination Problem

Additional constraints: does adding the constraints below complicate the problem? (a)no more than half of total power is in any 10 lamps (b)no more than half of the lamps are on (pj>0).Answer:

(a)does not complicate the problem, whereas(b)makes the problem extremely difficult.Moral: untrained intuition doesn"t always work; one needs to obtain

the proper background and develop the right intuition to discern between difficult and easy problems.

D. PalomarIntro to Convex Optimization16 / 52

Example: Lamp Illumination Problem

Additional constraints: does adding the constraints below complicate the problem? (a)no more than half of total power is in any 10 lamps (b)no more than half of the lamps are on (pj>0).Answer:

(a)does not complicate the problem, whereas(b)makes the problem extremely difficult.Moral: untrained intuition doesn"t always work; one needs to obtain

the proper background and develop the right intuition to discern between difficult and easy problems.

D. PalomarIntro to Convex Optimization16 / 52

Historical Snapshop of Convex Optimization

Theory(convex analysis): ca1900-1970 (e.g. Rockafellar)Algorithms:1947: simplex algorithm for linear programming (Dantzig)

1960s: early interior-point methods (Fiacco & McCormick, Dikin)

1970s: ellipsoid method and other subgradient methods

1980s: polynomial-time interior-point methods for linear programming

(Karmakar 1984)late 1980s-now: polynomial-time interior-point methods for nonlinear

convex optimization (Nesterov & Nemirovski 1994)Applications:before 1990s: mostly in operations research; few in engineering

since 1990: many new applications in engineering and new problem classes (SDP, SOCP, robust optim.)

D. PalomarIntro to Convex Optimization17 / 52

References on Convex Optimization

Stephen Boyd and Lieven Vandenberghe,Convex Optimization. Cambridge, U.K.: Cambridge University Press, 2004.

https://web.stanford.edu/~boyd/cvxbook/Daniel P. Palomar and Yonina C. Eldar, Eds.,Convex Optimization in

Signal Processing and Communications, Cambridge University Press,quotesdbs_dbs8.pdfusesText_14

[PDF] [PDF] Introduction to Convex Optimization - The Hong Kong University of

Introduction to Convex Optimization

Prof. Daniel P. Palomar

MAFS5310 - Portfolio Optimization with R

MSc in Financial Mathematics

Fall 2020-21, HKUST, Hong Kong

Outline

1Optimization Problems

2Convex Sets

3Convex Functions

4Convex Problems

Outline

1Optimization Problems

2Convex Sets

3Convex Functions

4Convex Problems

Optimization Problem

General optimization problem in standard form:

0:Rn!Ris the objective function

D. PalomarIntro to Convex Optimization4 / 52

Examples

D. PalomarIntro to Convex Optimization5 / 52

Examples: Elements in the Formulation

An optimization problem has three basic elements:

1variables,

2constraints, and

3objective.

Example: device sizing in electronic circuits:

Example: portfolio optimization:

D. PalomarIntro to Convex Optimization6 / 52

Example: Power Control in Wireless Networks

D. PalomarIntro to Convex Optimization7 / 52

Example: Power Control in Wireless Networks

2iis the noise power at theith receiver.Problem: maximize the weakest SINR subject to power constraints

0pipmaxi:

Solving Optimization Problems

2solving LS problems: closed-form solutionx?=ATA1ATbfor

D. PalomarIntro to Convex Optimization9 / 52

Solving Optimization Problems

Linear Programming (LP):

D. PalomarIntro to Convex Optimization10 / 52

Nonconvex Optimization

D. PalomarIntro to Convex Optimization11 / 52

Example: Lamp Illumination Problem

Considermlamps illuminatingnsmall flat patches:

D. PalomarIntro to Convex Optimization12 / 52

Example: Lamp Illumination Problem

1;:::;In;p1;:::;pmmaxkjlogIklogIdesj

D. PalomarIntro to Convex Optimization13 / 52

Example: Lamp Illumination Problem

1If you don"t know anything, then you just take a heuristic guess like

2If you know about least-squares, then approximate the problem as

1;:::;In;p1;:::;pmP

3If you know about linear programming, then approximate the problem

1;:::;In;p1;:::;pmmaxkjIkIdesj

D. PalomarIntro to Convex Optimization14 / 52

Example: Lamp Illumination Problem

1If you don"t know anything, then you just take a heuristic guess like

1;:::;In;p1;:::;pmP

1;:::;In;p1;:::;pmmaxkjIkIdesj

D. PalomarIntro to Convex Optimization14 / 52

Example: Lamp Illumination Problem

1If you don"t know anything, then you just take a heuristic guess like

1;:::;In;p1;:::;pmP

1;:::;In;p1;:::;pmmaxkjIkIdesj

D. PalomarIntro to Convex Optimization14 / 52

Example: Lamp Illumination Problem

4If you know about convex optimization, after staring at the problem

1;:::;In;p1;:::;pmmaxkh(Ik=Ides)

Example: Lamp Illumination Problem

D. PalomarIntro to Convex Optimization16 / 52

Example: Lamp Illumination Problem

D. PalomarIntro to Convex Optimization16 / 52

Example: Lamp Illumination Problem

D. PalomarIntro to Convex Optimization16 / 52

Example: Lamp Illumination Problem

D. PalomarIntro to Convex Optimization16 / 52

Historical Snapshop of Convex Optimization

1960s: early interior-point methods (Fiacco & McCormick, Dikin)

1970s: ellipsoid method and other subgradient methods