Questions tagged [nonconvex]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
0answers
82 views

Black box optimization

I have a simulation which gives a scalar result depending on the choice of some continuous design variables. I am trying to minimize the output of the simulation. As a first step, I want to study the ...
2
votes
0answers
37 views

Convergence of Truncated Newton for non-convex Hessian

I was wondering if anyone could enlighten me about the convergence properties of the truncated newton method in case of a non-positive definite hessian $\nabla^2 f = H$. From the Book 'Numerical ...
2
votes
0answers
109 views

Proving convexity of Frobenius norm and correlation function formulations of an optimization problem

I have been working on formulating my requirements in the form of an optimization problem in a multi-output regression setting. Firstly, I would like to make the variables I used in the problem and ...
1
vote
0answers
70 views

Ramp least squares estimation

With some given $s$ value, let \begin{equation} \begin{aligned} h(\beta)&=\min(\sum_{i=1}^n(Y_i - X_i\beta)^2, s)\\ &=\sum_{i=1}^n(Y_i - X_i\beta)^2-\max(0, \sum_{i=1}^n(Y_i - X_i\beta)...
1
vote
0answers
84 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 \...
6
votes
1answer
158 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
362 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
36 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
102 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
700 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
38 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
343 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
60 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
70 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
71 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
245 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
162 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
73 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
322 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
146 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
509 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
258 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 (...
21
votes
3answers
8k 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
139 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
2k 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
265 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
98 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 ...
2
votes
1answer
253 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
352 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
193 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
645 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
215 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
128 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
558 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
588 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
20 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
738 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
245 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$ ...