An optimization problem in artificial intelligence asks for the setting of some variables that makes a score as small or as large as possible while respecting stated limits. The score is the objective function, the limits are constraints, and the variables are the choices a system can change, such as the weights of a neural network or the order of stops on a delivery route. Training a model is the best-known case: the loss function scores how badly the model fits the data, and gradient descent searches for weights that lower it.
Key takeaways
- Every optimization problem has three parts: variables to choose, an objective to minimize or maximize, and constraints that rule out some choices.
- In a convex problem, any locally optimal point is also globally optimal. Neural network losses are not convex, so gradient descent gives no such guarantee.
- The learning rate decides whether gradient descent converges, crawls, or diverges. On a simple bowl-shaped function, a step size that is too large makes the error grow.
- Discrete problems, such as choosing which items fit in a limited space, are searched differently from continuous ones, and a fast greedy rule can miss the best answer.
- An optimizer finds the best answer to the objective it was given, which may differ from what the people who wrote the objective wanted.
The three parts of an optimization problem
The standard form used in the textbook Convex Optimization by Stephen Boyd and Lieven Vandenberghe is to minimize an objective over variables subject to constraints. Maximizing is the same task with the sign flipped. In AI work the parts take concrete forms. A spam filter chooses weights, the objective is the average error on labeled messages, and a constraint might cap the number of nonzero weights. A scheduling system chooses start times, the objective is total lateness, and constraints say that one machine cannot run two jobs at once.
Writing the problem down this way separates two questions that are often mixed together. What counts as a good answer is a modeling decision made by people. How to find it is an algorithmic question. The same objective can be attacked with different algorithms, and the same algorithm can be pointed at different objectives.
Gradient descent on a bowl: a worked example
The Stanford CS231n course notes describe gradient descent as repeatedly computing the slope of the loss and stepping the opposite way. A one-variable version shows the mechanics. Take the loss f(x) = (x - 3)^2, whose lowest point is at x = 3, and start at x = 0. The slope is 2(x - 3), so each update is x_new = x - rate * 2(x - 3).
With a learning rate of 0.1, the first four values of x are 0.6, 1.08, 1.464, and 1.771. The gap to 3 shrinks by a factor of 0.8 each step, so progress is steady but slow. With a rate of 1.0, x jumps to 6, then 0, then 6, never settling. With 1.1, the values 6.6, -1.32, 8.184, and -3.221 swing wider each time. The CS231n notes make the same point in words: too small a step is slow, and too large a step overshoots the minimum and can raise the loss. These figures are an illustrative calculation, not a measurement from any real model.
| Learning rate | x after steps one to four (start at 0) | Behavior |
|---|---|---|
| 0.1 | 0.6, 1.08, 1.464, 1.771 | Converges toward 3, slowly |
| 1.0 | 6, 0, 6, 0 | Oscillates, never converges |
| 1.1 | 6.6, -1.32, 8.184, -3.221 | Diverges |
Why convexity matters, and what happens without it
Section 4.2.2 of Boyd and Vandenberghe states that in a convex optimization problem any locally optimal point is also globally optimal. A bowl has one bottom, so a method that keeps going downhill cannot get stuck in a worse valley. The CS231n notes point out that a support vector machine loss is convex, while a neural network loss is non-convex, with bumpy terrain where those guarantees do not carry over.
A small illustrative case shows why this matters. For f(x) = x^4 - 3x^2 + x, plain gradient descent with a rate of 0.01 and 2,000 steps ends near x = -1.30 (f of about -3.51) when started at -2, but near x = 1.13 (f of about -1.07) when started at 2. Both runs stop at a flat point, yet only one reaches the lower of the two valleys. Practical training relies on noisy minibatch gradients and adaptive step sizes such as Adam, introduced by Kingma and Ba in 2014 for stochastic objectives, and works well in practice, but a good result is observed rather than guaranteed.
Discrete choices: when slopes do not exist
Many AI problems have no slope to follow because the variables are yes-or-no or ordered choices. Chapter 4 of Russell and Norvig's Artificial Intelligence: A Modern Approach is titled Search in Complex Environments, and Chapter 6 covers constraint satisfaction problems; both treat problems where choices are discrete. A compact illustration is a packing problem. Three items weigh 6, 5, and 4 units and are worth 13, 10, and 8, and the container holds 9 units.
A greedy rule that picks the highest value per unit of weight takes the first item (about 2.17 per unit), then finds that neither remaining item fits, for a total value of 13. Checking all eight combinations finds that the second and third items together weigh exactly 9 and are worth 18. The greedy rule is fast and sometimes good, and here it is beaten by 5 units of value. Exhaustive checking works for three items but doubles in cost with every item added, which is why larger problems use heuristics, relaxations, or specialized solvers.
Checklist for reading any claim that AI optimizes something
- What exactly is the objective, and who chose it?
- Which constraints were included, and which real-world limits were left out?
- Is the method guaranteed to find the best answer, or only a good one?
- How sensitive is the result to the starting point and the step size?
- Does a better score on the objective mean a better outcome for the people affected?
FAQ
Is training a neural network an optimization problem?
Yes. Training minimizes a loss function over the network's weights, usually with a variant of gradient descent. The separate question of whether the trained model works well on new data is about generalization, which the loss on training data does not settle by itself.
What is the difference between local and global optima?
A local optimum is the best point within a small neighborhood. A global optimum is the best point anywhere that satisfies the constraints. For convex problems the two coincide; for non-convex problems they can differ, as the two-valley example above shows.
Does a bigger learning rate always train faster?
No. On the bowl example, a rate of 1.0 never settles and 1.1 diverges, while 0.1 converges. Real training adds noise and many dimensions, but the same trade-off between speed and stability applies.
Can an optimizer pursue the wrong goal?
It pursues the objective it is given. If the score leaves out something people care about, such as fairness or safety margins, a very good optimizer can achieve a high score and still produce an undesirable result. Checking the objective is as important as checking the algorithm.
Related reading
- How AI approaches the traveling salesman route problem
- Worked examples of formulating a problem for AI
- Traditional AI methods compared with machine learning
- Deep learning applications and advances
More in AI Basics.
Last verified: October 2026
Sources
- Convex Optimization, Boyd S, Vandenberghe L, Cambridge University Press (free PDF on the authors' Stanford page), Sections 4.1 and 4.2.2
- Optimization: Stochastic Gradient Descent, CS231n course notes, Stanford University
- Adam: A Method for Stochastic Optimization, Kingma D, Ba J, ICLR 2015, arXiv:1412.6980
- Artificial Intelligence: A Modern Approach, Russell S, Norvig P, 4th US edition, table of contents on the book's UC Berkeley site