# Questions tagged [non-convex-optimization]

The tag has no usage guidance.

36 questions
Filter by
Sorted by
Tagged with
32 views

45 views

### Recovering sparsity from $\ell^1$ relaxation

I've read that $\ell^1$ norm on $\mathbb{R}^n$ is the convex relaxation of the $\ell^0$ "norm": $$\|x\|_0 \triangleq \sum_{i=1}^n I_{x_i \neq 0}.$$ In the regression setting, under what ...
21 views

### Approaches and approximations for specific non-convex low-rank optimization problem

I have recently begun looking at an optimization problem in the context of Wiener filtering and lower-dimensional representations. Assume $X$ is a random vector of length $n$ and $Y$ is a random ...
101 views

### Hardness of concave minimization problem

I have an optimization problem $\underset{x}{\min} ~ c(x) - k \cdot x$ where $c(x)$ is a non-decreasing concave function with $c(0) = 0$, $x \in C \subseteq \mathbb{R}^d_{\geq 0}$. By non-decreasing, ...
48 views

### Variational forms of non-convex functions

I am trying to understand what kind of variational forms exist for non-convex functions. Alternatively, are there conjugate forms which attain strong duality? For a non-convex function $f$, I am ...
102 views

### Necessary optimality condition for quadratic programming: a solution of a constrained QAP is a solution of a LP

I have a concern about a result given by Murty in  and also written by Floudas and Visweswaran in  They consider a QP: \begin{array}{ll}{\min _{x} Q(x)} & {=c^{T} x+\frac{1}{2} x^{T} D ...
127 views

121 views

135 views

### non-convex optimization with constraint

I have a special non-convex optimization problem: $\min / \max \ f(x) + g(x) + h(x)$, subject to $| g(x) - h(x)| < \varepsilon$, where $f(x)$ is non-convex, but both $g(x)$ and $h(x)$ are ...
259 views

77 views

### Why to multiply the penalty by $n$ in the penalized least squares and likelihood?

In the SCAD paper by Fan and Li (2001), there exist two forms of penalized least squares as follows: $$\frac{1}{2}\left \| y-X\beta \right \|^2+\lambda \sum_{j=1}^{d}p_j (\left | \beta _j \right |),$$ ...
242 views

### Are there any solvers to Chance Constrained Programming Problems

I'm trying to solve a chance constrained programming (CCP) problem $\min_x f_0(x, \xi), \text{ such that } \mathbb{P} ( f_i(x, \xi) \ge \alpha_i ) \le \epsilon_i, \text{ where } i = 1,2,\cdots, m$ ...
284 views

1k views

I have a problem that looks very much like a norm-constrained linear program, but with an extra constraint that is unusual for me. The problem is the following. Given a matrix $A$ and a vector $w$, ... 2answers 4k views ### Linearly constrained eigenvalue problem Suppose I'd like to: \begin{align} \mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\ \text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\ && \... 1answer 841 views ### Maximizing quadratic form on the hypercube I want to maximize a quadratic form \mathbf x^T\mathbf Q\mathbf x and also want to find out which vector \mathbf x maximizes the quadratic form when \mathbf Q is an n\times n positive ... 1answer 652 views ### Nonconvex optimization problem I have a nonconvex optimization problem with a linear objective function, a set of linear constraints and a set of nonlinear, non-convex constraints. Is this problem NP-hard? If so, how can I prove ... 1answer 382 views ### Is the feasibility of a system of non-convex quadratic equations and inequations decidable? I would like to know whether the following problem is decidable. Given the following system in x \in [0,1]^nx^T Q_i x + r_i = 0 \mbox{ for } i = 1, ..., kx^T Q_j x + r_j \neq 0 \mbox{ ...
152 views

I would like to optimize the following system: $$\min_{q,\|q\|=1} \sum_i^n |q^T M_i q|$$ More details: the size of the unknown vector $q$ is $4 \times 1$, $M_i$ is a matrix of size $4\times 4$. It ...
604 views