Hot answers tagged

15

$\newcommand{\Rbar}{\overline{\mathbb{R}}}\newcommand{\R}{\mathbb{R}}\newcommand{\minimize}{\operatorname{Minimize}}$Another way to derive the dual for any convex problem is to use Fenchel duality. Fenchel duality Define $\Rbar=\R\cup \{+\infty\}$. A function $f:\R^n\to\Rbar$ is called proper if there is an $x\in\R^n$ such that $f(x) < \infty$. Given a ...


13

In Linear Programming (LP) one chooses a vector $\lambda \geq 0$ to obtain $\lambda^\top Ax \geq \lambda^\top b$ and whenever we find such a $\lambda \geq 0$ with $A^\top\lambda =c$ we obtain a lower bound $b^\top \lambda$ for our linear programming problem. In conic programming we also search for vectors $\lambda$ such that $\lambda^\top Ax \geq \lambda^Tb$...


12

Whether a given formulation is faster / more stable than another depends on the software you use to solve either. What is the intuition behind it that a SOCP formulation can be solved more efficiently? Here are a few reasons. For more details, you can have a look at the Mosek modeling cookbook or the seminal book of Ben Tal & Nemirovskii, Lectures on ...


9

Succinct and (freely) accessible references, which include general "theory". Also, solved examples,. for instance for Second Order Cones (SOCP) and Linear Semidefinite cones (LMI, i.e., Linear SDP): Chapter 8 "Duality in conic optimization" in "MOSEK Modeling Cookbook" . Section 5.9 "Generalized inequalities" in "Convex Optimization" by Boyd and ...


4

How can we prove that the number of possible separating hyperplanes (separating $p$ and $\operatorname{pos}W$) is finite based on the fact that $\operatorname{pos}W$ is finitely generated? In general, it is not. There may be infinitely many separating hyperplanes. Let $\sigma_{1}$, $\sigma_{2}$ define two distinct separating hyperplanes. Then it's ...


4

Revamp of my answer given the example now provided. Let there be $n$ VaR factors. Let $R$ = $n$ by $n$ matrix of correlations (the 2nd matrix in your example) of the VaR factors. Let $W$ = $n$ by $1$ vector whose ith element is $W_i$. The VaR portfolio constraint can be expressed as $$W^TRW \le b^2.$$ This constraint can be rewritten in terms of $X$ as ...


4

For your simple (2 variable, 2 side) cone, you are on the right track. An extreme ray will be defined by $n-1$ binding constraints, which in this case means either $2x_1 - x_2= 0$ or $x_1 + 3x_2 = 0$. In the first case, $x_2 = 2x_1$, so the ray will be either $(1, 2)$ or $(-1, -2)$. The first one is not feasible, so the winner is $(-1, -2)$. In the second ...


2

Ok, after seeing the wrong attempt below which has been edited multiple times, I believe it is time to close this question. I will just leave my attempt: Assume $K^* \neq (\operatorname{int}K)^*$, so $\exists x_0 \in \operatorname{bd} K: \ x_0^\top y < 0$. Because of the strict inequality, we know that we can take a very small ball around $x_0$, say $B(...


1

Perhaps the argument is the following. Observe that $\operatorname{pos}W$ is a polyhedral cone (every finitely generated cone is polyhedral). That it is finitely generated can be seen from the fact that it is positively spanned by the finite number of columns of $W$. Thus we can write $$\operatorname{pos}W=\{t\mid Wy=t,y\geq 0\}=\{t\mid Dt\leq 0\}$$ for some ...


1

A new approach focusing only on $(\boldsymbol{\operatorname{int}}K)^* = K^*$, since that seems to be the biggest problem to you. From section 2.6 of Convex Optimization (Boyd, Vanderberghe) we have that: (3) $K^*$ is closed and convex. (1) $K^{**}$ is the closure of the convex hull. (2) For $K$ convex and closed, $K^{**} = K$. I will add a conjecture: (...


Only top voted, non community-wiki answers of a minimum length are eligible