1
$\begingroup$

I struggle solving a task related to Conic Linear Optimization. This is the task: "Consider the set of points D = $\{a_1, ..., a_n\}$ $\subset$ $\mathbb{R}^2$. Formulate as a conic problem the problem of finding the point $x \in \mathbb{R}^2$ which minimizes the maximum distance in euclidean norm to the points of D. Check the conditions which secure the existence of an exact dual problem and formulate it explicitly."

My thoughts so far have been: The optimization problem is the following:

 min   max ||a_i - x || 
 s.t.  x ∈ ℝ^2, a_i ∈ D 

An equivalent formulation of this problem is :

 min   z 
 s.t.  ||a_i - x || ≤ z 
       x ∈ ℝ^2, a_i ∈ D  

Now we can formulate the conic program using the Lorentz cone:

$L_2$ = $\{(a_i - x,z) \in \mathbb{R}^{2} \times \mathbb{R} \,, a_i \in D \,: \, \Vert a_i - x \Vert_2 \leq z \}$:

 min   z 
 s.t.  (a_i - x,z) ∈ L_2

Is this correct so far? I face three problems now:

  1. How do I return the actually looked for center x? Just via "$x \in \mathbb{R}^2$ for which holds: $\Vert a_i - x \Vert_2 = z$ for some a_i $\in$ D" ?
  2. What are the above mentioned existence conditions for the dual problem ?
  3. How do I state the dual for this?

The primal and the dual are normally given in the following form:

   min  C * X                          max y * b
   s.t. A * X = b                          yA + S = C
   X ∈ L_2                                 S ∈ L_2

So I think in my case C = (0,1) and X = $(a_i - x, z)$ and the Lorentz cone $L_2$ is self-dual, but what is A and b?

I would be very thankful for your help, Best regards, Sam

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.