Nonlinear objectives, nonlinear constraints, non-convex objective, non-convex feasible region.

learn more… | top users | synonyms (1)

-3
votes
0answers
26 views

How to compute the direction of flattest ascent for a convex function [on hold]

Consider an infinitely differentiable convex function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ at the point $x_0$. So long as $x_0$ is not the minimum, it is well known that we can compute a unit vector ...
2
votes
0answers
24 views

How does one go from convexity to submodularity?

If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular? It would be helpful is someone can share some specific ...
5
votes
2answers
52 views

convert a special case of nonlinear fractional programming into a convex problem

Is it possible to convert a fractional problem (maximization) with objective function equal to the ratio of a concave function and convex function ? This question sound impossible but I have read this ...
-2
votes
0answers
22 views

where I can find an example of higher order nonlinear systems? [closed]

where I can find an example of higher order nonlinear systems for example $6 \times 6 $ dimension ,? I want to applied a linearizion methods.
0
votes
2answers
97 views

Estimating the shift in the $\lambda_{max}$ of a matrix under a diagonal perturbation

Given a matrix $A$ and a diagonal matrix $D$, what ways do we have to estimate, $\lambda_{max}(A+D) - \lambda_{max}(A)$? (Feel free to make other assumptions about the matrices that they are all ...
-1
votes
0answers
55 views

About perturbation of spectral radius of a matrix because of diagonal perturbations

Say I have an off-diagonal symmetric $0,1,-1$ matrix $B$ and a set of $2k$ diagonal matrices, $D_{11}, D_{12}, D_{21}, D_{22},..,D_{k1},D_{k2}$. (you can assume the diagonal matrices to be such that ...
0
votes
0answers
56 views

Is there a space in which the $\vec a$ in $\sin(a_1\cdot x)+\sin(a_2\cdot x)$ is linear?

Suppose one has equations of the form $\sin(a_1\cdot x_i)+\sin(a_2\cdot x_i)=y_i$ for $i=1...n$ (there are also amplitudes and phase shifts, but let's ignore those for now). I want to solve for $\vec ...
1
vote
0answers
39 views

Optimization question: maximize quadratic objective with semidefinite constraints

I recently encountered the following optimization problem: $\max \|AX\|_F^2$ subject to: $X\succeq0$ and $Xb_i\leq c_i$ for a collection of $T$ conditions: $i=1,\ldots,T$. Matrices $A$ and $X$ are ...
0
votes
0answers
24 views

Relaxation of non-convex QCQP with one quadratic and one linear constraint

According to Boyd we know that a non-convex QCQP problem with one quadratic constraint has strong duality with the relaxed SDP or Lagrange counterpart. (check "Convex Optimization" by Boyd, Appendix ...
3
votes
1answer
58 views

Constrained optimization (QCLP) over $x$ with the constraint $x = Az$

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, given a matrix $A$ and a vector $w$, $$ \min_{x ...
5
votes
1answer
89 views

Resource Constrained Routing with Refueling

What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity? Especially modeling ...
2
votes
1answer
55 views

Fixed point iteration on symmetric biconvex function

Suppose $X\subseteq\mathbb{R}^n$ is a convex set and that a function $g(x,y):X\times X\rightarrow\mathbb{R}_+$ is smooth, "strictly biconvex" (strictly convex in $x$ and $y$ independently but not ...
0
votes
0answers
34 views

An obstacle problem

Let $f:[0,T]\to \mathbb{R}$ be an increasing function with $f(0)=0$. We want to maximize $f(T)$ with the following constraints: $|f^\prime(t)|\le M,\quad \forall t\in[0,T]$ $f(t)\le g(t),\quad ...
1
vote
0answers
124 views

Valid KKT Constraint Qualification? Linear constraints not full rank, Jacobian of nonlinear constraints full rank and independ. of linear constraints

For a nonlinear optimization problem having only linear constraints, by the Linearity Constraint Qualification, no further constraint qualification is required for the Karush-Kuhn-Tucker (KKT) ...
3
votes
0answers
66 views

Determining Nullspace Basis such that only one column is deleted or added as row is added or deleted, and remaining columns of basis stay the same

I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, ...
5
votes
2answers
71 views

Discrete optimization problem

Suppose you had $N$ many fixed points $X_1, X_2, ..., X_N$ in some Euclidean space $R^d$ and from these coordinates you had to choose $n$ many of them ($n \leq N$ also being fixed) to form a subset ...
1
vote
0answers
114 views

Why hexagons? The maximal minimum of a sum of cosines on the plane with frequencies on the unit circle

We wish to maximize the minimum of a weighted sum of cosines in the plane, when the frequency components are on the unit circle. Formally: $$\max_{\{ a_i,\theta_i,\phi_i \}_{i=1}^{N} } \min_{(x,y) ...
1
vote
1answer
78 views

Nonlinear least square with quadratic equality constraint

I am looking for an appropriate method or hint to solve the following constrained nonlinear least square problem: $\operatorname{argmin}_X \sum_{i\in I} \|\mathbf{X}_i - \mathbf{X}_{i+1}\|_2^2 + ...
1
vote
1answer
127 views

Maximal minimum for a sum of two (or more) cosines

Please prove (or disprove, and give the correct answer): $$2 =\mathrm{argmax}_{r\geq 1}\min_{x\in \mathbb{R}}\left[\cos\left(x\right)+\cos\left(rx\right)\right] $$ In other words, find $r \geq 1$, ...
1
vote
0answers
37 views

Frobenius nearest non-negative Gram matrix of balanced row-sums

Let $W \in \mathbb{R}^{n \times n}$ be any non-negative real symmetric matrix. For $k \leq n$, let $\mathcal{F} := \{X \in \mathbb{R}^{n \times k} \ | \ X \geq 0, X \mathbf{1} = \alpha \mathbf{1}, ...
2
votes
1answer
161 views

How can I find the maximum value of this function?

For given values of $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$, how can I find the value of: $$ \max_{x \in [0,1]^n} \|Ax+b \|_1 $$ Or is this problem NP-hard?
0
votes
0answers
56 views

Interior point V.S sqp algorithm for large scale optimization

I have an large scale optimization problem that works with fmincon solver within sqp algorithm. But it is so slow. However, ...
2
votes
1answer
85 views

Rate of convergence for cyclic gradient descent

I'm trying to solve the optimization problem $\min_x \frac{1}{n} \sum_{i=1}^n f_i(x)$ where $f_i$ are (strongly) convex, smooth, lower semi-continuous, etc. However, I am not able to do conventional ...
2
votes
0answers
255 views

Programming workbooks in C++ and Research Math [closed]

I know the basics of C++ by taking a few courses and going through "C++ Primer" by Lippman. As a math graduate student, I would love to get my hands on some programming-math exercises geared towards ...
2
votes
1answer
51 views

When is a convex program continuous in its constraint vectors?

Consider $$F(z)=\min ae^{-x}+b e^{-y} s.t. x\ge 0, y\ge 0\text{ and } x+y=z$$ I checked if this function is continuous, but it is not at $z=0$. $F(z)=2\sqrt{ab}e^{-z/2}$ when $z\ne 0$, and ...
0
votes
0answers
97 views

Global and local maxima in a weighted sum of logarithms of linear functionals?

Constrained Optimization Problem Is is possible to describe, and locate efficiently, the maxima of the function $f$, as described below in the parameters $\mathbf{x} = (x_1,...,x_m)$. The constraints ...
1
vote
0answers
29 views

Minimizing sum of functions, while keeping their values non-negative

Suppose we have data $\mathbf{x}_i$, $i\in \{1, \ldots, K\}$, and we're trying to find parameters $\hat{\mathbf{\theta}}$ such that $$\hat{\mathbf{\theta}} = \underset{\mathbf{\theta}} ...
0
votes
1answer
93 views

Can this equation have an explicit solution?

Given $n > 0$, $0 \leq i \leq n$ is an integer, $D = diag(d_1, \dots, d_n)$ is positive definite, $e_i$ is the $i$th column of a $n \times n$ identity matrix, $u \in R^n$ such that $B = D + u * ...
3
votes
0answers
117 views

existence of optimal control

I'm looking for an existential result in optimal control for the following class of problems: Given $T > 0$, $\bar x, \hat x\in\mathbb R^d$, an instantaneous cost function $c:\mathbb R^d\times ...
3
votes
1answer
186 views

Find a line such that sum of perpendicular distances of points to the line is minimized

Given a set of points (column vectors) $S = \{p_1, p_2, \cdots, p_n\} \subset \Re^d$, let $A \in \Re^{n \times d}$ be a matrix of which each row is just $p_i^T$. It is easy to find a unit vector $s_1$ ...
3
votes
1answer
112 views

Constrained vs Unconstrained Optimization

I'm currently working on an optimization problem with a linear objective with linear and nonlinear constraints, i'm facing difficulties reaching a good solution, so i was advised to move the nonlinear ...
0
votes
0answers
32 views

Complexity of optimizing a bi-objective function with integer constraints

I have two different objective functions, each of which can be solved optimally in polynomial time. Does this mean, I can optimize a linear combination of these objective functions in polynomial time ...
0
votes
0answers
114 views

How to decide a value of learning rate for Stochastic Gradient Descent?

I'd like to know how to decide a value of learning rate for Stochastic Gradient Descent (SGD), such as $\eta$ on the following parameter update iteration equation, $w_{i+1} = w_i + -\eta \nabla ...
4
votes
2answers
117 views

Convexity of a (non-symmetric) function of matrices

Let $f : H_{n\times n} (\mathbb{C}) \rightarrow \mathbb{R}$ be the function on Hermitian, positive semidefinite matrices $f(A) = \frac{M_i (A)}{\det(A)}$ where $M_i(A)$ is the determinant of the the ...
4
votes
1answer
82 views

Analysis of first-order methods for constrained convex optimization with approximate oracles

In many first-order optimization methods an oracle is needed whose action enforces the constraint/regularizations. For example, in projected gradient descent, conditional gradient method, and proximal ...
2
votes
1answer
114 views

Optimization over symmetric polynomials

Consider the following constraint satisfaction problem: Let $\alpha_1 , \ldots, \alpha_k \in \mathbb{R}$ be given as well as an error parameter $\epsilon$. Find $p_1, \ldots, p_n$ such that (i) $0 ...
5
votes
0answers
171 views

Characterizing matrices with rank constraint

Given matrix $M\in\Bbb\{0,1\}^{n\times n}$, is there a nice method to characterize $$\mathscr{D}[M]=\{Q\in\Bbb\{0,1\}^{n\times n}:\mathsf{rank}(M-Q)= \mathsf{rank}(Q),\quad M-Q\in\Bbb\{0,1\}^{n\times ...
6
votes
1answer
474 views

Bound on the sum of arguments

Problem: Show that for all real $s,t,u$ and all complex $z$ with $|z|<1$ one has $$(*)\qquad \arg\frac{1-zf(s-u)}{1-zf(s+u)} +\arg\frac{1-zf(t+u)}{1-zf(t-u)}<\pi, $$ where $f$ is the ...
1
vote
0answers
49 views

Likelihood convexification

I am doing constrained vector optimization using a non-convex non-linear likelihood function. My problem is of the following form: $$\begin{align*}\hat Q &= \underset{\vec Q}{\arg\min} -\log ...
2
votes
0answers
76 views

How to solve the following generalized quadratic programming problem [closed]

I want to solve a generalized form of a quadratic programming problem $$\min_x \left(\sqrt{x^TPx}+\sqrt{x^TQx}\right)^2+c^Tx$$, $$\textrm{ s.t. } Ax\le b.$$ Here, $P$ and $Q$ are both positive ...
0
votes
0answers
67 views

Specific optimization problem solution procedures

Is there a standard procedure to solve following two optimization problems? $$\mathsf{Problem\mbox{ }I}:\mbox{ }\min_{A\in\{0,1\}^{n\times n}:rk(A)=r}\mbox{ }\max_{R,S\in\Bbb R^{n\times ...
4
votes
2answers
232 views

Convexity of a function of matrices

Let $A$ be an $n\times n$ positive-definite matrix. Let $0<\lambda _1 \leq \lambda_2 \leq \lambda _3 \ldots \leq \lambda _n$ be the eigenvalues of $A$. Let $n\geq k\geq 1$. Is the function $f(A) = ...
1
vote
0answers
56 views

modern exposition of exact ground state of classical XY model or Ising model

What is the state of art technique in solving exact ground state of Heisenberg model, meaning minimization of the H terms (hamiltonian) provided infinite spin space? ...
5
votes
0answers
212 views

Find subset of collection of sets whose intersection has minimum average value

Let $a_1,\ldots,a_n>0$, and let $S_1,\ldots,S_d\subset\{1,\ldots,n\}$ (all non-empty). For any $I\subseteq\{1,\ldots,d\}$, define $S(I)=\bigcap_{i\in I} S_i$. Given some $1\leq s < d$, consider ...
1
vote
0answers
42 views

Optimization of a multilinear function over a product of hypersimplices

Let $P = \Delta_1 \times \cdots \times \Delta_N$ be the Cartesian product of $N$ hypersimplices. Let $f : P \to \mathbb{R}$ be a multilinear function of $N$ variables, ie $x_i \mapsto f(x_1, \ldots, ...
0
votes
0answers
29 views

non-coherent estimation problem

I have the following signals $$\left[\begin{array}{c} y_{mn} \\ y_{nm}\end{array}\right] =\left[\begin{array}{c} x_{n} \\ x_{m}\end{array}\right]h_{nm} +\left[\begin{array}{c} e_{mn} \\ ...
2
votes
0answers
141 views

Solution of a linearly constrained quadratic programming problem [closed]

What is the solution of the following optimization problem: \begin{align} &\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\ &\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}. ...
2
votes
0answers
51 views

Sequence transformations that are entropy invariant

Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Define entropy of $\mathcal{A}=\{a_i\}_{i=1}^m$ by ...
5
votes
1answer
183 views

Finding sparsest solution of a linear system

I want to find the solution with most zero-components for the following problem: $Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...
1
vote
0answers
42 views

Limiting Entropy of deterministic sequences - 2

Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Given $\{a_i\}_{i=1}^m$, let $\mathcal{P}_a$ be limiting distribution ...