Uncategorized

ECE1505H Convex Optimization. Lecture 7: Examples of convex and concave functions, local and global minimums. Taught by Prof. Stark Draper

February 2, 2017 Uncategorized No comments , , , , , , ,

[Click here for a PDF of this post with nicer formatting]

Disclaimer

Peeter’s lecture notes from class. These may be incoherent and rough.

These are notes for the UofT course ECE1505H, Convex Optimization, taught by Prof. Stark Draper, from [1].

Today

  • Local and global optimality
  • Compositions of functions
  • Examples

Example:

\begin{equation}\label{eqn:convexOptimizationLecture7:20}
\begin{aligned}
F(x) &= x^2 \\
F”(x) &= 2 > 0
\end{aligned}
\end{equation}

strictly convex.

Example:

\begin{equation}\label{eqn:convexOptimizationLecture7:40}
\begin{aligned}
F(x) &= x^3 \\
F”(x) &= 6 x.
\end{aligned}
\end{equation}

Not always non-negative, so not convex. However \( x^3 \) is convex on \( \textrm{dom} F = \mathbb{R}_{+} \).

Example:

\begin{equation}\label{eqn:convexOptimizationLecture7:60}
\begin{aligned}
F(x) &= x^\alpha \\
F'(x) &= \alpha x^{\alpha-1} \\
F”(x) &= \alpha(\alpha-1) x^{\alpha-2}.
\end{aligned}
\end{equation}

 

fig. 1. Powers of x.

This is convex on \( \mathbb{R}_{+} \), if \( \alpha \ge 1 \), or \( \alpha \le 0 \).

Example:

\begin{equation}\label{eqn:convexOptimizationLecture7:80}
\begin{aligned}
F(x) &= \log x \\
F'(x) &= \inv{x} \\
F”(x) &= -\inv{x^2} \le 0
\end{aligned}
\end{equation}

This is concave.

Example:

\begin{equation}\label{eqn:convexOptimizationLecture7:100}
\begin{aligned}
F(x) &= x\log x \\
F'(x) &= \log x + x \inv{x} = 1 + \log x \\
F”(x) &= \inv{x}
\end{aligned}
\end{equation}

This is strictly convex on
\( \mathbb{R}_{++} \), where
\( F”(x) \ge 0 \).

Example:

\begin{equation}\label{eqn:convexOptimizationLecture7:120}
\begin{aligned}
F(x) &= e^{\alpha x} \\
F'(x) &= \alpha e^{\alpha x} \\
F”(x) &= \alpha^2 e^{\alpha x} \ge 0
\end{aligned}
\end{equation}

fig. 2. Exponential.

Such functions are plotted in fig. 2, and are convex function for all \( \alpha \).

Example:

For symmetric \( P \in S^n \)

\begin{equation}\label{eqn:convexOptimizationLecture7:140}
\begin{aligned}
F(\Bx) &= \Bx^\T P \Bx + 2 \Bq^\T \Bx + r \\
\spacegrad F &= (P + P^\T) \Bx + 2 \Bq = 2 P \Bx + 2 \Bq \\
\spacegrad^2 F &= 2 P.
\end{aligned}
\end{equation}

This is convex(concave) if \( P \ge 0 \) (\( P \le 0\)).

Example:

A quadratic function

\begin{equation}\label{eqn:convexOptimizationLecture7:780}
F(x, y) = x^2 + y^2 + 3 x y,
\end{equation}

that is neither convex nor concave is plotted in fig 3.

fig 3. Function with saddle point (3d and contours)

This function can be put in matrix form

\begin{equation}\label{eqn:convexOptimizationLecture7:160}
F(x, y) = x^2 + y^2 + 3 x y
=
\begin{bmatrix}
x & y
\end{bmatrix}
\begin{bmatrix}
1 & 1.5 \\
1.5 & 1
\end{bmatrix}
\begin{bmatrix}
x \\
y
\end{bmatrix},
\end{equation}

and has the Hessian

\begin{equation}\label{eqn:convexOptimizationLecture7:180}
\begin{aligned}
\spacegrad^2 F
&=
\begin{bmatrix}
\partial_{xx} F & \partial_{xy} F \\
\partial_{yx} F & \partial_{yy} F \\
\end{bmatrix} \\
&=
\begin{bmatrix}
2 & 3 \\
3 & 2
\end{bmatrix} \\
&= 2 P.
\end{aligned}
\end{equation}

From the plot we know that this is not PSD, but this can be confirmed by checking the eigenvalues

\begin{equation}\label{eqn:convexOptimizationLecture7:200}
\begin{aligned}
0
&=
\det ( P – \lambda I ) \\
&=
(1 – \lambda)^2 – 1.5^2,
\end{aligned}
\end{equation}

which has solutions

\begin{equation}\label{eqn:convexOptimizationLecture7:220}
\lambda = 1 \pm \frac{3}{2} = \frac{3}{2}, -\frac{1}{2}.
\end{equation}

This is not PSD nor negative semi-definite, because it has one positive and one negative eigenvalues. This is neither convex nor concave.

Along \( y = -x \),

\begin{equation}\label{eqn:convexOptimizationLecture7:240}
\begin{aligned}
F(x,y)
&=
F(x,-x) \\
&=
2 x^2 – 3 x^2 \\
&=
– x^2,
\end{aligned}
\end{equation}

so it is concave along this line. Along \( y = x \)

\begin{equation}\label{eqn:convexOptimizationLecture7:260}
\begin{aligned}
F(x,y)
&=
F(x,x) \\
&=
2 x^2 + 3 x^2 \\
&=
5 x^2,
\end{aligned}
\end{equation}

so it is convex along this line.

Example:

\begin{equation}\label{eqn:convexOptimizationLecture7:280}
F(\Bx) = \sqrt{ x_1 x_2 },
\end{equation}

on \( \textrm{dom} F = \setlr{ x_1 \ge 0, x_2 \ge 0 } \)

For the Hessian
\begin{equation}\label{eqn:convexOptimizationLecture7:300}
\begin{aligned}
\PD{x_1}{F} &= \frac{1}{2} x_1^{-1/2} x_2^{1/2} \\
\PD{x_2}{F} &= \frac{1}{2} x_2^{-1/2} x_1^{1/2}
\end{aligned}
\end{equation}

The Hessian components are

\begin{equation}\label{eqn:convexOptimizationLecture7:320}
\begin{aligned}
\PD{x_1}{} \PD{x_1}{F} &= -\frac{1}{4} x_1^{-3/2} x_2^{1/2} \\
\PD{x_1}{} \PD{x_2}{F} &= \frac{1}{4} x_2^{-1/2} x_1^{-1/2} \\
\PD{x_2}{} \PD{x_1}{F} &= \frac{1}{4} x_1^{-1/2} x_2^{-1/2} \\
\PD{x_2}{} \PD{x_2}{F} &= -\frac{1}{4} x_2^{-3/2} x_1^{1/2}
\end{aligned}
\end{equation}

or
\begin{equation}\label{eqn:convexOptimizationLecture7:340}
\spacegrad^2 F
=
-\frac{\sqrt{x_1 x_2}}{4}
\begin{bmatrix}
\inv{x_1^2} & -\inv{x_1 x_2} \\
-\inv{x_1 x_2} & \inv{x_2^2}
\end{bmatrix}.
\end{equation}

Checking this for PSD against \( \Bv = (v_1, v_2) \), we have
\begin{equation}\label{eqn:convexOptimizationLecture7:360}
\begin{aligned}
\begin{bmatrix}
v_1 & v_2
\end{bmatrix}
\begin{bmatrix}
\inv{x_1^2} & -\inv{x_1 x_2} \\
-\inv{x_1 x_2} & \inv{x_2^2}
\end{bmatrix}
\begin{bmatrix}
v_1 \\ v_2
\end{bmatrix}
&=
\begin{bmatrix}
v_1 & v_2
\end{bmatrix}
\begin{bmatrix}
\inv{x_1^2} v_1 -\inv{x_1 x_2} v_2 \\
-\inv{x_1 x_2} v_1 + \inv{x_2^2} v_2
\end{bmatrix} \\
&=
\lr{ \inv{x_1^2} v_1 -\inv{x_1 x_2} v_2 } v_1 +
\lr{ -\inv{x_1 x_2} v_1 + \inv{x_2^2} v_2 } v_2
\\
&=
\inv{x_1^2} v_1^2
+ \inv{x_2^2} v_2^2
-2 \inv{x_1 x_2} v_1 v_2 \\
&=
\lr{
\frac{v_1}{x_1}
-\frac{v_2}{x_2}
}^2 \\
&\ge 0,
\end{aligned}
\end{equation}

so \( \spacegrad^2 F \le 0 \). This is a negative semi-definite function (concave). Observe that this check required checking PSD for all values of \( \Bx \).

This is an example of a more general result

\begin{equation}\label{eqn:convexOptimizationLecture7:380}
F(x) = \lr{ \prod_{i = 1}^n x_i }^{1/n},
\end{equation}

which is concave (prove on homework).

Summary.

If \( F \) is differentiable in \R{n}, then check the curvature of the function along all lines. i.e. At all locations and in all directions.

If the Hessian is PSD at all \( \Bx \in \textrm{dom} F \), that is

\begin{equation}\label{eqn:convexOptimizationLecture7:400}
\spacegrad^2 F \ge 0 \, \forall \Bx \in \textrm{dom} F,
\end{equation}

then the function is convex.

more examples of convex, but not necessarily differentiable functions

Example:

Over \( \textrm{dom} F = \mathbb{R}^n \)

\begin{equation}\label{eqn:convexOptimizationLecture7:420}
F(\Bx) = \max_{i = 1}^n x_i
\end{equation}

i.e.
\begin{equation}\label{eqn:convexOptimizationLecture7:440}
\begin{aligned}
F((1,2) &= 2 \\
F((3,-1) &= 3
\end{aligned}
\end{equation}

Example:

\begin{equation}\label{eqn:convexOptimizationLecture7:460}
F(\Bx) = \max_{i = 1}^n F_i(\Bx),
\end{equation}

where

\begin{equation}\label{eqn:convexOptimizationLecture7:480}
F_i(\Bx)
=
… ?
\end{equation}

max of a set of convex functions is a convex function.

Example:

\begin{equation}\label{eqn:convexOptimizationLecture7:500}
F(x) =
x_{[1]} +
x_{[2]} +
x_{[3]}
\end{equation}

where

\( x_{[k]} \) is the k-th largest number in the list

Write

\begin{equation}\label{eqn:convexOptimizationLecture7:520}
F(x) = \max x_i + x_j + x_k
\end{equation}

\begin{equation}\label{eqn:convexOptimizationLecture7:540}
(i,j,k) \in \binom{n}{3}
\end{equation}

Example:

For \( \Ba \in \mathbb{R}^n \) and \( b_i \in \mathbb{R} \)

\begin{equation}\label{eqn:convexOptimizationLecture7:560}
\begin{aligned}
F(\Bx)
&= \sum_{i = 1}^n \log( b_i – \Ba^\T \Bx )^{-1} \\
&= -\sum_{i = 1}^n \log( b_i – \Ba^\T \Bx )
\end{aligned}
\end{equation}

This \( b_i – \Ba^\T \Bx \) is an affine function of \( \Bx \) so it doesn’t affect convexity.

Since \( \log \) is concave, \( -\log \) is convex. Convex functions of affine function of \( \Bx \) is convex function of \( \Bx \).

Example:

\begin{equation}\label{eqn:convexOptimizationLecture7:580}
F(\Bx) = \sup_{\By \in C} \Norm{ \Bx – \By }
\end{equation}

 

fig. 3. Max length function

 

Here \( C \subseteq \mathbb{R}^n \) is not necessarily convex. We are using \( \sup \) here because the set \( C \) may be open. This function is the length of the line from \( \Bx \) to the point in \( C \) that is furthest from \( \Bx \).

  • \( \Bx – \By \) is linear in \( \Bx \)
  • \( g_\By(\Bx) = \Norm{\Bx – \By} \) is convex in \( \Bx \) since norms are convex functions.
  • \( F(\Bx) = \sup_{\By \in C} \Norm{ \Bx – \By } \). Each \( \By \) index is a convex function. Taking max of those.

Example:

\begin{equation}\label{eqn:convexOptimizationLecture7:600}
F(\Bx) = \inf_{\By \in C} \Norm{ \Bx – \By }.
\end{equation}

Min and max of two convex functions are plotted in fig. 4.

fig. 4. Min and max

The max is observed to be convex, whereas the min is not necessarily so.

\begin{equation}\label{eqn:convexOptimizationLecture7:800}
F(\Bz) = F(\theta \Bx + (1-\theta) \By) \ge \theta F(\Bx) + (1-\theta)F(\By).
\end{equation}

This is not necessarily convex for all sets \( C \subseteq \mathbb{R}^n \), because the \( \inf \) of a bunch of convex function is not necessarily convex. However, if \( C \) is convex, then \( F(\Bx) \) is convex.

Consequences of convexity for differentiable functions

  • Think about unconstrained functions \( \textrm{dom} F = \mathbb{R}^n \).
  • By first order condition \( F \) is convex iff the domain is convex and
    \begin{equation}\label{eqn:convexOptimizationLecture7:620}
    F(\Bx) \ge \lr{ \spacegrad F(\Bx)}^\T (\By – \Bx) \, \forall \Bx, \By \in \textrm{dom} F.
    \end{equation}

If \( F \) is convex and one can find an \( \Bx^\conj \in \textrm{dom} F \) such that

\begin{equation}\label{eqn:convexOptimizationLecture7:640}
\spacegrad F(\Bx^\conj) = 0,
\end{equation}

then

\begin{equation}\label{eqn:convexOptimizationLecture7:660}
F(\By) \ge F(\Bx^\conj) \, \forall \By \in \textrm{dom} F.
\end{equation}

If you can find the point where the gradient is zero (which can’t always be found), then \( \Bx^\conj\) is a global minimum of \( F \).

Conversely, if \( \Bx^\conj \) is a global minimizer of \( F \), then \( \spacegrad F(\Bx^\conj) = 0 \) must hold. If that were not the case, then you would be able to find a direction to move downhill, contracting the optimality of \( \Bx^\conj\).

Local vs Global optimum

 

fig. 6. Global and local minimums

Definition: Local optimum
\( \Bx^\conj \) is a local optimum of \( F \) if \( \exists \epsilon > 0 \) such that \( \forall \Bx \), \( \Norm{\Bx – \Bx^\conj} < \epsilon \), we have

\begin{equation*}
F(\Bx^\conj) \le F(\Bx)
\end{equation*}

 

fig. 5. min length function

Theorem:
Suppose \( F \) is twice continuously differentiable (not necessarily convex)

  • If \( \Bx^\conj\) is a local optimum then\begin{equation*}
    \begin{aligned}
    \spacegrad F(\Bx^\conj) &= 0 \\
    \spacegrad^2 F(\Bx^\conj) \ge 0
    \end{aligned}
    \end{equation*}
  • If
    \begin{equation*}
    \begin{aligned}
    \spacegrad F(\Bx^\conj) &= 0 \\
    \spacegrad^2 F(\Bx^\conj) \ge 0
    \end{aligned},
    \end{equation*}then \( \Bx^\conj\) is a local optimum.

Proof:

  • Let \( \Bx^\conj \) be a local optimum. Pick any \( \Bv \in \mathbb{R}^n \).\begin{equation}\label{eqn:convexOptimizationLecture7:720}
    \lim_{t \rightarrow 0} \frac{ F(\Bx^\conj + t \Bv) – F(\Bx^\conj)}{t}
    = \lr{ \spacegrad F(\Bx^\conj) }^\T \Bv
    \ge 0.
    \end{equation}

Here the fraction is \( \ge 0 \) since \( \Bx^\conj \) is a local optimum.

Since the choice of \( \Bv \) is arbitrary, the only case that you can ensure that \( \ge 0, \forall \Bv \) is

\begin{equation}\label{eqn:convexOptimizationLecture7:740}
\spacegrad F = 0,
\end{equation}

( or else could pick \( \Bv = -\spacegrad F(\Bx^\conj) \).

This means that \( \spacegrad F(\Bx^\conj) = 0 \) if \( \Bx^\conj \) is a local optimum.

Consider the 2nd order derivative

\begin{equation}\label{eqn:convexOptimizationLecture7:760}
\begin{aligned}
\lim_{t \rightarrow 0} \frac{ F(\Bx^\conj + t \Bv) – F(\Bx^\conj)}{t^2}
&=
\lim_{t \rightarrow 0} \inv{t^2}
\lr{
F(\Bx^\conj) + t \lr{ \spacegrad F(\Bx^\conj) }^\T \Bv + \inv{2} t^2 \Bv^\T \spacegrad^2 F(\Bx^\conj) \Bv + O(t^3)
– F(\Bx^\conj)
} \\
&=
\inv{2} \Bv^\T \spacegrad^2 F(\Bx^\conj) \Bv \\
&\ge 0.
\end{aligned}
\end{equation}

Here the \( \ge \) condition also comes from the fraction, based on the optimiality of \( \Bx^\conj \). This is true for all choice of \( \Bv \), thus \( \spacegrad^2 F(\Bx^\conj) \).

References

[1] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

New home office and network setup

August 30, 2016 Uncategorized 2 comments

I’ve just bought a nice new desk for my home office:

IMG_20160830_123415866_HDR

When I assembled the new desk, I took the opportunity to refine my home network setup.  In this post I’ll walk through that setup.

I’ve got the router in the living room, along with the two NUC6i’s that I use for my lzlabs development work:

nucs and router

I run the NUCs headless, using ssh and command line access for my work.  For those times that I need to refresh the install image and need a display, I also have them HDMI connected to the living room TV, and direct connected with short ethernet cables to the router:

nuc wiring

The router is also directly connected to the PS3 (for netflix), and then runs through some ethernet lines that I fished into the basement, before some of the basement finishing work we did just after we moved in.  All the lines I have going into the basement terminate in a patch panel:

patch panel

Does a patch panel sound like overkill?  Yes, it probably is.  However, I’ve got a pile of roughed in ethernet lines to the kids rooms and the rec room that I’ll eventually fish into the electrical-panel/laundry/network room:

wire bundle

I’d like to also eventually fish some ethernet lines into the upstairs space (i.e. for netflix run off a blue-ray player that sits mostly unused in the master bedroom), but that’s a harder fishing job, and I haven’t done it yet.  From the front of the patch panel things go off to the router:

patch panel 2

and from there to a switch:

switch and phone

One line comes from the router (through the patch panel), and then all the rest of the ethernet lines from the switch go to final destinations.  Four of those lines go back to the patch panel and up to the office space.  One is plugged into one of the thunderbolt monitors, so I can use a wired connection while “docked”.  One goes up to the office space and is connected to an Odroid (which can run the Lz stack on aarch64 hardware).  One line goes back to the living room, for optional wired couch surfing, and the last is connected to a voip phone.

I’ve got a lot of finishing touches to do.  I plan to mount the patch panel next to the electrical panel, instead of just placing it on top of the freezer down in the laundry room.  I’ve also got lines that are running through the ceiling, but are hanging loose still.  The wall panel in my office space is currently hanging loose:

desk cabling

I have a low voltage wiring box purchased, but need to cut the hole for it, so I can screw in this little panel and get it nicely out of the way, and do the plastering and painting to fix up the messy fishing holes I made trying to find a route down into the basement.

Shipping with DHL. They will screw you, but not quite as bad as UPS.

August 27, 2016 Incoherent ramblings, Uncategorized No comments , , , , ,

I previously complained about UPS customs clearing charges that I was slammed with receiving back some of my own goods.

Basically, the Canadian government grants shipping companies the right to extort receivers at the point of customs clearing. Canada might add a few cents or a buck or two of tax, but the shipping company is then able to add fees that are orders of magnitude higher than the actual taxes.

I actually stopped buying anything from the United States because of this, and have been buying from Europe and India instead, where I had not yet gotten blasted with customs clearing fees for the items I’ve been buying (usually textbooks).

However, it appears that my luck has run out.  Here’s the newest example, with a $15 dollar clearing fee that DHL added onto about a dollar of tax:

IMG_20160827_095043195 (1)

Note that I did not pick the shipping company.  That was selected by the book seller (one of the abebooks.com resellers).

For $1.17 of taxes, DHL has charged me $14.75 of fees, all for the right to allow Canada revenue to steal from me.  To add insult to injury, DHL is allowed to charge GST for their extortion service, so I end up paying an additional $3.09 (close to 3x the initial tax amount).  The value of the book + shipping that I purchased was only $23.30!

Aside: Why is the GST on $14.75 that high?  I thought that’s a 13% tax, so shouldn’t it be $1.92?

I’ve found some instructions that explain some of the black magic required to do my own customs clearing:

One of the first steps is to find the CBSA office that I can submit such a clearing form to.  I can narrow that search down to province, but some of these offices are restricted to specific purposes, and it isn’t obvious which of these offices I should use.  For example the one at Buttonville airport appears to be restricted to handling just the cargo that arrives there.

I wonder if there are any local resellers that import used and cheap textbooks in higher quantities and then resell them locally (taking the customs clearing charge only once per shipment)?

Fishing for wall trout.

April 28, 2016 Uncategorized 1 comment , , ,

Before we finished the kids half of the basement (2 bedrooms, 1 rec room, and a bathroom), I ran a couple cat5 cables through the ceiling alongside the cable modem line.  I didn’t know if I’d ever need them, but it seemed like a good idea at the time.

Now that I want ethernet lines in other parts of the house, I’m really glad I’d done that.  All I had to do was fish the unterminated lines out of the wall and put a couple jack inserts on them.  I bought a cheap non-cutting push down tool from home depot a while ago and finally got to use it:

 

 

IMG_1128 IMG_1129 IMG_1130

Because the push down tool didn’t have a blade, I just used an exacto knife to cut the lines before capping the jack inserts.  That worked very nicely since there is a small lip on the jack insert, and you can cut the wires right against that easily.

Next step was terminating the lines in the basement on the patch panel.

13055125_10209823933941722_9152519273805908410_o

That was a bit easier to do since the wiring block for the patch panel keeps all pairs together.  With the jack, it was more random, with some pairs pushed down next to each other, and others opposite.

IMG_1132IMG_1138

I used the 568B wiring convention.  It sounds like that is generally preferred for wiring data, although 568A is sometimes used for wiring phone.  I have no intention of ever simultaneously running both phone and data through any single wire, so I don’t think it really matters which of the conventions to use (so long as I do the same thing at both the patch panel and the jack insert).

Next step was testing the connections.  I bought a cheap ethernet cable tester at Sayal a while ago when I saw it on sale, so I got to play with that too.

IMG_1133 IMG_1136

I saw no red lights at either end as it proceeded with the wire check cycle, and the termination point sequence was monotonic as desired.  With both cables tested, I was ready to put the plate on the wall.  I’ve got speaker wire for the rear surround sound speakers coming out of that too, in a rather ugly fashion.  Eventually, I may try to figure out what to do to pretty that up, but most of the time I don’t think about it, since it hides back there sight unseen.

IMG_1142

The next step was the fishing trip.  I thought it was going to be easy to get through the wall into the unfinished section of the basement below, but I wasn’t able to find a route in one try (I kept hitting rafters and other obstructions).  I actually have three holes in the wall now, and have some patching to do (and probably have to pull the trim on that wall and reinstall it, since it is now pushed out).

IMG_1143 IMG_1144

Once I got my lines in place, I replaced my electric tape “numbering” sequence with some numbers, and started terminating them.

 

.IMG_1146 IMG_1147

Finally, a bit of patch panel work for these new lines, and I am left with something functional.

IMG_1149IMG_1150IMG_1152

This gives me wired connections to the two NUCs that I’m going to be using as development boxes (the RHEL7 + linux 4-5 kernel iwlwifi driver is pretty erratic, and has erratic and frequent hangs).

IMG_1151

I have a whole bunch of finishing to do for this project.  For example I haven’t even put in the box to attach the wall plate to in the office, and have unsecured lines in the basement, and don’t have the patch panel mounted yet.  I’d also like to run a new RG6 line to the office and put the router in there.  Because I ran lots of lines into the office space, this will allow me to feed other locations in the house through the patch panel.

 

All that said, I have accomplished the task I set out to do.  Get myself up and running with NUCs and monitor all in the office, and no more flaky wireless to those devices.

 

 

Another aggregation of notes for phy1520, Graduate Quantum Mechanics.

December 15, 2015 phy1520, Uncategorized No comments

I’ve posted a fourth (pre-exam) update of my aggregate notes for PHY1520H Graduate Quantum Mechanics, taught by Prof. Arun Paramekanti. In addition to what was noted previously, this contains the remainder of my lecture notes, more problem set solutions (not posted separately), and additional worked practice problems.

Most of the content was posted individually in the following locations, but those original documents will not be maintained individually any further.