LLVM IR Null pointer constants and function pointers. A wild goose chase after a bad assumption.

March 30, 2017 clang/llvm No comments , , , , , ,

With ELLCC, you can easily check out the LLVM IR for code like:

typedef void ( *f )( void );
void foo( void );

f bar() {
    return (f)foo;

That code is:

define nonnull void ()* @bar() local_unnamed_addr {
  ret void ()* @foo

declare void @foo()

I was trying to use @foo in a “struct” object, and was getting an error attempting this:

 llvm::CompositeType*, llvm::Value::ValueTy, llvm::ArrayRef<llvm::Constant*>):
 Assertion `V[I]->getType() == T->getTypeAtIndex(I) &&
 "Initializer for composite element doesn't match!"' failed.

After adding:


where it shows the whole function body of foo(), I thought that’s where the error was coming from, and that I needed some other method to obtain just “@foo”, a global variable reference to the function, and not the function body itself.

The actual story is much simpler. Here the LLVM code to generate the IR for a foo() with this interface:

// void foo(){ }
auto vt = m_builder.getVoidTy();
auto voidFuncVoidType = FunctionType::get( vt, false /* varargs */ );

Function *fooFunc = Function::Create(
    voidFuncVoidType, Function::InternalLinkage, "foo",
    m_module );
BasicBlock *fooBB =
    BasicBlock::Create( m_context, "", fooFunc );
m_builder.SetInsertPoint( fooBB );

My clue that the error is something else is that I am able to build a function that returns a foo function pointer:

// void(*)() bar() { return foo ; }
auto fpRetFuncType = FunctionType::get( voidFuncVoidType->getPointerTo(), false /* varargs */ );

Function *barFunc = Function::Create(
    fpRetFuncType, Function::ExternalLinkage, "bar",
    m_module );
BasicBlock *barBB =
    BasicBlock::Create( m_context, "", barFunc );
m_builder.SetInsertPoint( barBB );
m_builder.CreateRet( fooFunc );

The module at this point looks like:

define internal void @foo() {
   ret void

define void ()* @bar() {
   ret void ()* @foo

So why can I used fooFunc in a return statement, but don’t appear to be able to use it in a structure object? Here’s the code that created that structure type

// struct { int, void (*)(), char * }
auto i8t = m_builder.getInt8Ty();
auto i32t = m_builder.getInt32Ty();
std::vector<Type *> consStructMembers{
    i32t, voidFuncVoidType->getPointerTo(), i8t->getPointerTo()};
auto consStructType =
    StructType::create( m_context, consStructMembers, "" );

and my attempt to populate an object of this type:

// %struct { int, void (*)(), char * } = { 65535, foo, null };
auto consPriority = ConstantInt::get( i32t, 65535 );
auto consDataZero = ConstantInt::get( i8t->getPointerTo(), 0 );

std::vector<Constant *> v{consPriority, fooFunc, consDataZero};
Constant *g = ConstantStruct::get( consStructType, v );

The actual error was in the third struct member initialization, and had nothing to do with the function pointer value. In retrospect, this makes sense since llvm::Function is derived from llvm::Constant, so there shouldn’t logically be a mismatch there.

What actually fixed the error was simply:

auto consDataZero = ConstantPointerNull::get( i8t->getPointerTo() );

It appears that the numeric zero value isn’t the same thing as an LLVM ‘null’. With that corrected, my variable declaration is:

%"type 0x10ea0c0" { i32 65535, void ()* @foo, i8* null }

… so I should now be able to proceed with the actual task at hand.

COBOL code! Where’s the eyewash station?

March 20, 2017 Mainframe No comments , , , , , , ,

In code that I am writing for work, I’m calling into COBOL code from C, and in order to setup the parameters and interpret the results, I have to know a little bit about how variables are declared in COBOL. I got an explanation of a little bit of COBOL syntax today that takes some of the mystery away.

Here’s the equivalent of something like a declaration of compile time constant variables in COBOL, a hierarchical beast something akin to a structure:

004500 01  CONSTANT-VALUES.                                             ORIG_SRC
004600     02  AN-CONSTANT PIC X(5) VALUE "IC104".                      ORIG_SRC
004700     02  NUM-CONSTANT PIC 99V9999 VALUE 0.7654.                   ORIG_SRC

This is roughly the equivalent of the following pseudo-c++11:

   char AN_CONSTANT[5]{'I','C','1','0','4'};
   struct {
      char digits1[2]{'0', '0'};
      char decimalpoint{ '.' };
      char digits2[4]{'7', '6', '5', '4'};
} ;

Some points:

  • The first 6 characters are source sequence numbers.  They aren’t line numbers like in BASIC (ie. you wouldn’t do a ‘goto 004500’), but were related to punch cards to make sure that out of sequence cards weren’t inserted into the card reader, or a card wasn’t fed into the reader by the operator by accident.
  • The ‘ORIG_SRC’ stuff in column 73+ are ignored.  These columns are also related to punch cards, as an additional card sequence number could be encoded in those locations.
  • The 01 indicates the first level of the ‘structure’.
  • The 02 means a second level.  I don’t know if the indenting of the 01, 02 is significant, but I suspect not.
  • PIC or PICTURE basically means the structure line is a variable and not the name of a new level.
  • A sequence of 9’s means that the variable takes numeric digits in those locations, whereas the V means that location is a period.
  • A sequence of X’s (or the X(5) here that means XXXXX), means that those characters can be alphanumeric.
  • There is no reference to ‘CONSTANT-VALUES’ when the variables are referenced.  That is like a namespace of some sort.
  • The level indicators 01, 02 are arbitrary, but have to be less than 77 (why that magic number? … who knows).  For example 05, 10 could have been used, so that another level could have been inserted in between without renumbering things.

The 01, 02 level indicators are also used for global variable declarations, also somewhat struct like:

004900 01  GRP-01.                                                      ORIG_SRC
005000     02  AN-FIELD PICTURE X(5).                                   ORIG_SRC
005100     02  NUM-DISPLAY PIC 99.                                      ORIG_SRC
005200     02  GRP-LEVEL.                                               ORIG_SRC
005300         03  A-FIELD PICTURE A(3).                                ORIG_SRC

This might be considered equivalent to:

   char AN_FIELD[5];
   char NUM_DISPLAY[2];
   struct {
      char A_FIELD[3];
} GRP_01;


  • A(3), equivalent to AAA, means the field can have ASCII values.
  • The name ‘GRP-LEVEL’ header for the 03 structure level is not referenced in the code.

It is also possible to declare a variable as binary, like so:

005400 77  ELEM-01 PIC  V9(4) COMPUTATIONAL.                            ORIG_SRC
  • Here 77 is a special magic level number, that really means what follows is a variable and not a “structure”.
  • The V here means an implied decimal place in the interpretation of the value.
  • The 9(4), equivalent to 9999, means the variable must be able to hold 4 numeric digits.
  • The COMPUTATIONAL means the underlying variable must be able to hold a value as big as 9999.  i.e. a short or unsigned short must be used, and not a char or unsigned char.

The final variable group in the code I was looking at was:

005500 01  GRP-02.                                                      ORIG_SRC
005600     02  GRP-03.                                                  ORIG_SRC
005700         03  NUM-ITEM PICTURE S99.                                ORIG_SRC
005800         03  EDITED-FIELD  PIC XXBX0X.                            ORIG_SRC

which is roughly equivalent to:

   struct {
      char NUM_ITEM[2];
         char digits1[2];
         char blank1[1]{' '};
         char digits2[1];
         char zero1[1]{'0'};
         char digits3[1];
   } GRP_03;
} GRP_02;         


  • EDITED-FIELD includes fixed blank and zero markers (B, 0 respectively).  When a four character variable is copied into this field, only the characters in the non-blank and non-zero values are touched.
  • NUM-ITEM is a signed numeric value.  It’s representation is strange:

The signed representation is also char based, and uses what is referred to as an “over-punch” to encode the sign.  The normal (EBCDIC) encoding of a two digit variable 42 without a sign, would be:

‘4’, ‘2’ == 0xF4, 0xF2

when the S modifier is used in the PICTURE declaration, the F in the EDCDIC encoding range is changed to either C or D for unsigned and signed respectively.  That means the ‘4’, ‘2’ is encoded as:

0xF4, 0xC2

whereas the signed value “-42” is encoded as:

0xF4, 0xD2

The procedure prototype, specifically, what the parameters to the function are, are given in a ‘PROCEDURE DIVISION’ block, like so:



  • The first 6 characters are still just punch card junk.
  • Three variables are passed to and from the function: GRP-01, ELEM-01, GRP-02.  These are, respectively, 10, 4, and 8 bytes respectively.
  • On the mainframe the COBOL function could be called with R1 something like:
struct parms {
    void * pointers[3];
    char ten[10];
    uint16_t h;
    char eight[8];

struct parms p;

p.pointers[0] = &p.ten[0];
p.pointers[1] = &p.h;
p.pointers[2] = &p.eight | 0x80000000;

strncpy( p.ten, "XXXXX00ZZZ", 10 );
p.h = 0;
strncpy( p.eight, "99XXBX0X" );

setregister( R1, &p );

The 0x80000000 is the mainframe “31-bit” way of indicating the end of list. It relies on the fact that virtual memory addresses in 32-bit z/OS processes have only 31-bits of addressable space available, so you can hack one extra bit into a pointer to indicate end of list of pointers.

Suppose the program has statements like the following to populate its output fields

006500 ADD 25 TO NUM-DISPLAY. 
006600 MOVE "YES" TO A-FIELD. 

The results of this are roughly:

strncpy( p.ten, "IC104", 5 ); // MOVE AN-CONSTANT TO AN-FIELD (GRP-01)
strcpy( p.ten + 5, "25", 2 ); // ADD 25 TO NUM-DISPLAY (GRP-01): since the initial value was "00"
strncpy( p.ten + 7, "YES", 3 ); // MOVE "YES" TO A-FIELD. 
p.h = 7654 // MOVE NUM-CONSTANT TO ELEM-01. 
strcpy( p.eight, "25", 2 ); // MOVE NUM-DISPLAY TO NUM-ITEM. 
strncpy( p.eight + 2, "AB C0D", 6 ); // MOVE "ABCD" TO EDITED-FIELD. 

It appears that the the assignment of NUM-CONSTANT, a number of the form 99.9999 to the numeric value ELEM-01 which is of the form .9999, just truncates any whole portion of the number.

Notes compilation for ECE1505, Convex Optimization

March 18, 2017 ece1505 No comments

I’ve now posted a notes compilation for the subset of the Convex Optimization (ECE1505H) course I was taking in the winter 2017 session.

This course was taught by Prof. S. Draper.

These convex optimization notes are incomplet, covering only the first 9 lectures. The unredacted notes include my solution to problem set 1 (149 pages, vs. 131 pages).

I initially enrolled on this optimization course because I needed a specific quota of ECE courses to satisfy the M.Eng graduation requirements, and the electromagnetics group wasn’t offering enough courses.  I remembered liking linear programming in high school, and always wanted to understand the rational for some of the assumptions that was based on that were never proven in class.  Specifically, I recall that it was stated, but not proved in that high school class, that the extreme values were always found at the vertices of the optimization region.  So, my thought was, I’ll have fun learning the basis for those assumptions, and also learn about optimization theory in general.

It turns out that optimization theory, at least as presented in this course, is very very dry.  It was an endless seeming sequence of definition and proof, with the end goal so far away that it was very difficult to see the big picture.  I worked through the a number of weeks of this particular course before I had enough and bailed.  Work is too fun right now to torture myself and spend the time on an academic course that I am not enjoying, so I dropped it and am back to full time work at LzLabs (from 80%) until the next session at UofT starts again.

The reason I enrolled on the M.Eng in the first place was to study material that I was interested in.  Ideally I would have done that in a part time physics grad context, but that was not available, so I found that the M.Eng allowed me to take an interesting (but constrained) mix of physics and engineering electromagnetism courses.  However, when I enrolled, the electromagnetism course selection was a lot better, and now unfortunately it is sparse and includes only courses that I’d already taken.  I don’t want the M.Eng degree paper badly enough to torture myself with a course that I’m not actually interested in.

I now actually have a plan to satisfy both the degree requirements and my interests (using a project “course”).  That will involve independent study on Geometric Algebra applications to engineering electromagnetism.  I am irked that I have to pay a part time engineering program fee next year to self study, but it does seem worthwhile to come out of the M.Eng study with an actual degree as a side effect, so I am going to go ahead and do it anyways.

gdb pretty print of structures

March 9, 2017 C/C++ development and debugging. No comments , , , ,

Here’s a nice little gdb trick for displaying structure contents in a less compact format

(gdb) set print pretty on
(gdb) p dd[0]
$4 = {
  jfcb = {
    datasetName = "PJOOT.NVS1", ' ' <repeats 34 times>,
    vols = {"<AAAiW", "\000\000\000\000\000", "\000\000\000\000\000", "\000\000\000\000\000", "\000\000\000\000\000"},
  block_size = 800,
  device_class = 32 '\040',
  device_type = 15 '\017',
  disp_normal = 8 '\010',
  disp_cond = 8 '\010',
  volsers = 0x7fb71801ecd6 "<AAAiW",

compare this to the dense default

(gdb) set print pretty on
(gdb) p dd[0]
$5 = {jfcb = {datasetName = "PJOOT.NVS1", ... vols = {"<AAAiW", "\000\000\000\000\000", "\000\000\000\000\000", "\000\000\000\000\000", "\000\000\000\000\000"}, block_size = 800, block_size_limit = 0, device_class = 32 '\040', device_type = 15 '\017', disp_normal = 8 '\010', disp_cond = 8 '\010', volsers = 0x7fb71801ecd6 "<AAAiW"}

For really big structures (this one actually is, but I’ve pruned a bunch of stuff), this makes the structure print display a whole lot more readable. Additionally, if you combine this with ‘(gdb) set logging on’, then with pretty print enabled you can prune the output by line easily to see just what you want.

A really dumb DNS lookup for my internal network

March 8, 2017 perl and general scripting hackery No comments , , , , ,

The new Hitron cable modem in the house cowardly refuses to let me cache mac and ip address pairs, which is really annoying because my ip addresses now change on me over a couple days. The old router (also a Hitron) allowed that, so putting it on a UPS was generally enough to let me have a static IP table, provided I didn’t have to reboot it.

Here’s a hack using nmap that I just cobbled together to fill in the /etc/hosts entries on the couple machines that I want to talk to each other (mac and Linux machines, so all are unix like).

my %hostnameByMacAddr = (
'B8:4E:3F:C4:04:02' => 'router',
'E4:5C:89:C2:0F:4B' => 'macbookw # wireless',
'10:C2:C6:A0:20:58' => 'nuc2w',
'10:C2:C6:CA:93:6A' => 'nuc1w',
'A8:AE:ED:EB:39:86' => 'nuc1',
'A8:AE:ED:7D:CE:5A' => 'nuc2',
'28:C9:86:46:A8:15' => 'macbookt # thunderbolt monitor connected',
'10:24:2B:A1:7B:F7' => 'brother # printer',
'BC:87:A3:34:1A:FF' => 'macbooke # ethernet cable connected',

open my $h, "sudo nmap -n -p 22 2>&1 | grep -e '192' -e '^MAC' |" or die;

my $ip;
while ( <$h> )
   if ( /scan report for.*(192\.\d+\.\d+\.\d+)/ )
      $ip = $1 ;

   if ( /MAC Address: (.*) / ) {
      my $mac = $1;

      if ( defined $hostnameByMacAddr{$mac} ) {
         print "$ip $hostnameByMacAddr{$mac} # $mac\n" ;
      else {
         print "# $ip $mac # unknown\n" ;

close $h or die;

If anybody knows how to set up an actual DNS server for internal networks, I’d be interested to see what is involved, since it looked very hard when I googled it.

VSAM creation and population with JCL and IDCAMS

March 7, 2017 Mainframe No comments , , , , , , , ,

I learned a few JCL DATASET related things yesterday that seemed notable, at least for a JCL newbie.

Delete a DATASET, and ignore any error.

Each time I’ve wanted a DATASET cleanup step in JCL I’ve been using a separate script, and running that first.  A better way of doing this is to include a IDCAMS job step in the script, and have that do the deletion


This deletes the file PJOOT.XXXXX005, which in this case was a VSAM file. In case that file (a DATASETs in mainframe-eze) did not exist, the error code for that DELETE is ignored by setting MAXCC=0. If you have multiple things that you want to do with IDCAMS, you can do things like DELETE and then ALLOCATE immediately, such as

               CYLINDERS(1) VOLUMES(LZ0000) -
               INDEXED -
               KEYS(4 0) -
               RECORDSIZE(240 240) -
               ) -

This does the DELETE, ignores any error, and then proceeds to do the new ALLOCATE for the VSAM file. I haven’t seen any way described of ALLOCATING a VSAM file other than using IDCAMS, except in 3270 screens. I think I’ve seen that LzLabs has 3270 capabilities for this sort of stuff, but I’m not inclined to try to figure out how to use it. I’d rather use our much more intuitive GUI or do it in script with JCL like this.


Here is some JCL to copy an (INLINE) dataset into the VSAM file created above


There are two quirks that are noteworthy here.

  1. The VSAM file requires the input be sorted, which is why the words from ‘a quick brown fox’ are in the explicitly sorted order above.
  2. The VSAM file was created with RECORDSIZE 240, so the input file had to be forced to LRECL=240 to match.

Omission of either sort or the LRECL matching causes the VSAM load to fail.

This was the first time that I’d seen this specific INLINE DD syntax, with explicit parameters.  The way I’d seen it before was how SYSIN was specified above with ‘NAME DD *’, ending with C “comment start” /* sequence.  It turns out the default end of file delimiter can also be specified, for example, this also works:


Cat a file to spool

Because IDCAMS can copy files, this can also be used to cat a file to SPOOL if desired.  Here’s an example:


If I include a step like this, I’m able to see the file contents in our nice GUI spool browser along with the JCL script and all the other output.

peeking into relocation of function static in shared library

February 27, 2017 C/C++ development and debugging. 2 comments , , , , , , , ,

Here’s GUI (TUI) output of a function with a static variable access:

B+ |0x7ffff7616800 <st32>           test   %edi,%edi                                                                                                                     |
   |0x7ffff7616802 <st32+2>         je     0x7ffff7616811 <st32+17>                                                                                                      |
   |0x7ffff7616804 <st32+4>         mov    %edi,%eax                                                                                                                     |
   |0x7ffff7616806 <st32+6>         bswap  %eax                                                                                                                          |
   |0x7ffff7616808 <st32+8>         mov    %eax,0x200852(%rip)        # 0x7ffff7817060 <st32.yst32>                                                                        |
   |0x7ffff761680e <st32+14>        mov    %edi,%eax                                                                                                                     |
   |0x7ffff7616810 <st32+16>        retq                                                                                                                                 |
  >|0x7ffff7616811 <st32+17>        mov    0x200849(%rip),%edi        # 0x7ffff7817060 <st32.yst32>                                                                        |
   |0x7ffff7616817 <st32+23>        bswap  %edi                                                                                                                          |
   |0x7ffff7616819 <st32+25>        mov    %edi,%eax                                                                                                                     |
   |0x7ffff761681b <st32+27>        retq                                                                                                                                 |
   |0x7ffff761681c <_fini>          sub    $0x8,%rsp                                                                                                                     |
   |0x7ffff7616820 <_fini+4>        add    $0x8,%rsp                                                                                                                     |
   |0x7ffff7616824 <_fini+8>        retq                                                                                                                                 |
   |0x7ffff7616825                  add    %al,(%rcx)                                                                                                                    |
   |0x7ffff7616827 <x16+1>          add    (%rcx),%al                                                                                                                    |

The associated code is:

int st32( int v ) {
    static int yst32 = 0x1a2b3c4d;

    if ( v ) {
        yst32 = v;

    return yst32;

The object code dump (prior to relocation) just has zeros in the offset for the variable:

$ objdump -d g.bs.o | grep -A12 '<st32>'
0000000000000050 <st32>:
  50:   85 ff                   test   %edi,%edi
  52:   74 0d                   je     61 <st32+0x11>
  54:   89 f8                   mov    %edi,%eax
  56:   0f c8                   bswap  %eax
  58:   89 05 00 00 00 00       mov    %eax,0x0(%rip)        # 5e <st32+0xe>
  5e:   89 f8                   mov    %edi,%eax
  60:   c3                      retq   
  61:   8b 3d 00 00 00 00       mov    0x0(%rip),%edi        # 67 <st32+0x17>
  67:   0f cf                   bswap  %edi
  69:   89 f8                   mov    %edi,%eax
  6b:   c3                      retq   

The linker has filled in the real offsets in question, and the dynamic loader has collaborated to put the data segment in the desired location.

The observant reader may notice bwsap instructions in the listings above that don’t make sense for x86_64 code. That is because this code is compiled with an LLVM pass that performs byte swapping at load and store points, making it big endian in a limited fashion.

The book Linkers and Loaders has some nice explanation of how relocation works, but I wanted to see the end result first hand in the debugger. It turned out that my naive expectation that the sum of $rip and the constant relocation factor is the address of the global variable (actually static in this case) is incorrect. Check that out in the debugger:

(gdb) p /x 0x200849+$rip
$1 = 0x7ffff781705a

(gdb) x/10 $1
0x7ffff781705a <gy+26>: 0x22110000      0x2b1a4433      0x00004d3c      0x00000000
0x7ffff781706a: 0x00000000      0x00000000      0x00000000      0x30350000
0x7ffff781707a: 0x20333236      0x64655228

My magic value 0x1a2b3c4d looks like it is 6 bytes into the $rip + 0x200849 location that the disassembly appears to point to, and that is in fact the case:

(gdb) x/10 $1+6
0x7ffff7817060 <st32.yst32>:      0x4d3c2b1a      0x00000000      0x00000000      0x00000000
0x7ffff7817070 <y32>:   0x00000000      0x00000000      0x32363035      0x52282033
0x7ffff7817080: 0x48206465      0x34207461

My guess was the mysterious offset of 6 required to actually find this global address was the number of bytes in the MOV instruction, and sure enough that MOV is 6 bytes long:

(gdb) disassemble /r
Dump of assembler code for function st32:
   0x00007ffff7616800 <+0>:     85 ff   test   %edi,%edi
   0x00007ffff7616802 <+2>:     74 0d   je     0x7ffff7616811 <st32+17>
   0x00007ffff7616804 <+4>:     89 f8   mov    %edi,%eax
   0x00007ffff7616806 <+6>:     0f c8   bswap  %eax
   0x00007ffff7616808 <+8>:     89 05 52 08 20 00       mov    %eax,0x200852(%rip)        # 0x7ffff7817060 <st32.yst32>
   0x00007ffff761680e <+14>:    89 f8   mov    %edi,%eax
   0x00007ffff7616810 <+16>:    c3      retq
=> 0x00007ffff7616811 <+17>:    8b 3d 49 08 20 00       mov    0x200849(%rip),%edi        # 0x7ffff7817060 <st32.yst32>
   0x00007ffff7616817 <+23>:    0f cf   bswap  %edi
   0x00007ffff7616819 <+25>:    89 f8   mov    %edi,%eax
   0x00007ffff761681b <+27>:    c3      retq
End of assembler dump.

So, it appears that the %rip reference in the disassembly is really the value of the instruction pointer after the instruction executes, which is curious.

Note that this 4 byte relocation requires the shared library code segment and the shared library data segment be separated by no more than 4G. The linux dynamic loader has put all the segments back to back so that this is the case. This can be seen from /proc/PID/maps for the process:

$ ps -ef | grep maindl
pjoot    17622 17582  0 10:50 pts/3    00:00:00 /home/pjoot/workspace/pass/global/maindl libglobtestbs.so

$ grep libglob /proc/17622/maps
7ffff7616000-7ffff7617000 r-xp 00000000 fc:00 2492653                    /home/pjoot/workspace/pass/global/libglobtestbs.so
7ffff7617000-7ffff7816000 ---p 00001000 fc:00 2492653                    /home/pjoot/workspace/pass/global/libglobtestbs.so
7ffff7816000-7ffff7817000 r--p 00000000 fc:00 2492653                    /home/pjoot/workspace/pass/global/libglobtestbs.so
7ffff7817000-7ffff7818000 rw-p 00001000 fc:00 2492653                    /home/pjoot/workspace/pass/global/libglobtestbs.so

We’ve got a read-execute mmap region, where the code lies, and a read-write mmap region for the data. There’s a read-only segment which I presume is for read only global variables (my shared lib has one such variable and we have one page worth of space allocated for read only memory).

I wonder what the segment that has none of the read, write, nor execute permissions set is?

New book for work: Linkers and Loaders

February 24, 2017 C/C++ development and debugging. No comments , ,

Fresh off the press:

I got this book to get some background on relocation of ELF globals, and was surprised to find a bit on z/OS (punch card compatible!) object format layout:

… an interesting bonus that’s topical.

Omelets, a nice perk of working from home.

February 9, 2017 Food No comments , , ,

Today’s lunch was a three egg avocado, onion, red pepper, mushroom, cheese omelet, made with free range eggs from a little local Markham farm (16th just past York Durham line) .  I should have included a picture of the eggs before I cracked them, since two of them were an awesome blue, which the farm owner said is due to the Brazilian breed.

Prep included using Sofia’s awesome trick of separating the eggs, and pre-whipping the whites before a final recombination:

and the final delicious result:

I realize now that I forgot to add milk this time, which I’ve done in the past, but it all still worked out well.  I guess the milk is not really required.  As I tend to do with tortillas, I overstuffed this, and now I’m also overstuffed.

ECE1505H Convex Optimization. Lecture 8: Local vs. Global, and composition of functions. Taught by Prof. Stark Draper

February 4, 2017 ece1505 No comments , , , ,

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


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].


  • Finish local vs global.
  • Compositions of functions.
  • Introduction to convex optimization problems.

Continuing proof:

We want to prove that if

\spacegrad F(\Bx^\conj) &= 0 \\
\spacegrad^2 F(\Bx^\conj) \ge 0

then \( \Bx^\conj\) is a local optimum.


Again, using Taylor approximation

F(\Bx^\conj + \Bv) = F(\Bx^\conj) + \lr{ \spacegrad F(\Bx^\conj)}^\T \Bv + \inv{2} \Bv^\T \spacegrad^2 F(\Bx^\conj) \Bv + o(\Norm{\Bv}^2)

The linear term is zero by assumption, whereas the Hessian term is given as \( > 0 \). Any direction that you move in, if your move is small enough, this is going uphill at a local optimum.


For twice continuously differentiable functions, at a local optimum \( \Bx^\conj \), then

\spacegrad F(\Bx^\conj) &= 0 \\
\spacegrad^2 F(\Bx^\conj) \ge 0

If, in addition, \( F \) is convex, then \( \spacegrad F(\Bx^\conj) = 0 \) implies that \( \Bx^\conj \) is a global optimum. i.e. for (unconstrained) convex functions, local and global optimums are equivalent.

  • It is possible that a convex function does not have a global optimum. Examples are \( F(x) = e^x \)
    (fig. 1)
    , which has an \( \inf \), but no lowest point.

    fig. 1. Exponential has no global optimum.

  • Our discussion has been for unconstrained functions. For constrained problems (next topic) is not not necessarily true that \( \spacegrad F(\Bx) = 0 \) implies that \( \Bx \) is a global optimum, even for \( F \) convex.

    As an example of a constrained problem consider

    \min &2 x^2 + y^2 \\
    x &\ge 3 \\
    y &\ge 5.

    The level sets of this objective function are plotted in fig. 2. The optimal point is at \( \Bx^\conj = (3,5) \), where \( \spacegrad F \ne 0 \).

    fig. 2. Constrained problem with optimum not at the zero gradient point.


Given \( \Bx \in \mathbb{R}^n, \By \in \mathbb{R}^p \), if \( h(\Bx,\By) \) is convex in \( \Bx, \By \), then

F(\Bx_0) = \inf_\By h(\Bx_0,\By)

is convex in \( \Bx\), as sketched in fig. 3.

fig. 3. Epigraph of \( h \) is a filled bowl.

The intuition here is that shining light on the (filled) “bowl”. That is, the image of \( \textrm{epi} h \) on the \( \By = 0 \) screen which we will show is a convex set.


Since \( h \) is convex in \( \begin{bmatrix} \Bx \\ \By \end{bmatrix} \in \textrm{dom} h \), then

\textrm{epi} h = \setlr{ (\Bx,\By,t) | t \ge h(\Bx,\By), \begin{bmatrix} \Bx \\ \By \end{bmatrix} \in \textrm{dom} h },

is a convex set.

We also have to show that the domain of \( F \) is a convex set. To show this note that

\textrm{dom} F
&= \setlr{ \Bx | \exists \By s.t. \begin{bmatrix} \Bx \\ \By \end{bmatrix} \in \textrm{dom} h } \\
&= \setlr{
I_{n\times n} & 0_{n \times p}
\Bx \\
| \begin{bmatrix} \Bx \\ \By \end{bmatrix} \in \textrm{dom} h

This is an affine map of a convex set. Therefore \( \textrm{dom} F \) is a convex set.

\textrm{epi} F
\setlr{ \begin{bmatrix} \Bx \\ \By \end{bmatrix} | t \ge \inf h(\Bx,\By), \Bx \in \textrm{dom} F, \By: \begin{bmatrix} \Bx \\ \By \end{bmatrix} \in \textrm{dom} h } \\
I & 0 & 0 \\
0 & 0 & 1
\Bx \\
\By \\
t \ge h(\Bx,\By), \begin{bmatrix} \Bx \\ \By \end{bmatrix} \in \textrm{dom} h


The function

F(\Bx) = \inf_{\By \in C} \Norm{ \Bx – \By },

over \( \Bx \in \mathbb{R}^n, \By \in C \), ,is convex if \( C \) is a convex set. Reason:

  • \( \Bx – \By \) is linear in \((\Bx, \By)\).
  • \( \Norm{ \Bx – \By } \) is a convex function if the domain is a convex set
  • The domain is \( \mathbb{R}^n \times C \). This will be a convex set if \( C \) is.
  • \( h(\Bx, \By) = \Norm{\Bx -\By} \) is a convex function if \( \textrm{dom} h \) is a convex set. By setting \( \textrm{dom} h = \mathbb{R}^n \times C \), if \( C \) is convex, \( \textrm{dom} h \) is a convex set.
  • \( F() \)

Composition of functions


F(\Bx) &= h(g(\Bx)) \\
\textrm{dom} F &= \setlr{ \Bx \in \textrm{dom} g | g(\Bx) \in \textrm{dom} h } \\
F &: \mathbb{R}^n \rightarrow \mathbb{R} \\
g &: \mathbb{R}^n \rightarrow \mathbb{R} \\
h &: \mathbb{R} \rightarrow \mathbb{R}.


  1. \( g \) is convex, \( h \) is convex and non-decreasing.
  2. \( g \) is convex, \( h \) is convex and non-increasing.

Show for 1D case ( \( n = 1 \)). Get to \( n > 1 \) by applying to all lines.

  1. \begin{equation}\label{eqn:convexOptimizationLecture8:180}
    F'(x) &= h'(g(x)) g'(x) \\
    F”(x) &=
    h”(g(x)) g'(x) g'(x)
    h'(g(x)) g”(x) \\
    h”(g(x)) (g'(x))^2
    h'(g(x)) g”(x) \\
    \lr{ \ge 0 } \cdot \lr{ \ge 0 }^2 + \lr{ \ge 0 } \cdot \lr{ \ge 0 },

    since \( h \) is respectively convex, and non-decreasing.

  2. \begin{equation}\label{eqn:convexOptimizationLecture8:180b}
    F'(x) =
    \lr{ \ge 0 } \cdot \lr{ \ge 0 }^2 + \lr{ \le 0 } \cdot \lr{ \le 0 },

    since \( h \) is respectively convex, and non-increasing, and g is concave.

Extending to multiple dimensions

&= h(g(\Bx)) = h( g_1(\Bx), g_2(\Bx), \cdots g_k(\Bx) ) \\
g &: \mathbb{R}^n \rightarrow \mathbb{R} \\
h &: \mathbb{R}^k \rightarrow \mathbb{R}.

is convex if \( g_i \) is convex for each \( i \in [1,k] \) and \( h \) is convex and non-decreasing in each argument.


again assume \( n = 1 \), without loss of generality,

g &: \mathbb{R} \rightarrow \mathbb{R}^k \\
h &: \mathbb{R}^k \rightarrow \mathbb{R} \\

g_1(\Bx) & g_2(\Bx) & \cdots & g_k(\Bx)
\spacegrad^2 h(g(\Bx))
g_1′(\Bx) \\ g_2′(\Bx) \\ \vdots \\ g_k'(\Bx)
\lr{ \spacegrad h(g(x)) }^\T
g_1”(\Bx) \\ g_2”(\Bx) \\ \vdots \\ g_k”(\Bx)

The Hessian is PSD.


F(x) = \exp( g(x) ) = h( g(x) ),

where \( g \) is convex is convex, and \( h(y) = e^y \). This implies that \( F \) is a convex function.


F(x) = \inv{g(x)},

is convex if \( g(x) \) is concave and positive. The most simple such example of such a function is \( h(x) = 1/x, \textrm{dom} h = \mathbb{R}_{++} \), which is plotted in fig. 4.

fig. 4. Inverse function is convex over positive domain.


F(x) = – \sum_{i = 1}^n \log( -F_i(x) )

is convex on \( \setlr{ x | F_i(x) < 0 \forall i } \) if all \( F_i \) are convex.

  • Due to \( \textrm{dom} F \), \( -F_i(x) > 0 \,\forall x \in \textrm{dom} F \)
  • \( \log(x) \) concave on \( \mathbb{R}_{++} \) so \( -\log \) convex also non-increasing (fig. 5).

    fig. 5. Negative logarithm convex over positive domain.

F(x) = \sum h_i(x)

h_i(x) = -\log(-F_i(x)),

which is a convex and non-increasing function (\(-\log\)), of a convex function \( -F_i(x) \). Each
\( h_i \) is convex, so this is a sum of convex functions, and is therefore convex.


Over \( \textrm{dom} F = S^n_{++} \)

F(X) = \log \det X^{-1}

To show that this is convex, check all lines in domain. A line in \( S^n_{++} \) is a 1D family of matrices

\tilde{F}(t) = \log \det( \lr{X_0 + t H}^{-1} ),

where \( X_0 \in S^n_{++}, t \in \mathbb{R}, H \in S^n \).


For \( t \) small enough,

X_0 + t H \in S^n_{++}

&= \log \det( \lr{X_0 + t H}^{-1} ) \\
&= \log \det\lr{ X_0^{-1/2} \lr{I + t X_0^{-1/2} H X_0^{-1/2} }^{-1} X_0^{-1/2} } \\
&= \log \det\lr{ X_0^{-1} \lr{I + t X_0^{-1/2} H X_0^{-1/2} }^{-1} } \\
&= \log \det X_0^{-1} + \log\det \lr{I + t X_0^{-1/2} H X_0^{-1/2} }^{-1} \\
&= \log \det X_0^{-1} – \log\det \lr{I + t X_0^{-1/2} H X_0^{-1/2} } \\
&= \log \det X_0^{-1} – \log\det \lr{I + t M }.

If \( \lambda_i \) are eigenvalues of \( M \), then \( 1 + t \lambda_i \) are eigenvalues of \( I + t M \). i.e.:

(I + t M) \Bv
I \Bv + t \lambda_i \Bv \\
(1 + t \lambda_i) \Bv.

This gives

&= \log \det X_0^{-1} – \log \prod_{i = 1}^n (1 + t \lambda_i) \\
&= \log \det X_0^{-1} – \sum_{i = 1}^n \log (1 + t \lambda_i)

  • \( 1 + t \lambda_i \) is linear in \( t \).
  • \( -\log \) is convex in its argument.
  • sum of convex function is convex.


F(X) = \lambda_\max(X),

is convex on \( \textrm{dom} F \in S^n \)

\lambda_{\max} (X) = \sup_{\Norm{\Bv}_2 \le 1} \Bv^\T X \Bv,

\lambda_1 & & & \\
& \lambda_2 & & \\
& & \ddots & \\
& & & \lambda_n

Recall that a decomposition

X &= Q \Lambda Q^\T \\
Q^\T Q = Q Q^\T = I

can be used for any \( X \in S^n \).


Note that \( \Bv^\T X \Bv \) is linear in \( X \). This is a max of a number of linear (and convex) functions, so it is convex.

Last example:

(non-symmetric matrices)

F(X) = \sigma_\max(X),

is convex on \( \textrm{dom} F = \mathbb{R}^{m \times n} \). Here

\sigma_\max(X) = \sup_{\Norm{\Bv}_2 = 1} \Norm{X \Bv}_2

This is called an operator norm of \( X \). Using the SVD

X &= U sectionigma V^\T \\
U &= \mathbb{R}^{m \times r} \\
sectionigma &\in \mathrm{diag} \in \mathbb{R}{ r \times r } \\
V^T &\in \mathbb{R}^{r \times n}.


\Norm{X \Bv}_2^2
\Norm{ U sectionigma V^\T \Bv }_2^2
\Bv^\T V sectionigma U^\T U sectionigma V^\T \Bv
\Bv^\T V sectionigma sectionigma V^\T \Bv
\Bv^\T V sectionigma^2 V^\T \Bv
\tilde{\Bv}^\T sectionigma^2 \tilde{\Bv},

where \( \tilde{\Bv} = \Bv^\T V \), so

\Norm{X \Bv}_2^2
\sum_{i = 1}^r \sigma_i^2 \Norm{\tilde{\Bv}}
\le \sigma_\max^2 \Norm{\tilde{\Bv}}^2,

\Norm{X \Bv}_2
\le \sqrt{ \sigma_\max^2 } \Norm{\tilde{\Bv}}

Set \( \Bv \) to the right singular value of \( X \) to get equality.


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