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

0
votes
1answer
39 views

How to solve/deal with the following optimization issue?

I got the objective function $\displaystyle f(\alpha)=\alpha\cdot \left(1-\frac{\binom{N+K}{K}\beta^K}{\sum\limits_{k=0}^{K}\binom{N+k}{k}\beta^k}\right)$, where $N$ and $K$ are positive integers, ...
0
votes
0answers
18 views

Validity of nonlinear optimization with exponential type inequality constraint as KKT / Lagrange multipliers?

Given positive coefficients $h_i, \beta_i$ and $k$ we have the minimization problem $$\displaystyle \min\sum_{i = 1}^n h_{i}s_i\\ \text{subject to} \displaystyle\sum_{i = 1}^n \alpha^{s_i}\beta_i \leq ...
1
vote
1answer
33 views

Generalized Farkas Lemma

Farkas lemma can be stated as follow: If for all $\mu$ such that $\mu^T\cdot a_i \geq 0$ implies that $\mu^T\cdot b \geq 0$ then $b=\sum \lambda_i a_i$ with $\lambda_i \geq 0$ I need a generalized ...
0
votes
0answers
16 views

Converting an optimisation problem to an integer linear formulation

Is there a way to convert the following to a linear formulation? In other words, is there a workaround for the absolute value in the objective function? Minimise: ...
0
votes
1answer
26 views

How to linearize a constraint of the form of a product?

Is there a way to linearize a constraint of the form: $$\prod\limits_{ i=1 }^{ n }y_i\geqslant b,$$ where $y_i$ are discrete variables in the set $\{1,2,\ldots,2^m\}$ for some $m>2$ and $b$ is a ...
1
vote
1answer
58 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$ ...
0
votes
0answers
21 views

(Convex) reformulation of a nonlinear program

Consider the following program: \begin{eqnarray*} \min_{\mathrm x}\sum_{i=1}^{n}{\sum_{j=1}^{n}{\big(x_i(Sx)_i-x_j(Sx)_j\big)^2}}\\ \mathrm{subject\; to}\quad \sum_{i=1}^{n}{x_i}=1 \\ x_i\geq 0 ...
1
vote
1answer
78 views

What is the difference between min and max constraint problems?

For example, let's consider these two min max optimization questions (1) $$\max \ \ g(x,y)=xy$$ $$ \text{s.t. } x^2+y^2=1$$ (2) $$\min \ \ g(x,y)=xy$$ $$ \text{s.t. } x^2+y^2=1$$ Solution: By ...
0
votes
1answer
25 views

Condition for stationary point without maxima or minima

Consider $f(x) = \frac{1}{2}x^{T}Qx - c^{T}x$. Under what conditions on $Q$ does $f$ have a stationary point, but no local maxima or minima? I need help refining my thoughts here. I don't think I ...
0
votes
1answer
100 views

Binary integer program with nonlinear function

I have given a matrix $A^{m \times n}$ and I am looking for a submatrix $B^{m \times k}$ for a given $k$ that maximizes the following expression: $$\sum_{i=1}^m \max_{j \in \{1 \dots k\}} B_{i,j}$$ ...
0
votes
1answer
60 views

Prove or disprove convexity

I am dealing with the following function $f:\mathcal{R}^n \rightarrow \mathcal{R}$, how can I prove or disprove the convexity of the following function? $$f(x)=\|x-\frac{Ax}{\langle x,b\rangle}\|_2$$ ...
1
vote
0answers
18 views

Is there any “equivalence” to maximizing $\inf{f_i(y)}$?

I have to maximize the function $g(y) = inf_i{\|y - x_i\|_2}$ subject to $y\in B_0(1)\subset\mathbb{R}^n$. Then I thought that maybe there is an averaging or mollifying of the functions (using ...
-3
votes
1answer
25 views

Solve the above program [closed]

Consider the problem of covering the triangle with vertices at the points $(0, 0), (0, 1),$ and $(1, 0)$ with a ball of smallest radius. $$\min r$$ $$s. t. \> x ^2 + y ^2 ≤ r$$ $$(x − 1)^ 2 + y ^2 ...
-1
votes
1answer
46 views

Find all the points satisfying the Fritz John conditions

Consider the problem $$\min \>x^2+y^2 $$ $$s.t.\> x^2-(y-1)^3=0$$ Find all the points satisfying the Fritz John conditions Solution The FJ conditions are $$2x+\mu_1 2x=0$$ $$2y-\mu_1 ...
1
vote
0answers
36 views

A nonlinear optimization problem with difficult Kuhn-Tucker system of equations

I know about the sufficient optimality theorem Kuhn-Tucker, and this problem can use the Kuhn-Tucker theorem directly, but ridiculously, I got stuck on the system of equations to find one root for ...
0
votes
0answers
11 views

how does sequential axis search work?

I see that some algorithms that need to search for a global minimum in multiple dimension space, say find x and y to minimize f(x,y), instead of searching in x,y simultaniously, starting from initial ...
0
votes
0answers
25 views

What are the general algorithm and precise mathematical language that can optimise the nodes in a graph?

Recently I came across this via social media Out of curiosity (and because I am a visual learner) using the paragraph in the article, I end up drawing some kind of mixed graph, as shown I then ...
1
vote
1answer
29 views

Linear Matrix Inequality - “HOW TO”

I have a tough time understanding how to use Linear matrix Inequality to solve simple inequality problems. I would appreciate a simple "How to" on the following examples. $$ \bar PA + A \bar P - ...
0
votes
0answers
41 views

Non-binding constraints with positive shadow prices (matlab)

The output of fmincon indicates positive shadow price for linear constraints, although the corresponding constraints are not binding. What could be wrong mathematically? I've checked the code but ...
1
vote
1answer
52 views

Transportation problems

i'm a master student at the deparment of statistics. And i will prepare a presentation on transportation problems in the course of optimization (or linear programming / mathematical programming) I ...
1
vote
1answer
90 views

Weakly unimodal function using Golden Section Search

I was going through the Golden Section Search https://en.wikipedia.org/wiki/Golden_section_search and as I understand it should work for every unimodal function. Here, the definition of unimodal ...
0
votes
0answers
12 views

Nonlinear Programming

I have the following non-linear programmig problem that I have arrived at after various manipulations. I have to find the set of values for $x$ and $y$ that satisfy the following: $$ x^{n}+y^{m}=C $$ ...
0
votes
1answer
40 views

About a nonlinear problem using sufficient optimality Kuhn-Tucker theorem

I'm learning nonlinear programming and got stuck on this problem. Here is the problem: Find the minimum of $\theta(x,y) = x^2 + y^2 - 2xy + 3y + 5$, with $x, y \in R$ which satislies $g(x,y) = x^2 ...
0
votes
0answers
44 views

dual feasibility of Kuhn-Tucker condition?

minimize $f(x)$ subject to \begin{align} f_i(x) & \le 0, \quad i \in \left\{ 1,\ldots,m \right\} \\ h_i(x) & = 0, \quad i \in \left\{ 1,\ldots,p \right\} \end{align} Then the Lagrange ...
0
votes
1answer
57 views

Is mathematical programming an analytical or numerical technique?

Is linear programming, mixed-integer programming, integer programming, nonlinear programming, etc. numerical or analytical techniques? I always thought they were numerical methods because you can't ...
0
votes
0answers
28 views

Optimization of Inputs to Monte Carlo Simulation Based on Outputs

I have an optimization process that seems to work, but I want to better understand why it works and whether there's a better way to do what I'm trying to achieve. Basically I am optimizing two (or ...
1
vote
0answers
47 views

min-max optimization problem

how do you solve the following optimization problem to find the global solution? $~~~~~\underset{y}{min} ~ \underset{x}{max} f(x,y)$ subject to $~~~~~g(x)<0$ with knowing that both g(x) and ...
2
votes
1answer
45 views

Some True or False questions on Nonlinear Optimisation (Exam Preparation)

I am currently preparing for a Nonlinear Optimisation exam and am working through some old question papers and came across these True or False questions: When minimizing a convex function over ...
1
vote
1answer
25 views

Mistake in my NLP using Lagrange Multipliers?

I have the following NLP \begin{matrix}\text{Minimize:} &x^2+y^2+z^2 \\ \text{Subject To:} & x+2y+z-1=0 \\ &2x -y -3z-4=0\end{matrix} I need to solve this using the Lagrange ...
3
votes
1answer
65 views

Constrained LQR with a fixed terminal state. Can MPC be applied to this problem?

I am interested in solving the constrained LQR problem with discrete finite time when the target $x$ value is given, but the final $u$ could be anything s.t. constraints. $$\text{minimize }J = ...
0
votes
2answers
15 views

Linking between Square Matrix and Positive Definite Matrix?

I'm not mathematically trained. A module I'm taking this semester needs me to: Show that a square matrix with only diagonal values that are all positive is a positive definite matrix. What is the ...
0
votes
0answers
11 views

Find $\tau$ to minimize $\sum_{i=1}^{T/\tau} max \{ m_1, …, m_i \} $, such that $m_i = \{ d_{i\tau+1}, …, d_{(i+1)\tau} \} $

Suppose $T$ numbers $\{ d_1, ..., d_T \}$ are chosen by an adversay. We have divided the numbers into blocks of size $\tau$, i.e.$\{ d_1, ..., d_\tau \}$, plus $\{ d_{\tau+1}, ..., d_{2\tau} \}$, ...
0
votes
0answers
23 views

Singular value decomposition:Canonical Correlation, Reformulation of the objective function

The CCA method aims to find two loading vectors or projections $\alpha$, $\beta$, the linear combinations of variables in $X$ and $Y$, to maximize the correlation between $\alpha ^t X$ and $\beta^t ...
0
votes
0answers
48 views

Prove that a function is convex

In order to show that if the epigraph is convex then the function $f(x)$ is convex I did like this. Let $x_1,x_2 \in C$, C is a convex set. Then the points $(x_1,f(x_1))$ and $(x_2,f(x_2))$ are in ...
1
vote
1answer
105 views

Proving Convergence of a Derivative Free Method

Hopefully this question is on topic for the mathematics community (rather than the statistics) since the optimization method I am using relies on a statistical model. Well I am building an algorithm ...
0
votes
1answer
25 views

Nonlinear optimization related to symmetric functions

Suppose $f(x,y)\geq 0$ is integrable and symmetric in $x$ and $y$, i.e.$f(x,y)=f(y,x)$. Consider the following nonlinear optimization problem $$\max F(a,b)=\int_0^a\int_0^bf(x,y)dxdy,$$ Subject to ...
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: ...
0
votes
1answer
27 views

Positive definite and semi definite in non linear programming [duplicate]

How can I prove the following. Suppose that A is a square matrix and suppose that there is another matrix B such that $A=B^TB$. a)Show that A is positive semi definite b)Show that if B has ...
1
vote
1answer
36 views

Karush-Kuhn-Tucker NLP

Consider the nonlinear program Minimize: \begin{align}f(x,y) = \frac{1}{2}x^2 - 10xy + 10y^2\end{align} Subject to: \begin{align}2x +y^2 &\le 5 \implies g_1(x,y)=2x + y^2 -5 \le0 \\ ...
6
votes
1answer
169 views

How is the Lagrangian related to the perturbation function?

Given a convex programming problem $$\begin{align*} \text{minimize} &\quad f(x) &\\ \text{such that} &\quad g_i(x) \leq 0 & i=1\dots k\\ & \quad h_j(x) = 0 & j= k+1\dots n ...
0
votes
2answers
36 views

How to make a non-linear problem linear?

I have the following constraint which is the product of multiple binary variables: $1- \prod_i^n (1-(c_i x_i)) >= T$ where $x_i$ is a binary variable, $c_i$ is a constant and $T$ is a constant ...
2
votes
0answers
36 views

solving a collaborative filtering problem

I was reading this paper Bell RM, Koren Y. Scalable collaborative filtering with jointly derived neighborhood interpolation weights. Proc - IEEE Int Conf Data Mining, ICDM. 2007:43-52. ...
0
votes
2answers
93 views

Nonlinear LS regression

• Problem formulation I have to fit the following nonlinear model to a dataset: $$f(x)=\frac{C_1 \cdot a}{a^2 + C_2 \cdot x^2}$$ $a$: fitting parameter $C_1, C_2$: Given constants I can't apply ...
0
votes
0answers
68 views

references: L-BFGS rate of convergence

I was trying to find results about the rate of convergence for the L-BFGS algorithm (in the nonlinear case). What I end up with so far is that the BFGS-Algorithm converges Q-superlinearly this 50 ...
2
votes
0answers
23 views

Linear space transform transformation based on covariance?

I have a linear space of n dimensions with non-overlapping groups characterized by different variation (different covariance matrices). Is there a way to deform non-linearly the space according to an ...
1
vote
0answers
22 views

quasi-newton method converges in at most n+1 iterations

Given $B_{k+1}$ be obtained from $B_k$ using the symmetric rank-one update formula. Assume that the associated quasi-Newton method is applied to an n-dimensional, strictly convex, quadratic function, ...
1
vote
0answers
34 views

Nonlinear Least Squares vs. Extended Kalman Filter

What is the relationship between nonlinear least squares and the Extended Kalman Filter (EKF)? I've learned both topics separately and thought I understood them, but am now in a class where the EKF ...
0
votes
0answers
29 views

Is it true that there exist exactly ${k\choose n}$ bases that lead to this basic feasible solution?

Let a matrix $A=\left(A_{ij} \right)_{k\times n}$, with $A_{ij}\in\mathscr{R}$, and $$\mathrm{P}=\{ \mathtt{X}\in \mathscr{R}^n \,|\, A\mathtt{X}\ge b\}. $$ Suppose that at a particular basic ...
2
votes
1answer
64 views

KKT condition - minimization problem

$y^2-8 \ln(x+4)\rightarrow$ min, such that $-x^2 -y^2+9 \geq 0, y \geq 0$ *I have to find all possible optimal points.* Lagragian function is: $L(x,y,γ_1,γ_2) = y^2 - ...
0
votes
1answer
21 views

Linearizing a constraint for ILP

I have binary variables $x_{ij}$. One of my constraint is $$\sum\limits_{i}\sum\limits_{j} x_{ij}*f_i(\sum\limits_{j}x_{ij})\leq B \ $$ where my $f_i()$ is implemented as a table. Will it be ...