20
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
$...
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.
...
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 ...
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
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
As the "No Free Lunch Theorems for Search" [1] states that there is no one particular optimization algorithm that works best for every problem, i.e., citing the authors:
all algorithms that search for an extremum of a cost
function perform exactly the same, when averaged over all possible
cost functions. In particular, if algorithm A outperforms ...
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
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.
7
The whole point is that you do NOT include the constraint $U = uu^T$ . That constraint is non-convex.
Instead you include the constraint that $Z_j$ is (positive) semi-definite. This constraint is a convex relaxation of $U = uu^T$, obtained by Schur complement. I.e., the relaxed constraint, which is convex, is used instead of the original non-convex ...
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-...
6
The fact that $x^*$ is a (global!) minimizer of $f$ if and only if $0\in\partial f(x^*)$ is already fully explained in the notes you linked to -- it's really that simple, but here's the argument again for the sake of completeness. Assume that $x^*$ is a global minimizer of $f$. Then, by definition,
$$
f(x) - f(x^*) \geq 0 = 0^T (x-x^*) \qquad\text{for any }x\...
6
To consolidate my comments: The proof of inequality (A.2) rests on the fact that the solutions $x^{k+1}$ and $z^{k+1}$ of the substeps (3.2) and (3.3), respectively, are global minimizers, so you can compare them to the saddle points $x^*$ and $z^*$, respectively. (Here, Boyd uses the subdifferential characterization, but I'm sure you can also derive it ...
5
If you have derivatives available, no method can beat Newton's method in practice unless you use very specific features of your objective function. This is true whether you want to solve one or a billion problems: solving each one of them is most efficiently done using Newton's method since it is the only one that guarantees quadratic convergence, and this ...
5
You probably want to use a matrix-free method for linear programming. I don't know of any method specifically geared towards linear programming, but there exist matrix-free interior point methods for quadratic programs and for general nonlinear programs. The quadratic program case corresponds exactly to your problem, where the quadratic form coefficients are ...
5
Most of the work I'm aware of at labs for power flow problems is on stochastic optimization also, focusing mostly on MILPs.
In chemical engineering, they are interested in MINLPs, and the classic example is a mixing problem (specifically, the prototypical Haverly pooling problem), so bilinear terms come up a lot. Trilinear terms occasionally pop up, ...
5
One option here is to use the pseudoinverse of $\Sigma$ rather than the actual inverse. Appendix A of Boyd and Vandenberghe discusses a version of the Schur complement that includes this case.
Another alternative is to find a factorization of $\Sigma$ as
$\Sigma=M^{T}M$ (e.g. by eigenvalue decomposition), and then use the Schur theorem on
$\left[
\...
5
IPOPT is a good interior point method solver for convex nonlinear problems, and has a MATLAB interface, although I haven't used the MATLAB interface. (The solver, called from GAMS, is very good.)
CVX is also a good package for convex problems, and YALMIP is slightly more general; both of these packages provide a modeling language for posing nonlinear ...
5
Your problem is related to low rank approximation problems, about which there has been a lot of research in recent years.
Are you looking for a solution in which $X$ has a specified number of rows, or are you trying to find the smallest number of rows possible?
In most cases, users are interested in finding $X$ such that $X^{T}X$ is close to $C$ (in e.g....
5
It's very difficult to provide a useful answer to this question because you haven't provided enough details about your problem and what you have already tried.
There are various conditions under which the augmented Lagrangian method is certain to converge asymptotically to an optimal solution. You should make sure that the problem you're trying to solve ...
5
Most of the best modern methods for large-scale optimization involve making a local quadratic approximation to the objective function, moving towards the critical point of that approximation, then repeating. This includes Newton's method, L-BFGS, and so on.
A function can only be locally well-approximated by a quadratic with a minimum if the Hessian at the ...
5
You can use a Test Driven Development (TDD), the ideas behind are:
before write code you write the test with the expected result;
every line of code (almost all lines) is under test so when you modify a line you can check if there is the correct behavior or side effects.
With this methodology you can find and prevent some erros described by Dirk.
To ...
5
To ensure this does not drown in the comments, I make it an answer.
The solver used is not SeDuMi, as claimed in the question. The solver used is quadprog, and that solver (or more specifically, a severely outdated version of it), apparently had numerical issues on this particular instance. A recent version of quadprog, or any reasonably robust solver, ...
Only top voted, non community-wiki answers of a minimum length are eligible