Writing a finite sum as an optimization problem in Matlab

Question

I have the following problem: I have IID $(x_t,y_t)$ variables, where $t=1,…,N$.

I also have a 2-variable $K(x,y)$ function which returns a number between the depending on $x$ and $y$.

If I take the following example, where $x_1=1, x_2=2, x_3=3, y_1=0, y_2=4, y_3=2$, I want to write up the following optimization problem in Matlab:

$$\min_{\theta=[\theta_1,\theta_2,\theta_3]} \max_{t=1,2,3} |y_t-(\theta_1 K(x_t,x_1)+\theta_2K(x_t,x_2)+\theta_3K(x_t,x_3))|$$

Also: how could I write the code in the general case, where $(x_t,y_t)$ have like 100-100 variables without typing all the 100 elements of the sum?

I am familiar with the CVX package and here is what I tried so far:

X = [ 0 1 2 ];

Y = [ 1 4 2 ]; cvx_begin;

variable theta(3);

minimize(norm(Y – [K(X,X(1)+K(X,X(2)+K(X,X(3)]*theta,inf));

cvx_end;

I am probably doing something really wrong with the summation, can anyone help me out?

Thanks in advance!

Answer 1

Populate an N by N array, K, in MATLAB, whose i,j th element is $K(x_i,x_j)$, using a double for loop over i and j if the evaluator for K is not vectorized.

To make things simpler, I will use Y', i.e., a column vector. Note that variable theta(n) in CVX declares a column vector variable.

Y' - K*theta is then the n by 1 vector of which you wish to evaluate the infinity norm. So the following will do it.

cvx_begin
variable theta(n)
minimize(norm(Y' - K*theta,inf))
cvx_end