Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [non-convex-optimization]

A non-convex optimization problem is one where either the objective function is non-convex in a minimization problem (or non-concave in a maximization problem) or where the feasible region is not convex.

0
votes
2answers
41 views

What is the role of Tikhonov regularization in optimization?

Suppose I have the following objective function $$ L = \frac{1}{|X|}\sum_{x \in X} \| \hat{y} - y \|^2_2 + \lambda \|w\|_2^2 $$ where $X$ are my data, $\hat{y}$ the prediction, $y$ the target, $\...
0
votes
0answers
29 views

How to linearize a $1$-norm equality constraint?

Let $x, y \in \mathbb{R}^n$ be fixed vectors of $1$-norm $C$. My optimization problem is the following $$ \underset{\beta \in \mathrm{R}^n}{\text{minimize}} |\beta |_M \\ \text{subject to} \\ |x+...
0
votes
0answers
21 views

Which of these formulations is more efficient regarding the alternating optimization scheme?

I want to solve a multivariate optimization problem which is the more complex form of the following: $$\min_{A\in I,X\in J} \|Y-AX\|_F^2+\lambda \|Y-CX\|_F^2,$$ where $(Y, C, A, X)$ are matrices with ...
2
votes
1answer
38 views

Smallest trace of a matrix product where one is given and the other is orthogonal

What are the optimal solution and optimal value for the following semidefinite program $$ \min_{ V } \{ \mbox{tr} (V\Sigma) : VV^T=I \}$$ where $\Sigma$ is a given positive semidefinite matrix, and ...
0
votes
0answers
10 views

Do BFGS and L-BFGS methods converge when the matrix $H=B^{-1}$ is ill-conditioned?

I am using BFGS and L-BFGS to solve an unconstrained optimization problem. The objective function is the Mean Euclidean Error. The output is given by an Artificial Neural Network. The line search ...
-1
votes
0answers
11 views

Convert QCQP inti SDP using trace [closed]

How can we reformulate q^T*x in a trace fashion, e.i., tr {•}, where q and x are column vectors?
2
votes
0answers
31 views

Non-convex numerical optimization

I am looking for a way how to prove/show that one problem is easier to optimize(more robust to starting guesses) than another. Suppose I have two non-convex functions from $L_1,L_2:\mathbb{R_+}^8\...
0
votes
0answers
38 views

Nonnegative continuous functions on $[0,1]$ attaining maximum value in $\{0,1\}$

I have a strictly positive continuous function $f:=[0,1]\to \mathbb{R}^+$ that I need to maximise. $f$ is actually a polynomial with some parameters on the coefficients, arising in an expected value ...
0
votes
0answers
31 views

Non-convex QCQP with embedded variable

I have the following problem whose optimal solution (if possible), I would like to find. $\min_{\mathbf{f}} \left\| \mathbf{L}_1 \mathbf{f} \right\|^2_2 + \left\| \mathbf{L}_2 \mathbf{f} \right\|^2_2 ...
1
vote
1answer
65 views

Non linear optimisation with min functions

I have the following nonlinear optimisation problem under bounds constraints and involving $\min$ functions and the euclidean norm in the objective function : $$\underset{a,b,c,d}{\min} \Big\Vert \...
1
vote
1answer
15 views

Reference on Lipschitz property of the infimum of a family of Lipschitz functions

I can prove the following fact: the infimum, or supremum, of any family of L-Lipschitz functions is L-Lipschitz, as long as the constant L is fixed. However, since this is a very basic result, I am ...
0
votes
0answers
28 views

How important is the ratio of negative eigenvalues to the convexity of the optimization objective?

I have to minimize $f(x)$ with the Hessian matrix $H \in \mathbb{R}^{n\times n}$. Considering $H$ has one positive eigenvalue with the value of $10^5$ and the rest are equal to $-1$. In that case, can ...
0
votes
1answer
30 views

Optimizing a sum of functions

I'm not an expert in optimization, but I am currently working on a problem where I need to maximize/minimize a function of the form, \begin{equation*} g(\alpha_0, \alpha_1) = \displaystyle \sum_{i=1}^...
1
vote
0answers
40 views

Rewrite $ \min_{q\in Q_0} \sum_{x=1}^X |m_x(q)| $ with linear objective function

I have the following optimization problem $$ \min_{q\in Q_0} \sum_{x=1}^X |m_x(q_{1})| $$ where $q\equiv (q_1,q_2)$ is a vector that should satisfy a bunch of non-linear constraints collected in $...
0
votes
0answers
23 views

Linear convergence in iterates but not linearly convergent in function values or viceversa

In optimization literature, there are examples, where both iterates and function values are linearly convergent. For instance if the function is strongly convex and has Lipschitz continuous gradient, ...
0
votes
0answers
24 views

SOCP constraint vs Quadratic constraint - trust region methods

I'm implementing code for performing sequential convex optimization based on trust regions, but I have some doubts because I haven't found a unique approach. Suppose we want to minimize a convex ...
0
votes
1answer
31 views

Why the constraints in optimization problems are preferred to be convex?

Specifically in SVM, it is preferred to have a convex constraint. The preference given to a convex optimization objective is straight-away understandable (to ensure convergence at a global optimum), ...
0
votes
0answers
44 views

How relevant are theoretical convex optimization convergence rates in practice, when parameters are unknown and function may be nonconvex?

There are many theoretical results known on convergence rates for various (possibly stochastic) convex optimization problems. For example, the popular review on optimization algorithms for machine ...
0
votes
1answer
31 views

Does ADMM work for nonconvex optimization problems?

I need to solve the following nonconvex optimization problem: \begin{equation} \begin{split} \min_{x,y}\quad &f(x)+g(y)\\ \mathrm{s.t.}\quad &Ax+By=b \end{split} \end{equation} where $f$ is ...
0
votes
0answers
35 views

How to determine the convexity of multiple matrix variables function?

This formula is : $$f(W,V,B) =\|XW-V\|^2_F +\|Y-VB\|^2_F +\operatorname{tr}(V'LV) +2\operatorname{tr}(W'DW),$$ where $X$, $Y$ are constant matrices and $L$ is constant laplace matrix. Suppose $D$ is a ...
0
votes
0answers
41 views

How to solve a non-convex programming problem?

Let $A$ and $C\ $ be $n\times n$ symmetric matrices, and $A\bullet C=Tr(A^TC)$. Let $S\subseteq [n]\times [n]\times [n]$. Define a non-convex programming problem as follows. \begin{equation} \begin{...
0
votes
1answer
137 views

How to prove a matrix function is convex or nonconvex?

I have a function of three matrix variables. But now, the authors fix two of them, then update one, and I cannot understand how this function is convex in each iteration in the paper. This formula is ...
2
votes
1answer
122 views

What is the maximum value of $x^TAx$ subject to $x\in\{\pm1\}^n$?

Let $A \in \mathbb{R}^{n\times n}$ be symmetric and positive definite. What is the following maximum? $$\max_{x\in\{\pm1\}^n}x^T A x$$ My attempt: if all $a_{ij}\geq 0$, then \begin{equation} \...
0
votes
0answers
39 views

Quadratic program reformulation maximum to minimum

I am newbie in optimization problem, I have the following optimization problem: $$\max \quad \frac{1}{2}x^THx - q^THx$$ $$\text{s.t.} \;\;l\leq x \leq u$$ where $H, q$ are known constants, and H is ...
0
votes
0answers
7 views

Numerically determining if a critical point is a saddle point in the presence of inequality constraints

I have a constrained optimization problem $$\min_{\mathbf{x}} f(\mathbf{x}) \quad \mathrm{s.t.}\quad g(\mathbf{x}) = \mathbf{0}, h(\mathbf{x}) \geq \mathbf{0}$$ and need to probe if a critical point $\...
3
votes
0answers
52 views

Maximize a sum of posynomials

I am dealing with an optimization problem where I have to maximize a sum of posynomials subject to affine constraints. The formulation of the problem (P) is as follows: $$\text{maximize } f(\...
0
votes
1answer
25 views

Analytical solution of a non convex function optimization

I think this is probably obvious but I can not find a formal proof or any other reference on this online. My question is - If there exists a finite number of local minima/maxima of a non-convex ...
0
votes
0answers
17 views

Minimax programming with constraints

I want to solve the following optimization problem: $min\;max_{\mathbf{R}}\,E(\mathbf{R},\mathbf{w}),\;s.t., \mathbf{w}_{l}\leq \mathbf{w}\leq \mathbf{w}_{u}\;and\;\mathbf{R}_{l}\leq \mathbf{R}\leq \...
0
votes
0answers
39 views

L1 constraint on vectors of a matrix

I am trying to solve below minimization problem (rank $k$ approximation of a matrix) which is somewhat sparse SVD \begin{equation*} \begin{aligned} & \underset{B,\Lambda}{\text{minimize}} & &...
0
votes
0answers
29 views

Is it possible to “solve” iterative (convex/non-convex) optimization problems via learning (one-shot)?

I might be asking subjective question--and perhaps the answer may both be yes and no depending on the situation/problem definition. Nevertheless, I dare to ask. My questions are two fold: (1) Is it ...
0
votes
0answers
33 views

Trying to formulate optimization problems as a linear program (LP) or a quadratic program (QP)

I'm trying to formulate and determine the variables, objective, and constraints for the minimization problem $\min_\vec{x}f(\vec{x})$ for the following functions $f \in$ ($q,r,s,t$) as linear program (...
0
votes
1answer
47 views

Obvious claim about Kurdyka-Łojasiewicz inequality

Let $H$ be a hilbert space and $f$ a closed, proper, convex function from $H$ to $\mathbb{R}\cup\infty$. We write $[f < \mu]$ to denote the set $\{x\in H: f(x)<\mu\}$, $d$ for the hausdorff ...
0
votes
0answers
34 views

Constraint on product of matrices

I am trying to solve the below optimization problem \begin{equation*} \begin{aligned} & \underset{{A}, {B}, {\Lambda}}{\text{minimize }} & & \|X - AB\Lambda C^TD^T|_F^2 \\ & \text{...
0
votes
1answer
59 views

Diagonal constraint on product of matrices

I am trying to solve the below optimization problem \begin{equation*} \begin{aligned} & \underset{{A}, {B}, {\Lambda}}{\text{minimize }} & & \|X - AB\Lambda B^TA^T|_F^2 \\ & \text{...
0
votes
1answer
72 views

Proving convexity of the negative log complementary probability: $-\log\left(1 - \frac{\exp(x_i)}{ \sum_j \exp(x_j)}\right)$

I am familiar with the convexity proof for \begin{align} f_i(x) &= -\log\left(p_i(x)\right) = -\log\left(\frac{\exp(x_i)}{ \sum_j \exp(x_j)}\right) = \log\left(\sum_j \exp(x_j)\right) -x_i. \end{...
0
votes
2answers
34 views

stopping criteria for mathematical optimisation: objective function target, rather than convergence

Researching stopping criteria for mathematical-optimisation algorithms, any libraries I look at (e.g. matlab, apache commons math) only have iteration limits and convergence criteria (e.g. convergence ...
1
vote
1answer
37 views

Solving an integer (boolean) constraint satisfaction problem

I have a 0-1 integer constraint satisfaction problem of the following form: find binary vectors $x = (x_1,\dots,x_m) \in \{0,1\}^m$ and $y = (y_1, \dots,y_n) \in \{0,1\}^n$ that satisfy the ...
0
votes
0answers
16 views

What algorithm/method can solve this nonconvex problem?

I want to solve this optimization program: $$ \min_{H, f, x_i, \lambda_i} \sum_{i=1}^N ||x_i - y_i||_2^2 $$ subject to $$ H x_i + A_i^T \lambda_i= -f \qquad i = 1...N $$ $$ A_i x_i = b_i \qquad \quad \...
1
vote
0answers
25 views

Can the duality gap be infinite?

Given a primal problem $$ \min_{x \in \mathbf{R}^2} \{ f(x)|g(x)=0 \} $$ that has a solution $f(x^*)=0$ (where $x^*$ is the value of x that minimizes $f$ such that $g(x)=0$), and given a dual ...
0
votes
1answer
56 views

Finding the optimal value for a dual problem in optimization

Consider the following optimization problem: \begin{align*} &\min_{x_1,x_2 \in \mathbb{R}}x_1x_2\\ &\text{Subject to } x_1^2 + x_2^2\le 1, x_1\ge 0, x_2 \ge 0\\ \end{align*} I have been ...
0
votes
0answers
16 views

How to prove that 0-1 NLP problem is NP-hard?

I have written a binary nonlinear programming problem: $\min_{a,Y}\sum_{i=1}^{N}\sum_{j=1}^{K}\Big[ a(1-x_{i,j})+x_{i,j}(e_1y_{i,j}+e2(1-y_{i,j})+e3y_{i,j}) \Big]$ s.t $ b(1-x_{i,j})+x_{i,j}(t_1y_{...
0
votes
0answers
33 views

Smooth but not convex

In Theorem 4.2. of the following lecture http://users.ece.utexas.edu/~cmcaram/EE381V_2012F/Lecture_4_Scribe_Notes.final.pdf it is shown that when the objective function is smooth and not necessarily ...
1
vote
1answer
30 views

How to Reformulate an Image Constraint in the Dual of a Quadratic Program with Nonconvex Constraints?

I have the following nonconvex optimization problem, for which I want to formulate the dual: $\mathcal{P}:\underset{x}{\text{min}} \quad x^\top A x + b^\top x \\ \quad \ \ \text{s.t.} \quad x\in\{0,1\...
1
vote
0answers
26 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))...
0
votes
0answers
29 views

Construction of a linear programming given a solution

suppose given a solution $(x*, y*)$ of the nonlinear programming solution given below, I try to infer some conditions on the functions involved in the problem. The NLP I would like to solve has the ...
9
votes
2answers
466 views

Stable strict local minimum implies local convexity

Let $\bar{x}\in\mathbb{R}^n$ and $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a $C^2$ function. We have known that if $\nabla f(\bar{x})=0$ and $\nabla^2f(\bar{x})>0$, i.e. $\nabla^2f(\bar{x})$ is ...
0
votes
1answer
67 views

Equivalence of two optimization problems

Consider the optimization problem A defined as $$ \max_{x,y} f(x,y)\text{ subject to } x+y\leq 0. $$ and the optimization problem $B$ defined as $$ \max_{x,y} f(x,y) - \lambda (x+y) $$ where $\lambda$ ...
1
vote
1answer
80 views

Find convex envelope from the non-convex function to prove globally optimal using branch-and-bound

Based on this reference branch-and-bound methods can obtain globally optimal solutions to nonlinear programming problems in which a non-convex function is to be minimized. I have a non-convex function ...
0
votes
0answers
30 views

Maximizing sum of two Rayleigh quotient

Consider the following optimization: \begin{equation} \max_{\boldsymbol{x}} \frac{\boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x}}{\|\boldsymbol{x}\|^2} + \frac{\boldsymbol{x}^T \boldsymbol{B} \...
2
votes
0answers
29 views

On approximation of maximization of quadratic function over a convex set

Given a convex function $f : \mathbb{R}^n \to [0,\infty)$. Let $L = \left\lbrace x \in \mathbb{R}^n \mid f(x) \leq 1 \right\rbrace$ be it's sub-level set and suppose that $L$ is not empty as well as ...