4
$\begingroup$
  1. In a note:

    semi-definite programming is equivalent to vector programming.

    ...

    A Vector Program is a Linear Program over dot products.

  2. In Boyd's Convex Optimization, a vector optimization problem is defined to be optimizing a vector-valued function, where the vectors are ordered wrt a given cone.

I am not sure if the two definitions are equivalent and how they are related?

I am wondering what is the general formulation of a vector programming problem?

How is it solved in general?

Some more references on vector programming?

Thanks and regards!

$\endgroup$
  • $\begingroup$ Your note from UWisc is likely talking about something different than B&V's multiobjective optimization. Perhaps one of the earlier lecture notes from that same class provides a definition? $\endgroup$ – Michael Grant Mar 24 '13 at 15:14
  • $\begingroup$ @MichaelGrant: Thanks! Its definition is not found in the earlier notes. He gave something probably a definition in the same note. $\endgroup$ – Tim Mar 24 '13 at 17:19
  • $\begingroup$ I'm having a bit of trouble reverse engineering the general notion of a "vector program" from these notes alone, but I remain certain it is something different than a multiobjective problem. $\endgroup$ – Michael Grant Mar 24 '13 at 17:46
8
$\begingroup$

OK, now we're getting somewhere. From these notes we have:

A vector program consists of:

  • a collection of vector-valued variables $y_1, ... , y_n\in\mathbb{R}^k$
  • linear constraints on the dot products of variables
  • a linear objective function on the dot products

In other words, the variables $y_i$ never appear by themselves in the model, they appear only in dot products with themselves or with other variables.

Here would be a standard form for a vector program: $$\begin{array}{ll} \text{minimize} & \sum_{i,j} C_{ij} \langle y_i, y_j \rangle + d \\ \text{subject to} & \sum_{i,j} A_{ijk} \langle y_i, y_j \rangle = b_k , ~ k=1,2,\dots,K\\ \end{array}$$

Now let's examine the relationship between a VP and an SDP when $k\geq n$. Note that we can assume that $C_{ij}=C_{ji}$ and $A_{ijk}=A_{jik}$ since $\langle y_i,y_j\rangle = \langle y_j,y_i\rangle$. Collect these constants $C_{ij}$ and $A_{ijk}$ into matrices $C,A_1,A_2,\dots,A_k\in\mathbb{R}^{n\times n}$; these matrices will be symmetric. Now consider the following semidefinite program: $$\begin{array}{ll} \text{minimize} & \langle C, X \rangle + d \\ \text{subject to} & \langle A_k, X \rangle = b_k , ~ k=1,2,\dots,K\\ & X \succeq 0 \end{array}$$ If $X$ is a feasible point for the SDP, then let $Y\in\mathbb{R}^{k\times n}$ be a square root of $X$; that is, let it satisfy $X=Y^TY$. A square root must exist since $X$ is positive semidefinite. If $k=n$ you can use a Cholesky factor or a symmetric square root; if $k>n$, compute one of those square roots and pad it with $k-n$ zero rows. Then it is not difficult to verify that the columns of $Y$ $$Y \triangleq \begin{bmatrix} y_1 & y_2 & \dots & y_n \end{bmatrix}$$ are a feasible point for the VP, and obtain the same objective value. For instance, $$\langle C,X \rangle = \langle C,Y^TY \rangle = \sum_{ij} C_{ij} y_i^Ty_j = \sum_{ij} C_{ij} \langle y_i, y_j \rangle.$$ Conversely, if $y_1,y_2,\dots,y_k$ are an optimal solution to the VP, then $X=Y^TY$ is feasible for the SDP, and obtains the same objective value.

Since the objective values coincide in both directions, the optimal points are equivalent as well. But note that the mapping from $X$ to $Y$ is not one-to-one: there are an infinite number of possible $Y$ values for each $X$. And what happens when $k<n$? Well, you would have to add a constraint $\mathop{\textrm{rank}}(X) \leq k$ to the SDP to preserve equivalence, and that's a non-convex construct. In fact, from the PDF I quoted above:

Vector programs are p-time solvable, but the solver picks k.

This now makes sense if SDPs are used to solve VPs. If you solve the SDP and the optimal value of $X$ satisfies $\mathop{\textrm{rank}}(X) = k<n$, then you can indeed recover a VP solution for vector size $k$ or larger. The Max Cut problem discussed in those notes needs $k=1$, so the VP and/or SDP models are relaxations of the true Max Cut problem.

(It's possible to allow inequality constraints in a VP as well, by the way. This answer is already long enough, but basically you'd add slack variables to convert them to equations, then create one new vector variable for each slack.)

So now it's clear that the vector program he is referring to in these notes is indeed different than the multiobjective optimization problems discussed in Boyd & Vandenberghe. UPDATE: A wealth of resources on vector programs and their semidefinite equivalents can be found by searching for "vector program" "semidefinite" in Google. (Quotes included.)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.