New answers tagged

0

The optimization problem in standard form: $min_x \quad f_0(x)$ $\quad \quad f_i(x) \le 0, \quad i=1,\cdots, m$ $\quad \quad h_i(x) = 0 \quad i=1,\cdots,p$ is called a convex optimization problem if: The objective function $f_0$ is convex. The functions defining the inequality constraints, $f_i, i=1,\cdots,m$ are convex. The functions defining the ...


1

This is not true. $(0,1)$ and $(1,2)$ are convex sets in $\Bbb R^1$. Their intersection (and its closure) is empty, but their closures intersect in $\{1\}$.


1

Suppose that $P$ is not bounded. There is then a sequence $(x_i)_{i\geq0}$ of points in $P$ such that $|x_i|\to\infty$ as $i\to\infty$. We may assume that $x_i\neq x_0$ for all $i\geq1$, and then the sequence of vectors $$d_i=\frac{x_i-x_0}{|x_i-x_0|}$$ takes values in the unit sphere, which is compact, so by replacing our sequence by a subsequence, we may ...


1

I would cast this as a mixed-integer quadratic program. To do so, we first define new continuous variables $y_2,\dots,y_n$ and introduce these constraints: $$-y_k\leq x_k\leq y_k, \quad k=2,3,\dots, n, \quad y_2=1$$ Then we define new binary variables $z_2,\dots,z_{n-1}\in\{0,1\}$: $$x_k \geq y_{k+1} - 2 z_k, \quad -x_k \geq y_{k+1} - 2 ( 1 - z_k ), \quad ...


0

I just worked this problem and it took me a good day to do it so I figured I'd post my answer since I too looked to stack exchange for an answer. Given $\epsilon>0$ define $\vec{\epsilon}:=(\epsilon,...,\epsilon^m)$. Fix a basis $a_{i_{1}},...,a_{i_{n}}$ and $a_{i_{n+1}}$ not in the basis. Then for some $c_{1},...,c_{n}$ we have that ...


1

Take the definition of convex set (e.g. chapter 2.1.4 from Boyd & Vandenberghe). Can you say that $p(x) = \theta \, p_1(x) + (1-\theta) \, p_2(x) \in P$ for any $0 \leq \theta \leq 1$ and any $p_1(x),\,p_2(x) \in P$? Yes, $p(x)$ is a valid pdf, it is non-negative and integrates to 1. BTW, the resulting density is called a mixture density distribution ...


2

[Edited after After Michael's comment] In the general case, the OP's claim is not verified. For example if $$ X = \begin{bmatrix} 29& 11& 19\\ 11& 10& 12\\ 19& 12& 19 \end{bmatrix} , \quad Y = \begin{bmatrix} 14& 16& 17\\ 16& 21& 22\\ 17& 22& 29 \end{bmatrix} , \quad w = \begin{bmatrix} 1\\ 2\\ 3 \end{bmatrix} ...


0

I assume you are implying $a^tx-b>0$ to ensure convexity (see Michael's comment). For simplicity I also assume that $Q$ is Hermitian but the solution can be easily generalized. If $b \le 0$, then $x=\mathbf{0}$ is trivially a solution. If $b > 0$, you can follow the approach below (forgive some sloppiness in the maths, for brevity). Setting $\nabla ...


1

The Lagrangian is $$L(x,\lambda) = \tfrac{1}{2} x^T Q x + \lambda^T ( A x - b)$$ The optimality conditions are $$\begin{bmatrix} Q & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} x \\ \lambda \end{bmatrix} = \begin{bmatrix} 0 \\ b \end{bmatrix}$$ This is a symmetric indefinite linear system and can be solved for the combined value of $(x,\lambda)$. But ...


2

Column generation is a standard tool for large scale, possibly smooth convex optimization problem. Standard application are radiation therapy, traffic equilibrium among others. Under suitable assumption column-generation scheme can also converge to critical point of non convex problems. Take a look at http://www.math.chalmers.se/~mipat/LATEX/CGSD.ps ...


0

For $\mu$ a Borel positive measure on the sphere $S^{n-1}$, consider a continuous Minkowski sum of segments $$ K_\mu = \int_{S^{n-1}} [0,\theta] \, \mathrm{d}\mu (\theta) .$$ The set $K_\mu$ is convex (it could be defined by its support function, then the integral becomes a usual one). Now observe that (1) $K_{\mu+\nu} = K_\mu + K_\nu$ (2) by rotation ...


0

No, this is even fails in dimension $2$. Just try $C = \{(x,y) \in \mathbb R^2 \mid (x-1)^2 + y^2 \le 2 \}$.


2

The Euclidean distance between the two lines is $$\left\|s \begin{bmatrix} 1\\ 2\\ 3\end{bmatrix} - t \begin{bmatrix} 1\\ 1\\ 1\end{bmatrix} + \begin{bmatrix} 1\\ 0\\ 0\end{bmatrix}\right\| = \left\|\begin{bmatrix} 1 & -1\\ 2 & -1\\ 3 & -1\end{bmatrix} \begin{bmatrix} s\\ t\end{bmatrix} - \begin{bmatrix} -1\\ 0\\ 0\end{bmatrix}\right\|$$ ...


5

The difference vector is $$ d = L_2(s) - L_1(t) = s (1,2,3) + (1,0,0) - t (1,1,1) = (s - t + 1, 2s - t, 3s - t) $$ Then $$ q = \lVert d \rVert^2 = d^2 = (s-t+1)^2 + (2s - t)^2 + (3s - t)^2 $$ Then the gradient is $$ q_s =2(s-t+1)+ 4 (2s-t) + 6(3s-t) = 28s-12t + 2 \\ q_t = -2(s-t+1)-2(2s-t) -2(3s-t) = -12s+6t-2 $$ It vanishes for $$ \left( ...


11

First take the cross product of the two direction vectors: $<1,1,1>\times<1,2,3>=<1,-2,1>$. We can normalize to the unit vector $\frac{1}{\sqrt6}<1,-2,1>$ The minimum distance will be the length of the scalar projection of any line segment joining L1 and L2 onto this unit vector. We have the points (0,0,0) on L1 and (1,0,0) on L2, ...


3

Note that if $\|x\| < 1 $ and $z^T x \ge 0$, then $z^T {x \over \|x\|} \ge z^T x$. Hence $\sup \{z^T x : \|x \| \le 1 \} = \sup \{z^T x : \|x \|= 1 \}$.


4

You're correct. But note that in the BV definition, there is no benefit in taking $\|x\|<1$, so the definition may as well have stipulated that $\|x\|=1$.


0

I'm not sure I've understood you correctly, but the solution to an LP with rational data $(A,b,c)$ is always rational.


0

There is no duality gap in linear programming. In the primal world, the original problem and the version where it is in canonical form share the same solution (as in objective function). Since there is no duality gap, the corresponding dual will achieve the same objective function as well.


0

As $t_1 + t_3 - 5\le 1 + 1 - 5 = -3$ in the integration domain, is impossible.


2

Here is a proof in the setting of complete simply connected Riemannian manifolds of nonpositive sectional curvature. The case of general CAT(0) spaces should be similar, but there are some technical details which make the discussion less pleasant in that case: One needs to smooth out convex functions of one variable (which can be done via convolution with ...


2

Depends on your alternative; I'm one of the gpkit developers, and in comparisons we've run GPs solve much faster than naive gradient descent (it's worth noting that not all GPs are convex without the transformation). However, if your problem is can be solved by another convex solver (e.g. it's also a valid LP) then that solver is likely to be a little bit ...


1

From here For example, minimise $f(x) = \max(3x-4,2x-1)$ is equivalent to: minimise t subject to $3x-4 \le t$ $2x-1 \le t$ Note that $$f(x) = 3x-4 \iff x \ge 3$$ So if we have $x = 5$, then $f(5) = 11$ and $$11 \le t$$ $$9 \le t$$


1

Well, $$Ax \le b$$ Now pre-multiply $y^T$ on both sides. Also, $$c^T \le y^T A$$ Now post-multiply $x$ on both sides.


0

So I finally with a bit of help from a number of people seem to have figured this one out. First note that we can map the sub-additive subspace of $\prod^N [0,1]$ onto the additive space of $\prod^{N+1} [0,1]$ by adding another dimension which is 1 minus the sum of the other dimensions. I believe this is a special case of barycentric coordinates. Next take ...


0

I believe that using a simple vector in $\mathbb{R}^n$ will suffice. We will represent your probability distribution $p(k)$ as a vector $p = (p_1, p_2, \dots, p_n)^T$, where $p_i$ is the probability of $i$. Now, one of your optimization problem (the maximum cross-entropy) can be written like this: $$ \begin{aligned} \min_{p,q \in \mathbb{R}^n} &\quad ...


1

Here is a good link for books to learn on the probability theory. Some are more in depth while others meant for more casual reading. There are also a bunch of puzzles on the blog along with some that have code on them, that help with understanding the concepts.


0

Don't quite understand your question. The primal variable does not matter when you write the Lagrangian form, the constraint matters. For the positive-semidefinite constraint, you also need a matrix as the Lagrangian variable. $$ \lambda=\begin{bmatrix} \lambda_{11} & \lambda_{12} \\ \lambda_{21} & \lambda_{22} \\ \end{bmatrix}$$ And when ...


2

Since there is only a single variable in your reduced problem, you can find the best choice of $x_i$ just using techniques from precalculus. (Consider separately the cases $x_i \geq 0$ and $x_i \leq 0$, and visualize the graph of a quadratic function in each case.) Here's a different viewpoint (summarized very briefly). Let $f(x) = \|x\|$, where $\| \cdot ...


0

I think there is a simple way to look at it without using duality. Our goal is to find the minimizer for the problem \begin{align} \tag{$\spadesuit$} \text{minimize} & \quad \| x \|_2 + \frac{1}{2t} \| x - \hat x \|_2^2 \\ \text{subject to} & \quad x \geq 0. \end{align} First note that if $\hat x_i < 0$, then there is no benefit from taking ...


2

It's hard to tell what you need, since this depends on the level of complexity and sophistication you're targeting, and most importantly, what you aim to learn from these books. Here are a few references that might help. Convex analysis (in increasing order of "difficulty"): "Convex Optimization", S. Boyd et al. "Introductory Lectures on Convex ...


2

There is a neat geometric way to see why this should be so, but I've forgotten some of the details. Some papers of Daubeches, Dohono, etc. contain these details. Unfortunately, I've forgotten these refs too. So, I'll give you the somewhat lazy solution (you probably already figured out that I'm a very lazy person), based on proximal operators and the Mureau ...


1

The method of choosing all sets of 3 points, finding the circle that passes through that set, and seeing which other points lie on that circle has one big problem: roundoff error. If you try to use any method that involves taking square roots, roundoff can cause problems. Here is a method, based on some previous work of mine, that allows this to be done ...


2

A possible (non linear) model for this problem: Define the following variables : $a$ is the $x$-coordinate of the circle $b$ is the $y$-coordinate of the circle $r\ge0\;$ is the radius of the circle $\omega_i$ is a binary variable that equals $1$ if and only if point $(x_i,y_i)$ lies on the circle. The objective function is then to maximize $$ ...


0

Their proof uses subgradients of a function $f$ and their properties. If $f(x)$ is not convex, then not everywhere can you define its subgradient. Think about $f(x) = -x^2$, which is a concave function and not convex; the gradient $f'(x) = -2x$ is not a subgradient (sounds weird, doesn't it?) because $f'(x) = -2x$ does not satisfy the subgradient definition ...



Top 50 recent answers are included