22
Probably you ask for a proof that the median solves the problem? Well, this can be done like this:
The objective is piecewise linear and hence differentiable except for the points $m=x_i$. What is the slope of the objective is some point $m\neq x_i$? Well, the slope is the sum of the slopes of the mappings $m\mapsto |m-x_j|$ and this is either $+1$ (for $m>...
17
Based on personal experience, I'd say that simplex methods are marginally easier to understand how to implement than interior point methods, based on personal experience from implementing both primal simplex and a basic interior point method in MATLAB as part of taking a linear programming class. The main obstacles in primal simplex are making sure that you ...
16
A generalization of this problem to multiple dimensions is called the geometric median problem. As David points out, the median is the solution for the 1-D case; there, you could use median-finding selection algorithms, which are more efficient than sorting. Sorts are $O(n\log n)$ whereas selection algorithms are $O(n)$; sorts are only more efficient if ...
14
It's typically very hard if not impossible to implement a parallel version of an iterative algorithm that paralellizes across iterations. The completion of one iteration is a natural sequence point. If one algorithm requires fewer iterations but more work per iteration, then it's more likely that this algorithm can be effectively implemented in parallel.
...
14
If what you want is to solve
$\min \| Ax - b \|_{2}^{2} + \lambda^{2} \| x \|_{2}^{2}$
subject to
$x \geq 0$,
then this is easily implemented. Construct a matrix
$C=\left[
\begin{array}{c}
A \\
\lambda I
\end{array}
\right]$
and a vector
$d=\left[
\begin{array}{c}
b \\
0
\end{array}
\right]$.
Then use your nonnegative least squares solver on
$...
12
Overview
You might want to try a variant of the Alternating Directions Method of Multipliers (ADMM), which has been found to converge surprisingly quickly for $l_1$ lasso type problems. The strategy is to formulate the problem with an augmented Lagrangian and then do gradient ascent on the dual problem. It is especially nice for this particular $l^1$ ...
12
Just to clarify notation, I'll be discussing the Gauss-Newton method for the problem
$\min \phi(x)=(1/2) \| F(x) \|_{2}^{2}$
with the search direction $p$ computed as the solution to the linear system of equations
$J(x^{(k)})^{T}J(x^{(k)}) p = - J(x^{(k)})^{T} F(x^{(k)})$
where $J(x)$ is the matrix of partial derivatives of components of $F(x)$ with ...
11
CVXOPT only solves (smooth and nonsmooth) convex problems, giving access to several third party convex solvers with guaranteed state of the art worst case complexity. You may pose linear, convex quadratic, linear semidefinite, and many other convex types of constraints.
OpenOpt solves general (smooth and nonsmooth) nonlinear programs, including problems ...
11
I wrote a full answer (below the line) before discovering CVXPY, which (like CVX for MATLAB) does all the hard stuff for you and has a very short example almost identical to yours here. You only need to replace the relevant line with
p = program(minimize(norm2(A*x-b)),[equals(sum(x),1),geq(x,0)])
My old answer, doing it the harder way with CVXOPT:
...
10
A function that is convex needs to satisfy $f(\alpha x + (1-\alpha)y) \le \alpha f(x) + (1-\alpha)f(y)$ for all $\alpha\in(0,1)$ and $x,y$ in the domain of definition. You could simply try to verify this formula for a large number of pairs $x,y$ and a couple of values $\alpha$, e.g. $\alpha=\{1/4,1/2,3/4\}$.
9
Johan has certainly done a more complete job of answering Bel's question here than I did on the CVX Forum. But I do think there is a conceptual difficulty at play here that is worth discussing.
In my response on the CVX Forum, I said that "you simply cannot expect CVX to accept any expression that you want even if you prove it is convex." Johan offers a ...
9
You want to minimize
$\min \| Ax -y \|_{2}^{2} + x^{T}B^{T}Bx=\| Ax -y \|_{2}^{2} + \| Bx \|_{2}^{2}$
Recall that
$\| u \|_{2}^{2} + \| v \|_{2}^{2}=
\left\| \left[ \begin{array}{c}
u \\
v
\end{array} \right] \right\|_{2}^{2}$.
Thus your problem can be written as
$\min \| Hx - g \|_{2}^{2}$
where
$H=\left[ \begin{array}{c}
A \\
B
\end{array}
\...
9
Given $A \in {\bf S}^n$ (a positive definite matrix) with eigenvalues $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n $, then:
$\displaystyle f_k(A)=\sum_{i=1}^{k} \lambda_i$ is concave. Why?
$$f_k(A) = \inf \left\{ {\bf tr}(V^T A V) | V \in {\bf R}^{n \times k}, V^T V = I \right\}$$
This follows from the Poincare separation theorem (see e.g. Horn ...
8
I am pretty sure you can model the trace of the squared inverse by $trace(Z)$ where $Z$ and $X$ satisifes $\begin{bmatrix} X & I\\I & S\end{bmatrix} \succeq 0$ and $\begin{bmatrix}Z& X\\X&I\end{bmatrix} \succeq 0$ (Derived using Schur complements, $X$ is used to model/upper bound the inverse of $S$ and $Z$ is used for the square of $X$). ...
8
There are many ways of proving that a function is convex:
By definition
Construct it from known convex functions using composition rules that preserve convexity
Show that the Hessian is positive semi-definite (everywhere that you care about)
Show that values of the function always lie above the tangent planes of the function
8
From my own limited experience in the power industry, no one is solving SDPs at that sort of scale. I have some limited knowledge of what the New England ISO is doing, and I think they are more interested in incorporating stochasticity into their existing MILP models. From friends who have worked on power systems at governmental research labs in the USA, ...
8
TL;DR: The property you are looking for is coercivity. This is satisfied for the example in your question (as are properties 1 and 3 below), and hence yes, the penalized objective attains its minimum.
The classical proof of existence of minimizers of (a very general class of) functionals is the so-called direct method of the calculus of variations (...
7
The greedy algorithm works: start with some solution that satisfies your constraints, and then iteratively increase the $x_i$ with largest $a_i$ that isn't at $x_{\max}$ and shrink the $x_j$ with smallest $a_j$ that isn't at $x_{\min}$ as far as possible. Stop when no further pair motions are possible. This takes $O(n \log n)$ to sort $a$ and $O(n)$ time ...
7
You've identiifed the key problem. Certainly the primal can be solved directly by, say, a quadratic programming solver. But typical QP solvers often don't scale well to large problem sizes. A projected gradient method can often scale to significantly larger problems---but only if the derivatives and projections are simple to compute. As I will show, the dual ...
7
For the general audience: a biconvex optimization problem is a problem of the form:
$$\begin{array}{ll} \text{minimize} & f(x,y) \\ \text{subject to} & (X,Y)\in\mathcal{B} \end{array}$$
which is convex in $X$ for any fixed $Y$, convex in $Y$ for any fixed $X$, but is not convex in both $(X,Y)$ jointly.
No, biconvex problems are not polynomially ...
7
I can think of some possibilities:
If both algorithms monotonically reduce the error with each iteration, then it might be preferable to some to have more, cheaper iterations since it gives you more choices about when to stop iterating.
If $\mathcal{A}_1$ is $O(n)$ work and time but $O(n^k)$ memory, you might prefer $\mathcal{A}_2$ if $k$ is large. $k=2$ ...
7
Semidefinite programming and second order cone programming have not been adopted as rapidly in practice as many of us hoped. I've been involved in this for the last 20 years, and it has been very disappointing to see slow progress. Let me point out some of the challenges:
Although we have polynomial time algorithms for SDP and SOCP, the widely used primal-...
7
You can try to apply a convex optimization algorithm to a non-convex optimization problem, and it might even converge to a local minimum, but having only local information about the function, you'll never be able to conclude that you've in fact found the global minimum. The most important theoretical property of convex optimization problems is that any ...
7
Writing an optimization routine is like writing any other not too simple program and involves a fair amount of debugging. All things you mention in your question are good checks (i.e. taking care that all the things that theoretically should hold do indeed hold during iterations).
Some more general checks are:
Are you sure that solutions are unique? If ...
7
In addition to the things that @Dirk already states, run your algorithm on a problem that is simple enough that you can do each step of the algorithm exactly on a piece of paper. Then compare what your algorithm actually does.
For example, run it on a problem where you try to minimize a low-degree polynomial with linear constraints.
6
For a number of practically useful convexity/nonconvexity verification tests, see (self-disclaimer, I am the third author on this paper):
R. Fourer, C. Maheshwari, A. Neumaier, D. Orban, and H. Schichl, Convexity and Concavity Detection in Computational Graphs. Tree Walks for Convexity Assessment, INFORMS J. Computing 22 (2010), 26-43.
Note that there are ...
6
The explicit solution in terms of the median is correct, but in response to a comment by mayenew, here's another approach.
It is well-known that $\ell^1$ minimization problems generally, and the posted problem in particular, can be solved by linear programming.
The following LP formulation will do for the given exercise with unknowns $z_i,m$:
$$ min \sum ...
6
There's no need to use the Schur complement here because $A$ and $S$ are already symmetric. The conventional formulation of this problem as an SDP is
$$\min t \quad\text{ subject to}\\
A-S+tI \succeq 0 \\
A-S - tI \preceq 0$$
results in an SDP of the form (I'm specific here because there are so many different "standard forms" for SDP)
$$\min c^{T}x\\
...
6
A piecewise linear function is not differentiable (except in the trivial case), so as you noticed this method cannot be applied - the gradient does not exist, let alone its Lipschitz constant beta.
If you want to use a variant of Nesterov's accelerated algorithm, you have two options:
You replace your function by a smooth approximation and apply an ...
6
David Eberly has a good description of the solution (with pseudocode) here: http://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf
The short summary: like most convex-convex collision detection algorithms, you search systematically for a separating axis between the cylinders.
For future reference on similar problems, the authors of Real-...
Only top voted, non community-wiki answers of a minimum length are eligible
