Questions tagged [nonconvex]

The tag has no usage guidance.

1
vote
0answers
58 views

Best optimizer for unconnstrained non-convex nonlinear least-square optimization problem?

I am looking for a very good optimizer to the following problem: $$\min_{P,\Theta}\lVert APD(\Theta)P^{-1} -B \rVert_F$$ where $A,B \in \mathbb{R}^{n\times m}$, $P \in \mathbb{R}^{m\times m}$, $D\in \...
5
votes
0answers
93 views

How to solve a 4th order nonnegative LASSO problem?

I need to solve the following 4th order nonnegative LASSO problem: $$ \min_{x \geq 0} \quad || |Ax|^2 - b ||^2 + \lambda ||x||_1 $$ where $|\cdot|^2$ denotes element-wise squared. $A$ is small size (e....
0
votes
0answers
51 views

Solving a non-convex optimization problem using fmincon

I am trying to solve a non-convex optimization problem using fmincon(). At each iteration, I am iteratively looking for the optimum value and when the termination ...
0
votes
0answers
30 views

Minimizing the ratio of two specific non negative quadratic convex functions

$F$ is $m\times m$ diagonal, with real non negative elements $D$ is $n \times m$ complex $P$ is $n \times 1$ complex $A$ is $m \times 1$ complex. Minimize $\Gamma(A)$, with respect to $A$. $$\...
2
votes
1answer
84 views

Is there an optimization scheme/algorithm that converges, for this non-convex scenario but with some special properties

I have a smooth function $f(x) = \frac{g(x)}{h(x)}$ that is the ratio of two smooth convex functions $g(x)$ and $h(x)$. It is known that $f(x)$ has a global minimum, achieved at the unique point $x_0$....
2
votes
1answer
133 views

A robust algorithm to sort a non-convex polygon vertices

Let v_{0},...,v_{N-1} be N points in a Cartesian xy plane defining the vertices of closed polygon (i.e. v_{N} = v_{0}). Let P_{0}...
1
vote
0answers
33 views

Efficient numerical optimization of an “almost separable” function

I have come across an optimization problem with the following objective function: $$f(x_0,y_0,z_0,x_1,y_1,z_1,...,x_N,y_N,z_N) = \sum_{i=0}^N f_i(x_i,y_i,z_i, \alpha(x_{i+1}-x_i) + \beta(y_{i+1}-y_i))...
1
vote
1answer
138 views

Piecewise-Linear Quadratic Optimization for an “Almost Convex” Problem

I have a 7-14 dimensional piecewise linear cost function I'd like to minimize with two quadratic terms of the form: $$ f(X) = X^tCX + d \sum_i |x_i-x^*_i|^2 + \sum_i P_i(x_i-x^0_i) $$ $$ \sum_i x_i ...
0
votes
1answer
55 views

reduced system: primal-dual interior point method for nonconvex constrained problem

When solving a reduced KKT system of a nonlinear (and nonconvex) constrained program after eliminating slack and dual variables, how do we actually take the next step in a primal-dual method? For ...
0
votes
1answer
61 views

Why can't we discretize continuous domains in distributed non-convex constraint optimization problems?

Consider a non-convex distributed optimization problem. We have $X$ = a set of $n$ decision variables: $x_i$ where $i=1..n$ and $x_i \in R$, the set of Reals. We have $F$ = a set of $m$ constraint ...
1
vote
0answers
65 views

Minimizing the products of variables

My problem Maximize $$\min_{i} \{\ c_i \cdot \prod_{j \in A(i)} {x_{j}} \prod_{j \in B(i)} {y_{j}} \} $$ Subject to \begin{align} &\sum_{j \in C(k)} x_{j} = 1,\ \forall k \\ &l \leq x_{j}...
1
vote
0answers
182 views

Constrained optimization: Stationary point vs. Nash point

1s question: definition of stationary point for constrained optimization As far as I know, a stationary point of a constrained optimization problem is a stationary point of the Lagrangian (that has ...
4
votes
1answer
148 views

Optimization of non-smooth, non-convex, locally Lipschitz functions of type exp(-abs(x))

What would be the numerical method of choice to find minima in a non-smooth, non-convex, locally Lipschitz function $f: \mathbb{R}^n\rightarrow \mathbb{R}$. The function $f$ is mostly smooth but ...
2
votes
0answers
62 views

Global optimization with known distributions of some variables

I'm solving simple single-objective multidimensional global optimization problem using various stochastic algorithms like Monte-Carlo, GA and other evolutionary approaches. The task is formulated as ...
2
votes
2answers
187 views

Approach to handle a quadratic constraint xy <= z

I have non-linear constraints like $ x_1x_2\leq x_3 $ where $ x_1,x_2,x_3\geq 0 $. The objective is linear, and all other constraints are linear, too. I know that I can transform the product as $ ...
1
vote
0answers
112 views

preconditioning LBFGS?

I want to minimize an energy of the form $$V_1(\mathbf{x}) + V_2(\mathbf{x})$$ where $V_1$ is much stiffer than $V_2$. When I try to use LBFGS, convergence is extremely slow, as the solution ...
6
votes
1answer
382 views

Global convergence in trust region algorithm

I was reading about TR methods and there are some terms, which are confusing for me. It says, method is globaly convergent. What does it really mean? Converges to global minima, or converges for ...
1
vote
0answers
224 views

Numerical solution of non-linear advection equation other than inviscid burgers

I am solving a non-linear advection equation of the form $u_t + f(u)_x = 0$ where $f(u)$ is a complicated function of $u$. I am solving this equation using a first order fully implicit scheme (...
20
votes
3answers
7k views

Why should non-convexity be a problem in optimization?

I was very surprised when I started to read something about non-convex optimization in general and I saw statements like this: Many practical problems of importance are non-convex, and most non-...
1
vote
0answers
124 views

Minimization of the sum of convex function and non-linear non convex function

I'm trying to minimize the unconstrained scalar sum of a quadratic convex function (to which a convex optimizer is readily applied) and a non-linear and non-convex function which is differentiable. ...
3
votes
2answers
1k views

Subgradients of non-convex functions

In these notes (section 2.3), it is stated that: A point $x^*$ is a minimizer of a function $f$ (not necessarily convex) if and only if $f$ is subdifferentiable at $x^*$ and $0 \in\partial f(x^*).$ ...
3
votes
1answer
226 views

Symmetric nonnegative matrix factorization

Suppose $A\in\mathbb{R}_+^{n\times n}$ is symmetric. I would like to factorize $A\approx UU^\top$ by solving $$ \begin{array}{rl} \min_U & \sum_{ij} \left(A_{ij}\ln\frac{A_{ij}}{[UU^\top]_{ij}}+[...
2
votes
0answers
90 views

non convex, non linear optimization involving matrix differential equation solution

I'm trying to develop an inferential procedure for a multivariate dependent Markov process. Basically, the procedure could be considered as a non linear regression, with a known dependence structure ...
1
vote
0answers
186 views

Minimal surface finite differences problem - Matlab assemble

I face to the following problem: $$(1+u_x^2)u_{yy} - 2u_xu_yu_{xy} + (1+u_y^2)u_{xx}=0.$$ Problem needs to be discretized and assembled. Does anybody know how to proceed in Matlab?
2
votes
0answers
345 views

Finite difference scheme for solving nonlinear least-squares problem

I am dealing with following problem: $$ \min_{u,\gamma}\Bigg\{ \frac{1}{1000} \iint_{S_2} {\gamma (x,y)^2 dxdy} + \iint_{S_2} {[u(x,y) - u_0 (x,y)]^2 dxdy} + \iint_{S_2} {[\Delta u(x,y) - \gamma (...
4
votes
2answers
169 views

non-convex quadratic with only one quadratic constraint?

I have a non-convex optimization problem in the form: \begin{align} \min_{b,\xi,\eta} \sum_{i=1}^{n} b_i \xi_i + \gamma \Vert \eta \Vert \cr \text{s.t.} b\geq 0, b^\mathsf{T} 1 = 1,b_i \leq \frac{1}{n-...
4
votes
2answers
567 views

Finding a global minimum of non-convex quasi-smooth function that is costly to evaluate

I have a bounded non-convex function in 10-dimensional space. The function is quasi-smooth, you can imagine a histogram, here is an illustration, it just shows the idea and not related to my ...
5
votes
2answers
206 views

Is there guaranteed global solver for such an eigenvalue problem?

The original nonlinear optimization problem I have is as follows: For constant symmetric matrices $A=A^T, B_i=B_i^T(\forall i\in\mathbb{N}) \in \mathbb{R}^{n\times n}, \text{rank}(A)=n,$ $$\arg\min\...
0
votes
2answers
116 views

Nonconvex Optimization

Consider the following optimization problem: $\text{max}_{p} \quad ||p||^2 \\ s.t: x\geq 0\\ p\in D$ where $D$ is a convex set. Is this problem $\mathcal{NP}$-hard?
3
votes
2answers
488 views

Affect of approximating a non-differentiable function on optimisation of minimisation

I am looking at a problem of constrained minimization, where the function to be minimized contains the Heaviside function, and as such is not twice continuously differentiable. My question is what ...
0
votes
1answer
452 views

Non convex optimization

I have the following Max Min optimization problem that appears to be non convex. link where t p c are my variables and all others are constants. I took the eigen values of the hermetian part of the ...
6
votes
2answers
2k views

linear independence constraint qualification: what to do when they don't hold?

I want to solve a general nonlinear constrained optimization problem $$\min_q\ f(q)\quad \textrm{s.t.}\quad g_i(q) = 0,\ h_j(q) \geq 0.$$ The problem is that while the equality constraints $g_i(q)$ ...
2
votes
3answers
1k views

Global optimisation with discontinuous objective

I'm looking at a global minimisation problem on the $n$-sphere ($n$ of the order 10--50) but with a complete swine of an objective --- it is (effectively) a black box; it is piecewise smooth but with ...
1
vote
0answers
19 views

Reduction for NP-hardness [duplicate]

Consider the following optimization problem: \begin{align} \text{Min}_{i\neq j\neq s\neq t} |x_i x_j-x_sx_t|\\ s.t: Ax=b\\ x\geq 0; \end{align} This problem can be seen as an instance of non convex ...
3
votes
2answers
709 views

NP-Completeness

Consider an instance of non-convexoptimization problem: It seems that this problem is NP-complete. How can I find a suitable reduction for this?
7
votes
1answer
240 views

Algorithm for dealing with medium-size non-convex QCQP

I have the following problem in $x \in \mathbb C^{205}$ $$\displaystyle\min_{x}x^HAx$$ subject to the following constraints $$x^HBx = 1$$ $$x^HC_ix = 0$$ for $i \in \{0,1,\dots,203\}$, where $A$ ...