6
votes
Accepted
If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?
The application of proximal gradient to this exact problem is considered in (equations (2) and (35) in) the Uncertainty in Artificial Intelligence (UAI) 2019 paper Fast Proximal Gradient Descent for A ...
- 1,517
5
votes
Accepted
Minimal norm of Fréchet subdifferential for function Lipschitz over its domain
Let $C$ be a triangle on the plane with a vertex at origin and angle $179^\circ$ at this vertex; $f(x)=-\|x\|$, it is Lipschitz with $L=1$. Then we have $f(x)\geqslant \langle v,x\rangle$, where $v$ ...
- 109k
5
votes
Accepted
Maximizing a convex function with a convex constraint
Under your assumptions, this is a concave programming problem (i.e., minimization of a concave function subject to convex constraints) with compact constraint set, and therefore has a global minimum ...
- 1,517
4
votes
Can you give me good examples of non-convex functions that are problematic for optimization?
A less-known example is $f(x):=x^2+\exp(-1/(100(x-1))^2)-1$ on the closed interval $[-2,2]$. It takes $-.0067419337989203 $ at $x = .996387676055289 $.
See that discussion in MaplePrimes for more ...
- 3,486
4
votes
Accepted
Is non-convex optimisation really in NP class?
As noted in a comment by Emil Jeřábek, $\mathsf{NP}$ is a class of decision problems, so on the face of it, an optimization problem cannot be in $\mathsf{NP}$ for the rather trivial reason that it is ...
- 82.6k
4
votes
Accepted
Optimizing a multivariate symmetric (permutation-invariant) function
One can show that this function is Schur-concave using the Schur-Ostrowski criterion, which then implies the maximum is attained at the diagonal.
See also
https://math.stackexchange.com/questions/...
- 381
4
votes
Accepted
Proving an infinite norm minimization problem has finite support (non-convex p-norms)
If $p=1$, $N=1$ and $a_1=(1/2,2/3,3/4,4/5,\ldots)$, the infimum equals 1 and is not achieved on a finitely supported vector (moreover, it is not achieved at all).
However if $0<p<1$ and the ...
- 109k
3
votes
Proving an infinite norm minimization problem has finite support (non-convex p-norms)
If one use Lagrange multipliers, there exist $\mu_1, \mu_2 , \cdots \mu_N$ such that $$ \begin{cases} p|x^*(i)|^{p-1}=\sum_{n=1}^N \mu_n a_n(i) \quad\text{ or}\\ |x^*(i)|=0\end{cases}$$ for all $i$. ...
- 4,361
3
votes
$O(n^{2-\epsilon})$ bound on choosing $n$ points on the hypersphere to maximize $\pm 1$ weighted sum of their $\binom{n}{2}$ inner products
This is correct.
Consider a random symmetric matrix $A=(a_{ij})$, $a_{ij}=a_{ji}=\epsilon_{ij}/2$, $a_{ii}=0$.
Let $u_1,\ldots,u_n$ be your $n$ points on the sphere $\mathcal{S}^{d-1}$. Denote $u_i=(...
- 109k
3
votes
$O(n^{2-\epsilon})$ bound on choosing $n$ points on the hypersphere to maximize $\pm 1$ weighted sum of their $\binom{n}{2}$ inner products
Let $\lambda$ be the largest eigenvalue of the symmetric matrix $M_{ij}$ with diagonal entries $0$ and off-diagonal entries $\epsilon_{ij}$.
Then
$$\sum_{1\leq i<j\leq n} \epsilon_{ij} v_i v_j^T =\...
- 148k
3
votes
Accepted
Linear optimization with one positive definite quadratic equality condition in P?
The following conditions
$$
\begin{array}{l}
y=\sum x_i^2\\
0\leq x_i\leq 1\\
y=\sum x_i
\end{array}
$$
are equivalent to $x_i\in \{0,1\}$, which means your construction allows you to introduce ...
- 411
3
votes
Eigenvalue problem with two quadratic constraints
Generically, your system will have no solution, since $\mathbf{x}^t B \mathbf{x}$ is rarely zero for full-rank matrices. In the special case where $B$ is a degenerate symmetric matrix, then $x$ is in ...
- 96.4k
2
votes
Eigenvalue problem with two quadratic constraints
Because no one has offered a solution meeting your ideal of using a standard numerical linear algorithm, I will offer an approach using the global numerical nonlinear optimizer BARON.
Here is a ...
- 1,517
2
votes
Accepted
PCA, relation between the error and variance
$\newcommand{\Si}{\Sigma}\newcommand{\R}{\mathbb R}\newcommand{\la}{\lambda}$Let us work in an orthonormal eigenbasis of $\Si$. Then without loss of generality $\Si$ is the diagonal matrix with ...
- 128k
2
votes
Program to solve Optimization Problem
Given that you already have MATLAB, you can do this with software available for npo extra cost. Specifically, use the BMIBNB branch and bound global optimizer included with YALMIP https://yalmip....
- 1,517
2
votes
Minimal norm of Fréchet subdifferential for function Lipschitz over its domain
$\newcommand\R{\mathbb R}\newcommand\de{\delta}\newcommand\ep{\varepsilon}\newcommand\dom{\operatorname{dom}}$This is a detalization of Fedor Petrov's answer.
Let $n=2$. Take any real $k>0$. Let
$$...
- 128k
1
vote
Accepted
Solving a linear program, but over the unit sphere
Going by the first comment, the optimal solution to the convex problem (= replaced by $\leq$) must give a solution on the unit sphere. Firstly, Since $\{0,0\}$ is a feasible point, the optimal value ...
- 1,216
1
vote
Nonconvex optimization with linear constraints
First things first: Be aware that global minima may be out of reach.
Here are two possibilities that come to mind:
If you have differentiability, you may use projected gradient descent: Start with an ...
- 12.7k
1
vote
Hardness of concave minimization problem
If your problem has a solution $x^* \ne 0$, then $0$ is also a solution. Indeed, consider the function
$$\varphi(t) = c(t \, x^*) - k\cdot (t \, x^*).$$
Since $x^*$ is a solution, we have
$$\varphi(0) ...
- 1,714
1
vote
A quadratic program with non-negativity constraints
Is the problem well-defined in case $B$ has a negative eigenvalue?
Consider an unit eigenvector $v$ corresponding to a negative eigenvalue $\lambda$ of $B$. Since any vector $v$ can be written as ...
- 1,216
1
vote
Maximizing quadratic form subject to inequality constraints
This can be formulated and solved as a Quadratic Programming (QP) problem, by minimizing -trace($X^TSX)$ subject to the element-wise bounds $0 \le X \le 1$. If the objective is not convex, then a ...
- 1,517
1
vote
Why to multiply the penalty by $n$ in the penalized least squares and likelihood?
You are referring to "Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties", Fan and Li, Journal of the American Statistical Association, Dec 2001. http://orfe.princeton....
- 1,517
1
vote
Are there any solvers to Chance Constrained Programming Problems
This is not an answer. It is another perspective which may point to an answer. I have no references to provide.
Given a real valued continuous function h(x,v), where v will be restricted to D= [-1,...
- 13k
1
vote
Is all non-convex optimization heuristic?
Of course, generally the optimization is NP-hard. However there is a couple tricks that can be played in non-convex case.
First, if $d$ is domain dimension, the probability of, say, gradient descent ...
Only top scored, non community-wiki answers of a minimum length are eligible