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

1
vote
1answer
546 views

Constrained Optimization - Lagrange Multipliers (Example)

Let $f(x, y, z) = xyz$ $h1(x, y, z) = x + y + z − 4$5 and $h2(x, y, z) = 2x − y$. Goal: Minimize $f(x, y, z)$ subject to $h1(x, y, z) = 0$ and $h2(x, y, z) = 0$. First part: Show that every ...
2
votes
1answer
722 views

Prove every local minimum is a global minimum

Let $Q\in\mathbb{R^{dxd}}$ and $A\in\mathbb{R^{d'xd}}$ be two matrixes and $b\in\mathbb{R^d}$, $c\in\mathbb{R^{d'}}$. Suppose $d'\lt d $. For $x\in\mathbb{R^d}$. Minimize $$f(x)= ...
5
votes
1answer
2k 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 ...
4
votes
0answers
169 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$) ...
2
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 ...
3
votes
1answer
86 views

$P_{1c} = AP$ , $P_{2c} = BP$. How to find $P$? (being that $A$ and $B$ are $3\times 4$ matrices and $P$ is a $4\times 1$ vector)

This problem arose in my stereo vision project. $$ P_{1c} = A*P $$ $$ P_{2c} = B*P $$ where: $P_{1c}$ and $P_{2c}$ are $3\times1$ vectors, $A$ and $B$ are $3 \times 4$ matrices and $P$ is a ...
4
votes
4answers
522 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 ...
2
votes
1answer
115 views

Nonlinear optimization question

For (x,y) in $\mathbb R^2$, consider f(x,y) = $x^2 -2xy + \frac{4}{3}y^2 - 4y$ Find the local minimum of f. Is it a strict local minimum? Compute the $\lim\limits_{|(x,y)|\to \infty}$ f(x,y) to decide ...
1
vote
0answers
59 views

Deconvoluting linear combinations of unknown distributions

Summary I am trying to deconvolute the distribution $T(x)$ of a population's $x$ parameter into sub-distributions ($P(x)$, $Q(x)$, $R(x)$ ...), of which I don't know the form (only that they have ...
1
vote
1answer
65 views

Reformulation of BQP to SDP

I run into the following reading some optimization papars: $$\min_x x^TAx $$ where $x\in\{-1,1\}^n$ and $A\in S_n$, Is equivalent to $$ \min <X,A>$$ s.t $diag(X) = (1,1,...,1)\;\; rank(X) = 1$. ...
1
vote
0answers
18 views

Existence of solutions to a Specific kind of non-linear system of equations with rational variables

Consider a system of the form $c_{11}a_1b_{1} + c_{12}a_2b_{2} + \cdots c_{1n}a_nb_{n} = q_1$ $c_{21}a_1b_{1} + c_{22}a_2b_{2} + \cdots c_{2n}a_nb_{n} = q_2$ $\vdots$ $c_{m1}a_1b_{1} + ...
4
votes
1answer
186 views

Kuhn-Tucker condition is not satisfied

Show that the solution to finding minimum of $f(x)=-x_{1}$ With conditions $-\sin(x_{1})+x_{2} \leq 0$ $x_{1}-x_{2} \leq 0$ is point $(0,0)$, but the Kuhn-Tucker condition is not satisfied in this ...
1
vote
0answers
61 views

why is it important to have $\max_x \min_y f(x,y)=\min_y \max_x f(x,y)$?

I am currently trying to understand the minimax theorem of Von Neumann and the improved versions of this theorem. At any case we have the property $$\max_{x\in X} \min_{y\in Y}f(x,y)=\min_{y\in Y} ...
0
votes
1answer
127 views

Minimization to Maximization doubt in SVM

I came across a lecture on Support Vector Machines and in the lecture they converted a maximization problem into a minimization problem. I am wondering how it was done... $ Max \frac {1}{||x||} $ ...
0
votes
2answers
151 views

Minimize $z=2x_1+3x_2-x_1^2-2x_2^2$ subject to $x_1+3x_2\le 6$, $5x_1+2x_2\le 10$, and $x_1,x_2\ge 0$

How can we minimize $z=2x_1+3x_2-x_1^2-2x_2^2$ subject to $x_1+3x_2\le 6$, $5x_1+2x_2\le 10$, and $x_1,x_2\ge 0$? I need to know the steps to solve or at least the guidelines as I am really new to ...
1
vote
4answers
73 views

A non-linear maximisation

We know that $x+y=3$ where x and y are positive real numbers. How can one find the maximum value of $x^2y$? Is it $4,3\sqrt{2}, 9/4$ or $2$?
1
vote
1answer
228 views

Max function on a closed compact convex set.

Consider a closed convex compact subset $\mathbb{S}$ of $\mathbb{R}^N$ while we denote any of its point by $x=[x_1,x_2,\ldots,x_N]^T$. Define the function \begin{align} f(x)=max(x_1,x_2,\ldots,x_N) ...
0
votes
1answer
173 views

Convex optimization problem to quadratic programming problem

Briefly, have the following problem: \begin{equation} \sum_{i = 0}^n a_i \ (max [ F_i( \bar x ), 0 ] )^2 \rightarrow min, \\\\ s.t.\\\\ A \bar x \leq b \end{equation} where $ F( \bar x ) $ is a ...
1
vote
1answer
94 views

(system of) nonlinear equations and instability

I heard that a system of nonlinear equations is unstable. I am curious of how "instability" is defined, and why do nonlinear equations show instability? Edit: OK, so what about contexts in matrices ...
4
votes
2answers
531 views

Analog of Simplex Method for Quadratic Programming

It happened so I need to work with an algorithm for solving QP problems. The main issue here is that I can't find any references to this algorithms (at least no references in sources in english). ...
2
votes
1answer
70 views

Maximalization of a cubic puzzle

What is the maximal volume of a post package of length $L$, width $W$ and height $H$, subject to the following restrictions: $L+W+H \leq 90 $ $L \leq 60$, $W \leq 60$, $H \leq 60$ Intuitively I ...
2
votes
2answers
82 views

A Quadratic Problem (which looks very simple)

This arises as a part of my work. \begin{align} \min_{x^{H}x=1}~&x^{H}A_1x \\ subject~to~&x^{H}A_2x=0 \end{align} $A_1$ and $A_2$ are $N\times N$ hermitian matrices and $x$ is a unit norm ...
0
votes
1answer
48 views

Concave optimal value?

Let $A \in \mathbb{R}^{n \times m}$ and $B \in \mathbb{R}^{m \times n}$. Consider a compact set $C \subset \mathbb{R}^n$. For all $x \in C$ define $$ f(x) := \min_{y \in \mathbb{R}^m} \{ x^\top A y ...
1
vote
1answer
186 views

Lagrange method - non-linear system of equations

I have to compute optimal parametres of truncated cone so that its Volume is fixed (lets say it is 1) and its surface is minimal using Lagrange method These are equations desribing my object: ...
1
vote
0answers
616 views

Significance of Rank of Jacobian

I have been struggling with this question. What is the significance of finding the rank of a Jacobian matrix of a function? I understand that the Rank of a matrix signifies the number of linearly ...
5
votes
2answers
874 views

Minimizing with Lagrange multipliers and Newton-Raphson

I am writing a program minimizing a real-valued non-linear function of around 90 real variables subject to around 30 non-linear constraints. I found handy explanation in CERN's Data Analysis ...
1
vote
1answer
769 views

A sufficient condition for a unique maximum of the product of two concave functions

Given two concave functions $f(x)$ and $g(x)$, what conditions in terms of these functions can ensure that $h(x)=f(x)g(x)$ have a unique maximizer on an interval $[a,b]$ for $a<b$?
0
votes
1answer
34 views

Second order least squares problem with one parameter

I want to fit a set of measured data $x_i$ and $y_i$ to the expression: $$ \beta^2 + \beta x_i = y_i $$ $\beta$ is my only free parameter. Although this is a really simple expression, the standard ...
2
votes
0answers
296 views

sufficient condition for KKT problems

For the Karush-Kuhn Tucker optimsation problem, Wikipedia notes that: "The necessary conditions are sufficient for optimality if the objective function f and the inequality constraints g_j are ...
0
votes
1answer
63 views

Finding the value which minimises all residuals

I have a series of observations, measurements made at various times $t$. I now need to determine the most likely value of $R$ (distance) using the model below. The guide says I should find the value ...
2
votes
1answer
172 views

Positive values for a set of quadratic forms of Hermitian Matrices. (To find a set of vectors in which a hermitian matrix is positive definite)

Assume all matrices I discuss about are $N \times N$ and the vectors conform with dimensions. Consider the following set of Quadratic inequalities where all the matrices $A_i$ are hermitian. ...
3
votes
1answer
497 views

Lagrangian Multipliers

I have a fundamental question about Lagrange multipliers. Here it is: I have a function to maximize with respect to a parameter say $\theta$, subject to two constraints. Lets assume that the first ...
1
vote
1answer
292 views

Some type of Mixed Integer Nonlinear Programming Problem

This is a minimisation problem, to minimise the integral over possible $0\leq t \leq T$, $T$ is free, $$J = \text{min} \int_0^T (\alpha + \beta_1\cdot v \cdot R_T \cdot q+ \beta_2 \cdot ...
4
votes
1answer
645 views

Nonlinear Optimization/Programming: A good counter text

I am currently taking a nonlinear optimization course and the text is Bertsekas' "Nonlinear Programming 2e". I think the book does a decent job but I am a much more "hands-on" and visual learner so ...
2
votes
1answer
519 views

Nonlinear optimization with rotation matrix constraint

I'm trying to optimize the equation || R - W || = minimum where W is a predetermined 3x3 matrix and R is the 3x3 matrix that I'm trying to optimize, with the ...
1
vote
0answers
76 views

with a set of arbitrary initial values in newton method the system of equations don't have any answer

with a set of arbitrary initial values in newton method the system of equations don't have any answer. Does it mean that this system of equation don't have any answer at all or may be there exists a ...
1
vote
0answers
96 views

minimum of the function over symmetric body

Let $X$ be a normed space. Let $K$ be centrally symmetric convex body with $M$ known vertices and with $Vol(K)=V$. We subdivide body $K$ be $M$ equal pieces, $P_i, i=1, \ldots, M$, such that each ...
2
votes
0answers
254 views

Optimization over function spaces

There are many methods to solve optimization over standard spaces such as real and complex numbers or vector spaces of these. In my case I have a vector space of functions of a real value to find. ...
2
votes
3answers
663 views

how to compute the gradient of a function at an extremal point

I am writing a computer program that searches for the minimum of a multivariate function $f: \mathbb{R}^n \to \mathbb{R}$. This function is in fact the sum of many functions: $$f(x) = \sum_{i=1}^m ...
0
votes
2answers
485 views

Numerical optimization with nonlinear equality constraints

A problem that often comes up is minimizing a function $f(x_1,\ldots,x_n)$ under a constraint $g(x_1\ldots,x_n)=0$. In general this problem is very hard. When $f$ is convex and $g$ is affine, there ...
1
vote
1answer
462 views

Comparison of nonlinear system solvers?

I am dealing with nonlinear systems of equations that I am trying to solve numerically. These sets of equations derive from structural mechanics involving strong nonlinearities, like contact. The size ...
4
votes
0answers
296 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 ...
1
vote
0answers
20 views

Finding an element in a very specific set

I ran into the following problem during some self-motivated studies, and for the last 24 hours I have been unable to solve this problem. The problem arose by itself, meaning it doesn't have a source, ...
4
votes
4answers
733 views

Summary of Optimization Methods.

Context: So in a lot of my self-studies, I come across ways to solve problems that involve optimization of some objective function. (I am coming from signal processing background). Anyway, I seem to ...
0
votes
1answer
669 views

Max function is continuous and concave-convex?

Let $A \subset \mathbb{R}^n$ and $M \subset \mathbb{R}^{n \times m}$ be discrete sets of cardinality $N \geq 1$. Consider the function $f: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}$ ...
2
votes
1answer
691 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 ...
1
vote
1answer
270 views

Maximize function of two variables

Let $f: X \times Y \rightarrow \mathbb{R}$ be a continuous function, where $X \subset \mathbb{R}^n$ and $Y \subset \mathbb{R}^m$ are compact sets. Say under which conditions we have that $$ \max_{x ...
0
votes
0answers
150 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 ...
0
votes
1answer
104 views

Solving an optimization problem involving reciprocals

I am trying to solve the following minimization problem, perhaps by getting it into a LP form: Let $u= [u_1, u_2, ...u_N]^T$ a column vector, and $v=[{1\over u_1}, {1 \over u_2}, ...{1 \over u_N}]^T$ ...
0
votes
2answers
44 views

Solving a grid full of variables from the totals

We've been stumped by a much larger version of this problem, but we have simplified it down to a simple example: ...