1
Preface
2
Introduction
2.1
Some History
2.2
Optimization Methods
3
Block Relaxation
3.1
Introduction
3.2
Definition
3.3
First Examples
3.3.1
Two-block Least Squares
3.3.2
Multiple-block Least Squares
3.4
Generalized Block Relaxation
3.4.1
Rasch Model
3.4.2
Nonlinear Least Squares
3.5
Block Order
3.5.1
Projecting Blocks
3.6
Rate of Convergence
3.6.1
LU-form
3.6.2
Product Form
3.6.3
Block Optimization Methods
3.6.4
Block Newton Methods
3.6.5
Constrained Problems
3.7
Additional Examples
3.7.1
Canonical Correlation
3.7.2
Low Rank Approximation
3.7.3
Optimal Scaling with LINEALS
3.7.4
Multinormal Maximum Likelihood
3.7.5
Array Multinormals
3.7.6
Rasch Model
3.8
Some Counterexamples
3.8.1
Convergence to a Saddle
3.8.2
Convergence to Incorrect Solutions
3.8.3
Non-convergence and Cycling
3.8.4
Sublinear Convergence
4
Coordinate Descent
4.1
Introduction
4.2
Convergence rate
4.3
Examples
4.3.1
The Cartesian Folium
4.3.2
A Family of Quadratics
4.3.3
Loglinear Models
4.3.4
Rayleigh Quotient
4.3.5
Squared Distance Scaling
4.3.6
Least Squares Factor Analysis
5
Alternating Least Squares
5.1
Introduction
5.2
Close Relatives
5.2.1
ALSOS
5.2.2
ACE
5.2.3
NIPALS and PLS
5.3
Rate of Convergence
5.4
Examples
5.4.1
Homogeneity Analysis
5.4.2
Fixed Rank Approximation
5.4.3
Multilinear Fitting
5.4.4
MCR-ALS
5.4.5
Scaling and Splitting
6
Augmentation and Decomposition Methods
6.1
Introduction
6.2
Definition
6.3
Rate of Convergenc
6.4
Half-Quadratic Methods
6.5
Examples
6.5.1
Yates Augmentation
6.5.2
Optimal Scaling with ORDINALS
6.5.3
Least Squares Factor Analysis
6.5.4
Squared Distance Scaling
6.5.5
Linear Mixed Model
6.6
Decomposition Methods
6.6.1
Quadratic Form on a Sphere
6.6.2
Multidimensional Unfolding
7
Majorization Methods
7.1
Introduction
7.2
Definitions
7.2.1
Majorization at a Point
7.2.2
Majorization on a Set
7.2.3
Majorization Algorithm
7.2.4
Alternative Definitions
7.3
Relatives
7.3.1
The Concave-Convex Procedure
7.3.2
Generalized Weiszfeld Methods
7.3.3
The EM Algorithm
7.3.4
The Lower-Bound Principle
7.3.5
Dinkelbach Majorization
7.4
Further Results
7.4.1
Rate of Convergence
7.4.2
Univariate and Separable Functions
7.4.3
Differentiable Functions
7.4.4
Composition
7.4.5
Majorization Duality
7.4.6
Necessary Conditions by Majorization
7.4.7
Majorizing Constraints
7.4.8
Majorizing Value Functions
7.5
Some Examples
7.5.1
The Reciprocal
7.5.2
Cubics and Quartics
7.5.3
Normal PDF and CDF
7.5.4
Logistic PDF and CDF
8
Majorization Inequalities
8.1
Introduction
8.2
The AM/GM Inequality
8.2.1
Absolute Values
8.2.2
Absolute Values
8.2.3
Gini Mean Difference
8.2.4
Location Problems
8.2.5
The Lasso and the Bridge
8.3
Polar Norms and the Cauchy-Schwarz Inequality
8.3.1
Rayleigh Quotient
8.3.2
The Majorization Method for MDS
8.4
Conjugates and Young’s Inequality
8.4.1
Support Vector Machines
9
Using Convexity
9.1
Using Convexity
9.2
Jensen’s Inequality
9.2.1
Tomography
9.2.2
Logs of Sums and Integrals
9.3
The EM Algorithm
10
Tangential Majorization
10.1
Using the Tangent
10.1.1
Majorizing and Minorizing the Logarithm
10.1.2
Aspects of Correlation Matrices
10.1.3
Partially Observed Linear Systems
10.1.4
Gpower
10.2
Broadening the Scope
10.2.1
Differences of Convex Functions
10.2.2
Convexifiable Functions
10.2.3
Piecewise Linear Majorization
11
Quadratic Majorization
11.1
Introduction
11.2
Existence of Quadratic Majorizers
11.3
Convergence
11.4
Bounding Second Derivatives
11.4.1
Normal Density and Distribution
11.4.2
Nondiagonal Weights in Least Squares
11.4.3
Quadratic on a Sphere
11.4.4
Gifi Goes Logistic
11.4.5
A Matrix Example
11.4.6
Gauss-Newton Majorization
11.4.7
Marginal Functions
12
Using Higher Derivatives
12.1
Introduction
12.2
Mean Value Majorization
12.3
Taylor Majorization
12.3.1
Second Order
12.3.2
Higher Order
12.4
Nesterov Majorization
12.5
Examples
12.5.1
Revisiting the Reciprocal
12.5.2
Logit
12.5.3
Probit
13
Sharp Majorization
13.1
Introduction
13.2
Comparing Majorizations
13.3
Sharp Quadratic Majorization
13.3.1
Existence
13.3.2
Optimality with Two Support Points
13.3.3
Even and Odd Functions
13.4
Sharp Piecewise Linear
13.5
Examples
13.5.1
The cosine
13.5.2
The Rasch Model
13.5.3
Logits
13.5.4
Probits
14
Local and Localized Majorization
14.1
Introduction
14.1.1
Majorization in a Neighborhood
14.1.2
Cartesian Folium
14.1.3
Univariate Cubics
14.1.4
Majorization on the Sphere
14.1.5
Majorization on a Hyperrectangle
14.2
Proximal Point Majorization
14.3
Sub-level Majorization
14.4
Dinkelbach Majorization
15
Background
15.1
Introduction
15.2
Analysis
15.2.1
SemiContinuities
15.2.2
Directional Derivatives
15.2.3
Differentiability and Derivatives
15.2.4
Taylor’s Theorem
15.2.5
Implicit Functions
15.2.6
Necessary and Sufficient Conditions for a Minimum
15.3
Point-to-set Maps
15.3.1
Continuities
15.3.2
Marginal Functions and Solution Maps
15.3.3
Solution Maps
15.4
Basic Inequalities
15.4.1
Jensen’s Inequality
15.4.2
The AM-GM Inequality
15.4.3
Polar Norms and the Cauchy-Schwarz Inequality
15.4.4
Young’s Inequality
15.5
Fixed Point Problems and Methods
15.5.1
Subsequential Limits
15.6
Convex Functions
15.7
Composition
15.7.1
Differentiable Convex Functions
15.8
Zangwill Theory
15.8.1
Algorithms as Point-to-set Maps
15.8.2
Convergence of Function Values
15.8.3
Convergence of Solutions
15.9
Rates of Convergence
15.9.1
Over- and Under-Relaxation
15.9.2
Acceleration of Convergence of Fixed Point Methods
15.10
Matrix Algebra
15.10.1
Eigenvalues and Eigenvectors of Symmetric Matrices
15.10.2
Singular Values and Singular Vectors
15.10.3
Canonical Correlation
15.10.4
Eigenvalues and Eigenvectors of Asymmetric Matrices
15.10.5
Modified Eigenvalue Problems
15.10.6
Quadratic on a Sphere
15.10.7
Generalized Inverses
15.10.8
Partitioned Matrices
15.11
Matrix Differential Calculus
15.11.1
Matrix Derivatives
15.11.2
Derivatives of Eigenvalues and Eigenvectors
15.12
Graphics and Code
15.12.1
Multidimensional Scaling
15.12.2
Cobweb Plots
16
Code
17
NEWS
18
References
Block Relaxation Methods in Statistics
17
NEWS
001 03/10/16
First translation from gitbook
002 03/16/16
Now generates legal tex
crossrefs sorted out
003 03/17/16
bibtex file completed