A non-linear optimization problem includes an objective function (to be minimized or maximized) and some number of equality and/or inequality constraints where the objective or some of the constraints are non-linear. Use this tag for questions related to the theory of solving such problems or for ...

learn more… | top users | synonyms

7
votes
1answer
3k views

The composition of two convex functions is convex

Let $f$ be a convex function on a convex domain $\Omega$ and $g$ a convex non-decreasing function on $\mathbb{R}$. prove that the composition of $g(f)$ is convex on $\Omega$. Under what conditions is ...
3
votes
1answer
124 views

minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$
2
votes
1answer
170 views

Control on Conformal map

Let $\Omega$ be smooth simply connected open set of $\mathbb{R}^2$ such that $\overline{\Omega}$ is compact. We know that there exists a conformal diffeomorphism $\psi$ from $\mathbb{D}$ to $\Omega$. ...
1
vote
1answer
56 views

Min problem by using Lagrange method

$$\min x^2+y^2 $$ $$\text{s.t.}\ \ (x-2)^2+(y-3)^2\le 4 \ \ \ \text{and} \ \ \ x^2=4y$$ Please explicitly solve this question by using Lagrange multiplier method. I accept $(x-2)^2+(y-3)^2=4$ ...
1
vote
1answer
57 views

A non-linear optimization problem

I have the following optimization problem on the variables $a_1, ..., a_n$: $$ minimize \frac{\sum_{k=1}^{n}\max(k\cdot a_{k},1)}{\sum_{k=1}^{n}a_{k}} $$ $$ such\ that\ \ 0\leq a_k\leq 1\ \ \ (k=1, ...
3
votes
1answer
2k views

Prove the supremum of the set of affine functions is convex

Let $\langle f_i \rangle _{i \in I}$ be a family of affine functions on a convex and compact set $\Omega \subset \mathbb{R^d}$ such that $f_i = a_i.x +b_i$ for $x \in \Omega$. Prove that f, defined by ...
0
votes
1answer
95 views

How to perform the optimization when gradient is a matrix $\mathbf{R}^{n\times n}$

I am trying to optimize this cost function by using Gauss-Newton method. $$f = \sum_{i = 1}^n Tr{(Z^TZ)}$$ where $Z$ is a $4\times4$ matrix and it is a function of real vector ...
0
votes
2answers
110 views

Constraint minimization of sum of Non-symmetric matrices

I am trying to find closed form solution to following problem \begin{equation} \begin{array}{c} \text{min} \hspace{4mm} \big(\lambda_1\left( \mathbf{y}^T V^{(1)}\mathbf{x} \right)^2 + ...
0
votes
1answer
210 views

Finding Shortest distance between a Sphere and Ellipsoid?

Suppose that ,I have a Sphere and an ellipsoid as Sphere: $(x-x_1)^2 + (y-y_1)^2 + (z-z_1)^2 = R_1^2$ Ellipsoid: $\large\frac{(x-x_2)^2}{a^2} + \frac{(y-y_2)^2}{b^2} + \frac{(z-z_2)^2}{c^2} = 1$ ...
0
votes
2answers
58 views

Maximum of convex functions

how can i proof that: If $f_1, . . . , f_m$ are convex functions,than function $F(x) = \max(f_1(x), \dots , f_m(x))$ is convex? thanx for help.
7
votes
7answers
6k views

Operations research book to start with

for somebody having a quite strong background in Mathematics, which are some good books for the domain of Operations research? I guess there are textbooks covering topics like linear and nonlinear ...
8
votes
3answers
457 views

Optimization problem for a parity-check code

I have $n$ data blocks and $k$ parity blocks distributed across $m$ boxes where each box can contain atmost $b$ blocks. Each parity block is Ex-or of some data blocks (for ease of understanding we can ...
8
votes
1answer
312 views

Minimization of $\sum \frac{1}{n_k}\ln n_k >1 $ subject to $\sum \frac{1}{n_k}\simeq 1$

Looking at an algorithm for minimizing $\sum_{k=1}^{m} \frac{1}{n_k}\ln n_k > 1$ subject to $\sum_{k=1}^{m}\frac{1}{n_k} = 1$ in which $n_k$ are positive and in general non-sequential integers, I ...
5
votes
2answers
793 views

Multilinear optimization

Are there any efficient algorithms to solve, multi-linear objective and multi-linear constraint optimization problems? The multilinear functions are sums of bilinear, trilinear (and so on) terms ...
2
votes
1answer
955 views

When $\min \max = \max \min$?

Let $X \subset \mathbb{R}^n$ and $Y \subset \mathbb{R}^m$ be compact sets. Consider a continuous function $f : X \times Y \rightarrow \mathbb{R}$. Say under which condition we have $$ \min_{x \in ...
0
votes
1answer
25 views

Optimization involving integrals with varying limits

What are the common methods and tools to tackle optimization problemsinvolving integrals. To be precise lets consider the following optimization problem that I came across with: ...
5
votes
2answers
90 views

General solution to a system of non linear equations with a specific pattern

I am seeking a general solution to a system of non linear equations with a specific pattern: Order 1: $$ x_0 = a^2 + b^2 $$ $$ x_1 = 2ab $$ Order 2: $$ x_0 = a^2 + b^2 + c^2 $$ $$ x_1 = 2ab + 2bc ...
5
votes
0answers
304 views

(easier version)What is a working example for finding the maximum of a algebraic function $f(a,b,c,d,e)$ with 4 equality …

edit 2: If you are founding an answer would be interesting to you, please upvote this question, because i may use those point in order to start a new bounty. Edit 3: Can somebody answer? Edit 4:I ...
4
votes
0answers
188 views

Why Compactness is Necessary at Minimax Theorem

According to Von Neumann's minimax theorem, I have $$\max_{x\in X} \min_{y\in Y}f(x,y)=\min_{y\in Y} \max_{x\in X} f(x,y)$$ for some compact sets $X$ and $Y$ and a convex (in $y$), concave (in $x$) ...
3
votes
0answers
98 views

If this problem is not unbounded, what's wrong in this dual derivation?

In a paper with 100 citation, Robust Support Vector Machine Training via Convex outlier Ablation, a convex relaxation is used. In this paper, a form of robust svm proposed: \begin{align} \min_{0\leq ...
3
votes
1answer
1k views

Intuition for gradient descent with Nesterov momentum

A clear article on Nesterov’s Accelerated Gradient Descent (S. Bubeck, April 2013) says The intuition behind the algorithm is quite difficult to grasp, and unfortunately the analysis will not be ...
3
votes
1answer
196 views

Newton optimization algorithm with non-positive definite Hessian

In the newton optimization algorithm to find the local minimum $x^*$ of a non-linear function $f(x)$ with iteration sequence of $x_0 \rightarrow x_1 \rightarrow x_2 ... \rightarrow x^*$ all $\nabla ^2 ...
3
votes
2answers
173 views

Optimization for constrained problem

I'm reading about Lagrange multipliers from a Pattern recognition book appendix and on one point the following is stated: $\begin{align} ...
3
votes
1answer
301 views

Finding a function that satisfies constraints numerically

I have the following system of equations for function $p(y)$ and I need help debugging my solution: $$\begin{align} 0&=\log(p(y))+1-\lambda-\gamma y^2-\eta ...
2
votes
1answer
304 views

Does the uniqueness of solutions to convex optimization with linear constraints hold in n>3 dimensions?

This is a repost of an earlier question, where I think I was not clear enough in what I was asking: I am examining the following optimization problem, for which I would like to know if, when a ...
1
vote
1answer
45 views

how to find the solution of this cost function?

I have the following cost function. $J = \sum_{i=1}^N a\, Trace(W^TX_iW) - b\, Trace(W^TY_iW)$ Where $X_i$ and $Y_i$ are symmetric matrices, $a$ and $b$ are scalars. How can I find W?
1
vote
2answers
261 views

Local optimality of a KKT point.

Consider the problem \begin{equation} \min_x f(x)~~~{\rm s.t.}~~~ g_i(x)\leq 0,~~i=1,\dots,I, \end{equation} where $x$ is the optimization parameter vector, $f(x)$ is the objective function and ...
1
vote
1answer
147 views

Solving a Non-linear Multivariable System of equations

How would I go about solving a system of nonlinear equations where the highest degree is two? For example: $$f_1(x) = f_1(x_1, x_2,\dots, x_n) = 0,$$ $$f_2(x) = f_2(x_1, x_2,\dots, x_n) = 0,$$ ...
1
vote
1answer
426 views

Properties of the positive definite Hessian matrix of a convex function

I'm reading about nonlinear programming and I'm having trouble understanding the cool properties that a positive definite Hessian matrix $Q$ of $n$-dimensional function $f: \mathbf{R}^n\rightarrow ...
1
vote
2answers
257 views

What is a convex optimisation problem? Objective function convex, domain convex or codomain convex?

My teacher in the course Mat-2.3139 did not want to answer this question because it would take too much time. So what does a convex optimisation problem actually mean? Convex objective function? ...
1
vote
2answers
334 views

Why nonlinear programming problem (NLO) called “nonlinear”? What does “nonlinearity” actually mean? Is it “not linear” or something different?

My teacher in the course Mat-2.3139 presented the same definition as in Wikipedia for the nonlinear programming problem here but he did not specify what the nonlinearity actually means or what it ...
0
votes
1answer
53 views

Find $\min x^TAy+b^Tx+c^Ty$ subject to $1^Tx=1^Ty=1,x\ge 0,y\ge 0$

The problem seems to be easy but I can't find a solution :( Problem: Given $A\in\mathbb{R}^{m\times n}, A\ge 0, b\in\mathbb{R}^{m}, c\in\mathbb{R}^{n}$. Minimize $f(x,y) = x^TAy+b^Tx+c^Ty$ subject to ...
4
votes
0answers
299 views

Optimizing non linear programs of two variables

The scenario is; We've got $n$ stationary 360$^{\circ}$ sensors in an confined area (each sensor is located at some arbitrary $\left(x,y\right) = \left(x_{n},y_{n}\right)$), once a unit $t$ enters ...
4
votes
4answers
599 views

Approximate a function over the interval $[0, 1]$ by a polynomial of degree $n$ (or less).

To approximate a function $G$ over the interval $[0,1]$ by a polynomial $P$ of degree $n$ (or less), we minimize the function $f:R^{n+1} \to R$ given by $F(a) = \int_0^1 (G(x) - P_a(x))^2\,dx$, where ...
3
votes
1answer
188 views

non linear optimization

How to solve this optimization problem using matlab or some other tool. I know that, this is a convex problem with non-linear constraint $\rho\geq \rho_{min}$ , so i have tried many times it in ...
2
votes
1answer
372 views

Difference: Newton's method, Newton-Rhapson method, Gauss Newton-method.

I would appreciate some clarification w.r.t. algorithms for solving nonlinear systems of equations. 1 - I don't understand the difference between Newton's method and Newton-Rhapson method. In [1], ...
2
votes
2answers
530 views

How to maximize an entropy function?

I'm very novice in optimization and have a convex optimization function of form $\sum_{i,k} p_{k,i}*\log{p_{k,i}} $ to minimize with the following constraints: $\forall i, a_i = \sum_{k=1}^{m} b_k. ...
1
vote
0answers
33 views

Division of linear functions in convex polytope

I am a computer scientist, and find myself needing the following lemma: If f(x)=(g(x))/(h(x)), where g and h are linear and positive with domain the convex polytope d, then extrema of f occur at ...
1
vote
0answers
53 views

How to solve coupled nonlinear ODEs with a algebraic constraints?

Here is the problem I'm currently facing right now, I have set of ODEs which I can solve numerically given the initial condition. But I'm not sure how to go about giving algebraic solution with ...
1
vote
1answer
70 views

A minimization problem

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \left\|\frac{w}{x}\right\|,~w,u\in \Bbb{R}^n$$ where $$\frac{w}{x}=\left(\frac{w_1}{x_1},\ldots, \frac{w_n}{x_n}\right)$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ ...
1
vote
5answers
424 views

Independence of Rotation Matrix Definitions

I am trying to solve a system of non-linear equations. I know that 9 of my variables put together form a 3x3 rotation matrix $$ A = \left( \begin{matrix} a_{11}& a_{12}& a_{13}\\ a_{21}& ...
1
vote
2answers
162 views

Find the range of $x$, given $y_{min} \leq y(x) \leq y_{max}$, where $y(x) $ can be any function ( Updated)

I have a series of inequalities: $$y_{1min} \leq y_{1}(x) \leq y_{1max}$$ $$y_{2min} \leq y_{2}(x) \leq y_{2max}$$ $$..$$ $$y_{nmin} \leq y_{n}(x) \leq y_{nmax}$$ Note that $x\in\mathbb{R}$ The ...
0
votes
1answer
151 views

An Interesting Resource Allocation Problem

Here is the problem: \begin{array}{ll} \text{minimize} & \sum_{i=1}^N \frac{1}{1 + \textrm{exp}(C_i + x_i)}\\ \text{subject to} & \sum_{i=1}^N x_i \le R \\ & x_i \ge 0, ~ i = 1,2,...,N ...
0
votes
0answers
170 views

MiniMax Theorem

Consider the compact sets $X \in \mathbb{R}^n$, $Y \in \mathbb{R}^m$, $A \in \mathbb{R}^n$, $M \in \mathbb{R}^{n \times m}$. For fixed $(\bar{a},\bar{B}) \in A \times M$, by the MiniMax Theorem we ...