Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

2
votes
1answer
151 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. ...
5
votes
2answers
527 views

Are Legendre transforms of non-convex functions useful?

Do Legendre transforms have any applications that do not appeal to convexity? What is the intuitive interpretation of the Legendre transform of a non-convex function?
0
votes
1answer
44 views

Reason for hardness of optimal minimization, and use of iterative optimizers

Suppose a set of $n-1$ are given in 2D space, $x_1, x_2, \dots, x_{n-1}$, and an additional point $x_n$ is to be assigned a 2D coordinate such that the prescribed Euclidean distances $d_1, d_2, \dots, ...
3
votes
1answer
244 views

How to compute the pareto frontier for dimensions higher than 2?

I'm looking for an intuitive way to compute the pareto frontier for dimensions higher than 2, i.e. a generalization of this (very nice) solution: How to compute the Pareto Frontier, intuitively ...
1
vote
1answer
101 views

Different definitions of Positively definite: are they really giving the same result?

My teacher in course Mat-2.3139 here claims that all positive-definite -definitions will result in the same result or I am misunderstanding something. I am clearly misunderstanding something because ...
1
vote
1answer
263 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 ...
3
votes
1answer
491 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 ...
1
vote
0answers
134 views

Upper bound for L1-L2 optimization problem

I am interested in the following convex optimization problem: \begin{align*} \max & ||x||_1 \\ \text{s.t.} & ||x-a||_1 \le K \\ & ||b\circ x||_2 \le 1\\ & x \in R^n \end{align*} where ...
1
vote
2answers
459 views

Bell-shaped polynomial over a limited domain

The function $f(x) = e^{-x^2}$ has a bell-shaped peak at $x=0$ and then approaches an asymptote at $y=0$. I need to achieve a similar result, but with a polynomial function. I can use a series ...
1
vote
1answer
51 views

Why is ROC analysis not used in optimization problems?

In machine learning and applied fields of statistics, receiver operating characterization (ROC) analysis is commonly used to select optimal algorithms/models. However, at a lecture I once attended on ...
3
votes
0answers
225 views

Global optimum of sum of convex functions

Take two real differentiable convex functions, $f_1$ and $f_2$, defined on the unit interval $[0; 1]$. I want to find the global optimum of: $\min_{x \in [0;1]} af_1(x)+bf_2(x)$, for given $a, b \in ...
4
votes
1answer
280 views

principal “pseudo eigenvector” of a real symmetric positive-semidefinite matrix

Let $A$ be a real symmetric positive-semidefinite matrix and suppose that $c>0$ is a sufficiently small number. I wonder if it is possible to solve the non-convex optimization $$\arg\max_u\ ...
0
votes
0answers
131 views

Divide and conquer possible on linear equation systems?

Suppose a 4-connected regular grid $$\mathcal{G}=(\mathcal{E},\mathcal{V}),$$ where $\mathcal{E}$ and $\mathcal{V}$ denote the set of edges and vertices of that grid, respectively. Given this ...
2
votes
2answers
97 views

Is this question erroneous? (Stationary points)

Using the second partial derivative test, I have found (-1,1) to be a saddle point but this option is not available in the MCQ. Have I made a mistake? The person who set the question insists ...
1
vote
1answer
119 views

For integers $a$ and $b \gt 0$, and $n^2$ a sum of two square integers, does this strategy find the largest integer $x | x^2 \lt n^2(a^2 + b^2)$?

Here is some background information on the problem I am trying to solve. I start with the following equation: $n^2(a^2 + b^2) = x^2 + y^2$, where $n, a, b, x, y \in \mathbb Z$, and $a \ge b \gt 0$, ...
3
votes
1answer
458 views

Minimise the entropy of a probability vector using Lagrange multipliers

Problem statement: The entropy of a probability vector $ p = (p_1, ... , p_n)^T $ is defined as $ H(p)= - \sum\limits_{i=1}^{n} p_i \log{p_i} $, subject to $ \sum\limits_{i=1}^{n} p_i = 1 \mbox{ ...
0
votes
1answer
43 views

Unique solution on subspaces whose union is dense implies unique solution globally?

Let $V$ denote the space of all $f : [0,1] \to {\mathbb R}$ such that the second derivative $f''$ is continuous except on a finite set, equipped with the norm $N(f)=|f(0)|+|f’(0)|+||f''||_{\infty}$ ...
0
votes
0answers
18 views

Effective Strategies on optimizing a separable function

The problem statement is $max \sum_i f_i(x)$ $s.t. x\in X$ Is there any effective strategies/frameworks that allows me to optimize a separable function? Like an objective function analogy of ...
1
vote
1answer
831 views

A question about the operation research and simplex method

For the simplex method, we need to add slack variables. My question is how to determine how many slack variables should be considered in the LP problem? I don't quite get why in the cases to find out ...
3
votes
2answers
888 views

Time complexity of quadratic programming

I am using the Matlab built-in quadprog to solve a quadratic program with linear constraints. I vaguely recalled from school that the time complexity of quadratic programming should be $O(n^3)$, and I ...
3
votes
1answer
210 views

Fitting Shape in Circle for Shape Classification

I need to classify arbitrary 2D shapes. The classification should be invariant to at least affine transform. To achieve this invariance, I decided to "normalize" each shape by fitting it to a unit ...
2
votes
1answer
70 views

Root and sign of a complicated bivariate function

Given two natural numbers $p$ and $i$, such that $0 < i \leqslant 2^p$, let $$ \Phi(p,i) := \frac{1}{2^p+1} + \frac{1}{(i+1)^2} - \frac{1}{2^p}\lg\left(\frac{2^p}{i}+1\right), $$ where $\lg x$ is ...
2
votes
1answer
385 views

Developing Constraints for a linear programming based problem

Recently, I thought of developing a mathematical approach to a task I commonly do every week. Simply enough, it's a schedule. That said, I have a few questions regarding the process. I haven't ...
1
vote
0answers
95 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 ...
0
votes
1answer
59 views

$f(x_1,x_2)=x_1x_2$ in $\mathbb R^2_{++}$, positively definite?

The square form is $H:=x^T\nabla^2 f(x) x= 2 a b$ where $x=[a,b]$. Now $f(x_1,x_2)=x_1x_2$ in $\mathbb R^2_{++}$ (problem b). I am perplexed: I think my teacher means that this not ...
2
votes
1answer
57 views

Minimizing the product of some variables with constant summation having an additional condition

What is the minimum of $a_1\times a_2 \times \dots \times a_n$ such that $a_1+a_2+\dots+a_n=S$ and $0 < x \le a_i \le (1+\alpha)\frac{S}{n}$? My conjecture is that we need to set as many ...
2
votes
1answer
239 views

Joint/Simultaneous optimization

$\DeclareMathOperator*{\argmin}{arg\,min}$ Suppose I have to jointly minimize two functions. The solution to the joint minimization does not necessarily minimize each function individually but sort of ...
2
votes
0answers
193 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. ...
3
votes
0answers
154 views

Solving Linear Inequalities for Optimization

I want the max of: $100-(2x_1+3x_2+4x_3+5x_4+6x_5+7x_6)$ I am given 5 inequalities: $x_1+x_4\le6$ $x_2+x_5\le8$ $x_3+x_6\le7$ $x_1+x_2+x_3\le9$ $x_4+x_5+x_6\le11$ and ...
1
vote
0answers
83 views

Alternative strategies for Optimization

I have a function F(x,y) and a constraint G(x,y), I am trying to maximize F but the normal Lagrange Multiplier method can't be solved analytically; it's too complicated, even for mathematica. Are ...
2
votes
2answers
2k views

Minimal distance from origin to quadric surface

How can we find the shortest distance from the origin to the following quadric surface? $$3x^2+y^2-4xz = 4$$ I see lagrangian multipliers being used, partials and such, but have trouble organizing ...
0
votes
1answer
138 views

Parametric Linear Program: Continuous Solution?

Consider the parametric linear problem $$ x^*(\theta) := \min_{Y , \ Z } \left\| Z \right\|_1 $$ $$ \text{sub. to: } \ \theta A + B Y = \theta C Z.$$ where $Y \in \mathbb{R}^{m \times s} $, $Z \in ...
2
votes
3answers
632 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
312 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 ...
8
votes
1answer
243 views

Practical applications of the $L^p$ norm when $p \neq 1,2,\infty$

I'm roughly familiar with the concept of $L^p$ norms -- what they represent and how they are computed -- though I am far from educated in functional analysis in general. For reasons that are more or ...
4
votes
2answers
89 views

Squared linear sum

Is there any effective algorithm for a squared linear sum assignment problem? For squared linear sum assignment problem I mean the following: $$\min\left(\sum_i \sum_j c_{ij}x_{ij}\right)^2$$ with ...
1
vote
1answer
279 views

Maximize distance between points on a line

So lets say I have a certain duration of time starting at time(0) ranging to time(N). I also have a set of points whose values all exist within the range of values of that time frame. I want to pick ...
11
votes
2answers
483 views

2 circles and one ellipse and minimum area problem.

2 circles ($r_1 \neq r_2$) and one ellipse touch each other as shown in Figure-1. What is the minimum area (A) among them ? Please consider $a,b,r_1,r_2$ given values(constants). Let's imagine we ...
1
vote
1answer
126 views

how to obtain Euler equation for smoothing spline minimization problem?

The question might be trivial, but I don't understand why this minimization problem in Sobolev space $$ \min_{g}\int_{0}^{1}\left\{ f(x)-g(x)\right\}^{2} dx+\lambda\int_{0}^{1}\left\{ ...
3
votes
1answer
487 views

Packing cannonballs in a tetrahedron

I have a somewhat interesting problem. Assume one has a tower of cannonballs, or spheres as pictured below As in you have a tower of spheres where the first layer has $1$ cannonball, the next ...
2
votes
0answers
382 views

Quasiconcavity for the sum of specific quasiconcave functions

I want to show that a function $ψ(a_1,a_0)$, which is separable (additively decomposed) in two quasiconcave functions, is also quasiconcave (QC). I know that the sum of QC functions is not generally ...
2
votes
1answer
568 views

Maximum and minimum over a curve given in polar coordinates

Let $\mathcal C$ the curve in the plane given by the polar equation $$ r=1+\cos\vartheta. $$ Find the maximum and the minimum of $f(x,y)=\max\{x,y\}$ on $C$. First question: how can we apply ...
4
votes
0answers
295 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 ...
0
votes
1answer
60 views

How to find optimal border that defines, who is “friend”

I have the data about usage of several services in the population and the data about interactions among users. The idea is to determine, who is user's friend and who has interacted just ...
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, ...
3
votes
1answer
108 views

Fraction of SO(3) within an angle

SO(3) describes a space of rotations. These rotations can be described in axis-angle representation. I would like to know what fraction of SO(3) has an angle less than 30 degrees.
1
vote
2answers
427 views

Maximizing an Expected Value

I have a simple program that helps with purchasing decisions. The problem being solved is how to most profitably select products for a grocery shelf using competing products in different varieties. ...
3
votes
2answers
216 views

Finding the nearest integers to real numbers defined implicitly

I was trying to bound the maximum cost of top-down merge sort: $$ f(0) = f(1) = 0,\quad f(n) = n\lceil{\lg n}\rceil - 2^{\lceil\lg n\rceil} + 1, $$ where $\lg n$ is the binary logarithm of $n$ and ...
1
vote
0answers
117 views

History of calculus-based optimization

I would like to know: - who started with calculus-based optimization problems and when it was, - if there is a book focusing on history of ellipses/ conic sections - if someone ever tried to ...
2
votes
0answers
139 views

What kind of math is required to solve packing problems?

Sometimes while I'm daydreaming I come up with math problems for myself, to solve. I don't know why but they are mostly packing problems. I don't know how to solve them mathematically but I could ...