# Questions tagged [non-convex-optimization]

The tag has no usage guidance.

44 questions
Filter by
Sorted by
Tagged with
99 views

### $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

Given $n,d\in\mathbb{N}, n\gg d$, I'm looking for a bound on the maximum (or minimum) expected value of the following game: Draw a vector $\epsilon\in\{\pm 1\}^{\binom{n}{2}}$, uniformly at random. ...
31 views

68 views

1 vote
98 views

50 views

### Why the result of the non-convex optimization problem will be farther and farther away from the optimal

When I try to solve a optimization problem by Riemannian stochastic variance reduced gradient algorithm(RSVRG), the formulation of problem like $\frac{1}{N}\sum_{i=1}^Nf_i(x)$ and $f_i(x)$ is a non-...
1 vote
45 views

1 vote
332 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, ...
74 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 ...
129 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 ...
1 vote
216 views

253 views

152 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 ...
1 vote
372 views

99 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 |),$$ ...
350 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$ ...
353 views

2k 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$, ... 13 votes 2 answers 5k 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\\ && \... 5 votes 1 answer 1k 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 ... 3 votes 1 answer 759 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 ... 3 votes 1 answer 458 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{ ...
186 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 ...
1 vote
624 views